2. 考研
  3. 采用散列函数H(k)=3×k MOD 13并用线性探测开放地址法处理冲突，在数列地址空间[0．．12]中对关键字序列22，41，5 3，46，30，13，1，67，51； (1)构造散列表(画示意图)； (2)装填因子； (3)等概

采用散列函数H(k)=3×k MOD 13并用线性探测开放地址法处理冲突，在数列地址空间[0．．12]中对关键字序列22，41，5 3，46，30，13，1，67，51； (1)构造散列表(画示意图)； (2)装填因子； (3)等概

admin2012-06-26  78
问题 采用散列函数H(k)=3×k MOD 13并用线性探测开放地址法处理冲突，在数列地址空间[0．．12]中对关键字序列22，41，5 3，46，30，13，1，67，51；
    (1)构造散列表(画示意图)；
    (2)装填因子；
    (3)等概率情况下查找成功的平均查找长度；
    (4)等概率情况下查找失败的平均查找长度。
选项
答案(1)各关键字的散列函数值如下： [*] 采用线性探测法再散列法处理冲突，所构造的散列表为： [*] (2)装填因子一关键字总数／表长一9／13≈0．7。 (3)设查找成功在每个关键字上是等概率的，则查找每个关键字的概率为1／9，各关键字的探查次数分别为： [*] 所以有，ASLSUCC=(1+1+1+2+1+2+1+1+1)／9=11／9。 (4)设不成功的查找在每个地址上发生的概率相同，平均概率为1／13，对每个位置不成功查找的探查次数分别为： [*] 以散列地址在位置2的关键字为例，由于此处关键字为空，只需比较1次就可确定本次查找不成功；以散列地址在位置3的关键字为例，若该关键字不在散列表中，需要将它与从位置3开始向后直至位置5的关键字相比较，由于关键字5的关键字为空，所以不再向后比较，共比较3次，其他的类推得到。 所以有，ASLunSUCC=(3+2+1+3+2+1+4+3+2+1+2+1+4)／13=29／13。
解析 用线性探测法解决冲突构造散列表，并对查找性能进行分析，具体解题步骤如下。
转载请注明原文地址:https://kaotiyun.com/show/oyxi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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