第九章

查找

一、

选择题

1.

若查找每个记录的概率均等，

则在具有

n

个记录的连续顺序文件中采用顺序查找法查找一

个记录，其平均查找长度

ASL

为

(    )

。

A

．

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

2.

下面关于二分查找的叙述正确的是

(    )

A.

表必须有序，

表可以顺序方式存储，

也可以链表方式存储

C.

表必须有序，

而且只

能从小到大排列

B.

表必须有序且表中数据必须是整型，

实型或字符型

D.

表必须有序，

且表只

能以顺序方式存储

3.

用二分(对半)查找表的元素的速度比用顺序法

(    )

A

．必然快

B.

必然慢

C.

相等

D.

不能确定

4.

具有

12

个关键字的有序表，折半查找的平均查找长度(

)

A. 3.1            B. 4            C. 2.5            D. 5

5

．当采用分块查找时，数据的组织方式为

(    )

A

．数据分成若干块，每块内数据有序

B

．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大(或最小)

的数据组成索引块

C.

数据分成若干块，每块内数据有序，每块内最大(或最小)的数据组成索引块

D.

数据分成若干块，每块(除最后一块外)中数据个数需相同

6.

二叉查找树的查找效率与二叉树的

(

(

1

)

)

有关

,

在

(

(

2

)

)

时其查找效率最低

(1):  A.

高度

B.

结点的多少

C.

树型

D.

结点的位置

(2):  A.

结点太多

B.

完全二叉树

C.

呈单枝树

D.

结点太复杂。

7.

对大小均为

n

的有序表和无序表分别进行顺序查找

,

在等概率查找的情况下

,

对于查找失

败

,

它们的平均查找长度是

((1)) ,

对于查找成功

,

他们的平均查找长度是

((2))

供选择

的答案

:

A.

相同的

B.

不同的

9

．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是

(    )

A

．

(

100

，

80

，

90

，

60

，

120

，

110

，

130

)

B.

(

100

，

120

，

110

，

130

，

80

，

60

，

90

)

C.

(

100

，

60

，

80

，

90

，

120

，

110

，

130

)

D.

(100

，

80

，

60

，

90

，

120

，

130

，

110)

10.

在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为

A,

并已知

A

的

左孩子的平衡因子为

0

右孩子的平衡因子为

1,

则应作

(    )

型调整以使其平衡。

A.  LL           B. LR          C.  RL          D.  RR

11.

下面关于

m

阶

B-

树说法正确的是

(    )

①每个结点至少有两棵非空子树；

②树中每个结点至多有

m

一

1

个关键字

;

③所有叶子在同一层上

;

④当插入一个数据项引起

B

树结点分裂后，树

长高一层。

A

．

①②③

B.

②③

C.

②③④

D.

③

12. m

阶

B-

树是一棵

(    )

A.

m

叉排序树

B.

m

叉平衡排序树

C.  m-1

叉平衡排序树

D.  m+1

叉平衡排序树

15.

设有一组记录的关键字为

{19

，

14

，

23

，

1

，

68

，

20

，

84

，

27

，

55

，

11

，

10

，

79}

，用链

地址法构造散列表，散列函数为

H

(

key

)

=key

MOD

13,

散列地址为

1

的链中有(

)

个记录。

A

．

1           B. 2         C. 3         D. 4

16.

关于哈希查找说法不正确的有几个

(    )

(

1

)采用链地址法解决冲突时，查找一个元素的时间是相同的

(

2

)采用链地址法解决冲突时，若插入规定总是在链首，则插入任一个元素的时间是

相同的

(

3

)用链地址法解决冲突易引起聚集现象

(

4

)再哈希法不易产生聚集