【正确答案】[解答] (1)各关键字的散列函数值如下:
key | 22 | 41 | 53 | 46 | 30 | 13 | 1 | 67 | 51 |
H(key) | 1 | 6 | 3 | 8 | 12 | 0 | 3 | 6 | 10 |
采用线性探测法再散列法处理冲突,所构造的散列表为:
下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
关键字 | 13 | 22 | | 53 | 1 | | 41 | 67 | 46 | | 51 | | 30 |
探查次数 | 1 | 1 | | 1 | 2 | | 1 | 2 | 1 | | 1 | | 1 |
(2)装填因子=关键字总数/表长=9/13≈0.7。 (3)设查找成功在每个关键字上是等概率的,则查找每个关键字的概率为1/9,各关键字的探查次数分别为:
关键字 | 13 | 22 | | 53 | 1 | | 41 | 67 | 46 | | 51 | | 30 |
成功时的 探查次数 | 1 | 1 | | 1 | 2 | | 1 | 2 | 1 | | 1 | | 1 |
|
所以有,ASL
succ=(1+1+1+2+l+2+1+1+1)/9=11/9。 (4)设不成功的查找在每个地址上发生的概率相同,平均概率为1/13,对每个位置不成功查找的探查次数分别为:
下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
关键字 | 13 | 22 | | 53 | 1 | | 41 | 67 | 46 | | 51 | | 30 |
不成功时 的探查次数 | 3 | 2 | 1 | 3 | 2 | 1 | 4 | 3 | 2 | 1 | 2 | 1 | 4 |
|
以散列地址在位置2的关键字为例,由于此处关键字为空,只需比较1次就可确定本次查找不成功;以散列地址在位置3的关键字为例,若该关键字不在散列表中,需要将它与从位置3开始向后直至位置5的关键字相比较,由于位置5的关键字为空,所以不再向后比较,共比较3次,其他的类推得到。
所以有,ASL
unsucc=(3+2+1+3+2+1+4+3+2+1+2+1+4)/13=29/13。