首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
已知一个线性表(38,25,74,63,52,48),假定采用散列函数h(key)=key%7计算散列地址,并散列存储在散列表A[0,…,6]中,若采用线性探测方法解决冲突,则在该散列表上进行等概率成功查找的平均查找长度为( )。
已知一个线性表(38,25,74,63,52,48),假定采用散列函数h(key)=key%7计算散列地址,并散列存储在散列表A[0,…,6]中,若采用线性探测方法解决冲突,则在该散列表上进行等概率成功查找的平均查找长度为( )。
admin
2019-06-12
21
问题
已知一个线性表(38,25,74,63,52,48),假定采用散列函数h(key)=key%7计算散列地址,并散列存储在散列表A[0,…,6]中,若采用线性探测方法解决冲突,则在该散列表上进行等概率成功查找的平均查找长度为( )。
选项
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
=(H(key)%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/zbCZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
DNS服务器中提供了多种资源记录,其中__________定义了区域的授权服务器。(2012年下半年试题)
在操作系统文件管理中,通常采用______来组织和管理外存中的信息。
下面关于ManChester编码的叙述中,错误的是______。
若一个项目由9个主要任务构成,其计划图(如下图所示)展示了任务之间的前后关系以及每个任务所需天数,该项目的关键路径是(1),完成项目所需的最短时间是(2)天。(2)
若一个项目由9个主要任务构成,其计划图(如下图所示)展示了任务之间的前后关系以及每个任务所需天数,该项目的关键路径是(1),完成项目所需的最短时间是(2)天。(1)
ATM网是一种高速网技术,其核心技术主要取决于__________技术。
下列选项中,同属于报文摘要算法的是______。
SNMPv2MIB扩展和细化了MIB-II中定义的管理对象,又增加了新的管理对象。扩展和新增的管理对象不包括__________。
多媒体电子出版物创作的主要过程可分为(19)。基于内容检索的体系结构可分为两个子系统:(20)。
传统的数据库基本上是由(38)组成的。(39)在技术和理论上已经成熟,成为当前商用数据库的主流。(40)技术是20世纪80年代中期引入的。目前,多媒体数据库基本上靠与关系模式相结合的(41)来支持。但当数据量大,数据结构复杂时,靠(41)很难适应。当前,在
随机试题
采用下向焊焊接时,可由多个焊工组成连续操作的流水作业班组,它特别适用于球形储罐的焊接施工。
COPD
常见的成果激励主要包括两类:物质激励和_____。
阿托品中毒时,不出现
汗证肺卫不固证,治疗原则是
银柴胡牛膝
甲股份有限公司(以下简称“甲公司”)为增值税一般纳税人,适用的增值税税率为17%。2014年甲公司自行建造一条生产线,相关业务的资料如下:(1)1月10日,购进为生产线准备的一批物资,价款为140万元,增值税税额为23.8万元。该批物资已验收入库;款项以
一个优秀项目团队的形成,一般需要经历5个阶段,按次序分别是(49)。
_____________方法是一种仅有方法头、没有具体方法体和操作实现的方法,该方法必须在抽象类之中定义。
Theprofessorrequeststhatwe______thetermpapersbytheendofthismonth.
最新回复
(
0
)