采用散列函数H(k)=3×k MOD13并用线性探测开放地址法处理冲突，在散列地址空间[0，…，12]对关键字序列22，41，53，46，30，13，1，67，51；
(1)构造散列表；
(2)计算装填因子；
(3)等概率情况下查找成功的平均查找长度；
(4)等概率情况下查找失败的平均杏找长度。
参考答案：用线性探测法解决冲突构造散列表，并对查找性能进行分析，具体解题步骤如下：
(1)各关键字的散列函数值如下：
H(22)=3×22 MOD 13=1；
H(41)=3×41 MOD 13=6；
H(53)=3×53 MOD 13=3；
H(46)=3×46 MOD 13=8；
H(30)=3×30 MOD 13=12；
H(13)=3×13 MOD 13=0；
H(1)=3×1 MOD 13=3；
H(67)=3×67 MOD 13=6；
H(51)=3×51 MOD 13=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 |
所以ASLsucc=(1+1+1+2+1+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次，其他的类推得到。
所以ASLsucc=(3+2+1+3+2+1+4+3+2+1+2+1+4)/13=29/13
