有一结点的关键字序列F={129,72,180,105,147,96,45,69},散列函数为H(k)=kmod11,其中k为关键字,散列地址空间为0~10。要求: 画出相应的散列表。当发生冲突时,以线性探测法解决。该散列表的装填因子是多少?计算在等概率

admin2014-04-17  41

问题 有一结点的关键字序列F={129,72,180,105,147,96,45,69},散列函数为H(k)=kmod11,其中k为关键字,散列地址空间为0~10。要求:
画出相应的散列表。当发生冲突时,以线性探测法解决。该散列表的装填因子是多少?计算在等概率情况下,查找成功和查找不成功时的平均查找长度ASL。

选项

答案采用线性探测法处理冲突建立的散列表如下: H(129)=129mod11=8 H(72)=72mod11=6 H(180)=180mod11=4 H(105)=105 mod11=6冲突H1(105)=(105+1)mod11=7 H(147)=147mod11=4冲突H1(147)=(147+1)mod 11=5 H(96)=96mod11=8冲突H1(96)=(96+1)mod11=9 H(45)=45mod11=1 H(69)=69mod11=3 综上所述,散列表如表4—7所示。 [*] 装填因子α=8/11。 ASLSUCC=(5×1+2×3)/8=11/8 ASLUNSUCC=(1+2+1+8+7+6+5+4+3+2+1)/11=40/11

解析
转载请注明原文地址:https://kaotiyun.com/show/Mlxi777K
0

最新回复(0)