企业官网建设流程全解析

数据结构期末复习 第八章查找

一、选择题

1.顺序查找方法适合于存储结构为（D）的线性表。

A．散列存储 B．索引存储

C．散列存储或索引存储 D．顺序存储或链接存储

2．在有序表{1，3，8，13，33，42，46，63，76，78，86，97，100}中，用折半查找值86时，经（B）次比较后查找成功。

A．3 B．4 C．6 D．8

3．对二叉排序树进行（C）遍历，可以使遍历所得到的序列是有序序列。

A．按层次 B．后序 C．中序 D．前序

4．有一个长度为12的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为（A）。

A．37/12 B．39/12 C．41/12 D．35/12

5．已知一个有序表为{11,22,33,44,55,66,77,88,99}，则顺序查找元素55需要比较（C）次。

A．3 B．4 C．5 D．6

6.顺序查找法与折半查找法对存储结构的要求是（D）。

A．顺序查找与折半查找均只适用于顺序表

B．顺序查找与折半查找均既适用于顺序表，也适用于链表

C．顺序查找只是适用于顺序表

D．折半查找适用于顺序表

7．有数据{53,30,37,12,45,24,96}，从空二叉树开始逐个插入数据来形成二叉排序树，若希望高度最小，应该选择的序列是（B）。

A．45,24,53,12,37,96,30 B．37,24,12,30,53,45,96

C．12,24,30,37,45,53,96 D．30,24,12,37,45,96,53

8.采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为（C）。

A．n B．n/2

C．(n+1)/2 D．(n-1)/2

9.对于一个线性表，若要求既能进行较快地插入和删除，又要求存储结构能够反映数据元素之间的逻辑关系，则应该（B）。

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

C．以索引存储方式 D．以散列存储方式

10.哈希函数有一个共同的性质，即函数值应当以（D）取其值域的每个值。

A．最大概率 B．最小概率

C．平均概率 D．同等概率

解析：哈希函数的一个重要性质是：对于不同的输入，其输出应尽可能均匀分布在值域中，即每个输出值被选中的概率应大致相等。

平均概率是个综合性的计算，不是对具体某个输出值的控制。且平均概率的表象下，有极小概率和极大概率共存的不均匀状态

11.在最坏情况下，折半查找与二叉排序树查找性能比较，（B）

A. 完全相同 B.折半查找性能好

C. 二叉排序树查找性能好 D.不能确定

解析：折半查找（对有序顺序表）：最坏情况下需要比较⌊log2n⌋+1次，时间复杂度为O(logn)，且是严格稳定的对数级别。

二叉排序树查找：最坏情况发生在树退化成单支（即插入序列有序或逆序时），此时树高为n，查找退化为顺序查找，最坏时间复杂度为O(n)。

因此，在最坏情况下，折半查找的性能远优于二叉排序树查找。

12.设哈希表长m=14，哈希函数H(key)=key mod 11。表中已有4个结点：addr(15)=4; addr(38)=5; addr(61)=6; addr(84)=7。如用线性探测处理冲突，关键字为49的结点的地址是（A）。

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

解析：哈希表长m=14，地址范围0~13。

哈希函数H(key)=key mod 11

已有结点：
H(15)=15 mod11=4（地址4）
H(38)=38 mod 11=5（地址5）
H(61)=61 mod 11=6（地址6）
H(84)=84 mod 11=7（地址7）

插入49：

计算H(49)=49 mod 11=5

地址5已被38占用→冲突

线性探测：(5+1) mod14=6 →地址6已被61占用

继续：(6+1) mod 14=7 →地址7已被84占用

继续：(7+1) mod 14=8 →地址8空闲

所以49存放在地址8。

13.采用折半查找方法查找长度为n的线性表时，每个元素的平均查找长度为（D）。

A．n2 B.nlog2n C.n D.log2n

14.哈希表的平均查找长度（A）

A．与处理冲突的方法有关，与表的长度无关

B．与处理冲突的方法无关，与表的长度有关

C．与处理冲突的方法有关，与表的长度有关

D．与处理冲突的方法无关，与表的长度无关

解析：按严格哈希表理论，应选C（与冲突方法和装填因子有关，而装填因子包含表长）。

按常见应试答案（尤其部分教材），选A。

解释：

哈希表的平均查找长度（ASL）受多个因素影响：

与处理冲突的方法有关
不同冲突解决方法（如线性探测、二次探测、链地址法等）对查找长度影响很大。例如，线性探测容易产生“聚集”，平均查找长度通常比链地址法要大。

与表的长度有关（更准确地说，与装填因子α=n/mα=n/m有关）
表长mm固定时，表中已存元素个数nn越大（即装填因子越大），冲突越可能发生，平均查找长度越大。反之，表越长（mm越大）而nn固定时，装填因子越小，平均查找长度越小。
因此，“与表的长度有关”在通常意义上可以理解为与装填因子有关，而装填因子包含表长mm这个因素。

综上，平均查找长度既与冲突处理方法有关，也与表的长度（通过装填因子）有关。

故选择C。

15.一组记录的关键字是{19,14,23,1,68,20,84,27,55,11,10,79}，用链接地址法构造散列表，散列函数为H(key)=key mod 13,散列地址为1的链中有（D）个记录。

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

解析：

19mod13=6

14mod 13=1←地址1

23mod 13=10

1mod 13=1←地址1

68mod 13=68−65=3

20mod 13=7

84mod 13=84−78=6

27mod 13=1←地址1

55mod 13=55−52=3

11mod 13=11

10mod 13=10

79mod 13=79−78=1←地址1

散列地址为1的关键字有：14、1、27、79
一共4个。

16.二叉排序树的查找效率与二叉树的（C）有关。

A.高度 B.结点个数 C.树形 D.结点的位置

解释：

二叉排序树的查找效率主要取决于树的形状（即树形），而树形又由关键字插入的顺序决定。

树形直接影响树的高度。同样nn个结点：

平衡的树形→高度约log⁡2nlog2​n→查找效率高O(log⁡n)O(logn)

退化的树形（如单支树）→高度nn→查找效率低O(n)O(n)

A.高度：高度是树形的直接结果，但“与高度有关”不够本质，因为高度由树形决定。不过某些题目会选高度，但本题有“树形”这个更根本的选项时，应选树形。

B.结点个数：nn一定时，不同树形效率不同，所以查找效率不只看结点个数。

D.结点的位置：这是微观描述，不够准确。

二、判断题

1．在顺序查找、折半查找、哈希表查找3种方法中，平均查找长度与结点个数n无关的查找方法是折半查找。（×）

2．在一个查找表中，能够唯一地确定一个记录的关键字称为主关键字。（√）

3.顺序查找是一种最简单的查找方法。（√）

4.折半查找的前提条件是，查找表中记录相应的关键字值必须有序或者部分有序。（×）

5.二叉排序树的建立过程上实际上是从空树逐次插入的过程。（√）

6.理想情况下，哈希表查找等概率查找成功的时间复杂度是O(1)。（√）

7.按照一定规则，在二叉排序树上插入、删除结点，仍能保持二叉排序树的性质。（√）

8.分块查找分为两个步骤：第一步是要对索引表进行查找；第二步是在块中查找。这两步查找都可以采用折半查找或者顺序查找方法。（×）

9.一个好的哈希函数，应该使哈希地址均匀地分布在整个哈希表的地址区间中，完全避免冲突的发生。（×）

10.在有序顺序存储的线性表中查找一个元素，用折半查找速度一定比顺序查找快。（×）

11.二叉树为二叉排序树的充分必要条件是，任一个分支结点的值都大于其左孩子的值，小于右孩子的值。（×）

12.二叉排序树在呈单支二叉树时，查找效率最低。（√）

13.将10个元素散列到10000个单元的哈希表中，仍然可能会产生冲突。（√）

14.根据无序序列构造二叉排序树的过程，也是对无序序列排序的过程。（√）

15.折半查找方法运用在升序序列比降序序列效率更高，所以降序序列最好先转换为升序序列。（×）