数据结构第七章参考答案.pdfVIP

丹青不知老将至，贫贱于我如浮云。——杜甫

习题7

1.填空题

（1）由10000个结点构成的二叉排序树，在等概率查找的条件下，查找成功时的平均查找

长度的最大值可能达到（___________）。

答案：5000.5

（2）长度为11的有序序列：1，12，13，24，35，36，47，58，59，69，71进行等概率查

找，如果采用顺序查找，则平均查找长度为（___________），如果采用二分查找，则平均查

找长度为（___________），如果采用哈希查找，哈希表长为15，哈希函数为H（key）＝key%13，

采用线性探测解决地址冲突，即d=(H(key)+i)%15，则平均查找长度为（保留1位小数）

i

（___________）。

答案：6，3，1.6

（3）在折半查找中，查找终止的条件为（___________）。

答案：找到匹配元素或者lowhigh?

（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的关系是（___________）。

答案：(1)(2s-1)b=2s([log(2s-1)]+1)-2[log2(2s-1)]+1+1

2

(2)分两种情况考虑，见解答。

解：(1)设所有元素的个数为n，显然有s=n*(n+1)/(2n),则

n=2s-1

设折半查找树高度为k，则前k-1层是满二叉树，最后一层的节点数为

n-(2k-1-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