数据结构之散列表题解

单项选择题

01. 只能在顺序存储结构上进行的查找方法是()

A. 顺序查找法
B. 折半查找法
C. 树型查找法
D. 散列查找法

答案: B. 折半查找法
解释:
顺序查找法既可以在顺序存储结构上，也可以在链式存储结构上进行查找；折半查找法必须要求查找表是顺序存储并且关键字有序；树型查找法可以采用顺序存储或链式存储；散列查找与存储方式无关，可以结合顺序存储与链式存储。

02. 散列查找一般适用于()的情况下的查找。

A. 查找表为链表
B. 查找表为有序表
C. 关键字集合比地址集合大得多
D. 关键字集合与地址集合之间存在对应关系

答案: D. 关键字集合与地址集合之间存在对应关系
解释:
散列查找通过散列函数将关键字映射到地址，因此关键字集合与地址集合之间需要存在对应关系。查找过程中不需要表是有序的，也不局限于链表。

03. 下列关于散列表的说法中，正确的是()。

A. 若散列表的填装因子 $ < 1 $，则可避免碰撞的产生
B. 散列查找中不需要任何关键字的比较
C. 散列表在查找成功时平均查找长度与表长有关
D. 若在散列表中删除一个元素，不能简单地将该元素删除

答案: D. 若在散列表中删除一个元素，不能简单地将该元素删除
解释:

错误：即使填装因子 $ < 1 $，仍然可能发生冲突，冲突是不可避免的，因此需要处理冲突的方法。
错误：散列查找需要在散列地址确定后进行关键字比较，以确定查找是否成功。
错误：散列表的查找效率与填装因子 $ $ 有关，而与表的长度无关。
正确：在开放定址法中，简单删除元素可能导致查找路径中断，因此通常使用标记删除法，而不是直接删除。

04. 在开放定址法中散列到同一个地址而引起的“堆积”问题是由于()引起的。

A. 同义词之间发生冲突
B. 非同义词之间发生冲突
C. 同义词之间或非同义词之间发生冲突
D. 散列表“溢出”

答案: C. 同义词之间或非同义词之间发生冲突
解释:
在开放定址法中，"堆积"问题是由于同义词和非同义词在散列到同一个地址时引发的冲突，探查序列交织在一起，导致后续的查找、插入操作需要经过较长的探测距离，从而降低查找效率。因此，处理冲突时要选用合适的策略来减少堆积现象。

05. 下列关于散列冲突处理方法的说法中，正确的有()

I. 采用再散列法处理冲突时不易产生聚集
1. 采用线性探测法处理冲突时，所有同义词在散列表中一定相邻
1. 采用链地址法处理冲突时，若限定在链首插入，则插入任一个元素的时间是相同的
1. 采用链地址法处理冲突易引起聚集现象
A. I 和 III
B. I、II 和 III
C. III 和 IV
D. I 和 IV

答案: A. I 和 III
解释:

I 正确：再散列法通过按不同的散列函数计算下一个地址，减少了发生“堆积”或聚集的可能性，因此不易产生聚集。
II 错误：采用线性探测法时，同义词不一定相邻。探测时，冲突后形成的探测序列可能导致同义词和非同义词之间没有直接的相邻关系。
III 正确：在链地址法中，若采用在链首插入元素，则插入操作时间是相同的，因为插入操作不依赖于链表的长度。
IV 错误：链地址法将同义词放在同一个链表中，不会引起堆积或聚集现象，堆积问题一般在开放定址法中才出现。

06. 设有一个含有 200 个表项的散列表，用线性探测法解决冲突，按关键字查询时找到一个表项的平均探测次数不超过 1.5，则散列表应能够容纳()个表项（设查找成功的平均查找长度为 ASL = $\frac{1 + \frac{1}{1-\alpha}}{2}$，其中 $\alpha$ 为装填因子）。

A. 400
B. 526
C. 624
D. 676

答案: A. 400
解释:
给定查找成功的平均查找长度公式为： $ ASL = $ 其中 $\alpha = \frac{n}{m}$ 是装填因子，$n$ 是表项数量，$m$ 是散列表的长度。

步骤：

题目要求 ASL 不超过 1.5： $ $
解方程： $ 1 + $ $ $ $ 1- $ $ $
计算表的长度 $m$： $ = = m = 400 $ 因此，散列表的长度应为 400。

07. 假定有 K 个关键字互为同义词，若用线性探测法把这 K 个关键字填入散列表，至少要进行( )次探测。

A. $K-1$
B. $K$
C. $K+1$
D. $K(K+1)/2$

答案: D. $K(K+1)/2$
解释:
在线性探测法中，第一个关键字不需要探测，直接插入。第二个关键字需要探测一次，依次类推，第 $K$ 个关键字需要探测 $K-1$ 次。探测次数的总和为： $ 1 + 2 + 3 + + K = $ 因此，至少需要进行 $K(K+1)/2$ 次探测。

08. 对包含 $n$ 个元素的散列表进行查找，平均查找长度()。

A. 为 $O(\log_2 n)$
B. 为 $O(1)$
C. 不直接依赖于 $n$
D. 直接依赖于表长 $m$

答案: C. 不直接依赖于 $n$
解释:
散列表的查找效率主要取决于装填因子 $\alpha = \frac{n}{m}$ 和冲突处理方式，查找长度不直接依赖于表中已有元素的个数 $n$ 或表长 $m$，而是与装填因子的大小相关。

09. 采用开放定址法解决冲突的散列查找中，发生聚集的原因主要是()。

A. 数据元素过多
B. 负载因子过大
C. 散列函数选择不当
D. 解决冲突的方法选择不当

答案: D. 解决冲突的方法选择不当
解释:
聚集现象是由于解决冲突的方法不当导致的，尤其是采用线性探测法时，容易引发“初级聚集”（不同关键字争夺相邻的地址）。

10. 一组记录的关键字为 $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

答案: D. 4
解释:
根据散列函数 $H(key) = key \mod 13$，计算每个关键字的散列地址： $ \[\begin{aligned} H(14) &= 14 \mod 13 = 1, \\ H(1) &= 1 \mod 13 = 1, \\ H(27) &= 27 \mod 13 = 1, \\ H(79) &= 79 \mod 13 = 1. \end{aligned}\]

$ 因此，散列地址为1的链中有 14, 1, 27, 79 四个记录。

11. 在采用链地址法处理冲突所构成的散列表上查找某一关键字，则在查找成功的情况下，所探测的这些位置上的键值()；若采用线性探测法，则()。

A. 一定都是同义词
B. 不一定都是同义词
C. 都相同
D. 一定都不是同义词

答案: A. 一定都是同义词；B. 不一定都是同义词
解释:

在链地址法中，散列到相同地址的关键字被存放在同一个链表中，因此在查找成功的情况下，探测到的所有位置上的关键字一定都是同义词。
但是在线性探测法中，解决冲突时可能会将非同义词存放在相邻地址，因此不一定探测到的都是同义词。

12. 若采用链地址法构造散列表，散列函数为 $H(key) = key \mod 17$，则需()个链表。这些链的链首指针构成一个指针数组，数组的下标范围为()。

A. 17
B. 13
C. 16
D. 任意
②
A. 0~17
B. 1~17
C. 0~16
D. 1~16

答案: A. 17；C. 0~16
解释:

散列函数 $H(key) = key \mod 17$ 共有 17 种可能的取值（0 到 16），因此需要 17 个链表。
由于散列函数的结果范围是 0 到 16，因此数组的下标范围为 0~16。

13. 设散列表长 $ m = 14 $，散列函数为 $ H(key) = key $，表中仅有 4 个结点 $ H(15) = 4 $， $ H(38) = 5 $， $ H(61) = 6 $， $ H(84) = 7 $，若采用线性探测法处理冲突，则关键字为 49 的结点地址是( )。

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

答案: A. 8
解释:

首先，计算关键字 49 的散列地址： $ H(49) = 49 = 5. $ 由于 $ H(49) = 5 $ 在表中已经存在关键字 38，因此发生冲突。
接下来，使用线性探测法来寻找下一个可用地址。线性探测法的公式为： $ H' = (H(key) + d) m, $ 其中 $ d = 1, 2, 3, , m-1 $。
开始探测：
- 当 $ d = 1 $:$ H' = (5 + 1) = 6 $
- 当 $ d = 2 $:$ H' = (5 + 2) = 7 $
- 当 $ d = 3 $:$ H' = (5 + 3) = 8 $

因此，关键字为 49 的结点地址是 8。

14. 将10个元素散列到100000个单元的散列表中，则( )产生冲突

A. 一定不会
B. 一定会
C. 仍可能会
D. 不确定

答案: C. 仍可能会
解释:

尽管散列表的单元数远大于元素数量（10个元素与100000个单元的比为1:10000），但由于散列函数的特性，仍然可能会产生冲突。即使元素数量少，冲突是由散列函数的设计决定的，因此选项 C 是正确的。

15. 【2011统考真题】为提高散列表的查找效率，可以采取的正确措施是()

增大装填(载)因子
设计冲突(碰撞)少的散列函数
处理冲突(碰撞)时避免产生聚集(堆积)现象

A. 仅 I
B. 仅 II
C. 仅 III
D. 仅 II、III

答案: D. 仅 II、III
解释:

增大装填因子通常会导致更多的冲突，因此选项 I 是不利于查找效率的。设计一个冲突少的散列函数（选项 II）和处理冲突时避免产生聚集现象（选项 III）是提高查找效率的有效措施，因此选 D 为正确答案。

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

A. 存储效率
B. 散列函数
C. 装填(装载)因子
D. 平均查找长度

答案: D. 平均查找长度
解释:

堆积现象导致查找过程中必须进行更多的探测，因此直接影响平均查找长度。存储效率、散列函数和装填因子不会因为堆积现象而发生变化。因此选项 D 是正确的。

17. 【2018 统考真题】现有长度为 7、初始为空的散列表 HT，散列函数 $ H(k) = k $，用线性探测再散列法解决冲突。将关键字 22、43、15 依次插入 HT 后，查找成功的平均查找长度是()。

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

答案: C. 2 解释:

计算散列地址：
- $ H(22) = 22 = 1 $
- $ H(43) = 43 = 1 $（冲突，线性探测到 2）
- $ H(15) = 15 = 1 $（冲突，线性探测到 3）
插入结果如下：
- 1: 22
- 2: 43
- 3: 15
查找成功的平均查找长度（ASL）：
- 插入顺序：22 → 43 → 15
- 查找 22 的次数: 1 (1次)
- 查找 43 的次数: 2 (2次)
- 查找 15 的次数: 3 (3次)
计算 ASL： $ = = = 2 $

题目所问的是查找成功的平均查找长度，故选 C。

18. 【2019 统考真题】现有长度为 11 且初始为空的散列表 HT，散列函数是 $ H(key) = key $，采用线性探查法解决冲突。将关键字序列 87, 40, 30, 6, 11, 22, 98, 20 依次插入 HT 后，HT 查找失败的平均查找长度是()。

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

答案: C. 6
解释:

计算 ASL（查找失败）： $ ^* = = = 6 $

因此，查找失败的平均查找长度为 6。

程序题

问题01

问题 1: 若要在散列表中删除一个记录，应如何操作? 为什么?

解答:
在散列表中删除一个记录的方法依赖于冲突解决策略：

拉链法 (Chaining):
- 在这种方法中，每个表项包含一个链表（或其他数据结构）来存储冲突的记录。
- 删除操作可以通过在对应的链表中找到并移除特定记录来完成。可以直接物理删除该记录，因为其他记录仍然在链表中，查找路径不会受到影响。
开放定址法 (Open Addressing):
- 在这种方法中，记录直接存储在散列表的表项中。
- 删除时不能物理删除记录，因为这会中断查找路径（即如果查找过程中遇到空位，查找会被视为失败）。
- 正确的做法是将要删除的记录标记为“已删除”而不是完全删除。这样可以在查找时继续找到其他同义词（即在查找过程中碰到已删除标记的记录时，可以继续探测下一个地址）。

问题02

假定把关键字 key 散列到有 n 个表项 (从 0 到 n-1 编址) 的散列表中，下面的每个函数 $ H(key) $ 能否作为散列函数? 若能，它是一个好的散列函数吗? 说明理由。

$ H(key) = $
- 答案: 不能作为散列函数。
- 理由: 因为 $ $ 可能大于或等于 $ n $，这会导致散列值超出散列表的范围。此函数无法保证映射到有效的表项。
$ H(key) = 1 $
- 答案: 能作为散列函数，但不是一个好的散列函数。
- 理由: 所有关键字都会映射到同一个位置（1），这将导致大量冲突，极大地降低了散列的效率。
$ H(key) = (key + (n)) n $
- 答案: 不能作为散列函数。
- 理由: 此函数的返回值不确定，因为它依赖于随机数，这意味着同一个关键字在不同的情况下可能会映射到不同的位置，无法保证一致性。
$ H(key) = key p(n) $，其中 $ p(n) $ 是不大于 $ n $ 的最大素数
- 答案: 能作为散列函数，是一个好的散列函数。
- 理由: 该函数可以将关键字均匀分布到散列表中，特别是当 $ p(n) $ 是一个合适的素数时，可以减少冲突的可能性，提高散列效率。

问题03

使用散列函数 $ H(key) = key $ 将数据集 $1, 13, 12, 34, 38, 33, 27, 22$ 插入散列表，分别采用线性探测法和链地址法。

1. 线性探测法构造散列表

散列地址计算及插入过程:

关键字	散列地址 $ H(key) $	冲突处理过程	最终地址
1	1	无	1
13	2	无	2
12	12 (1)	冲突 -> 2 (冲突) -> 3 (无冲突)	3
34	1	冲突 -> 2 (冲突) -> 3 (冲突) -> 4 (无冲突)	4
38	5	无	5
33	0	无	0
27	5	冲突 -> 6 (无冲突)	6
22	0	冲突 -> 1 (冲突) -> 2 (冲突) -> 3 (冲突) -> 4 (冲突) -> 5 (冲突) -> 6 (冲突) -> 7 (无冲突)	7

最终散列表:

散列地址	关键字
0	33
1	1
2	13
3	12
4	34
5	38
6	27
7	22
8
9
10

查找成功所需的平均查找长度 (ASL)

对于每个元素:
- 1: 1次
- 13: 1次
- 12: 3次
- 34: 4次
- 38: 1次
- 33: 1次
- 27: 2次
- 22: 8次

$ _{} = = = 2.625 $

查找失败所需的平均查找长度 (ASL)

每个位置的查找失败概率均为 $ $:
- 查找不成功的元素:
  - 0: 9次 (查找0~8)
  - 1: 8次 (查找1~8)
  - 2: 7次 (查找2~8)
  - 3: 6次 (查找3~8)
  - 4: 5次 (查找4~8)
  - 5: 4次 (查找5~8)
  - 6: 3次 (查找6~8)
  - 7: 2次 (查找7~8)
  - 8: 1次 (查找8)
  - 9: 1次 (查找9)
  - 10: 1次 (查找10)

$ _{} = = $

2. 链地址法构造散列表

散列地址计算及插入过程:

关键字	散列地址 $ H(key) $	链表位置
1	1	1
13	2	2
12	1	1 -> 12
34	1	1 -> 12 -> 34
38	5	5
33	0	0
27	5	5 -> 27
22	0	0 -> 22

最终链表表示:

散列地址	链表
0	33 -> 22
1	1 -> 12 -> 34
2	13
5	38 -> 27
3
4
6
7
8
9
10

查找成功所需的平均查找长度 (ASL)

对于每个元素:
- 1: 1次
- 13: 1次
- 12: 2次
- 34: 3次
- 38: 1次
- 33: 1次
- 27: 2次
- 22: 2次

$ _{} = = = 1.625 $

查找失败所需的平均查找长度 (ASL)

对于每个位置，查找不成功的元素:
- 0: 2次 (查找33、22)
- 1: 4次 (查找1、12、34)
- 2: 1次 (查找13)
- 5: 2次 (查找38、27)
- 其他: 1次 (0次元素)

$ _{} = = $

问题04

已知关键字为 $26, 36, 41, 38, 44, 15, 68, 12, 51, 25$，使用链地址法解决冲突。假设装填因子 $\alpha = 0.75$，散列函数形式为 $ H(key) = key P $。

构造散列函数

首先，选择一个合适的素数 $ P $ 作为散列表的大小。因为我们希望装填因子 $\alpha = 0.75$，所以我们可以选择一个接近 10 的素数。

选择 $ P = 13 $，因为 $ = 13.33 $ 取整后为 13。

因此，散列函数为:

$ H(key) = key $

由此构造的链地址法处理冲突的散列表为

ASL_{成功}=(1*7+2*2+3*1+4*1)/11=18/11

ASL_{失败}=(1+0+2+1+0+1+1+0+0+0+1+0+4)/13=11/13

问题05

设散列表为 $ HT[0..12] $，即表的大小为 $ m = 13 $。使用双散列法解决冲突。散列函数和再散列函数如下：

初始散列函数：
$ H_0(key) = key $
再散列函数： $ H_i = (H_{i-1} + (key + 1) + 1) $ 其中，函数 REV(x) 表示颠倒十进制数 x 的各位，例如，REV(37) = 73，REV(7) = 7。

1. 插入关键码序列

插入的关键码序列为 $ (2, 8, 31, 20, 19, 18, 53, 27) $。

插入过程

插入 2:
- $ H_0(2) = 2 $ → 插入到 $ HT[2] $
插入 8:
- $ H_0(8) = 8 $ → 插入到 $ HT[8] $
插入 31:
- $ H_0(31) = 5 $ → 插入到 $ HT[5] $
插入 20:
- $ H_0(20) = 7 $ → 插入到 $ HT[7] $
插入 19:
- $ H_0(19) = 6 $ → 插入到 $ HT[6] $
插入 18:
- $ H_0(18) = 5 $ → 发生冲突
- 计算 $ H_1 $:
  - $ (18 + 1) = (19) = 91 $
  - $ H_1 = (5 + 91 + 1) = (5 + 3 + 1) = 9 $ → 插入到 $ HT[9] $
插入 53:
- $ H_0(53) = 1 $ → 插入到 $ HT[1] $
插入 27:
- $ H_0(27) = 1 $ → 发生冲突
- 计算 $ H_1 $:
  - $ (27 + 1) = (28) = 82 $
  - $ H_1 = (1 + 82 + 1) = (1 + 5 + 1) = 7 $ → 发生冲突
- 计算 $ H_2 $:
  - $ H_2 = (7 + 82 + 1) = (7 + 5 + 1) = 0 $ → 插入到 $ HT[0] $