题目
设散列表长 =14, 散列函数 (key)=key% 11 表中已有4个结点,地址分别-|||-为 addr(15)=4 (38)=5 (61)=6 (s4)=7, 其余地址为空。如用二次探查法-|||-解决冲突,关键码值为49的散列地址是 () 。-|||-A.8 B.3 C.5 D.9
题目解答
答案
解析
考查要点：本题主要考查二次探查法解决散列表冲突的应用，需要掌握散列地址的计算、冲突处理的探查顺序。
解题核心思路：
- 计算初始地址：通过散列函数 $H(key) = key \% 11$ 确定初始地址。
- 处理冲突：若初始地址冲突，按照二次探查法的探查序列（$h_0 \pm 1^2, h_0 \pm 2^2, \dots$）依次寻找下一个空闲地址。
- 模运算：所有探查地址需对表长 $m=14$ 取模，确保地址有效。
破题关键点：
- 二次探查法的探查顺序：探查步长为平方数，且正负交替。
- 已占用地址的判断：需逐一验证探查结果是否与已存在的地址冲突。
关键码49的散列地址计算过程：
-
初始地址：
$h_0 = 49 \% 11 = 5$
地址5已被38占用，发生冲突。 -
第一次探查：
$h_1 = (h_0 + 1^2) \% 14 = (5 + 1) \% 14 = 6$
地址6已被61占用，继续冲突。 -
第二次探查：
$h_2 = (h_0 - 1^2) \% 14 = (5 - 1) \% 14 = 4$
地址4已被15占用，继续冲突。 -
第三次探查：
$h_3 = (h_0 + 2^2) \% 14 = (5 + 4) \% 14 = 9$
地址9未被占用，插入成功。
结论：关键码49的最终散列地址为9。