首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
已知一个线性表(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
55
问题
已知一个线性表(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
软件设计师上午基础知识考试
软考中级
相关试题推荐
以太网的数据帧封装如下图所示,包含在TCP段中的数据部分最长应该是(18)字节。
电子商务交易必须具备抗抵赖性,目的在于防止(19)。
以下关于域名查询的叙述中,正确的是__________。
OSPF网络可以划分成多个区域(area),下面对于区域的描述中错误的是____________。
4.某计算机系统由下图所示的部件构成,假定每个部件的千小时可靠度都为R,则该系统的干小时可靠度为______。
假设网络的生产管理系统采用B/S工作方式,经常上网的用户数为100个,每个用户每分钟平均产生11个事务,平均事务量大小为0.06MB,则这个系统需要的信息传输速率为(34)。
利用报文摘要算法生成报文摘要的目的是__________。(2013年上半年试题)
SHA-1是一种将不同长度的输入信息转换成__________位固定长度摘要的算法。
若这三个事务允许并行执行,则请列举出有多少可能的正确结果。各个事务的内部结构如下所示。若事务不施加任何锁,则有多少可能的调度。T1:R1(GetAintot1;t1:=t1+1);U1(UpdateAfromt1);
阅读以下说明和VisualBasic码,将应填入(n)处的字名写在的对应栏内[说明]编写一工资调整程序。若基本工资大于等于800元,工资增加20%,若小于800元大于600元,则工资增加15%,若小于600元则工资增加10%。要求在文本框Tex
随机试题
个人词库是为了减少系统词库中的词而专门设置的。
甲犯某罪,应处3年以上7年以下有期徒刑,对甲的追诉时效是()
在下列哪种波长处测定DNA吸光值的变化可作为监测DNA是否发生变性的指标
消渴病并发白内障、耳聋、雀盲,治疗首选
(2009)古希腊建筑形成的柱式有()。
利用5年期政府债券的空头头寸为10年期政府债券的多头头寸进行保值。当收益率曲线变陡时,10年期政府债券多头头寸的经济价值会()。
实现抵押权、获得清偿的方式有()
设函数f(x)在区间[0,+∞)上连续可导,f(0)=1,且对任意t>0,曲线y=f(x)与直线x=0,x=t,y=0所围图形的面积与曲线y=f(x)在[0,t]上的一段弧长相等,求f(x).
在数据库管理技术的发展中,数据独立性最高的是()。
下列描述中正确的是
最新回复
(
0
)