首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
采用散列函数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
40
问题
采用散列函数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://jikaoti.com/ti/lVajFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
利玛窦与李之藻合译的()一书,介绍了西方数学中的算术知识,尤为可贵的是,其传入了中国所没有的西洋笔算法。
在新民主主义革命中,进步势力和革命的主要力量是()。
第三世界所共有的特征及崛起的标志是什么?
在英国革命中,平等派的领导人是()。
论述中国古代历史上北方少数民族南进的周期性原因及其影响。(南开大学2014年中国历史真题)
下列选项中不属于一战所带来的后果的是()。
1949年4月,中国人民解放军发起的重大战役是()。
文艺复兴时期,系统提出了国家主权理论的政治思想家是()。
文艺复兴时期,系统提出了国家主权理论的政治思想家是()。
解析两个战场的地位、作用及相互关系。
随机试题
关于后张法预应力筋的张拉控制,下列说法正确的是()。
除哪项外均为《内经》论病情昼夜变化的原文
工程施工过程中,项目部对施工进度计划应进行定期或不定期审核,目的在于()
某实施施工监理的工程,建设单位按照《建设工程施工合同(示范文本)》与甲施工单位签订了施工总承包合同。合同约定开工日期为2006年3月1日,工期为302d,建设单位负责施工现场外道路开通及设备采购;设备安装工程可以分包;甲施工单位通过筛选与乙施工单位签订了安
()不属于“跳槽热”现象出现的原因。
下列属于道德情感的是()。
结合幼儿园教育实践。试分析:(1)目前幼儿园教育实践中存在着的一些主要问题;(2)由此对教师素养提出的最迫切的要求。
1924年出版了第一本由我国学者编著的《教育心理学》教科书,作者是()。
我国《保险法》将保险公司经营的业务分为()两大类。
S.Koreasubwayarsoninjured______.
最新回复
(
0
)