首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
采用散列函数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
78
问题
采用散列函数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
学硕统考专业
相关试题推荐
最先把生产资料由国家所有制改为社会所有制的是()
“时方镇缺守帅,稍命文臣权之……又置转运使、通判,为之条禁,文薄渐为精密,由是利归公上而外权削矣。”这段文字反映出北宋初期加强地方控制的基本理念是()。
二战期间,下列四次战役的时间先后顺序是()①莫斯科战役②诺曼底登陆③不列颠之战④阿拉曼战役
十六国时期的历史,可以划分为前后两个时期,其分界线是()。
试述中国共产党诞生的历史条件和意义。
十六国时期的历史,可以划分为前后两个时期,其分界线是()。
1948年,南斯拉夫对从苏联照搬来的“行政命令式的国家集权式”体制进行改革逐步形成有自己特色的建设社会主义的理论和方法,其核心是()。
解放军渡江战役中横渡长江的东西两个攻击点是()。
在西北地区,西北野战军采取了蘑菇战术与敌人周旋,这实际上是()。
詹天佑自主设计修建了中国第一条铁路是在()。
随机试题
A.齿状线B.刍线C.肛窦D.痔环E.直肠横襞皮肤和黏膜的分界线是
易袭阳位,具有升发向上特性的邪气是
下列选项中,与所给立体图形相同的是:
我们常用的AutoCAD软件,就其应用领域而言属于_________应用。
鼠疫的主要传播媒介是
A公司的甲产品5月份发生的生产费用为10万元,甲产品5月份的完工产品成本也是10万元,则下列各项有关分析结论正确的有()。
Theygotallthepackages__________ontime.
李老师在校内开了一个超市,学生张某喝了该超市所售卖的过期的饮料,腹泻不止,在此事件中应当承担责任的是()。
1927年大革命失败后,党的工作重心
下列有关过程的叙述中错误的是()。
最新回复
(
0
)