设有一组关键字{9,1,23,14,55,20,84,27}，采用哈希函数：h（key）=key mod 7 ，表长为10，用开放地址法的线性探测再散列方法解决冲突。要求：对该关键字序列构造哈希表。计算查找成功,失败的平均查找长度。 依次给出哈希表地址0--9单元的值。

### 回答1：
首先，根据哈希函数 h(key) = key mod 7，可以得到每个关键字的哈希地址：

9 mod 7 = 2
1 mod 7 = 1
23 mod 7 = 2
14 mod 7 =
55 mod 7 = 6
20 mod 7 = 6
84 mod 7 =
27 mod 7 = 6

接下来，采用开放地址法的线性探测再散列方法解决冲突，即如果某个关键字的哈希地址已经被占用，就往后探测，直到找到一个空闲的位置为止。具体过程如下：

1. 将关键字 9 存放在地址 2 处。
2. 将关键字 1 存放在地址 1 处。
3. 将关键字 23 存放在地址 3 处。
4. 将关键字 14 存放在地址 处。
5. 将关键字 55 存放在地址 6 处。
6. 由于地址 6 已经被占用，线性探测到地址 7，发现地址 7 也被占用，继续线性探测到地址 8，发现地址 8 为空，将关键字 20 存放在地址 8 处。
7. 由于地址 已经被占用，线性探测到地址 1，发现地址 1 已经被占用，继续线性探测到地址 2，发现地址 2 已经被占用，继续线性探测到地址 3，发现地址 3已经被占用，继续线性探测到地址 4，发现地址 4 已经被占用，继续线性探测到地址 5，发现地址 5 已经被占用，继续线性探测到地址 6，发现地址 6 已经被占用，继续线性探测到地址 7，发现地址 7 已经被占用，继续线性探测到地址 8，发现地址 8 已经被占用，继续线性探测到地址 9，发现地址 9 为空，将关键字 27 存放在地址 9 处。

此时，哈希表的地址--9单元的值为：

: 14
1: 1
2: 9
3: 23
4:
5:
6: 55
7:
8: 20
9: 27

接下来计算查找成功和失败的平均查找长度：

查找成功的平均查找长度 = 所有查找成功的关键字的查找长度之和 / 查找成功的关键字个数

查找失败的平均查找长度 = 所有查找失败的关键字的查找长度之和 / 查找失败的关键字个数

假设要查找的关键字为 x，先计算它的哈希地址 h(x)：

h( x ) = x mod 7

假设要查找的关键字为 14，它的哈希地址为 ，直接在地址 处找到了，查找长度为 1。

假设要查找的关键字为 27，它的哈希地址为 6，由于地址 6 已经被占用，线性探测到地址 7，发现地址 7 为空，但是地址 7 之后的所有地址都已经被占用了，因此查找失败，查找长度为 3。

假设要查找的关键字为 10，它的哈希地址为 3，由于地址 3 已经被占用，线性探测到地址 4，发现地址 4 为空，但是地址 4 之后的所有地址都已经被占用了，因此查找失败，查找长度为 2。

假设要查找的关键字为 84，它的哈希地址为 ，由于地址 已经被占用，线性探测到地址 1，发现地址 1 已经被占用，继续线性探测到地址 2，发现地址 2 已经被占用，继续线性探测到地址 3，发现地址 3已经被占用，继续线性探测到地址 4，发现地址 4 已经被占用，继续线性探测到地址 5，发现地址 5 已经被占用，继续线性探测到地址 6，发现地址 6 已经被占用，继续线性探测到地址 7，发现地址 7 已经被占用，继续线性探测到地址 8，发现地址 8 已经被占用，继续线性探测到地址 9，发现地址 9 为空，但是地址 9 之后的所有地址都已经被占用了，因此查找失败，查找长度为 10。

因此，查找成功的平均查找长度为 (1+1+1) / 3 = 1，查找失败的平均查找长度为 (3+2+10) / 3 = 5。

哈希表地址--9单元的值为：

: 14
1: 1
2: 9
3: 23
4:
5:
6: 55
7:
8: 20
9: 27

### 回答2：
首先，根据哈希函数 h（key）=key mod 7 ，将关键字{9，1，23，14，55，20，84，27}分别求余获得哈希值{2，1，2，0，6，6，0，6}。

然后，构造哈希表并解决冲突。由于表长为10，因此哈希表共有10个单元，初始化时将所有单元置为空。由于采用开放地址法的线性探测再散列方法，因此当发现当前位置已被占用时，需要顺序向后查找，直到找到一个空位置插入元素。

2号位：9，23
1号位：1
0号位：14，84
6号位：55，20，27

可以得到 0--9 单元的值如下：

0号位：14
1号位：1
2号位：9
3号位：
4号位：
5号位：
6号位：55
7号位：
8号位：
9号位：

接下来计算查找成功、失败的平均查找长度。

对于查找成功的情况，需要先根据哈希函数求出关键字所在的位置，然后顺序向后查找，直到找到目标元素。例如，查找关键字为 20 的元素，其哈希值为 6，可能的查找路径为 6->7->8，共查找了 3 次，因此其平均查找长度为 3/1=3。

对于查找失败的情况，需要先根据哈希函数求出关键字所在的位置，然后顺序向后查找，直到找到一个空位置或者回到起点。例如，查找关键字为 18 的元素，其哈希值为 4，可能的查找路径为 4->5->6->0->1->2->3->4，共查找了 8 次，因此其平均查找长度为 8/1=8。

综上所述，该哈希表构造完成后，对于查找成功的关键字，平均查找长度为 3；对于查找失败的关键字，平均查找长度为 8。

### 回答3：
哈希表的构造：
按照哈希函数h(key)=key mod 7的规则，将每个关键字映射到哈希表中的一个地址。
9%7=2，1%7=1，23%7=2，14%7=0，55%7=6，20%7=6，84%7=0，27%7=6.
故该组关键字在哈希表中应该依次存放在地址为：2，1，3，0，6，5，0，6的单元中。当地址已被占用，则进行线性探测再散列，即沿着哈希表向后查找，直到找到空闲的位置存放。

计算哈希表的平均查找长度：
（1）查找成功：假设要查找的关键字是14，则直接访问地址为0的单元，平均查找长度为1/8。
（2）查找失败：假设要查找的关键字是17，则依次访问地址为3、4、5、6、0、1、2的单元，直到发现查找失败为止，平均查找长度为（3+4+5+6+1+2）/8=21/8。

哈希表地址0--9单元的值：
0：14 84
1：1
2：9 23
3：27
4：
5：20
6：55

注：散列表中每个插槽中表示的数字是使用哈希表中该插槽的下标与该插槽连续存储的数字之间的余数。如果该插槽为空，则表示没有数字。