首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知一组关键字为(26,36,41,38,44,15,68,12,6,51,25),用链地址法解决冲突。假设装填因子a=0.75,散列函数的形式为H(K)=K MOD P,回答下列问题: (1)构造散列函数; (2)画出散列表; (
已知一组关键字为(26,36,41,38,44,15,68,12,6,51,25),用链地址法解决冲突。假设装填因子a=0.75,散列函数的形式为H(K)=K MOD P,回答下列问题: (1)构造散列函数; (2)画出散列表; (
admin
2013-07-12
39
问题
已知一组关键字为(26,36,41,38,44,15,68,12,6,51,25),用链地址法解决冲突。假设装填因子a=0.75,散列函数的形式为H(K)=K MOD P,回答下列问题:
(1)构造散列函数;
(2)画出散列表;
(3)计算出等概率情况下查找成功的平均查找长度;
(4)计算出等概率情况下查找不成功的平均查找长度。
选项
答案
由a=0.75,得表长m=11/0.75≈15。 (1)在一般情况下,H(K)=K MOD P中,P取质数或者不包含小于20的质因数的和数,因此选择P=13。散列函数H(K)=K MOD13。 (2)散列表: [*] (3)等概率情况下查找成功的平均查找长度:ASI=(1×7+2×2+3×1+4×1)/11=18/11。 (4)等概率情况下查找不成功的平均查找长度:ASI=(1×5+2×1+4×1)/13=11/13。
解析
本题是对散列表的一种常见考查方式,题目的难点是求查找成功和不成功的平均查找长度。用链地址法解决冲突构造散列表,并对查找性能进行分析,具体解题步骤如下。
[归纳总结]散列表的查找效率(比较次数)取决于:散列函数、处理冲突的方法和散列表的装填因子。
当具体给出散列表的长度m、元素个数n,以及散列函数和解决冲突方式后,可以在求出散列表的基础上计算查找成功时的平均查找长度和查找不成功的平均查找长度。
查找成功时的平均查找长度是指查找到表中已有表项的平均探查次数,它是找到表中各个已有表项的探查次数的平均值。而查找不成功的平均查找长度是指在表中查找不到待查的表项,但找到插入位置的平均探查次数,它是表中所有可能散列到的位置上要插入新元素时为找到空位置的探查次数的平均值。
转载请注明原文地址:https://jikaoti.com/ti/v2ajFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
东汉时期,一再削弱地方的军权,强化中央控制下的军队,在下列中央控制的军队中,主要负责保卫京师的是()
1861年俄国废除农奴制改革的主要作用是()。①造成资本的集中②扩大了国内市场③提供了自由劳动力④强化了中央集权
简述近代香港问题的形成。
我国第一部系统的史学理论著作是()。
下列关于柏拉图的叙述不正确的是()。
西汉初年,反驳刘邦“马上治天下”的说法,并向汉帝国治国献策的是()。
系统总结了6世纪以前黄河中下游地区农牧业生产经验的著作是()。
印加人记载事物使用的方法是()。
假设系统的所有资源是同类型的,系统中的进程每次申请资源数最多1个,那么,下面列出的4种情况中,()可能发生死锁。情况序号系统中进程数资源总量
一棵:BS’r树共7个结点,值分别为1、2、3、4、5、6、7,形态为满二叉树,()不是插入序列。
随机试题
下列属于西方国家采用货币政策中介目标的指标有
患者,女,39岁。反复上腹痛伴反酸10年,近来疼痛加剧,服抗酸药等不能缓解。近1周来上腹痛加重,伴呕吐,呕吐量较大,呕吐物带有发酵味。查体:上腹部压痛,有振水音。下列关于该患者的治疗用药,错误的是
高血压病脑出血时,最常见的出血部位是
在一次机关作风检查中,当场发现有四人上班期间在办公室打牌。单独进行身份询问时,戴眼镜的说:“我们都不是该单位的。”年轻的说:“至少有一人是该单位的。”黑脸的说:“我什么都不知道。”穿皮夹克的说:“至少有一人不是该单位的。”经核实,四人中只有一人讲了真话。由
阅读材料,回答问题:材料1对中国来说,1948年,是一个孕育着无限希望的年份。一个独立、统一、民主、自由的新中国。犹如朝阳,即将喷薄。中国向何处去?抗日战争胜利时中国所面临的“两种命运、两种前途”已泾渭分明:一方面,国民党军队已是强弩之末,蒋介石的专
设向量组α1,…,αn为两两正交的非零向量组,证明:α1,…,αn线性无关,举例说明逆命题不成立.
NormanKingUnit502,MazeCentralAlbertRoad,BristolDearMr.King,Youhavemadetherightdecisiontoleada【K4】______lifes
在过去20年中,有这样一种完全向市场经济发展的趋势。这种前景当然意味着政府越少插手越好。
(1)ThismonthSingaporepassedabillthatwouldgivelegalteethtothemoralobligationtosupportone’sparents.CalledtheM
Sportsisoneoftheworld’slargestindustries,andmostathletesareprofessionalswhoarepaidfortheirefforts.Becausean
最新回复
(
0
)