首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
已知一个线性表(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
80
问题
已知一个线性表(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
软件设计师上午基础知识考试
软考中级
相关试题推荐
下面的选项中属于链路状态路由选择协议的是__________。
某企业有生产部和销售部,生产部负责生产产品并送人仓库,销售部从仓库取出产品销售。假设仓库可存放n件产品。用PV操作实现它们之间的同步过程如下图所示。图中信号量S1和S2为同步信号量,初值分别为n和0;S是一个互斥信号量,初值为______
按照RSA算法,若选两奇数p=5,q=3,公钥e=7,则私钥d为__________。(2010年下半年试题)
在建立TCP连接过程中,出现错误连接时,__________标志字段置“1”。
路由器收到一个数据报文,其目标地址为20.112.17.12,该地址属于()子网。
在快速以太网物理层标准中,使用两对五类无屏蔽双绞线的是__________。(2009年上半年试题)
以下关于程序设计语言的叙述中,错误的是_____________。
数据流图(DFD)对系统的功能和功能之间的数据流进行建模,其中顶层数据流图描述了系统的__________。(2012年上半年试题)
计算机感染特洛伊木马后的典型现象是__________。(2008年下半年试题)
若浮点数的阶码用移码表示,尾数用补码表示。两规格化浮点数相乘,最后对结果规格化时,右规的右移位数最多为(2)位。
随机试题
WhileinLondon,wepaidavisittothehospitalfounded________thenurseFlorenceNightingale.
中和试验是利用下列哪一种原理建立起来的鉴定病毒和测定中和抗体的经典实验
A.养心B.渗湿C.温胃D.益阴E.温阳参苓白术散除益气健脾、止泻外,还具有的功用是
下列关于直肠吸收的影响因素叙述正确的是()
2011年7月11日,A市升湖区法院受理了黎明丽(女)诉张成功(男)离婚案。7月13日,升湖区法院向张成功送达了起诉状副本。7月18日,张成功向升湖区法院提交了答辩状,未对案件的管辖权提出异议。8月2日,张成功向升湖区法院提出管辖权异议申请,称其与黎明丽已
根据施工合同示范文本规定,承包人应在( )之后28天内,向发包人递交竣工结算报告及完整的结算资料。
根据《公司法》的规定,下列有关股份有限公司股份转让限制的表述中,错误的是()。
下列食物中,属于油脂类坚果的有()。
数据报选项和填充域使得IP数据报的头部长度是
Whomostlikelyisthetalkintendedfor?
最新回复
(
0
)