问题
问答题
采用散列函数H(k)=3×k MOD 13并用线性探测开放地址法处理冲突，在数列地址空间[0..12]中对关键字序列22，41，53，46，30，13，1，67，51
等概率情况下查找失败的平均查找长度。
答案
参考答案：设不成功的查找在每个地址上发生的概率相同，平均概率为1/13，对每个位置不成功查找的探查次数见表4：
以散列地址在位置2的关键字为例，由于此处关键字为空，只需比较1次就可确定本次查找不成功；以散列地址在位置3的关键字为例，若该关键字不在散列表中，需要将它与从位置3开始向后直至位置5的关键字相比较，由于位置5的关键字为空，所以不再向后比较，共比较3次，其他的类推得到。 表4 下标 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
所以有，ASLunsucc=(3+2+1+3+2+1+4+3+2+1+2+1+4)/13=29/13。
解析： 用线性探测法解决冲突构造散列表，并对查找性能进行分析，具体解题步骤如下。