将关键字序列 (7 、 8 、 30 、 11 、 18 、 9 、 14) 散列存储到散列表中

将关键字序列 (7 、 8 、 30 、 11 、 18 、 9 、 14) 散列存储到散列表中，散列表的存储空间是一个下标从 0 开始的一个一维数组，散列函数为： H(key)=(key x 3) MOD T ，处理冲突采用线性探测再散列法，要求装载因子为 0.7 。问题： (1) 请画出所构造的散列表； (2) 计算等概率情况下，查找成功的平均查找长度ASL。

还没有评论

举报纠错

切换

1 个答案

(1) 因为装填因子为 0.7 ，数据总数为 7 ，所以存储空间长度为 L = 7/0.7 = 10 因此可选 T=10 ，构造的散列函数为 H(key) = (key*3) MOD 10 线性探测再散列函数为： Hi = ( H(key)+ di ) MOD 10 , (di = 1,2,3...9) 因此，各数据的下标为 H(7) = (7*3) MOD 10 = 1 H(8) = (8*3) MOD 10 = 4 H(30) = (30*3) MOD 10 = 0 H(11) = (11*3) MOD 10 = 3 H(18) = (18*3) MOD 10 = 4 H1 = ( H(18) +1) MOD 10 = 5 H(9) = (9*3) MOD 10 = 7 H(14) = (14*3) MOD 10 = 2 所构造的散列表如下： 0 1 2 3 4 5 6 7 8 9 30 7 14 11 8 18 9 (2) 查找成功的平均查找长度为： ASL1 = (1+1+1+1+2+1+1)/7 = 8/7

还没有评论

切换

撰写答案

扫描后移动端查看本题

我也分享一个题目