2024 年 408 真题

2024 年 408 数据结构 · 第 42 题

选中文字高亮 · 下划线

将关键字 $20, 3, 11, 18, 9, 14, 7$ 依次存储到长度为 $11$ 的散列表 $H T$ 中，散列函数为 $H (k ey) = (k ey \times 3) %11$ ， $H 0$ 为初始散列地址， $H_{1}$ 、 $H_{2}$ 、 $H_{3}$ 、 $\dots$ 、 $H_{k}$ 分别为第 $1$ 次冲突、第 $2$ 次冲突、第 $3$ 次冲突、 $\dots$ 、第 $k$ 次冲突时探测的地址。 $H_{k} = (H_{0} + k^{2}) %11$ 。请回答下列问题：

(1) 画出所构造的 $H T$ 。并计算 $H T$ 的域装因子（6 分）

(2) 给出在 $H T$ 中查找关键字 14 的关键字比较序列（2 分）

(3) 在 $H T$ 中查找关键字 8，确认查找失败时的散列地址是多少？（2 分）