习　题　8

一、填空题

1.顺序查找法等概率下查找成功时的平均查找长度为＿＿＿＿,查找不成功时的比较次数为＿＿＿＿。

2.对线性表进行折半查找时,要求线性表必须＿＿＿＿。

3.采用分块查找法（块长为s,以顺序查找确定块）查找长度为n的线性表时的平均查找长度为＿＿＿＿。

4.已知一个有序表为（12,18,20,25,29,32,40,62,83,90,95,98）,当二分查找值为29和90的元素时,分别需要＿＿＿＿次和＿＿＿＿次比较才能查找成功；若采用顺序查找时,分别需要＿＿＿＿次和＿＿＿＿次比较才能查找成功。

5.从一棵二叉排序树中查找一个元素时,若元素的值等于根结点的值,则表明＿＿＿＿,若元素的值小于根结点的值,则继续向＿＿＿＿查找,若元素的值大于根结点的值,则继续向＿＿＿＿查找。

6.设散列表L长m＝14,散列函数h（k）＝k%11。表中已有4个结点:L[4]＝15,L[5]＝38,L[6]＝61,L[7]＝84,其余地址为空。若先用二次探测再散列法处理冲突,关键字值为49的结点在L中的下标为＿＿＿＿。

7.散列表查找法中仍需进行关键字间比较的原因是＿＿＿＿的存在。

8.在各种查找方法中,平均查找长度与结点个数无关的查找方法是＿＿＿＿。

二、分析题

1.若对具有n个元素的有序的顺序表和无序的顺序表分别进行顺序查找,试在下述两种情况下分别讨论两者在等概率时的平均查找长度:

（1）查找不成功,即表中无关键字等于给定值k的记录；

（2）查找成功,即表中有关键字等于给定值k的记录。

2.画出对长度为17的有序表进行折半查找的判定树,并求等概率下查找成功时的平均查找长度。

3.按给定关键字序列（33、62、76、45、52、58）构造二叉排序树,并求等概率下查找成功时的平均查找长度。

4.按给定关键字序列（33、62、76、45、52、58）构造平衡的二叉排序树,并求等概率下查找成功时的平均查找长度。

5.设有3阶B－树如下,画出删除关键字值17的过程。

6.已知散列表的地址区间为0～11,散列函数为h（k）＝k%11,采用线性探测法处理冲突。将关键字序列20,30,70,15,8,12,18,63,19依次存储到散列表中,试构造出该散列表,并求出在等概率情况下的平均查找长度。

7.设散列函数为h（k）＝k%11,采用拉链法处理冲突,将上例中关键字序列依次存储到散列表中,并求出在等概率情况下的平均查找长度。

8.设散列函数h（k）＝k%13,用公共溢出区法处理冲突。试在0～19的散列地址空间中对关键字序列（19,01,23,14,55,20,84,27,68,11,10,77）构造哈希表,并求等概率下查找成功时的平均查找长度。

9.设散列表为ht[13],散列函数为h（k）＝k%13。用散列法解决冲突,对下列关键码序列12,23,45,57,20,03,78,31,15,36构造表。

（1）采用线性探查法寻找下一个空位,画出相应的散列表,并计算等概率下搜索成功的平均搜索长度和搜索不成功的平均搜索长度。

（2）采用双散列法寻找下一个空位,再散列函数为rh（k）＝（7＊k）%10＋1,寻找下一个空位的公式为h_i＝（h_i－1＋rh（k））%13,h₁＝h（k）。画出相应的散列表,并计算等概率下搜索成功的平均搜索长度。

10.设有150个记录要存储到散列表中,要求利用线性探查法解决冲突,同时要求找到所需记录的平均比较次数不超过2次。试问散列表需要设计多大？（设α是散列表的装载因子）