首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知一组关键字为(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
47
问题
已知一组关键字为(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
学硕统考专业
相关试题推荐
马克思指出:“鸦片不曾产生催眠的作用,而倒产生了惊醒作用,历史的发展好像首先要麻醉这个国家的人民,然后才可能把他们从历来的麻木状态唤醒似的。”这里所说的“唤醒”的意思是()。
法国大革命中,颁布全面限价法案的政治派别是
简述自由民权运动及其历史作用。(南京大学2013年历史学基础(世界史)真题)
简述第二国际建立的历史条件。
系统阐明社会主义初级阶段理论是在()。
抗日战争期间,日本将沦陷区的许多矿产业、钢铁业等交给日本公司管理,而名义是()
《马可波罗行纪》中载:“此汗八里大城之周围,约有城市二百,位置远近不等,每城皆有商人来此买卖货物,盖此城为商业繁荣之城也。”“此城”指的是()。
1543年发表解剖学专著《人体结构论》的是()。
由元素序列(27,16,75,38,51)构造平衡二叉树,则首次出现的最小不平衡子树的根(即离插入结点最近且平衡因子的绝对值为2的结点)是()。
已知一组关键字为(26,36,41,38,44,15,68,12,6,51,25),用链地址法解决冲突。假设装填因子a=0.75,散列函数的形式为H(K)=KMODP,回答下列问题:(1)构造散列函数;(2)画出散列表;
随机试题
下述哪一种是非特异性梅毒血清试验
纽曼保健系统模式主要包括的三个部分不包括
某男,52岁,哮喘已六年,反复缠绵不愈,喉中痰鸣,胸闷胁痛,爪甲青紫,面色晦黯,有时夹有口苦口干,便干腹胀,舌紫暗或有瘀斑,脉沉涩。应为
A.脾阳虚证B.寒湿困脾证C.湿热蕴脾证D.肝胆湿热证E.肾气不固证
直接接触防护应选用()。
受甲公司委托,乙锅炉压力容器检测检验站委派具有检验资格的张某,到甲公司对一200立方米的球形液氧储罐进行检测检验。该球罐是由丙公司制造、丁施工公司安装的。依据《特种设备安全法》的规定,下列关于张某检测和执业的说法,正确的是()。
建设项目安全设施设计有下列()情形的,不予批准,并不得开工建设。
根据皮亚杰的理论,图式从低级到高级发展是通过同化与顺应的形式进行的。()
党的十一届三中全会的主要功绩是()。
Between1883and1837,thepublishersofa"pennypress"provedthatalow-pricedpaper,editedtointerestordinarypeople,cou
最新回复
(
0
)