设散列表的长度为 8 ，散列函数 H(k)=k % 7 ，用

[填空题]

设散列表的长度为 8 ，散列函数 H(k)=k % 7 ，用线性探测法解决冲突，则根据一组初始关键字序列 (8 ， 15 ， 16 ， 22 ， 30 ， 32) 构造出的散列表的平均查找长度是 1 。

查看正确选项

sunlight_run

哈希表中元素如图所示：

对于8：8%7=1 一次就能查找到。。。。查找需要比较1次

对于15：15%7=1 因为下标1处已经放了8，所以往后挪1位，将15放在2处。。。查找需要比较2次

对于16：16%7=2 因为下标2处放了15，往后挪1位，将16放在3处。。。。。。。查找需要比较2次

对于22：22%7=1 因为1、2、3处全部放了元素，往后挪3位，放在4处。。。。。查找需比较4次

对于30：30%7=2 因为2，3，4处全部放了元素，往后挪3位，放在5处。。。。。查找需要比较4次

对于32：32%7=4 因为4，5处全部放了元素，往后挪2位，放在6处。。。。。。查找需要比较3次

结果：（1+2+2+4+4+3）/6=8/3

发表于 2017-07-01 15:27:16 回复(1)

EmmaLR

搜索成功的平均搜索长度=1/6 * (1+2+2+4+4+3)=8/3

发表于 2017-05-31 09:53:28 回复(0)

提交观点

问题信息

查找

上传者：阿奻_

难度：

2条回答 29收藏 10045浏览

扫一扫，把题目装进口袋