首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
采用散列函数H(k)=3×k MOD 13并用线性探测开放地址法处理冲突,在数列地址空间[0..12]中对关键字序列22,41,5 3,46,30,13,1,67,51; (1)构造散列表(画示意图); (2)装填因子; (3)等概
采用散列函数H(k)=3×k MOD 13并用线性探测开放地址法处理冲突,在数列地址空间[0..12]中对关键字序列22,41,5 3,46,30,13,1,67,51; (1)构造散列表(画示意图); (2)装填因子; (3)等概
admin
2012-06-26
140
问题
采用散列函数H(k)=3×k MOD 13并用线性探测开放地址法处理冲突,在数列地址空间[0..12]中对关键字序列22,41,5 3,46,30,13,1,67,51;
(1)构造散列表(画示意图);
(2)装填因子;
(3)等概率情况下查找成功的平均查找长度;
(4)等概率情况下查找失败的平均查找长度。
选项
答案
(1)各关键字的散列函数值如下: [*] 采用线性探测法再散列法处理冲突,所构造的散列表为: [*] (2)装填因子一关键字总数/表长一9/13≈0.7。 (3)设查找成功在每个关键字上是等概率的,则查找每个关键字的概率为1/9,各关键字的探查次数分别为: [*] 所以有,ASL
SUCC
=(1+1+1+2+1+2+1+1+1)/9=11/9。 (4)设不成功的查找在每个地址上发生的概率相同,平均概率为1/13,对每个位置不成功查找的探查次数分别为: [*] 以散列地址在位置2的关键字为例,由于此处关键字为空,只需比较1次就可确定本次查找不成功;以散列地址在位置3的关键字为例,若该关键字不在散列表中,需要将它与从位置3开始向后直至位置5的关键字相比较,由于关键字5的关键字为空,所以不再向后比较,共比较3次,其他的类推得到。 所以有,ASL
unSUCC
=(3+2+1+3+2+1+4+3+2+1+2+1+4)/13=29/13。
解析
用线性探测法解决冲突构造散列表,并对查找性能进行分析,具体解题步骤如下。
转载请注明原文地址:https://kaotiyun.com/show/oyxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
春秋后期的()用望、闻、问、切的方法诊断病人。
“二战期间,美国研制了原子弹并用于实践;1946年美国投入的第一台电子计算机最初是用于计算炮弹弹道;德国人研制成功的远程液体火箭是用于空袭英国的。”以上史实说明()。
近代中国第一个系统介绍西方思想与文化名著的翻译家和启蒙思想家是()。
阅读下列材料,回答问题:材料一:列宁说:“我们在夺取政权时便知道,不存在将资本主义制度具体改造成社会主义制度的现存方法……我不知道哪位社会主义者处理过这类问题……我们必须根据实践作出判断。”——摘自《苏联
到1869年为止,人类已发现了多少种化学元素()。
(1)以太网采用了曼彻斯特编码,一个比特的数据需要两个信号来传输,那么为了达到100Mbps的数据传送速率,需要线路达到200Mbps的带宽。(2)以太网的最小帧长度是64字节,那么发送一个最小帧需要的时间T1=64×8/(100×106),
如下图所示为一个网络连接的示意图,主机1到主机2采用了SLIP网络连接,SLIP网络可以传输的最大数据段是296字节,主机2和主机3使用了以太网连接。请问:(1)为了使IP不分片,主机1可以在TCP包中承载多少数据?(2)主机3可以在TCP包中承载多
一组记录的关键字为{25,50,15,35,80,85,20,40,36,70),其中含有5个长度为2的有序表,用归并排序方法对该序列进行一趟归并后的结果是()。
A、1243B、4312C、2134D、3214D图的BFS遍历。D选项,首先访问结点3,与3邻接的结点4、2都未曾访问过,故3后面因该为2、4(或4、2),故D错。
高度为7的AVL树最少有()个结点。
随机试题
(63)Iflanguagewerefornothingbutthecommunicationofwarningsandweatherreports,anartificialinternationallanguagewo
在Access中,每个日期/时间字段需要【】空间来存储。
目前,放射免疫技术测定在下列选项中使用较少的是:()
慢性胃溃疡最常见的并发症是
关于要约邀请说法不正确的是()。
下列关于短波的说法,正确的有()。
1.背景某政府机关新建高层办公大楼幕墙工程公开招标,有6家具有建筑幕墙施工资质的企业参加投标。开标后,招标人按照法定程序组织评标委员会进行评标,评标的标准和方法在开标会议上公布,并作为《招标文件》附件发送给各投标人。评标委员会在对各投标人的资信、商务、技
我国商业银行的累积外汇敞口头寸比例一般不应高于()。
2016年5月,甲公司将一厂房出租给乙公司,月租金为3万元,租期为5年。租赁合同签订前,甲公司书面告知乙公司该厂房已为丙银行设定抵押权,用以担保甲公司向丙银行的借款本金1000万元及其利息。2018年6月,甲公司不能履行对丙银行的到期借款债务,致使厂房被人
注意可分为()。
最新回复
(
0
)