发布时间 : 星期六 文章数据结构第七章参考答案更新完毕开始阅读7a9cad2d4b73f242336c5fe3
习题7
1. 填空题
（1）由10000个结点构成的二叉排序树，在等概率查找的条件下，查找成功时的平均查找长度的最大值可能达到（___________）。 答案：5000.5
（2）长度为11的有序序列：1，12，13，24，35，36，47，58，59，69，71进行等概率查找，如果采用顺序查找，则平均查找长度为（___________），如果采用二分查找，则平均查找长度为（___________），如果采用哈希查找，哈希表长为15，哈希函数为H（key）＝key，采用线性探测解决地址冲突，即di=(H(key)+i)，则平均查找长度为（保留1位小数）（___________）。 答案：6，3，1.6
（3）在折半查找中，查找终止的条件为（___________）。 答案：找到匹配元素或者low>high?
（4）某索引顺序表共有元素275个，平均分成5块。若先对索引表采用顺序查找，再对块元素进行顺序查找，则等概率情况下，分块查找成功的平均查找长度是（___________）。 答案：31
（5）高度为8的平衡二叉树的结点数至少是（___________）。 答案： 54 计算公式：F(n)=F(n-1)+F(n-2)+1
（6）对于这个序列{25，43，62，31，48，56}，采用的散列函数为H(k)=k%7，则元素48的同义词是（___________）。 答案：62
（7）在各种查找方法中，平均查找长度与结点个数无关的查找方法是（___________）。 答案：散列查找
（8）一个按元素值排好的顺序表（长度大于2），分别用顺序查找和折半查找与给定值相等的元素，平均比较次数分别是s和b，在查找成功的情况下，s和b的关系是（___________）；在查找不成功的情况下，s和b的关系是（___________）。
[log(2s-1)]+1
答案：(1)(2s-1)b=2s([log2(2s-1)]+1)-2+1
(2)分两种情况考虑，见解答。
解： (1)设所有元素的个数为n，显然有s=n*(n+1)/(2n),则
n=2s-1
设折半查找树高度为k，则前k-1层是满二叉树，最后一层的节点数为
k-1
n-(2 -1）
因此，总比较次数
012k-2k-1
nb=2*1+2*2+2*3+…+2*(k-1)+(n-(2 -1))*k,
而
012k-2k-1k
2*1+2*2+2*3+…+2*(k-1)=2*k-2+1
因此
k-1kk-1k
nb=2*k-2+1+(n-(2-1))*k=(n+1)k-2+1
又k=[log2n]+1,n=2s-1,所以有
[log(2s-1)]+1
(2s-1)b=2s([log2(2s-1)]+1)-2+1
(2)查找不成功，对于顺序查找有：s=n。对于折半查找，找不到的情况有n+1种,查找
2
2
到每个叶子节点或度为1的节点后就不再查找，设折半查找树高度为k，则第k-1层的节点
k-2k-1
数x=2，第k层的节点数y=n-(2 -1）
（a）当第k层的节点数y小于等于第k-1层的节点数x时， 则第k-1层有y结点度为1，其余x-y个结点度为0。 则查找次数为：(n+1)b=2yk+2(x-y)(k-1)+y(k-1)=2x(k-1)+yk
k-1k-1
(n+1)b=2 *(k-1)+(n-(2 -1))*k
（b）当第k层的节点数y大于第k-1层的节点数x时，
则第k-1层不存在度为0的结点，有2x-y个结点度为1，其余y-x个结点度为2
则查找次数为：(n+1)b=2yk+(2x-y)(k-1)=2x(k-1)+y(k+1)
k-1k-1
(n+1)b=2 *(k-1)+(n-(2 -1))*(k+1)
将k=[log2n]+1，n=s分别代入（a）（b）两个等式即得。
2. 选择题
（1）从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较（ ）个结点。 A. n B. n/2 C. (n-1)/2 D. (n+1)/2
（2）对一个长度为50的有序表进行折半查找，最多比较（ ）次就能查找出结果。 A. 6 B. 7 C. 8 D. 9
（3）对有18个元素的有序表做折半查找，则查找A[3]（下标从1开始）的比较序列的下标依次为（ ）。 A. 1-2-3 B. 9-5-2-3 C. 9-5-3 D. 9-4-2-3
（4）在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡点为A，并已知A的左孩子的平衡因子为－1，右孩子的平衡因子为0，则做（ ）型调整以使其平衡。 A. LL B. LR C. RL D. RR （5）理论上，散列表的平均比较次数为（ ）次。 A. 1 B. 2 C. 4 D. n （6）二叉排序树中，最小值结点的（ ）。 A. 左指针一定为空 B. 右指针一定为空 C. 左、右指针均为空 D. 左、右指针均不为空 （7）散列技术中的冲突指的是（ ）。
A.两个元素具有相同的序号 B. 两个元素的键值不同，而其他属性相同 C. 数据元素过多 D. 不同键值的元素对应于相同的存储地址
（8）散列表表长m=14，散列函数H(k)=k。表中已有15，38，61，84四个元素，如果用线性探测法处理冲突，则元素49的存储地址是（ ）。 A. 8 B. 3 C. 5 D. 9
（9）采用线性探测法处理冲突所构成的闭散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置的键值（ ）。 A. 一定都是同词义词 B. 一定都不是同义词 C. 不一定都是同义词 D. 都相同
（10）静态查找与动态查找的根本区别在于（ ）。 A. 它们的逻辑结构不一样 B. 施加在其上的操作不同
C. 所包含的数据元素的类型不一样
D. 存储实现不一样
3．设一个散列表包含hashSize=13个表项，其下标从0到12，采用线性探查法解决冲突，请按以下要求，将关键码{10，100，32，45，58，126，3，29，200，400，0}散列到表中。 （1）散列函数采用除留余数法，用%hashSize(取余运算)将各关键码映像到表中，请指出每一个产生冲突的关键码可能产生多少次冲突。 答案：如下表， H(key) 0 key 0 1 2 3 3 4 29 5 200 6 32 7 45 8 58 9 100 10 10 11 126 12 400 产生冲突的关键码有：29－1次，45－1次，58－2次，126－2次，400－2次
（2）散列函数采用先将关键码各位数字折叠相加，再用%hashSize将相加的结果映像到表中的办法，请指出每一个产生冲突的关键码可能产生多少次冲突。 答案：如下表， H(key) 0 key 58 1 10 2 100 3 3 4 200 5 32 6 400 7 0 8 9 45 10 126 11 29 12 产生冲突的关键码有：100－1次，200－2次，400－2次，0－7次，126－1次
4．试编写一个函数，完成拉链法解决冲突的散列表上删除一个指定结点的算法。
5．设散列表的长度为13，散列函数为H(k)=k，给定的关键字序列为：19，14，23，01，68，20，84，27，55，11，10，79。试画出分别用拉链法和线性探测查找解决冲突时所构造的散列表，并求出在等概率情况下，这两种方法的查找成功和查找不成功的平均查找长度。 答案：拉链法：
1141277936855671920841011231110 平均查找次数：成功时是21/12=1.75次，不成功时是(4+2+2+2+1+2+1)/13=12/13=0.92次（在这里查找比较是指元素值的比较。如果指针为空，则不进行查找比较，此时不算查找）。
线性探测法： H(key) 0 key 冲突次数 成功时的比较1 14 0 1 2 01 1 2 3 68 0 1 4 27 3 4 5 55 2 3 6 19 0 1 7 20 0 1 8 84 2 3 9 79 8 9 10 23 0 1 11 11 0 1 12 10 2 3 次数 不成功时的比较次数 0 12 11 10 9 8 7 6 5 4 3 2 1 平均查找次数：成功时是2.5次，不成功时ASL=（0+12+11+10+9+8+7+6+5+4+3+2+1）/13 = 6次。