对于输入30,20,56,75,31,19和散列函数h(K)=Kmod11，做以 a.构造它们的闭散列表。" b.求在本表中成功查找的最大键值比较次数。 c.求本表中成功查找的平均键值比较次数

a. 首先根据散列函数 h(K)=Kmod11，求出每个关键字的散列地址：

- h(30) = 8
- h(20) = 9
- h(56) = 1
- h(75) = 10
- h(31) = 9 （发生了冲突）
- h(19) = 8 （发生了冲突）

为了解决冲突，我们可以采用闭散列法，具体方法是将冲突的关键字放到散列表中的下一个空位置上（如果下一个位置也被占用，则继续往后找，直到找到一个空位置为止）。

- h(30) = 8
- h(20) = 9
- h(56) = 1
- h(75) = 10
- h(31) = 9 （放到下一个空位置，即位置10）
- h(19) = 8 （放到下一个空位置，即位置9）

最终得到的闭散列表为：

| 槽位 | 关键字 |
| --- | --- |
| 0 | |
| 1 | 56 |
| 2 | |
| 3 | |
| 4 | |
| 5 | |
| 6 | |
| 7 | |
| 8 | 30<br>19 |
| 9 | 20<br>31 |
| 10 | 75 |

b. 成功查找的最大键值比较次数取决于查找的关键字所在的槽位，因此最大键值比较次数为2（对应槽位8和9的关键字）。

c. 成功查找的平均键值比较次数可以通过所有成功查找的键值比较次数之和除以总的成功查找次数来计算。假设我们要查找的关键字是等概率地分布在各个槽位上的，则成功查找的概率为 $p=\frac{6}{11}$，失败查找的概率为 $q=1-p=\frac{5}{11}$。对于成功查找的情况，需要比较的键值次数为1或2，因此平均键值比较次数为：

$$\frac{1}{6}\cdot1+\frac{5}{6}\cdot\left(\frac{2}{6}\cdot1+\frac{4}{6}\cdot2\right)=\frac{11}{6}\approx1.83$$

因此，在本表中成功查找的平均键值比较次数为约1.83。