首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
已知一个线性表(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
31
问题
已知一个线性表(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
软件设计师上午基础知识考试
软考中级
相关试题推荐
帧中继的地址格式中,表示虚电路标识符的是(15)。
下列关于风险的叙述不正确的是:风险是指______。
关于Windows操作系统中DHCP服务器的租约,下列说法中错误的是________________。
4B/5B编码先将数据按4位分组,将每个分组映射到5单位的代码,然后采用___________进行编码。
决定局域网特性的主要技术要素是网络拓扑、传输介质和__________。
Linux系统中,__________服务的作用与Windows的共享文件服务作用相似,提供基于网络的共享文件/打印服务。(2010年下半年试题)
TCP使用的流量控制协议是_________。
在层次化网络设计中,__________不是分布层/接入层交换机的选型策略。(2009年上半年试题)
阅读以下说明和C语言函数,应填入(n)处。【说明】在一个分布网络中,资源(石油、天然气、电力等)可从生产地送往其他地方。在传输过程中,资源会有损耗。例如,天然气的气压会减少,电压会降低。我们将需要输送的资源信息称为信号。在信号从信源地送往消耗
请认真阅读以下函数说明、图及C程序,将程序段中(1)~(7)空缺处的语句填写完整。[说明]一般的树结构常采用孩子—兄弟表示法表示,即用二叉链表做树的存储结构,链表中节点的两个链域分别指向该节点的第一个孩子节点和下一个兄弟节点。例如,如图1
随机试题
在工程网络计划的执行过程中,如果需要判断某工作进度偏差对总工期是否造成影响,应根据()的差值确定。
2005年,第十届全国人民代表大会第三次会议通过的法律是()
常累及胃肠道,在粘膜下形成多个息肉状结节的淋巴瘤是
5个月婴儿每日所需8%的糖牛奶量为
下列关于建筑面积的计算,说法正确的有()。
分部工程中对工程质量影响大的分项工程应划定为()。
以下关于债券交易场所的说法正确的是()。Ⅰ.交易所市场是由各类社会投资者参与,属于集中撮合交易的零售市场,典型的结算方式是实行净额结算Ⅱ.交易所市场实行两级托管体制,其中,中央结算公司为一级托管人,负责为交易所开立代理总账户,与
汇率直接标价法的特点是:当汇率变动时,()。
阅读下列说明,回答问题1至问题3,将解答填入对应栏内。[说明]某信息系统集成公司(承建方)成功中标当地政府某部门(建设方)办公场所的一项信息系统软件升级改造项目。项目自2月初开始,工期1年。承建方项目经理制定了相应的进度计划,将项目工期分为4个阶
A、Hefellillonthejetplane.B、Hehasbeenworkingtoohard.C、Hewenttobedtoolatelastnight.D、Hehasn’tadaptedtothe
最新回复
(
0
)