第九章 查找

第九章 查找 习题及答案

一、基础知识题

1.对含有n个互不相同元素的集合，同时找最大元和最小元至少需进行多少次比较?

2.若对具有n个元素的有序的顺序表和无序的顺序表分别进行顺序查找，试在下述两种情况下分别讨论两者在等概率时的平均查找长度：(1)查找不成功，即表中无关键字等于给定值K的记录；(2)查找成功，即表中有关键字等于给定值K的记录。

3.画出对长度为18的有序的顺序表进行二分查找的判定树，并指出在等概率时查找成功的平均查找长度，以及查找失败时所需的最多的关键字比较次数。 答：如图：

4.为什么有序的单链表不能进行折半查找?

5.设有序表为(a,b,c,e,f,g,i,j,k,p,q),请分别画出对给定值b,g和n进行折半查找的过程。

6.将(for, case, while, class, protected, virtual,

public, private, do, template, const ,if,

int)中的关键字依次插入初态为空的二叉排序树中，请画出所得到的树T。然后画出删去for之后的二叉排序树T',若再将for

插入T'中得到的二叉排序树T''是否与T相同?最后给出T\的先序、中序和后序序列。

答：二叉排序树T如下图：

删去for后的二叉排序树如下图：圈内的for表示再插入后的结点：

7.对给定的关键字集合，以不同的次序插入初始为空的树中，是否有可能得到同一棵二叉排序树?

8.将二叉排序树T的先序序列中的关键字依次插入一空树中，所得和二叉排序树T'与T\是否相同?为什么?

9.设二叉排序树中关键字由1至1000的整数构成，现要查找关键字为363的结点，下述关键字序列哪一个不可能是在二叉排序树上查找到的序列?

(a) 2，252，401，398，330, 344，397，363； (b) 924, 220, 911, 244, 898, 258, 362, 363; (c) 925, 202, 911, 240, 912, 245, 363;

(d) 2, 399, 387, 219, 266, 382, 381, 278, 363.

10.设二叉排序树中关键字互不相同，则其中最小元必无左孩子，最大元必无右孩子。此命题是否正确?最小元和最大元一定是叶子吗?一个新结点总是插在二叉排序树的某叶子上吗?

11.在一棵m阶的B-树中，当将一关键字插入某结点而引起该结点的分裂时，此结点原有多少个关键字?若删去某结点中的一个关键字，而导致结点合并时，该结点中原有几个关键字?

12.在一棵B-树中，空指针数总是比关键字数多一个，此说法是否正确?请问包含8个关键字的3阶B-树(即2-3树)最多有几个结点?最少有几个结点?画出这两种情况的B-树。 答:图如下：

13.从空树开始，依次输入20，30，50，52，60，68，70，画出建立2-3树的过程。并画出删除50和68后的B-树状态。

答：过程如下：

(1) 插入20，30： (2) 插入50：

(3) 插入52： (4) 插入60：

(5) 插入68： (6) 插入70：

(7)删去50： (8) 删去68

(答案及点评) 14。画出依次插入z,v,o,p,w,y到图9.12(h)所示的5阶B-树

的过程。

答：如图：第一步，插入z:

第二、三步,插入v,o：

第四五六步，插入p,w,y:

15. 在含有n个关键字的m阶B-树中进行查找，至多读盘多少次?完全平衡的二叉排序树的读盘次数大约比它大多少倍?

16.为什么在内存中使用的B-树通常是3阶的，而不使用更高阶的B-树? 17.为什么二叉排序树长高时，新结点总是一个叶子，而B-树长高时，新结点总是根?哪一种长高能保证树平衡?

18.已知关键字序列为(PAL,LAP,PAM,MAP,PAT,PET,SET,SAT,TAT,BAT)试为它们设计一个散列函数，将其映射到区间[0..n-1]上，要求碰撞尽可能的少。这里n=11,13,17,19.

19.对于一组给定的、固定不变的关键字序列，有可能设计出无冲突的散列函数H，此时称H为完备的散列函数(perfect hashing function)，若H能无冲突地将关键字完全填满散列表，则称H是最小完备(minimal perfect)的散列函数。通常找完备的散列函数非常困难，找最小完备的散列函数就更困难。请问：

(1)若h是已知关键字集合K的完备的散列函数，若要增加一个新的关键字到集合K，一般情况下H还是完备的吗?

(2)已知关键字集合为(81，129，301，38，434，216，412，487，234)，散列函数为H(x)=(x+18)/63,请问H是完备的吗?它是最小完备的吗?

(3)考虑由字符串构成的关键字集合

(Bret,Jane,Shirley,Bryce,Michelle,Heather)，试为散列表[0..6]设计一个完备的散列函数。(提示：考虑每个字符串的第3个字符，即s[2])

20.设散列函数为h(key)=key1,解决冲突的方法为线性探查，表中用\表示空单元。若删去散列表HT中的304(即令HT[1]=-1)之后，在表HT中查找707

本文来源：https://www.bwwdw.com/article/ed2f.html