首页
题库
面试
求职
学习
竞赛
More+
所有博客
搜索面经/职位/试题/公司
搜索
我要招人
去企业版
登录 / 注册
首页
>
试题广场
>
设哈希表长 M=14,哈希函数 H(key)=key mod
[单选题]
设哈希表长 M=14,哈希函数 H(key)=key mod 11,表中已有 4 个元素,其关键字分别是 4、27、61、84,如果用二次探测再散列处理冲突,关键字为 49 的结点的地址是( )
9
8
3
2
添加笔记
求解答(3)
邀请回答
收藏(10)
分享
纠错
4个回答
添加回答
2
聆歌59
初始用4mod11=4,27mod11=5,61mod11=6,84mod11=7,所以哈希表目前的状态是:
4 5 6 7
4 27 61 84
二次探测再散列,又叫平方探测再散列。例如所给值49mod11=5,现在5的位置上已有值,所以查找5+1^2=6的位置,6也有值,查找
5-1^2=4的位置,4有值,查找
5+2^2=9的位置,9为空,所以49放置在9的位置上
如果9不为空,则查找依次查找如下位置:5-2^2,5+3^2...
发表于 2018-12-09 15:04:27
回复(1)
1
牛客882122502号
得到的哈希表:
4个元素只探测了一次,最后插入的49探测了4次
49%11=5,冲突
(5+1)%14=6,冲突
(5-1)%14=4,冲突
(5+4)%14=9,成功插入
其中有9个地址对应数据为空,只需比较一次;
地址4处查找3次,(4,5,3)
地址5处查找5次,(5,6,4,9,1)
地址6处查找4次,(6,7,5,10)
地址7处查找2次,(7,8)
地址9处查找2次,(9,10)
编辑于 2021-04-06 23:46:54
回复(0)
0
天尊墨宇
选A
发表于 2020-07-15 11:15:46
回复(0)
0
一个晗子
查找成功的平均查找长度ASL=(1+1+1+1+4)/5=1.6
解析:4、27、61、84的比较次数都为1次,(4个数字地址都不冲突,所以每个数字都只比较1次)
49一共比较4次(地址5、6、4、9共4次)
查找失败的平均查找长度ASL=3
首先表长为14.地址为0-13
0-2都为空,所以失败次数共为3次
从3开始到下次为空查找失败的比较次数为(3一次,4一次,5一次,6一次,7一次、8一次,9一次,10一次,10地址为空失败,停止)共8次
从4开始到下次为空查找失败的比较次数为(4一次、5一次、6一次、7一次、8一次、9一次、10一次)共7次
同理从5开始(5,6,7,8,9,10)共6次
6(678910)5次
7(78910)4次
8 3次
9 2次
10-13都为1次,共4次
所以查找失败的ASL=(3+8+7+6+5+4+3+2+4)/14(14个地址)=3
如有错误请指正!虚心学习
发表于 2019-11-12 22:51:41
回复(0)
这道题你会答吗?花几分钟告诉大家答案吧!
提交观点
问题信息
哈希
上传者:
zsw3
难度:
4条回答
10收藏
10483浏览
热门推荐
相关试题
数据链路层滑动窗口机制中发送窗口(...
网络基础
评论
(1)
供受文者使用的具有法定效用的正式文...
京东
产品运营
2018
常识判断
行政
评论
(1)
有关linux线程的描述,正确的是...
京东
Java工程师
C++工程师
iOS工程师
安卓工程师
运维工程师
前端工程师
算法工程师
PHP工程师
2018
评论
(1)
用一种动物介绍你自己
通用能力
评论
(1)
请你说几个海量数据存储常见问题以及...
评论
(1)
扫描二维码,关注牛客网
意见反馈
下载牛客APP,随时随地刷题