图结构和查找习题复习(7-8章).ppt

例题1 对于给定的关键序列，若哈希函数无冲突，则称其为完备(perfect)的。设哈希表长度为7，试为{Bret，Jane，Michelle，Heatther}设计一个完备的哈希函数H（提示：考虑每个字串的第3个字符），并写出其C代码。 解： 设计哈希函数H如下： H（key）=key（第3个字母的ASCII码MOD 7），则： H（Bert）=101 MOD 7=3 H（Jane）=110 MOD 7=5 H（Shirley）=105 MOD 7 H（Bryce）=121 MOD 7=2 H（Michelle）=99 MOD 7=1 H（Heather）=97 MOD 7=6 例题2：试述顺序查找法、二分查找法和分块查找法对被查找的表中元素的要求。对长度为n的表来说，3种查找法在查找成功时的平均查找长度各是多少？ 解：3种方法对查找的要求分别如下： 1）顺序查找法：表中元素可以任意次序存入。 2）二分查找法：表中元素必须以关键字的大小递增或递减的次序有序列且顺序表存储。 3）分块查找法：表中元素块内的元素可以任意次序存放，但块与块之间必须以关键字的大小递增（或递减）存放，即前一块内所有元素的关键字都不能大（或小）于后一块内任何元素的关键字。 3种方法平均查找长度分别如下： ⑴顺序查找法：查找成功的平均查找长度为n+1/2。 ⑵二分查找法：查找成功的平均长度为log2（n+1）-1。 ⑶分块查找法：若用顺序查找确定所在的块，平均查找长度为：1/2（n/1+s）+1；若用二分查找确定所在块，平均查找长度为log2（n/s+1）+s/2。其中，s为每块含有的元素的个数。 例题3： 设有一组关键字{19，1，23，14，55，20，84，27，68，11，10，77}采用哈希函数：H（key）=key%13采用开放定址法的二次探测再哈希方法解决冲突，试在0～18的哈希地址空间中对该关键字序列构造哈希表。 【解】 依题意，m=19，二次探测再哈希的下一地址计算公式为： d1=H（key）；d2j=（d1+j*j）%m；d2j+1（d1-j*j）%m；j=1，2，… 其计算函数如下： H（19）=19%13=6 H（1）=1%13=1 H（23）=23%13=10 H（14）=14%13=1（发生冲突） H（14）=（1+1*1）%19=2 H（55）=55%13=3 H（20）=20%13=7 H（84）=84%13=6（发生冲突） H（84）=（6+1*1）%19=7（仍发生冲突） H（84）=（6-1*1）%19=5 H（27）=27%13=1（发生冲突） H（27）=（1+1*1）%19=2（发生冲突） H（27）=（1-1）%19=0 H（68）=68%13=3（发生冲突） H（68）=（3+1*1）%19=4 H（11）=11%13=11 H（10）=10%13=10（发生冲突） H（10）=（10+1*1）%19=11（仍发生冲突） H（10）=（10-1*1）%19=9 H（77）=11%13=12 因此，各关键字的记录对应的地址分配如下： addr（27）=0 addr（1）=1 addr（14）=2 addr（55）=3 addr（68）=4 addr（84）=5 addr（19）=6 addr（20）=7 addr（10）=9 addr（23）=10 addr（11）=11 addr（77）=12 其他地址为空。 例题8 试给出一棵树的关键字序列，使AVL树的4种调整平衡操作（LL，LR，RR，RL）各至少执行一次，并画出其构造过程。 【解】 设关键字的输入序列为：4、5、7、2、1、3、6，则AVL树的构造过程如下图所示。 输入结点 插入后 调整平衡后 4 无需调整 例题9 给定序列{3，5，7，9，11，13，15，17}： ⑴按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成后的二叉排序树，并求在等概率情况下查找成功的平均查找长度。 ⑵按表中元素顺序构造一棵二叉平衡树，并求其在等概率情况下查找成功的平均查找长度，与⑴比较，可得出什么结论？ 【解】 ⑴按输入顺序进行插入后的二充满排序树