首页 > 试题广场 >

设散列表的长度为10,散列函数H(n)=n mod 7,初始

[单选题]

设散列表的长度为10,散列函数H(n)=n mod 7,初始关键字序列为 (33,24,8,17,21,10),用链地址法作为解决冲突的方法,平均查找长度是()

  • 1
  • 1.5
  • 2
  • 2.5
链地址法,将所有具有相同哈希地址的而不同关键字的数据元素连接到同一个单链表中
33%7=5 24%7=3 8%7=1 17%7=3 放在24后面(24->17)21%7=0 10%7=3放在17后面(24->17->10)
(1+1+1+2+1+3)/6=1.5
发表于 2018-09-04 09:41:31 回复(3)
发表于 2019-08-08 16:10:03 回复(0)

(1×4+1×2+1×3)/6=1.5

发表于 2018-08-20 16:43:53 回复(0)
链地址法解决冲突
简单来说,就是把每一个关键字作为一个链表头(head),依次存放冲突的元素
33 mod 7 = 5
24 mod 7 = 3
8   mod 7 = 1
17 mod 7 = 3
21 mod 7 = 0
10 mod 7 = 3
查询次数依次为 1 1 1 2 1 3
平均次数为 (1+1+1+2+1+3)/ 6 = 1.5
发表于 2019-09-12 19:24:47 回复(0)
33%7=5 24%7=3 8%7=1 17%7=3 (17+1)%7=4 21%7=0 10%7=3 (10+1)%7=4 (10+1+1)%7=5 (10+1+1+1)%7=6 不应该是4*1+1*4+1*2吗 10/6吗 不应该1.5啊
发表于 2018-08-24 12:23:31 回复(1)
33%7=5
24%7=3
8%7=1
17%7=3
因为又出现了一个3,所以冲突了,找17就先找24 ,所以是2次
21%7=0
10%7=3
因为又出现了一个3,所以冲突了,找10就要找17再找24 ,所以是3次
(1+1+1+2+1+3)/6=1.5
发表于 2019-01-08 17:07:20 回复(2)
5 3 1 3 0 3   
5 1 0 3 3 3 
1 +1 +1 +1 + 2 + 3 = 9 
9/6 = 1/5
发表于 2019-10-22 09:34:06 回复(0)
我还是没有明白,哪位大佬解答下,1.5怎么算出来的
发表于 2019-10-17 20:30:50 回复(0)
平均查找长度1.5,平均查找次数1.
发表于 2019-10-10 10:04:31 回复(0)
链地址的公式 1+x/2;
线性探测法:(1+1/(1-x))/2
发表于 2018-08-09 21:10:47 回复(0)