首页 > 试题广场 >

已知一个线性表（38，25，74，63，52，48），假定采

[单选题]
已知一个线性表（38，25，74，63，52，48），假定采用散列函数h（key) = key%7 计算散列地址，并散列存储在散列表A[0....6]中，若采用线性探测方法解决冲突，则在该散列表上进行等概率成功查找的平均查找长度为？ 
  • 1.5
  • 1.7
  • 2.0
  • 2.3
添加回答
推荐
Chaos的Elaine头像 Chaos的Elaine
依次进行取模运算求出哈希地址：

74 应该放在下标为4 的位置，由于25 已经放在这个地方，所以74往后移动，放在了下标 为5的位置上了。 由于是等概率查找，所以结果为：1/6*（1+3+1+1+2+4）= 2.0
编辑于 2015-02-04 21:46:03 回复(6)
菜小豆头像 菜小豆
38%7=3 （第1次出现3，无冲突，放在位置3，查找次数为1）
25%7=4（第1次出现4，无冲突，放在位置4，查找次数为1）
74%7=4（第2次出现4，有冲突，放在位置5，查找次数为2）
63%7=0（第1次出现0，无冲突，放在位置0，查找次数为1）
52%7=3（第2次出现3，有冲突，发现冲突3,4,5，故只能放到6，查找次数为4）
48%7=6 （第1次出现6，有冲突，发现冲突6,1，故只能放到1，查找次数为3）
结果：（1+1+2+1+4+3）÷6=2
编辑于 2015-09-19 22:07:16 回复(7)
ridikuius头像 ridikuius
答案C：
平均查找长度=总的查找次数/元素数
总的查找次数： 38%7=3 （第1次出现3，无冲突，放在位置3，查找次数为1）
25%7=4（第1次出现4，无冲突，放在位置4，查找次数为1）
74%7=4（第2次出现4，有冲突，放在位置5，查找次数为2）
63%7=0（第1次出现0，无冲突，放在位置0，查找次数为1）
52%7=3（第2次出现3，有冲突，发现冲突3,4,5，故只能放到6，查找次数为4）
48%7=6 （第1次出现6，有冲突，发现冲突6,0，故只能放到1，查找次数为3）
1+1+2+1+4+3=12
元素数=6
所以：平均查找长度=12/6=2
编辑于 2016-04-18 09:41:11 回复(2)
斥_斥头像 斥_斥
简单计算，一次插入算1，位置被占往后走一格，直到走到空地，走几步算几 + 1，最后加起来除以数字个数
发表于 2015-07-03 06:41:43 回复(0)
本命年的Offer！头像 本命年的Offer！
查找成功时，分母为哈希表元素个数，查找不成功时，分母为哈希表长度！切记切记！
发表于 2017-10-08 14:47:30 回复(0)
牛客370940号头像 牛客370940号
不会做
发表于 2015-09-18 22:47:51 回复(0)
Yunru头像 Yunru
原来进行hash(key)也算作一次步长呀😂
发表于 2023-09-05 17:26:22 回复(0)
牛客401326037号头像 牛客401326037号
一窍不通，可怜
发表于 2023-03-23 09:09:17 回复(0)
牛客348130649号头像 牛客348130649号
全还给老师了😓，一看解析想起来了
发表于 2022-05-25 02:56:16 回复(0)
张添博头像 张添博
注意若冲突n次 查找次数为（n+1）次
发表于 2022-05-23 17:38:02 回复(0)
牛客803828780号头像 牛客803828780号
38 3 25 4 74 4(放5) 2次 63 0 52 3(放6) 4次 48 6 （放1）3次 总共12次 12/6=2
发表于 2022-01-11 23:01:58 回复(0)
你永远得不到的祖奶奶头像 你永远得不到的祖奶奶
余数是多少一般就放到第几个位置，当余数相同时，也就是发生了冲突，发生了冲突就需要往下找一个空位置来进行放置。
发表于 2020-07-04 11:10:47 回复(0)
houp头像 houp
哪位大佬算一下等概率不成功查找的平均查找长度呗！！我算是（1+2+3+4+5+6+7）/7 但是答案是（1+1+2+3+4+5+6）/7 ，，哪里错拉求解答！！！！
发表于 2019-09-19 15:45:45 回复(2)
LauZyHou头像 LauZyHou
3,4,4->5,0,3->4->5->6,6->0->1

avg=(1+1+2+1+4+3)/6=2.0
发表于 2019-02-18 12:01:36 回复(0)
yzzheng头像 yzzheng
asl成功= 查找次数 / 元素个数
发表于 2018-11-19 18:46:44 回复(0)
sunlight_run头像 sunlight_run
首先取模：

0 1 2 3 4 5 6
%7 63 48
38 25 74 52
查找次数 1 3
1 1 2 4

举一个例子：52！52%7=3，但此时下标3处放了38、往下看下标4处有25、继续往下下标5有74，最后发现下标6处为空，放在此处，查找次数为4
（1+3+1+1+2+4）/6=2
发表于 2017-06-16 15:37:40 回复(1)
清心123头像 清心123
发表于 2017-05-21 16:05:56 回复(0)
公众号:重温新知头像 公众号:重温新知
总的查找次数都算对了，就是败在最后除6和除7上了！
发表于 2017-03-06 20:25:28 回复(0)
阳光依旧smile头像 阳光依旧smile
查找成功的情况是只有这六个数能查找成功 按查找成功的总概率为1则每个查找成功的概率为1/6
发表于 2016-04-18 17:19:41 回复(0)
百度高级测试开发工程师头像 百度高级测试开发工程师
除以的是  元素数 而不是散列表的大小 大爷的
发表于 2016-01-18 15:55:51 回复(0)
提交观点

问题信息

C++工程师 运维工程师 美团 算法工程师 哈希 腾讯 2016 查找 Java工程师
来自：美团2016研发工程师...
难度：
20条回答 27765浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号