结构推理
设散列表为HT[13], 散列函数为 H (key) = key /%13。用闭散列法解决冲突, 对下列关键码序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。采用线性探查法寻找下一个空位, 画出相应的散列表, 并计算等概率下搜索成功的平均搜索长度和搜索不成功的平均搜索长度。
(2) 采用双散列法寻找下一个空位, 再散列函数为 RH (key) = (7*key) /% 10 + 1, 寻找下一个空位的公式为 Hi = (Hi-1 + RH (key)) /% 13, H1 = H (key)。画出相应的散列表, 并计算等概率下搜索成功的平均搜索长度。
【正确答案】使用散列函数 H(key) = key mod 13，有
H(12) = 12, H(23) = 10, H(45) = 6, H(57) = 5,
H(20) = 7, H(03) = 3, H(78) = 0, H(31) = 5,
H(15) = 2, H(36) = 10.
(1) 利用线性探查法造表：
0123456789101112
78150357452031233612
(1)(1)(1)(1)(1)(1)(4)(1)(2)(1)
搜索成功的平均搜索长度为
ASLsucc = (1 + 1 + 1 + 1 + 1 + 1 + 4 + 1 + 2 + 1) =
搜索不成功的平均搜索长度为
ASLunsucc = (2 + 1 + 3 + 2 + 1 + 5 + 4 + 3 + 2 + 1 + 5 + 4 + 3) =
(2) 利用双散列法造表：
Hi = (Hi-1 + RH (key)) /% 13, H1 = H (key)
0123456789101112
78150357452031362312
(1)(1)(1)(1)(1)(1)(3)(5)(1)(1)
搜索成功的平均搜索长度为
ASLsucc = (1 + 1 + 1 + 1 + 1 + 1 + 3 + 5 + 1 + 1) =
【答案解析】