首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知一组关键字为(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
92
问题
已知一组关键字为(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
学硕统考专业
相关试题推荐
概括指出新民主主义革命各个阶段中国社会的主要矛盾及其表现形式的演变,说明中共根据上述变化对政策的调整及其结果。
1949年4月,中国人民解放军发起的重大战役是()。
1938年,英、法、德、意在德国召开会议讨论对捷克斯洛伐克的苏台德地区的问题,这次会议被称为(),它把英法的绥靖政策推到了顶峰,加速了二战的爆发。
下面条约没有涉及德国的赔款问题的是()。
二战后,美国以经济手段扶植和控制西欧的表现是()。
系统总结了6世纪以前黄河中下游地区农牧业生产经验的著作是()。
1956年,苏共二十大后,匈牙利大党员和群众强烈要求克服个人崇拜,扩大民主,实行经济改革,一些由知识分子、大学生和干部组成的社团组织纷纷成立,其中最有影响者是()。
《马可波罗行纪》中载:“此汗八里大城之周围,约有城市二百,位置远近不等,每城皆有商人来此买卖货物,盖此城为商业繁荣之城也。”“此城”指的是()。
指令系统字长16位,每个地址码为6位,采用扩展操作码的方式,试设计14条二地址指令,100条一地址指令,100条零地址指令。(1)画出操作码的扩展形式。(2)下图为指令译码逻辑图,其中只给出了二地址指令的译码逻辑,试补全一地址指令和零地址指令的
荷兰国旗问题:设有一个仅红、白、蓝三种颜色的条块组成的条块序列,请编写一个时间复杂度为O(n)的算法,使得这些条块按红、白、蓝的顺序排好,即排成荷兰国旗图案。
随机试题
圆柱(Cylinder)体素特征的类型有______和______。
在大陆法系中,代理法的调整范畴为()
某县打算在县中心城区建设一个城市广场,决定做出后,县政府成立了由副县长为组长、15人组成的城市广场建设领导指挥办公室,购置各种办公设备花费20万元。然后开始进行拆迁工作,动用3000万元,安置被迁居民、商户,又请专家进行规划设计,花费了400万元。为了建设
大秦艽汤的配伍特点
局部电位与动作电位相比有何特征。
垂直于水流方向的围堰为()。
作为抵押贷款担保的抵押品可以是股票、债券等有价证券。()
某产品是由5个单元组成的串联系统,若每个单元的可靠度均为0.9,则产品可靠度约为()。
贝卡利亚是意大利著名的刑法学家,他在《论犯罪与刑罚》一书中提出了很多原则,对监狱的改良起到了很大的促进作用。这些原则包括()。
根据《侵权责任法》规定,下列选项中,管理者或组织者不负有安全保障义务的是()。
最新回复
(
0
)