.

;. 《查找》练习题

一、单项选择题

1.若查找每个元素的概率相等，则在长度为n的顺序表上查找任一元素的平均查找长度为( )。

A. n

B. n+1

C. (n-1)/2

D. (n+1)/2

2.对于长度为9的顺序存储的有序表，若采用折半查找，在等概率情况下的平均查找长度为( )。

A. 20/9

B. 18/9

C. 25/9

D. 22/9

3.对于长度为18的顺序存储的有序表，若采用折半查找，则查找第15个元素(从1开始数)的比较次数为( )。

A. 3

B. 4

C. 5

D. 6

4.对于顺序存储的有序表(5,12,20,26,37,42,46,50,64)，若采用折半查找，则查找元素26的比较次数为( )。

A. 2

B. 3

C. 4

D. 5

5.对具有n个元素的有序表采用折半查找，则算法的时间复杂度为( )。

A. O(n)

B. O(n2)

C. O(1)

D. O(log2n)

6.在索引查找中，若用于保存数据元素的主表的长度为144，它被均分为12子表，每个子表的长度均为12，则索引查找的平均查找长度为( )。

A. 13

B. 24

C. 12

D. 79

7.从具有n个结点的二叉排序树中查找一个元素时，在平均情况下的时间复杂度大致为( )。

A. O(n)

B. O(1)

C. O(log2n)

D. O(n2)

8.从具有n个结点的二叉排序树中查找一个元素时，在最坏情况下的时间复杂度为( )。

A. O(n)

B. O(1)

C. O(log2n)

D. O(n2)

9.若根据查找表(23,44,36,48,52,73,64,58)建立哈希表，采用h(K)=K%13计算哈希地址，则元素64的哈希地址为( )。

A. 4

B. 8

C. 12

D. 13

10.若根据查找表建立长度为m的哈希表，采用线性探测法处理冲突，假定对一个元素第一次计算的哈希地址为d，则下一次的哈希地址为( )。

A. d

B. d+1

C. (d+1)/m

D. (d+1)%m

二、填空题

1.以顺序查找方法从长度为n的顺序表或单链表中查找一个元素时，平均查找长度为____

（n+1）/2____。

2.以折半查找方法从长度为n的有序表中查找一个元素时，平均查找长度约等于

__log2n______的向上取整减1，时间复杂度为___O(log2n) _____。

3.以折半查找方法在一个查找表上进行查找时，该查找表必须组织成__顺序______存储的