首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
已知一个线性表(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
44
问题
已知一个线性表(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
软件设计师上午基础知识考试
软考中级
相关试题推荐
在进行域名解析过程中,由______获取的解析结果耗时最短。
在CPU中用于跟踪指令地址的寄存器是______。
开放系统的外挂存储方式不包括__________。
在网络管理中要防止各种安全威胁。在SNMP中,无法预防的安全威胁是__________。(2011年下半年试题)
使用ADSL接入Internet,用户端需要安装________________协议。
无线局域网标准IEEE 802.11i提出了新的TKIP协议来解决(66)中存在的安全隐患。
某主机本地连接属性如下图所示,下列说法中错误的是__________。(2012年下半年试题)
计算机指令一股包括操作码和地址码两部分,为分析执行一条指令,其______。
阅读下列程序说明和C代码,将应填入(n)处。【程序5说明】设M叉树采用列表法表示,即每棵子树对应一个列表,列表的结构为:子树根结点的值部分(设为一个字符)和用“()”括起来的各子树的列表(如有子树的话),各子列表间用“,”分隔。例如下面的
阅读下列函数说明、图和C代码,将应填入(n)处的字句写在答题纸对应栏内。【说明】在进行文法分析的时候,通常需要检测一个单词是否在我们的单词列表里。为了提高查找和定位的速度,通常都要画出与单词列表所对应的单词查找树。程序构造一棵二叉排序树,每个节点存储一
随机试题
手工钨极氩弧焊时,填充焊丝的方法有哪些?各有何特点?
夏季,某奶牛场部分青年牛出现体温升高、精神沉郁、食欲不振、奶产量下降症状;同时患牛眼睛发生羞明、流泪、眼睑痉挛和闭锁、局部增温,并表现出角膜炎和结膜炎症状,多数病牛形成圆锥形角膜。该病的病原是
慢性肾炎的临床表现不包括
房地产经纪执业规范的适用对象是()。[2010年考试真题]
企业风险管理基本框架包括()个方面的内容?
在强势有效市场中,下列描述正确的是()。Ⅰ.任何人都不可能通过对公开或内幕信息的分析获取额外收益Ⅱ.证券价格总是能及时充分地反映所有相关信息Ⅲ.每一位投资者都掌握了有关证券产品的所有公开可得信息Ⅳ.基本面分析是无效的
下面关于证券公司代销金融产品与委托人签署书面代销合同,应约定的是()。I.证券公司对金融产品承担担保责任Ⅱ.因金融产品设计产生的责任由委托人承担Ⅲ.因金融产品设计产生的责任由委托人承担Ⅳ.双方在信息披露、风险
(2017年)关于拉弗曲线的说法,正确的是()。
下列协议中不是电子邮件协议的是()。
Ifthesunhasenough【C1】______towarmandlightthewholeearth,itmusthaveenoughpowertodootherthings,【C2】______.Canw
最新回复
(
0
)