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

admin2013-12-31  38

问题 采用散列函数H(k)===3 X k MOD 13并用线性探测开放地址法处理冲突,在数列地址空间[0..12]中对关键字序列22,41,53,46,30,13,1,67,51
      (1)构造散列表(画示意图);
      (2)装填因子;
      (3)等概率情况下查找成功的平均查找长度;
      (4)等概率情况下查找失败的平均查找长度。

选项

答案(1)各关键字的散列函数值如下表9—3所列: [*] 采用线性探测法再散列法处理冲突,所构造的散列表见表9—4: [*] (2)装填因子=关键字总数/表长=9/13≈0.7。 (3)设查找成功在每个关键字上是等概率的,则查找每个关键字的概率为1/9,各关键字的探查次数见表9—5: [*] 所以有,ASLsucc=(1+1+1+2+1+2+1+1+1)/9=11/9。 (4)设不成功的查找在每个地址上发生的概率相同,平均概率为1/13,对每个位置不成功查找的探查次数见表9—6: [*] 以散列地址在位置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://jikaoti.com/ti/8CajFFFM
0

最新回复(0)