有一结点的关键字序列F= {129,72,180,105,147,96,45,69},散列函数为:H (k) =k mod 11,其中k为关键字,散列地址空间为0~10。要求: 画出相应的散列表。当发生冲突时,以链地址法解决。计算在等概率情况下,查找成功

admin2017-04-28  47

问题 有一结点的关键字序列F= {129,72,180,105,147,96,45,69},散列函数为:H (k) =k mod 11,其中k为关键字,散列地址空间为0~10。要求:
画出相应的散列表。当发生冲突时,以链地址法解决。计算在等概率情况下,查找成功和查找不成功时的平均查找长度ASL(只将与关键字的比较次数计算在内即可)。

选项

答案采用链地址法处理冲突建立的散列表如下: [*] ASLsucc=(5×1+3×2)/8=11/8 ASLunsucc(0+1+0+1+2+0+2+0+2+0+0)/11=8/11 说明:本题中已经明确指出采用链地址法,只将与关键字的比较计算在内,因此上述ASLusucc的解法是正确的。如果本题要求将空指针的比较也包括在内,则 ASLunsucc=(1+2+1+2+3+1+3+1+3+1+1)/11=19/11 提醒:散列表查找成功的平均查找长度与查找不成功的平均查找长度是不一样的计算方式,千万要注意!

解析
转载请注明原文地址:https://jikaoti.com/ti/anfjFFFM
0

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