题目

将关键字 20, 3, 11, 18, 9, 14, 7 依次存储到长度为 11 的散列表 HT 中，散列函数为 H(key) = (key × 3) mod 11。

H₀ 为初始散列地址，H₁、H₂、H₃、…、H_k 分别为第 1 次冲突、第 2 次冲突、第 3 次冲突、…、第 k 次冲突时探测的地址，H_k = (H₀ + k²) mod 11。

请回答下列问题：

(1) 画出所构造的 HT，并计算 HT 的装填因子。

(2) 给出在 HT 中查找关键字 14 的关键字比较序列。

(3) 在 HT 中查找关键字 8，确认查找失败时的散列地址是多少？

解析

(1) 构造 HT 与装填因子

答案：HT 如下，装填因子 。

地址	0	1	2	3	4	5	6	7	8	9	10
关键字	11		14	7		20	9			3	18

推导——按插入顺序逐个算 ，冲突时按 继续探查（注意是单向加 ，不是 ）：

#	key		探查过程	落入
1	20	5	空	5
2	3	9	空	9
3	11	0	空	0
4	18	10	空	10
5	9	5	HT[5]=20 冲突 → 空	6
6	14	9	HT[9]=3 冲突 → =18 冲突 → 空	2
7	7	10	HT[10]=18 冲突 → =11 冲突 → 空	3

(2) 查找 14 的关键字比较序列

答案：3, 18, 14（共 3 次比较）。

，从地址 9 开始按二次探查比对：

步骤	地址	HT 内容	结果
	9	3	3 ≠ 14，继续
	10	18	18 ≠ 14，继续
	2	14	命中

编者注（生僻术语）：「关键字比较序列」写的是实际与目标做比较的 HT 内容（3、18、14），不是探查地址（9、10、2）——这是常见失分点。

(3) 查找 8 失败时的散列地址

答案：7。

，开放定址法探查到空槽即判定失败，对应那个空槽的地址就是"失败地址"：

步骤	地址	HT 内容	结果
	2	14	14 ≠ 8，继续
	3	7	7 ≠ 8，继续
	6	9	9 ≠ 8，继续
	0	11	11 ≠ 8，继续
	7	空	失败