首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
采用散列函数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
47
问题
采用散列函数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
学硕统考专业
相关试题推荐
二战中,德国制定的“绿色方案”侵略计划针对的国家是()。
1868年,擅自代表清政府与美国政府签订《中美续增新约》,承认美国享有掠夺华工以及在中国各通商口岸设立学校的特权的外国人是()。
从鸦片战争的过程和结局可以看出,()是决定战争胜败的关键。
租庸调制对农业生产的最大作用是()。
近现代以来,国际关系中先后出现了维也纳体系、凡尔赛一华盛顿体系和雅尔塔体系。关于这三个体系共同点的表述不正确的是()。
在西北地区,西北野战军采取了蘑菇战术与敌人周旋,这实际上是()。
在一个长度为n(n>1)的带头结点的单链表h上,设有尾指针r(指向尾结点),则执行()操作与链表的长度有关。
一棵:BS’r树共7个结点,值分别为1、2、3、4、5、6、7,形态为满二叉树,()不是插入序列。
某机字长32位,总线数据线宽度是16位,一个总线周期占用4个时钟周期,总线时钟频率为10MHz,则总线带宽是()。
给定单链表的结点结构typedefstructnode*link;structnode{intitem,linknext;);将两个升序单链表归并为一个升序单链表。
随机试题
子宫内膜癌当侵犯宫颈管时,其淋巴引流与哪种肿瘤相似
下列选项中,关于补钾原则的说法,正确的是
A.谷类B.矿物质C.蔬菜、水果D.脂肪E.豆类及豆制品
A.呼吸困难B.呕吐C.腰痛D.肌肉震颤E.腹泻属循环系统疾病问诊内容的是()
某蒸汽压缩机制冷理论循环的冷凝温度tk=30℃,蒸发温度t0=-15℃,若已知制冷量为q0=16.4kW,其热力完善度η=0.8,则冷凝负荷为()。
在总结某知名企业集团破产的过程中,人们发现如下情况。资料一:为了满足公司大规模扩张的需要、把资金从上市公司转移出来,集团采取以上市公司存款为大股东贷款担保的方式“套钱”。在难以得到上市公司过半数董事同意的情况下,集团制造虚假的上市公司董事会决议:一是未经授
()是国务院统筹协调金融稳定和改革发展重大问题的议事协调机构。
下列各句中没有语病的一句是( )。
增加派生性冗余列的调优方法是典型的以【10】换时间的调优方法。
Thebell______.Pleaseopenthedoor,Jim.
最新回复
(
0
)