2. 考研
  3. 已知一组关键字为(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)画出散列表； (

admin2013-07-12  64
问题 已知一组关键字为(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

学硕统考专业

相关试题推荐
随机试题
最新回复(0)