首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
已知一个线性表(38,25,74,63,52,48),假定采用散列函数h(key)=key%7计算散列地址,并散列存储在散列表A[0,…,6]中,若采用线性探测方法解决冲突,则在该散列表上进行等概率成功查找的平均查找长度为(27)。
已知一个线性表(38,25,74,63,52,48),假定采用散列函数h(key)=key%7计算散列地址,并散列存储在散列表A[0,…,6]中,若采用线性探测方法解决冲突,则在该散列表上进行等概率成功查找的平均查找长度为(27)。
admin
2019-06-12
61
问题
已知一个线性表(38,25,74,63,52,48),假定采用散列函数h(key)=key%7计算散列地址,并散列存储在散列表A[0,…,6]中,若采用线性探测方法解决冲突,则在该散列表上进行等概率成功查找的平均查找长度为(27)。
选项
A、1.5
B、1.7
C、2.0
D、2.3
答案
C
解析
要计算散列表上的平均查找长度,首先必须知道在建立这个散列表时,每个数据存储时进行了几次散列。这样就知道哪一个元素的查找长度是多少。散列表的填表过程如下:
首先存入第1个元素38,由于h(38)=38%7=3,又因为3号单元现在没有数据,所以把38存入3号单元,如图1-7所示。
接着存入第2个元素25,由于h(25)=25%7=4,又因为4号单元现在没有数据,所以把25存入4号单元,如图1-8所示。
接着存入第3个元素74,由于h(74)=74%7=4,此时的4号单元已经被25占据,所以进行线性再散列,线性再散列的公式为:H
i
=(key)+d
i
)%m,其中的d
i
=1,2,3, 4,…,所以H
1
=(4+1)%7=5,此时的单元5没有存数据,所以把74存入到5号单元,如图1-9所示。
接着存入第4个元素63,由于h(63)=63.%7=0,此时的0号单元没有数据,所以把63存入0号单元,如图1-10所示。
接着存入第5个元素52,由于h(52)=52%7=3,此时的3号单元已被38占据,所以进行线性再散列H
1
=(3+1)%7=4,但4号单元也被占据了,所以再次散列H
2
=(3+2)%7=5,但5号单元也被占据了,所以再次散列H
3
=(3+3)%7=6,6号单元为空,所以把52存入6号单元,如图1-11所示。
最后存入第6个元素48,由于h(48)=48%7=6,此时的6号单元已被占据,所以进行线性再散列H
1
=(6+1)%7=0,但0号单元也被占据了,所以再次散列H
2
=(6+2)%7=1,1号单元为空,所以把48存入1号单元,如图1-12所示。
如果一个元素存入时,进行了N次散列,相应的查找次数也是N,所以38,25,63这三个元素的查找长度为1,74的查找长度为2,48的查找长度为3,52的查找长度为4。平均查找长度为(1+1+1+2+3+4)/6=2。
转载请注明原文地址:https://kaotiyun.com/show/5zCZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
下列关于Microsoft管理控制台(MMC)的说法中,错误的是__________。(2009年下半年试题)
在下面关于VLAN的描述中,不正确的是(55)。
在Windows环境下,DHCP客户端可以使用__________命令重新获得IP地址,这时客户机向DHCP服务器发送一个dhcpdiscover数据包来请求重新租用IP地址。(2012年下半年试题)
当DHCP服务器拒绝客户端的IP地址请求时发送____________报文。
在冗余磁盘阵列中,以下不具有容错技术的是(62)________________。
管理站用SetRequest在RMON表中产生一个新行,如果新行的索引值与表中其他行的索引值不冲突,则代理产生一个新行,其状态对象的值为(47)。
按照美国制定的光纤通信标准SONET,OC-48的线路速率是(11)Mb/s。
ZigBee网络是IEEE802.15.4定义的低速无线个人网,其中包含全功能和简单功能两类设备,下面关于这两类设备的描述中错误的是()。
阅读下列说明和图,回答问题1至问题4,将解答填入答题纸的对应栏内。【说明】某会议中心提供举办会议的场地设施和各种设备,供公司与各类组织机构租用。场地包括一个大型报告厅、一个小型报告厅以及诸多会议室。这些报告厅和会议室可提供的设备有投影仪、白板、视频播放
CDMA系统中使用的多路复用技术是(62)。我国自行研制的移动通信3G标准是(63)。
随机试题
简述共同犯罪人的分类。
患者慢性肾炎病史4年。现症见面浮肢肿,面色萎黄,少气无力,易感冒,腰脊酸痛。舌淡,苔白润,脉细弱。实验室检查:尿常规尿蛋白(++),镜检可见颗粒管型。治疗应首选
某公司于1994年11月以出让方式取得一面积为500m2的地块,具有50年的土地使用权,并于1995年11月建成一建筑面积为450m2的建筑物,建筑物全部出租。已知当地同类建筑物出租租金一般每月为30元/建筑mm2,每年支付的土地税及房产税为20元/建筑
设计有围护结构的深基础架空层层高在()及以上的部位应计算全面积。
某水利枢纽工程由电站、溢洪道和土坝组成。主坝为均质土坝,上游设干砌石护坡,下游设草皮护坡和堆石排水体,坝顶设碎石路,工程实施过程中发生下述事件:事件1:项目法人委托该工程质量监督机构对于大坝填筑按《水利水电基本建设工程单元工程质量评定标准》规定的
某建筑高度为42m的玩具厂,地上10层,耐火等级为一级,每层建筑面积为6000m2,设有消防电梯,且消防电梯与疏散楼梯间合用前室。下列做法中正确的是()。
订立集体合同应当遵循的原则包括()
依我国继承法,关于遗嘱继承与法定继承的关系,正确的选项是()
For:【L5】______Blake.From:【L6】______Anderson.Tomorrow’s【L7】______iscancelled.Helen’stelephonenumber:【L8】______.【L6】
【46】Teaisakindofdrinkmadebypouringboilingwaterontoprocessedteatreeleaves.Chinawasthefirstcountrytoproduce
最新回复
(
0
)