首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
采用散列函数H(k)=3×k MOD 13并用线性探测开放地址法处理冲突,在数列地址空间[0..12]中对关键字序列22,41,53,46,30,13,1,67,51; (1)构造散列表(画示意图); (2)装填因子; (3)等概率
采用散列函数H(k)=3×k MOD 13并用线性探测开放地址法处理冲突,在数列地址空间[0..12]中对关键字序列22,41,53,46,30,13,1,67,51; (1)构造散列表(画示意图); (2)装填因子; (3)等概率
admin
2013-07-12
32
问题
采用散列函数H(k)=3×k MOD 13并用线性探测开放地址法处理冲突,在数列地址空间[0..12]中对关键字序列22,41,53,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/yrxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
光绪元年七月,清政府迫于()强烈要求派一位使臣到其国,()成为中国第一个驻外公使
布雷顿森林体系的建立对世界历史产生的重大影响是()。
我国第一部系统的史学理论著作是()。
元封六年(前105),西汉以宗室女细君与乌孙王和亲。细君死后,又以宗室女()和亲,巩固了汉与乌孙的关系,使乌孙成为牵制匈奴的重要力量。
清初设置的两个“办事大臣”是()。①宁古塔②西宁③库伦④西藏
建立中国道教史上第一个成熟的神仙系统的是()。
元代对边疆地区的统治方式不同于其他三地的一地是()。
简述当代科学技术革命兴起的背景、特点及影响。
【《周礼》】中国人民大学2006年中国古代史真题;中山大学2013年历史学基础(A)真题;西北民族大学2017年中国史综合真题
(将关键字序列(7、8、30、11、18、9、14)散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组,散列函数为H(key)=(keyx3)MOD7,处理冲突采用线性探测再散列法,要求装填(载)因子为0.7。请画出所构造的散列表。
随机试题
在职业病的危害防治和职业人群健康监护中,不属于第一级预防的措施是
远处物体平行光线聚焦于视网膜之前是()
肠内营养制剂可用于防治肝性脑病的特殊配方制剂是
A.正胜邪退B.邪去正虚C.邪盛正虚D.邪正相持E.心虚邪恋
结算所实行无负债的每日结算制度,又称为“逐日盯市制度”。()
“关山万里残霄梦,犹听江东战鼓声。”中华民族伟大复兴这一梦想,______了几代中国人的夙愿。填入画横线部分最恰当的一项是:
“外行看热闹,内行看门道”体现了知觉的()
平均利润率形成的过程,同时就是()
西周末年思想家史伯说“和实生物,同则不继。以它平它谓之和,故能丰长而物归之”。这里所包含的辩证法思想有()
CMM模型将软件过程的成熟度分为5个等级。在(21)使用定量分析来不断地改进和管理软件过程。
最新回复
(
0
)