数据结构-作业11

参考教材：数据结构教程（Java语言描述)        作者：李春葆

1 . 容易 （4分）假设有k个关键字互为同义词，若用线性探测法把这k个关键字插入到哈希表中，至少要进行______ 次探测。

A. k-1

B. k

C. k+1

D. k(k+1)/2

2 . 容易 （4分）对于下列关键字序列，不可能构成某二叉排序树中一条查找路径是______。

A. 95，22，91，24，94，71

B. 92，20，91，34，88，35

C. 21，89，77，29，36，38

D. 12，25，71，68，33，34

3 . 容易 （4分）一棵二叉排序树是由关键字集合{18，43，27，44，36，39}中的某个关键字序列构建的，其中序遍历序列是______。

A. 树形未定，无法确定

B. 18，43，27，77，44，36，39

C. 18，27，36，39，43，44，77

D. 18，44，43，39，36，27，77

4 . 容易 （4分）以下查找方法中速度最快的是______。

A. 折半查找

B. 顺序查找

C. 分块查找

D. 二叉排序树查找

5 . 容易 （4分）下面有关哈希表的叙述中，正确的是______。

A. 哈希查找的时间与元素个数n成正比 

B. 不管是开放地址法还是拉链法，查找时间都与装填因子α有关

C. 线性探测法存在堆积现象，而拉链法不存在堆积现象

D. 拉链法中装填因子α必须小于1

6 . 容易 （4分）在哈希查找过程中，可用______ 来处理冲突。

A. 除留余数法

B. 数字分析法

C. 线性探测法

D. 关键字比较法

7 . 容易 （4分）哈希表中出现同义词冲突是指______。

A. 两个元素具有相同的序号

B. 两个元素的关键字不同，而其他属性相同

C. 数据元素过多

D. 两个元素的关键字不同，而对应的哈希函数值相同

8 . 容易 （4分）为提高哈希（Hash）表的查找效率，可以采取的正确措施是______。 Ⅰ.增大装填因子 Ⅱ.设计冲突少的哈希函数 Ⅲ.处理冲突时避免产生堆积现象

A. 仅Ⅰ

B. 仅Ⅱ

C. 仅Ⅰ、Ⅱ

D. 仅Ⅱ、Ⅲ

9 . 容易 （4分）采用线性探查法解决冲突的哈希表中，引起的堆积现象的原因是______。

A. 同义词之间发生冲突

B. 非同义词之间发生冲突

C. 同义词或非同义词之间发生冲突

D. 哈希表溢出

10 . 容易 （4分）由一个关键字序列建立一棵二叉排序树，该二叉排序树的形状取决于______。

A. 该序列的存储结构

B. 序列中的关键字的取值范围

C. 关键字的输入次序

D. 使用的计算机的软、硬件条件

11 . 容易 （4分）有一个有序表为（1，3，9，12，32，41，45，62，75，77，82，95，99），当采用折半查找法查找关键字为82的元素时，______ 次比较后查找成功。

A. 1

B. 2

C. 4

D. 8

12 . 容易 （4分）在长度为n的线性表中顺序查找时，成功情况下最多的比较次数是______。

A. 1

B. n

C. n/2

D. (n+1)/2

13 . 容易 （4分）对长度为3的顺序表进行顺序查找，若查找第1个元素的概率是1/2，查找第2个元素的概率是1/3，查找第3个元素的概率是1/6，则成功查找表中任一元素的平均查找长度是______。

A. 5/3

B. 2

C. 7/3

D. 3

14 . 容易 （4分）对线性表进行折半查找时，要求线性表必须______。

A. 以顺序方式存储

B. 以链接方式存储

C. 以顺序方式存储，且结点按关键字有序排序

D. 以链表方式存储，且结点按关键字有序排序

15 . 容易 （4分）折半查找对应的判定树中，外部结点是______。

A. 一次成功查找过程终止的结点

B. 一次失败查找过程终止的结点

C. 一次成功查找过程中经过的中间结点

D. 一次失败查找过程中经过的中间结点

16 . 容易 （4分）已知一个长度为16的有序顺序表R[1..16]，采用折半查找方法查找一个存在的元素，则比较的次数最多是______。

A. 5

B. 4

C. 7

D. 6

17 . 容易 （4分）设有100个元素的有序顺序表，采用折半查找方法，不成功时最大的比较次数是______。

A. 25

B. 50

C. 10

D. 7

18 . 容易 （4分）有一个长度为12的有序表R[0..11]，按折半查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为______。

A. 35/12

B. 37/12

C. 39/12

D. 43/12

19 . 容易 （4分）有一个长度为12的有序表R[0..11]，按折半查找法对该表进行查找，在表内各元素等概率情况下查找不成功所需的平均比较次数为______。

A. 35/11

B. 37/12

C. 49/12

D. 49/13 

20 . 容易 （4分）在长度为n的线性表中顺序查找时，不成功情况下平均比较次数是______。

A. n

B. n/2

C. (n+1)/2

D. (n-1)/2

21 . 容易 （4分）有一个长度为n的有序顺序表，采用折半查找，经过i次比较成功找到的最多元素个数是______。

A. 2i

B. 2i+1

C. 2i-1

D. 2i-1

系统中默认答案为D，C、D答案一致为系统设置bug

22 . 容易 （4分）当采用分块查找时，数据的组织方式为______。

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

B. 数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的关键字组成索引块

C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的关键字组成索引块

D. 数据分成若干块，每块中的数据个数必须相同

23 . 容易 （3分）对含有3600个元素的顺序表进行分块查找，若索引表和方块均采用顺序查找方法，最理想的块长是______。

A. 1800

B. 60

C. 1200

D. log23600

24 . 容易 （3分）设待查关键字为47，且已存入变量k中，如果在查找过程中，和k进行比较的元素依次是47、32、46、25、47，则所采用的查找方法______。

A. 是一种错误的方法

B. 可能是分块查找

C. 可能是顺序查找

D. 可能是折半查找

25 . 容易 （3分）设待查关键字为47，且已存入变量k中，如果在查找过程中，和k进行比较的元素依次是27、72、16、84、47，则所采用的查找方法是______。

A. 二叉排序树查找

B. 分块查找

C. 顺序查找

D. 折半查找

26 . 容易 （3分）从19个元素的序列中查找其中某个元素，如果最多进行5次元素之间的比较，则采用的查找方法只可能是______。

A. 折半查找

B. 分块查找

C. 顺序查找

D. 二叉排序树查找