.

第9章查找

一、 选择题

1. 顺序查找一个共有n个元素的线性表，其时间复杂度为（），折半查找一个具有n个元素的有序表，其时间复

杂度为（）。【＊，★】

A. O(n) B. O(log2n) C. O(n2) D. O(nlog2n)

2. 在对长度为n的顺序存储的有序表进行折半查找，对应的折半查找判定树的高度为（）。【＊，★】

A. n B. C. D.

3. 采用顺序查找方式查找长度为n的线性表时，平均查找长度为（）。【＊】

A. n B. n/2 C. (n+1)/2 D. (n-1)/2

4. 采用折半查找方法检索长度为n的有序表，检索每个元素的平均比较次数（）对应判定树的高度（设高度大于

等于2）。【＊＊】

A. 小于 B. 大于 C. 等于 D. 大于等于

5. 已知有序表（13，18，24，35，47，50，62，83，90，115，134），当折半查找值为90的元素时，查找成功

的比较次数为（）。【＊】

A. 1 B. 2 C. 3 D. 4

6. 对线性表进行折半查找时，要求线性表必须（）。【＊】

A. 以顺序方式存储 B. 以链接方式存储

C. 以顺序方式存储，且结点按关键字有序排序 D. 以链接方式存储，且结点按关键字有序排序 7. 顺序查找法适合于存储结构为（）的查找表。【＊】

A. 散列存储 B. 顺序或链接存储 C. 压缩存储 D. 索引存储

8. 采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在

的块时，每块应分（）个结点最佳。【＊＊】

A. 10 B. 25 C. 6 D. 625

9. 从键盘依次输入关键字的值：t、u、r、b、o、p、a、s、c、l，建立二叉排序树，则其先序遍历序列为（），

中序遍历序列为（）。【＊＊，★】

A. abcloprstu B. alcpobsrut C. trbaoclpsu D. trubsaocpl 10. 折半查找和二叉排序树的时间性能（）。【＊】

A. 相同 B. 不相同

11. 一棵深度为k的平衡二叉树，其每个非终端结点的平衡因子均为0，则该树共有（）个结点。

A. 2k-1-1 B. 2k-1 C. 2k-1+1 D. 2k-1

12. 利用逐点插入法建立序列{50，72，43，85，75，20，35，45，65，30}对应的二叉排序树以后，查找元素35要

1页

.

进行（）元素间的比较。

A. 4次 B. 5次 C. 7次 D. 10次

13. 设Hash地址空间为0到m-1，哈希函数为h(k)=k%p，为了减少发生冲突的可能性，一般取p为（）。

A. 小于m的最大奇数 B. 小于m的最大素数 C. 小于m的最大偶数 D. 小于m的最大合数

14. 长度为10的按关键字有序的查找表采用顺序组织方式。若采用折半查找方法，则在等概率情况下，查找失败

时的ASL值是（）。

A. 24/10 B. 24/11 C. 39/10 D. 39/11

15. 在表长为n的顺序表中，实施顺序查找，在查找不成功时，与关键字比较的次数为（）

A. n+1 B. 1 C. n D. n-1 16. 设哈希函数为H(key)=key%7，一组关键字为（37，21，9，20，30，19，46），哈希表T的地址空间为0…6，

用线性探测法解决冲突，依次将这组关键字插入T中，得到的哈希表为（）。【＊，★】

17. 设有一个用线性探测法解决冲突得到的哈希表：

哈希函数为H(key)=key，若要查找元素14，探测的次数是（） A. 3 B. 6 C. 7 D. 9

18. 在哈希函数H(key)=key%m中，一般来讲，m应取（）。

A. 奇数 B. 偶数 C. 素数 D. 充分大的数 19. 分块查找的时间性能（）。

A. 低于二分查找 B. 高于顺序查找而低于二分查找 C. 高于顺序查找 D. 低于顺序查找高于二分查找 20. 以下说法错误的是（）。

A. 哈希法存储的基本思想是由关键字的值决定数据的存储地址 B. 哈希表的结点中只包含数据元素自身的信息，不包含任何指针 C. 装填因子是哈希法的一个重要参数，它反映哈希表的装填程度

D. 哈希表的查找效率主要取决于哈希表造表时选取的散列函数和处理冲突的方法 21. 以下说法正确的是（）。

A. 前序遍历二叉排序树的结点就可以得到排好序的结点序列

B. 任一二叉排序树的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间 C. 对具有相同关键字集合的任一插入序列，得到的二叉排序树的形态都是相同的

D. 采用分块查找方法，既能实现线性表所希望的较快的查找速度，又能适应动态变化的需要 22. 已知采用开放地址法解决哈希表冲突，要从此哈希表中删除一个记录，正确的做法是（）。【＊，★】

A. 将该元素所在的存储单元清空

2页

.

B. 将该元素用一个特殊的符号代替

C. 将与该元素有相同Hash地址的后继元素顺次前移一个位置 D. 用与该元素有相同Hash地址的最后插入表中的元素替代

23. 设哈希表长为M=14，哈希函数H(key)=key，表中已有4个结点：ADDR(15)=4、ADDR(38)=5、ADDR(61)=6、

ADDR(84)=7，其余地址为空，如用二次探测再散列处理冲突，现插入关键字为50的结点的地址应是（）。

【＊，★】

A. 3 B. 8 C. 9 D. 10

24. 有一个长度为12的有序表，按折半查找法对该表进行查找，在表内各元素查找概率相同的情况下，查找成功

所需的平均比较次数为（）。【＊＊，★】 A. 32/12 B. 35/12

C. 37/12

D. 39/12

25. 如果要求一个线性表既能较快的查找，又能适应动太变化的要求，可以采用（）查找方法。【＊】

A. 分块

B. 顺序

C. 折半 D. 散列

26. 深度为6的AVL树至少有（）个结点。【＊＊】

A. 10 B. 12 C. 20 D. 21 27. 哈希表的平均查找长度（ ）。

A. 与处理冲突的方法有关而与表的长度无关 B. 与处理冲突的方法无关而与表的长度有关 C. 与处理冲突的方法有关且与表的长度有关 D. 与处理冲突的方法无关且与表的长度无关

28. 若为查找表长度为m的闭散列表采用二次探测再散列处理冲突，对一个元素第1次计算的哈希地址为d，则第3

次计算的哈希地址为（ ）。【＊＊】

A. (d+1)%m B. (d-1)%m C. (d+4)%m D. (d-4)%m

29. 有数据（49，32，40，6，45，12，56），从空二叉树开始依次插入数据形成二叉排序树，若希望高度最小，

则应选择下列哪个输入序列（）。【＊，★】

A. 45，12，49，6，40，56，32 B. 40，12，6，32，49，45，56 C. 6，12，32，40，45，49，56 D. 32，12，6，40，45，56，49

30. 在一棵深度为h的具有n个元素的二叉排序树中，查找所有元素的最长查找长度为（）。【＊】

A. n B. log2n

C. (h+1)/2

D. h

二、 判断题

1. 分块查找方法的平均查找长度低于顺序查找，高于折半查找。（）【＊＊】

2. 采用线性探测再散列法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置为空，

因为这会影响以后的查找。（）【＊】

3. 前序遍历二叉排序树的结点就可以得到排好序的结点序列。（）【＊】

3页

.

4. 在任一二叉排序树上查找某个结点都小于用顺序查找法查找同样结点的线性表的查找时间。（ ）【＊】 5. 虽然关键字的序列的顺序不一样，但依次生成的二叉排序树却是一样的。（ ）【＊】

6. 对二棵具有相同关键字集合的形状不同的二叉排序树，按中序遍历它们得到的序列的顺序是一样的。（ ）

【＊】

7. 在二叉排序树上插入新的结点时，不必移动其他结点，仅需要改动某个结点的指针，由空变为非空即可。

（ ）【＊】

8. 在二叉排序树上删除一个结点时，不必移动其他结点，只要将该结点的父结点的相应指针域置空即可。

（ ）【＊】

三、 填空题

1. 折半查找效率较高，但要求结点（）并且要求线性表（）；而对于顺序查找，则线性表的存储方式（）。

【＊，★】

2. 假设在有序线性表A[0]—A[9]上进行折半查找，则比较一次查找成功的结点数为（ ），比较二次查找成

功的结点数为（ ），比较三次查找成功的结点数为（ ），比较四次查找成功的结点数为（ ），

平均查找长度为（ ）。【＊】

3. 在n个记录的有序顺序表中进行折半查找，最大的比较次数是（ ）。【＊】 4. 折半查找判定树既是一种（ ），也是一种（ ）。【＊，？】

5. 顺序查找法的平均查找长度为（）；折半查找法的平均查找长度为（）；分块查找法（以顺序查找确定块）

的平均查找长度为（）；分块查找法（以折半查找确定块）的平均查找长度为（）；哈希表查找法采用链接

法处理冲突时的平均查找长度为（）。【＊＊，★】

6. 对于长度为n的线性表，若进行顺序查找，则时间复杂度为（ ）；若进行折半查找，则复杂度为

（ ）；若采用分块查找（假定总块数和每块长度均接近n的平方），则时间复杂度为（ ）。【＊＊，★】

7. 用二分法查找一个线性表时，该线性表必须具有的特点是（ ），而分块查找法要求将待查找的表均匀地

分成若干块且块中诸记录的顺序可以是任意的，但块与块之间（ ）。【＊】 8. 采用散列技术来实现查找，需要解决的问题有：（ ）和（ ）。【＊】 9. 在散列存储中，处理冲突有（ ）和（ ）两类方法。【＊】 10. （）法构造的哈希函数肯定不会发生冲突。【＊，？】

4页

.

11. 在各种查找方法中，平均查找长度与结点个数无关的查找方法为（ ）。【＊，？】

12. 在开散列表上查找健值等于K的结点，首先必须计算该健值的（ ），然后再通过指针查找该结点。

13. 在索引顺序表上，对于顺序表中的每一块，索引表中有相应的一个“索引项”。每个索引项有两个域：块内

最大（ ）值和块（ ）位置。【＊】

14. 索引顺序表上的查找分两个阶段：一.（）；二.（）。该查找方法称为（）查找。【＊】

15. 二叉排序树是一种特殊的、增加了限制条件的二叉树，其限制条件是任一结点的键值（ ）于其左孩子

（及其子孙）的键值且（ ）于其右孩子（及其子孙）的键值。【＊】

16. 在表示一棵二叉排序树的二叉链表上，要找键值比某结点X的键值（ ）的结点，只需通过结点X的右指

针到它的右子树中去找。【＊】

17. 中序遍历一棵二叉排序树所得的结点访问序列是键值的（ ）序列。【＊】

18. 二叉排序树上的查找长度不仅与（ ）有关，也与二叉排序树的（ ）有关。【＊】

19. 二叉排序树的查找效率与树的形态有关，当二叉排序树退化为一条单支树时，查找算法退化为（ ）查找，

平均查找长度上升为（ ）。【＊，★】

20. 有n个结点的AVL树的深度与（ ）是同数量级的，因而在它上面进行查找的平均查找长度也与（ ）

同数量级。【＊，？】

21. （ ）查找法的平均查找长度与元素个数n个数无关。【＊】

22. 在具有20个元素的有序表上进行折半查找，则比较一次查找成功的结点数为（ ），比较二查找成功的

结点数为（ ），比较五次查找成功的结点数为（ ）。总平均查找长度为（ ）。【＊＊】 23. 折半查找方法仅适用于这样的表：表中的记录必须（ ），其存储结构必须是（ ）。【＊】 24. 考虑具有如下性质的二叉树：除叶子结点外，每个结点的值都大于其左子树上的一切结点的值，并小于或等

于其右子树上的一切结点的值。现把9个数1，2，3，4，5，6，7，8，9填入如图9.1所示的二叉树中，并使之满足上述性质。（圆圈旁边的数字表示插入结点的序号）【＊，★】

25. 设线性表L=（a1，a2，…，an）（n>2），表中元素按值的递增顺序排列。对一个给定的值k，分别用顺序查

找和折半查找与k相等的元素，比较次数为s和b，若检索不成功，则s和b的数据关系是（）。（注：大于、小于或等于）【＊】

26. 某顺序存储的表，其中有10000个元素，已按关键字的值升序排列。现假定对各个元素进行查找的概率是相

同的，并且各个元素的关键字都不相同。用顺序查找法查找时，查找成功时的平均比较次数为（ ），最

5页