首页 > 试题广场 >

一个线性序列(30,14,40,63,22,5),假定采用散

[单选题]
一个线性序列(30,14,40,63,22,5),假定采用散列函数Hash(key)=key%7来计算散列地址,将其散列存储在A[0~6]中,采用链地址法解决冲突。若查找每个元素的概率相同,则查找成功的平均查找长度是(      )。
  • 4/3
  • 1
  • 3/2
  • 5/3
不应该选A么?(1*4+2*2)/6
发表于 2019-08-15 17:25:00 回复(4)
不应该是(1x3+2x2+3x1)/6=5/3吗
发表于 2019-08-21 16:45:21 回复(0)
计算哈希地址,如果冲突则加1再取模:
hash(30)= 30 % 7 = 2
hash(14)= 14 % 7 = 0
hash(40)= 40 % 7 = 5
hash(63)= 63 % 7 = 0,与hash(14)冲突,故(0+1)% 7 = 1
hash(22)= 22 % 7 = 1,与hash(63)冲突,故(1+1)% 7 =2;与hash(30)冲突,故(2+1)% 7 = 3
hash(5)= 5 % 7 = 5,与hash(40)冲突,故(5+1)% 7 = 6

构造哈希表:

哈希地址 0 1 2 3 4 5 6
关键字 14 63 30 22
40 5
比较次数 1 2 1 3
1 2

平均查找长度 = (1 + 2 + 1 + 3 + 1 + 2)/ 6 = 5/3

发表于 2020-06-13 12:10:41 回复(1)
牛客就是垃圾!各种题目冲突!
发表于 2019-10-18 10:55:57 回复(0)
查找成功: x/查找的个数 查找失败:x/散列表长度
发表于 2019-09-03 16:25:49 回复(0)

0位 14 63

1位 22

2位 30 5

5位 40


发表于 2019-08-27 14:40:53 回复(0)