首页 > 试题广场 >

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

[填空题]
设散列表的长度为 8 ,散列函数 H(k)=k % 7 ,用线性探测法解决冲突,则根据一组初始关键字序列 (8 15 16 22 30 32) 构造出的散列表的平均查找长度是 1
哈希表中元素如图所示:
对于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 回复(0)
搜索成功的平均搜索长度=1/6 * (1+2+2+4+4+3)=8/3
发表于 2017-05-31 09:53:28 回复(0)