🏷️ 知识点：散列表

散列表的地址范围为 0-17，散列函数为 H(k)=k mod 17。采用线性探测法处理冲突，将关键字序列 26,25,72,38,8,18,59 依次存储到散列表中。元素 59 存放在散列表中的地址是（ ）。

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

散列表

[tag_link]

正确答案：D

散列表地址范围为 0 到 17，共 18 个地址。 散列函数为

$H(k)=k\mathrm{mod}17$ ，采用线性探测法处理冲突。

将关键字序列 26, 25, 72, 38, 8, 18, 59 依次插入：

• 插入 26： $H(26)=26\mathrm{mod}17=9$ ，地址 9 为空，存入。 >
• 插入 25： $H(25)=25\mathrm{mod}17=8$ ，地址 8 为空，存入。 >
• 插入 72： $H(72)=72\mathrm{mod}17=4$ ，地址 4 为空，存入。 >
• 插入 38： $H(38)=38\mathrm{mod}17=4$ ，地址 4 冲突，线性探测下一个地址 5，地址 5 为空，存入。 >
• 插入 8： $H(8)=8\mathrm{mod}17=8$ ，地址 8 冲突，线性探测地址 9 冲突，地址 10 为空，存入。 >
• 插入 18： $H(18)=18\mathrm{mod}17=1$ ，地址 1 为空，存入。 >
• 插入 59： $H(59)=59\mathrm{mod}17=8$ ，地址 8 冲突，线性探测地址 9 冲突，地址 10 冲突，地址 11 为空，存入。 >

因此，元素 59 存放在地址 11。 >

用哈希(散列)方法处理冲突(碰撞)时可能出现堆积(聚集)现象，下列选项中，会受堆积现象直接 影 响 的 是 ( ) 。

A. 存储效率

B. 散列函数

C. 装填(装载)因子

D. 平均查找长度

[tag_link]

正确答案：D

产生堆积现象，即产生了冲突，它对存储效率、散列函数和装填因子均 不会有影响，而 平均查找长度 会因为堆积现象而增大，选 D。

现有长度为 11 且初始为空的散列表 HT，散列函数是 H(key)=key%7，采用线性探查（线性探测再散列）法解决冲突将关键字序列 87，40，30，6，11，22，98，20 依次插入到 HT 后，HT 查找失败的平均查找长度是（ ）。

散列表 平均查找长度

A. 4 B. 5.25 C. 6 D. 6.29

[tag_link]

正确答案：C

构造 散列表 只有当遇到关键字为空的地址时才会查找失败，key%7 之后，初始地址只可能在 06，所以即 06 到空地址的距离求平均，即为查找失败的平均查找长度初始地址是 0 的失败查找长度为 9，同理得初始地址为 1，2，3，4，5，6 的失败查找长度为 8，7，6，5，4，3，(9+8+7+6+5+4+3)/7 = 6 答案是 C。

下列关于散列表的说法中，不正确的是（ ）个。 Ⅰ. 散列表的平均查找长度与处理冲突方法无关 Ⅱ. 在散列表中，“比较”操作一般也是不可避免的 Ⅲ. 散列表在查找成功时的平均查找长度与表长有关 Ⅳ. 若在散列表中删除一个元素，只需简单地将该元素删除即可

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

散列表

[tag_link]

正确答案：C

Ⅰ错误。

散列表的平均查找长度（ASL）与处理冲突的方法密切相关。 例如，线性探测、二次探测和链地址法等不同方法会导致不同的查找性能，ASL 计算公式也各不相同，因此该说法不正确。

Ⅱ正确。 在散列表查找过程中，即使哈希函数直接映射到槽位，通常也需要比较关键字以确认是否找到目标元素，因为哈希冲突可能发生或需要验证匹配，因此“比较”操作一般是不可避免的。

Ⅲ错误。 散列表在查找成功时的平均查找长度主要取决于负载因子（元素个数与表长的比值），而不是表长本身。 例如，链地址法中成功查找的 ASL 约为 1 + α/2（α为负载因子），当负载因子固定时，ASL 与表长无关，因此该说法不正确。

Ⅳ错误。 在散列表中删除元素并不总是简单的，尤其是采用开放定址法时，直接删除元素可能会破坏查找链，导致后续查找失败，通常需要标记为“已删除”状态。 即使在链地址法中，删除也需调整指针，因此该说法不正确。

综上，不正确的说法有Ⅰ、Ⅲ、Ⅳ，共 3 个，故选 C。

为提高哈希（Hash）表的查找效率，可以采取的正确措施是（ ）。

I. 增大装填因子

II. 设计冲突少的哈希函数

III. 处理冲突时避免产生堆积现象

散列表

A. 仅 I

B. 仅 II

C. 仅 I、II

D. 仅 II、III

[tag_link]

正确答案：D 哈希表 的查找效率取决于散列函数、处理冲突的方法和装填因子。显然，冲突的产生概率与装填因子（表中记录数与表长之比）的大小成正比，即装填得越满越容易发生冲突，I 错误。II 显然正确。采用合适的处理冲突的方式避免产生聚集现象，也将提高查找效率，例如用拉链法解决冲突时就不存在聚集现象，用线性探测法解决冲突时易引起聚集现象，III 正确。

现有长度为 7、初始为空的散列表 HT，散列函数 H(k) = k % 7，用线性探测再散列法解决冲突。将关键字 22, 43, 15 依次插人到 HT 后，查找成功的平均查找长度是（ ）

散列表 平均查找长度

A. 1.5 B. 1.6 C. 2 D. 3

[tag_link]

正确答案：C

可以构造得到如下的 HT：

成功时的平均查找长度 = (1+2+3)/3 = 2。

下列因素中，影响散列(哈希)方法平均查找长度的是()。

I. 装填因子

II. 散列函数

II. 冲突解决策略

A. 仅 I 、Ⅱ B. 仅 I 、Ⅲ

C. 仅 I 、Ⅲ D.I 、Ⅱ 、Ⅲ

[tag_link]

正确答案：D

三者都会影响：装填因子越大，说明 哈希表 中存储的元素越满，发生冲突的可能性越大，平均查找长度也越大。散列函数、突解决策略会影响发生冲突的可能性。

现有长度为 5，初始为空的散列表 HT，散列表函数 H(k) = (k+4) % 5 用线性探查再散列法解决冲突。若将关键字序列 2022,12,25 依次插入 HT 中，然后删除关键字 25，则 HT 中查找失败的平均查找长度（ ）。

散列表 平均查找长度

A. 1 B. 1.6 C. 1.8 D. 2.2

[tag_link]

正确答案：C

线性探测再散列法中删除一个关键字会导致后面的关键字无法通过线性探测找到正确的位置。当删除一个关键字时，为了保持散列表的连续性，通常会将后续的关键字向前移动填充空缺，这样后续的查找操作才能继续正确地找到它们。然而，如果删除的是一个位于中间位置的关键字，后面的关键字需要依次向前移动，这会导致删除操作的时间复杂度较高，因为需要移动大量的关键字。为了解决删除操作中的位置依赖性问题，可以使用删除标记来表示一个位置上的关键字已被删除。如下表所示，查找失败的平均查找长度为 (1+3+2+1+2)/5=1.8。本题答案选 C。

下列关于散列法处理冲突的叙述中，正确的是（ ）。

散列表

A. 只要散列表不满，线性探查再散列一定能找到一个空闲位置 B. 只要散列表不满，二次探查再散列一定能找到一个空闲位置 C. 线性探查再散列处理的冲突，一定是发生在同义词之间 D. 二次探查再散列处理的冲突，一定是发生在非同义词之间

[tag_link]

正确答案：A

在散列（哈希）方法中，同义词 是指不同的元素通过哈希函数映射到同一个哈希值（或哈希地址)。这意味着这些元素在散列表中会发生冲突，因为它们试图占用相同的位置。非同义词 指的是通过哈希函数映射到不同哈希值的元素，它们通常不会在初始哈希地址上发生冲突。对于题目中的选项： A. 只要散列表不满，线性探查再散列一定能找到一个空闲位置。线性探查是在发生冲突时，按顺序查找下一个可用位置。例如，如果发生冲突，就逐一检查下一个位置，直到找到空闲位置。只要散列表有空位，线性探查一定能找到一个空闲位置。因此，这个选项是正确的。 B. 只要散列表不满，二次探查再散列一定能找到一个空闲位置。二次探查是通过二次函数（如平方）来决定下一个检查的位置。虽然理论上在某些情况下可能会更快找到空位，但由于散列表的装填因子和特定的探查序列，可能会有探查不到空闲位置的情况，因此这个选项不一定总是正确。 C. 线性探查再散列处理的冲突，一定是发生在同义词之间。线性探查处理的冲突可能发生在同义词之间（即初始哈希值相同的元素），但也可能发生在非同义词之间（即由于探查过程而导致的冲突）。因此，这个选项是不正确的。 D. 二次探查再散列处理的冲突，一定是发生在非同义词之间。二次探查可能会导致同义词和非同义词之间的冲突。因此，这个选项是不正确的。

右图所示是 一棵()。 12 25

A. 4 阶 B 树 B.3 阶 B 树 C. 4 阶 B+ 树 D. 无法确定

[tag_link]

正确答案：D

下列关于m 阶 B 树的说法中，错误的是()。

A. 根结点至多有m 棵子树 B. 所有叶结点都在同一层次上 C. 非叶结点至少有 m/2(m 为偶数)或(m+1)/2(m 为奇数)棵子树 D. 根结点中的数据是有序的

[tag_link]

正确答案：C

下列关于高度为3的3阶B 树的说法中，正确的是()。 I. 每个内部结点至少有两棵非空子树 II. 树中每个结点至多有2个关键字 Ⅲ. 树中最多能存储26个关键字 IV. 插入一个元素引起B树结点分裂后，树的高度变为4

A. I 、Ⅱ B.I 、Ⅱ 、Ⅲ C.Ⅲ 、IV D.I 、Ⅱ 、IV

[tag_link]

正确答案：B

在一棵m 阶 B 树中做插入操作前，若一个结点中的关键字个数等于(),则插入操作 后必须分裂成两个结点；在一棵 m 阶 B 树中做删除操作前，若一个结点中的关键字个 数等于(),则删除操作后可能需要同它的左兄弟或右兄弟结点合并成一个结点。

A. m,[m/27-2 B.m-1,「m/27-1 C. m+1,[m/27 D.m/2,[m/27+1

[tag_link]

正确答案：B

CSMA 协议可以利用多种监听算法来减小发送冲突的概率，下面关于各种监听算法的描述中，错误的是（ ）。

A. Ⅰ、Ⅱ和Ⅲ B. Ⅱ和Ⅲ C. Ⅰ、Ⅱ和Ⅳ D. Ⅱ和Ⅳ

散列表

[tag_link]

正确答案：A

首先，分析各监听算法的特性：非坚持型监听算法在信道忙时等待随机时间再监听，这减少了冲突，但可能导致信道空闲时无站点立即发送，从而增加网络空闲时间，因此陈述Ⅰ“有利于减少网络空闲时间”是错误的。

其次，1-坚持型监听算法在信道空闲时立即发送，虽然减少了空闲时间，但多个站点可能同时发送，导致冲突概率增加，因此陈述Ⅱ“有利于减少冲突的概率”是错误的。

再者，P 坚持型监听算法通过概率

$P$ 发送来平衡冲突和空闲时间，相比非坚持型能减少空闲时间，因此陈述Ⅲ“无法减少网络的空闲时间”是错误的。

最后，1-坚持型算法因持续监听并在信道空闲时立即发送，能及时抢占信道，陈述Ⅳ是正确的。

综上，错误的陈述是Ⅰ、Ⅱ和Ⅲ，对应选项 A。

具有n 个关键字的m 阶 B 树，应有()个叶结点。

A. n+1 B.n - 1 C.mn D.nm/2

[tag_link]

正确答案：A

以太网中如果发生介质访问冲突，按照二进制指数后退算法决定下一次重发的时间，使用二进制后退算法的好处是（ ）。

A. 这种算法简单 B. 这种算法执行速度快 C. 这种算法考虑了网络负载对冲突的影响 D. 这种算法与网络的规模大小无关

散列表

[tag_link]

正确答案：C

二进制指数后退算法在以太网中用于处理介质访问冲突。

当冲突发生时，发送方会根据冲突次数 k，从 0 到 2^k - 1 个时间槽中随机选择一个值作为退避时间。 随着冲突次数增加，退避时间区间呈指数增长，这意味着在网络负载较高、冲突频繁时，发送方会等待更长时间再重发，从而降低再次冲突的概率。

这种设计使算法能够动态适应网络负载：负载越重，冲突越多，退避时间越长，有效缓解拥塞。 因此，算法的主要好处是考虑了网络负载对冲突的影响。 选项 A 和 B 并非算法的核心优势； 选项 D 不准确，因为算法参数（如时间槽）与网络规模（如传播延迟）相关，但算法重点在于负载自适应。

在 CSMA/CD 协议中，下列指标与冲突时间没有关系的是（ ）。

A. 检测一次冲突所需要的最长时间 B. 最小帧长度 C. 最大帧长度 D. 最大帧碎片长度

散列表 协议数据单元

[tag_link]

正确答案：C

在 CSMA/CD 协议中，冲突时间（即冲突窗口或往返传播延迟）是一个关键参数，它决定了信号从发送端到最远站点再返回所需的最长时间。

这个时间直接影响到冲突检测和帧设计。

选项 A“检测一次冲突所需要的最长时间”本质上就是冲突时间本身，因此与冲突时间直接相关。 选项 B“最小帧长度”是为了确保在帧发送完毕前能够检测到冲突，其计算公式为最小帧长度 = 2 × 传播延迟 × 数据传输速率，这与冲突时间紧密相连。 选项 D“最大帧碎片长度”指的是冲突发生后可能产生的碎片的最大长度，由于碎片只能在冲突窗口内形成，其最大长度受限于冲突时间内传输的比特数，因此也与冲突时间有关。

相比之下，选项 C“最大帧长度”通常由协议规范、网络性能或缓冲区大小等因素决定，例如传统以太网中最大帧长度为 1518 字节，目的是限制帧的大小以避免信道过长时间被占用，但这一指标与冲突时间没有直接关系，冲突时间并不影响最大帧长度的设定。 因此，与冲突时间没有关系的是最大帧长度。

高度为5的3阶B 树至少有()个结点，至多有()个结点。

A. 32 B. 31 C . 120 D.121

[tag_link]

正确答案：

含有n 个非叶结点的m 阶 B 树中至少包含()个关键字。

A. n(m+1) B.n C.n([m/27-1) D.(n-1)(「m/27-1)+1

[tag_link]

正确答案：D

已知一棵5阶B 树中共有53个关键字，则树的最大高度为(),最小高度为()。

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

[tag_link]

正确答案：

已知 一棵3阶B 树中共有2047个关键字，则树的最大高度为(),最小高度为()。

A. 1 1 B. 10 C. 8 D.7

[tag_link]

正确答案：

在 7 阶 B 树中，按从上往下、从左往右的顺序搜索第2016个关键字，若根结点已读入 内存，则最多需启动()次I/O。

A. 4 B.5 C.6 D.7

[tag_link]

正确答案：B

（13 分）设记录的关键字（key）集合：K={24, 15, 39, 26, 18, 31, 05, 22}，请回答： （1）依次取 K 中各值，构造一棵二叉排序树（不要求平衡），并写出该树的前序、中序和后序遍历序列。 （2）设 Hash 表表长 m=16，Hash 函数 H(key)=(key)%13，处理冲突方法为“二次探测法”，请依次取 K 中各值，构造出满足所给条件的 Hash 表；并求出等概率条件下查找成功时的平均查找长度。 （3）将给定的 K 调整成一个堆顶元素取最大值的堆（即大根堆）。

散列表

[tag_link]

**【解析】** （1）将关键字{24，15，39，26，18，31，05，22}依次插入构成的二叉排序树如下：

先序遍历序列：24，15，05，18，22，39，26，31 中序遍历序列：05，15，18，22，24，26，31，39 后序遍历序列：05，22，18，15，31，26，39，24

（2）各关键字通过 Hash 函数得到的散列地址如下表。

Key=24、15、39 均没有冲突，H₀(26)=0，冲突，H₁(26)=0+1=1，没有冲突； Key=18 没有冲突，H₀(31)=5，冲突，H₁(31)=5+1=6，没有冲突；H₀(05)=5，冲突，H₁(05)=5+1=6，冲突，H₂(05)=5-1=4，没有冲突；Key=22 没有冲突。故各个关键字的存储地址如下表所示。

没有发生冲突的关键字，查找的比较次数为 1，发生冲突的关键字，查找的比较次数为冲突次数+1，因此，等概率下的平均查找长度为：

ASL = (1+1+1+2+1+2+3+1)/2 = 1.5 次

（3）首先对以 26 为根的子树进行调整，调整后的结果如图 b 所示；对以 39 为根的子树进行调整，调整后的结果如图 c 所示；再对以 15 为根的子树进行调整，调整后的结果如图 d 所示；最后对根结点进行调整，调整后的结果如图 e 所示。