首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知一组关键字为(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
93
问题
已知一组关键字为(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://kaotiyun.com/show/Egxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
下列不属于清统治者加强文化专制和思想控制的是()
利玛窦与李之藻合译的()一书,介绍了西方数学中的算术知识,尤为可贵的是,其传入了中国所没有的西洋笔算法。
关于美国内战,不正确的说法是()。
中共十四届六中全会《关于加强社会主义精神文明建设若干重要问题的决议》,强调要()。
论述中国古代历史上北方少数民族南进的周期性原因及其影响。(南开大学2014年中国历史真题)
概述人民公社运动发生的原因、错误、危害及主要教训。
下列对凡尔赛和约中有关德国疆界问题的表述,正确是()。
蒙古军西征之后,罗斯处于()的控制之下。
阅读下列史料,并回答问题:在琶勒尼斯(注:地名)一役获胜后,他(庇西特拉图)便占领政府,并解除人民武装;现在他已能稳定地握住僭主政权,并且取得那克索斯。以吕格达密斯为统治者。他解除人民武装的方法是这样的:他在塞修斯庙举行了一个武装的阅兵式,同时举行一次民
某计算机采用微程序控制方式,微指令字长32位,采用字段直接编码的控制方式,共有55个微命令,可分为6个互斥组,分别包含1、3、7、8、12、24个微命令。另外,该机共有5个可判定的外部条件,采用断定方式形成后续微指令地址。(1)设计该机微指令的格式,
随机试题
麻花钻刃磨时,只要两条主切削刃长度相等就行。()
导致肾动脉狭窄的病因是
有关X线胶片卤化银颗粒的叙述,错误的是
()负责非煤矿矿山企业和危险化学品、烟花爆竹生产企业安全生产许可证的颁发和管理。
下列各项中,属于证券经纪商与投资者签订的《证券交易委托代理协议》内容的是()。Ⅰ.网上委托Ⅱ.违约责任和免责条款Ⅲ.投资范围和投资限制Ⅳ.变更和撤销
速动比率较高,()。
S公司为高新技术企业,有A、B、C三个资产组,每个资产组负责不同的项目,能够产生独立的现金流。假定S公司的全部资产均为固定资产,由于行业竞争激烈,技术更新速度快,2020年末S公司部分资产出现减值迹象,相关资料如下:(1)A资产组为一条完整的生产线,主要
以下几个文件中,使用了无损压缩技术的是()。
秀才参加乡试合格者才有资格参加会试,那么会试考中者称为()
根据地中海及其沿岸地区知识,回答问题。地中海气候的特征是()。
最新回复
(
0
)