首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知一组关键字为(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
70
问题
已知一组关键字为(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
学硕统考专业
相关试题推荐
下列不属于清统治者加强文化专制和思想控制的是()
以下对于清初恢复发展经济的措施论述正确的一项是()。①停止圈地②“更名田”③奖励垦荒④整顿赋役制度⑤废除匠籍
德国法西斯能够通过合法方式夺取政权,主要原因有()。①垄断资产阶级要求建立极权统治②纳粹党利用了人民对现状的不满③骗人的宣传欺骗了社会的信任④通过国会纵火案打击了共产党
概括指出新民主主义革命各个阶段中国社会的主要矛盾及其表现形式的演变,说明中共根据上述变化对政策的调整及其结果。
我国第一部系统的史学理论著作是()。
最晚到汉武帝时期,出现了我国第一部算学著作(),它记载了用竿标测日影以求日高的方法,从而认识了勾股定理。
洋务运动中翻译出《几何原本》后九卷、《代数学》、《重学》等数学、物理方面的科技书籍的翻译家是()。
继承并发展德谟克利特和伊壁鸠鲁的“原子论”,认为宇宙万物都是由原子构成的,并按照物质本身所特有的规律发展的罗马共和国时期的哲学家()。
—棵二叉树的后序遍历序列为DABEC,中序遍历序列为DFBAC,则先序遍历序列为()。
在二叉树的顺序存储中,每个结点的存储位置与其父结点、左右子树结点的位置都存在一个简单的映射关系,因此可与三叉链表对应。若某二叉树共有n个结点,采用三叉链表存储时,每个结点的数据域需要d个字节,每个指针域占用4个字节,若采用顺序存储,则最后一个结点下标为k(
随机试题
TM公司与HR公司的合作美国HR公司是一个大型家庭装潢用品零售商,在美国18个州经营着200多家仓储式店铺,平均每个店铺面积10万平方英尺,并提供2.5万种不同的商品。其销售明细如下:墙纸和装饰布料50%;装饰辅助品25%;
李商隐《锦瑟》:沧海月明珠有泪,_______。
心肺复苏初期成功后,强化脑复苏治疗,保证平均动脉压在
百日咳咳嗽的特点为
护士为使用双气囊三腔管的患者实施护理措施,正确的是
场景某机电工程安装公司承包本市某化工厂车间的洁净空调工程安装任务。其洁净空调设计等级为N7级,并安装了高效过滤器。为保证工程质量,机电安装公司在风管制作、系统严密性检验、系统调试等关键工作中采取了相应的措施。空调工程在竣工验收后,进行了综合效能测定。由于
一个孩子出现打架行为,因此父母规定他一个月不准吃肯德基,这种做法属于()。
有个学生平时行动迟缓、情绪反应极慢又不表现于外,如果一旦发生情绪反应,却深刻、持久,能体验到别人觉察不出的事件。这位学生的气质类型属于()。
()对于停止相当于回车对于()
某投资者在10月份以80点的权利金(每点10美元,合500美元)买进一张12月份到期、执行价格为9500的道·琼斯指数美式看涨期权,期权标的物是12月到期的道·琼斯指数期货合约。若后来在到期时12月道·琼斯指数期货升至9550点,若该投资者此时决定执行
最新回复
(
0
)