首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
已知一个线性表(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
45
问题
已知一个线性表(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
软件设计师上午基础知识考试
软考中级
相关试题推荐
两个以上的申请人分别就相同内容的计算机程序的发明创造,先后向国务院专利行政部门提出申请,______可以获得专利申请权。
在Windows操作系统中,(37)文件可以帮助域名解析。
关于OSPF协议,下列说法错误的是(23)。
动态划分VLAN的方法中不包括(23)。
TCP/IP网络中的__________实现应答、排序和流控功能。
SNMPv2MIB扩展和细化了MIB-II中定义的管理对象,又增加了新的管理对象。扩展和新增的管理对象不包括__________。
DNS服务器中提供了多种资源记录,其中____________定义了区域的授权服务器。
阅读下列C程序和程序说明,将应填入(n)处的字句写在对应栏内。【说明】本程序从正文文件text.in中读入一篇英文短文,统计该短文中不同单词及出现次数,并按词典编辑顺序将单词及出现次数输出到正文文件word.out中。程序用一棵有序二叉树存
请根据下面叙述的场景选用适当的设计模式。若某面向对象系统中的某些类有且只有一个实例,那么采用(42)设计模式能够有效达到该目的;该系统中的某子模块需要为其他模块提供访问不同数据库系统(Oracle、SQLServer、DB2UDB等)的功能,这些数据库系统
(43)设计模式将抽象部分与它的实现部分相分离,使它们都可以独立地变化。下图为该设计模式的类图,其中,(44)用于定义实现部分的接口。
随机试题
______(Necessary)isthemotherofinvention.Thisisremarkablytrue.
关于肺癌的放射治疗,下列哪项是错误的
肝硬化病人因腹泻发生昏迷。血钾2.5mmol/L,血钠135mmol/L,血氯化物112mmo/L,血氨146.5μmol/L,血pH7.40。选用何种药物为宜
在实际生活中,有些产品的市场价格不能真实反映国民经济对项目的投入和产出,在这种情况下进行经济分析时,必须采用()。
甲公司是乙中央企业在香港设立的全资子公司,是乙企业的重要子公司。根据企业国有资产法律制度的规定,下列情形中,需报国资委审核同意的是()。(2014年)
某钢铁公司2014年7月购进一台铣床并在当月投入使用,取得的增值税专用发票注明价款100万元、税额17万元。同时购进多套备用件。取得的增值税专用发票注明价款2万元,税额0.34万元。公司预计2014—2016年连续亏损。现公司拟对该固定资产进行税收筹划。下
【2014.四川成都】思想品德课是我国德育的主要途径。()
市场失灵
某校以年级为单位,把学生的学习成绩分为优、良、中、差四等。在一学年中,各门考试总分前10%的为优;后30%的为差,其余的为良与中。在上一学年中,高二年级成绩为优的学生多于高一年级成绩为优的学生。如果上述断定为真,则以下哪项一定为真?
Inthepastdecade,newscientificdevelopmentsincommunicationshavechangedthewaymanypeoplegatherinformationaboutpoli
最新回复
(
0
)