首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
采用散列函数H(k)===3 X k MOD 13并用线性探测开放地址法处理冲突,在数列地址空间[0..12]中对关键字序列22,41,53,46,30,13,1,67,51 (1)构造散列表(画示意图); (2)装填因子;
采用散列函数H(k)===3 X k MOD 13并用线性探测开放地址法处理冲突,在数列地址空间[0..12]中对关键字序列22,41,53,46,30,13,1,67,51 (1)构造散列表(画示意图); (2)装填因子;
admin
2013-12-31
48
问题
采用散列函数H(k)===3 X k MOD 13并用线性探测开放地址法处理冲突,在数列地址空间[0..12]中对关键字序列22,41,53,46,30,13,1,67,51
(1)构造散列表(画示意图);
(2)装填因子;
(3)等概率情况下查找成功的平均查找长度;
(4)等概率情况下查找失败的平均查找长度。
选项
答案
(1)各关键字的散列函数值如下表9—3所列: [*] 采用线性探测法再散列法处理冲突,所构造的散列表见表9—4: [*] (2)装填因子=关键字总数/表长=9/13≈0.7。 (3)设查找成功在每个关键字上是等概率的,则查找每个关键字的概率为1/9,各关键字的探查次数见表9—5: [*] 所以有,ASL
succ
=(1+1+1+2+1+2+1+1+1)/9=11/9。 (4)设不成功的查找在每个地址上发生的概率相同,平均概率为1/13,对每个位置不成功查找的探查次数见表9—6: [*] 以散列地址在位置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/2Sxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
试述戊戌变法失败的原因和历史意义。
分析父系氏族公社的经济生活和社会组织。
分析百家争鸣的社会背景及主要原因。
科举是一种读书、应考、任官三位一体的选官方法,其中的进士科始创于()。
西藏自治区的设立时间是()。
为了加强对地方的控制,唐太宗根据山川形势,把全国划分成10个(),经常派官员监察地方官吏。
晚清时期下列武装力量出现的先后顺序是()。
提出电磁感应定律的是物理学家()。
如果互联的局域网高层分别采用TCP/IP协议与SPX/IPX协议,那么我们可以选择的多个网络互联设备应该是()。
42.设有带头结点的循环双链表表示的线性表L=(a1,a2,……,an-1,an)。设计在时间和空间上都尽可能高效的算法,将L改造成L=(a1,a2,……,an,……a4,a2)。要求:(1)给出算法的基本设计思想。(2)根据设计思想,
随机试题
“当某人获取信息后,他或她的认识也随之改变”,这里的信息是作为
IamafraidIcan’t______you______;youwillhavetogotoahotel.
A.息风止痉B.通络止痛C.两者均是D.两者均非全蝎的功效是()
患者,男,67岁。患有咳嗽咳痰病史15年,2天来胸闷症状明显加重,登一层楼或爬缓坡时常出现明显呼吸困难。患者最常见的并发症是
唇裂是由于以下哪两种突起不能联合形成的
(2005年)如图6-4所示,用一附有水压差计的毕托管测定某风道中空气流速。已知压差计的读数△h=185mm,水的密度ρ=1000kg/m3,空气的密度ρa=1.20kg/m3,测得的气流速度u约为()m/s。
M公司拟开发新式制图桌灯,花费3万元聘请一家咨询公司开展项目前期咨询。(1)项目基础数据:项目建设期1年,经营期5年;固定资产年限平均法计提折旧,折旧年限为5年,期未无残值:营业税金及附加为营业收入的1%,贷款年利率8%,M公司的所得税率为25%。(2
塞万提斯
Educationisprimarilytheresponsibilityofthestates.Stateconstitutionssetupcertainstandardsandrulesfortheestablis
Onlyastudentortwo______tocleantheclassroomafterschool.
最新回复
(
0
)