选取哈希函数H(k)=(3k) MOD 11。用开放定址法处理冲突，di= i((7k) MOD 10+1) (i=1,2,3, …)。试在0~10的散列地址空间中对关键字序列(22, 41, 53, 46, 30, 13, 01, 67)造哈希表，并求等概率情况下查找成功时的平均查找长度

按照哈希函数H(k)=(3k) MOD 11，可以得到关键字对应的散列地址如下：

- H(22) = 2
- H(41) = 7
- H(53) = 8
- H(46) = 7（冲突）
- H(30) = 9
- H(13) = 6
- H(01) = 3
- H(67) = 10

由于关键字46和关键字41的散列地址相同，因此需要处理冲突。按照开放定址法，可以得到它们的探测序列如下：

- d1(46) = 8
- d2(46) = 10
- d3(46) = 2
- d4(46) = 4
- d5(46) = 6
- d6(46) = 9
- d7(46) = 1
- d1(41) = 5
- d2(41) = 7
- d3(41) = 9
- d4(41) = 1
- d5(41) = 3
- d6(41) = 6
- d7(41) = 8

最终得到的哈希表如下：

| 散列地址 | 关键字 |
| ------- | ------ |
| 0 | |
| 1 | 67 |
| 2 | 22 |
| 3 | 01 |
| 4 | 46 |
| 5 | 41 |
| 6 | 13 |
| 7 | 41 |
| 8 | 53 |
| 9 | 30 |
| 10 | |

等概率情况下查找成功时的平均查找长度ASL可以通过以下公式计算：

ASL = (p1 * 1) + (p2 * 2) + ... + (pi * i)

其中pi表示表中有i个关键字的概率。在本题中，共有8个关键字，因此pi的取值如下：

- p0 = 0.25（0个关键字的概率）
- p1 = 0.25（1个关键字的概率）
- p2 = 0.25（2个关键字的概率）
- p3 = 0.125（3个关键字的概率）
- p4 = 0.0625（4个关键字的概率）
- p5 = 0.03125（5个关键字的概率）
- p6 = 0.015625（6个关键字的概率）
- p7 = 0.015625（7个关键字的概率）

根据散列表中各关键字的探测序列，可以得到每个关键字在表中的位置和需要比较的次数，如下：

- 22：2（1次比较）
- 41：5（1次比较）
- 53：8（1次比较）
- 46：4（6次比较）
- 30：9（1次比较）
- 13：6（1次比较）
- 01：3（1次比较）
- 67：1（1次比较）

因此，ASL的计算如下：

ASL = (0.25 * 0) + (0.25 * 1) + (0.25 * 2) + (0.125 * 3) + (0.0625 * 4) + (0.03125 * 5) + (0.015625 * 6) + (0.015625 * 7) = 2.546875

因此，等概率情况下查找成功时的平均查找长度ASL为2.546875。