设有一组关键字{19，01，23，14，55，20，84，27，68，11，10，77}，采用散列函数H(key)=key%13，采用开放地址法的二次探测再散列方法解决冲突，试在0~18的散列地址空间中对该关键字序列构造散列表。

好的，让我来回答你的问题。

根据题目中所给的关键字和散列函数，我们可以得到以下散列地址：

- 19 -> 6
- 01 -> 1
- 23 -> 10
- 14 -> 1
- 55 -> 3
- 20 -> 7
- 84 -> 11
- 27 -> 1
- 68 -> 4
- 11 -> 11
- 10 -> 10
- 77 -> 5

其中，关键字14和27的散列地址与关键字01相同，发生了冲突。我们可以采用开放地址法中的二次探测再散列方法解决冲突。具体地，如果第一次散列地址为h，冲突解决的第i步散列地址为：

$h_i = (h + c_1i + c_2i^2) \mod m$

其中，c1和c2是正整数，m是散列表的大小。

在本题中，我们可以取c1=1，c2=3，m=13。则，关键字14的散列地址为2，关键字27的散列地址为12。最终的散列表如下：

- 0:
- 1: 01
- 2: 14
- 3: 55
- 4: 68
- 5: 77
- 6: 19
- 7: 20
- 8:
- 9: 23
- 10: 10
- 11: 84, 11
- 12: 27

这样，我们就成功地构造出了一个散列表，其中每个关键字都被正确地插入到了对应的散列地址处。

相关问题

设有一组关键字（19，1，23，14，55，20，84，27，68，11，10，77），其哈希函数为h(key)=key % 13。采用开放地址法的线性探测法解决冲突，试在0～18的哈希表中对该关键字序列构造哈希表，并求在成功和不成功情况下的平均查找长度。 （参考答案： 23/12=1.92 58/13=4.46）

首先，根据哈希函数h(key)=key % 13，可以得到以下哈希表：

0 1 2 3 4 5 6 7 8 9 10 11 12
---------------------------------------------------
1 14 23
55 20
84 27 68
77 11 10

接下来，对每个关键字进行插入操作。如果发生冲突，则使用线性探测法解决。

1. 插入关键字19

h(19) = 6，哈希表第6个位置为空，将19插入该位置。

0 1 2 3 4 5 6 7 8 9 10 11 12
---------------------------------------------------
1 14 19 23
55 20
84 27 68
77 11 10

2. 插入关键字1

h(1) = 1，哈希表第1个位置为空，将1插入该位置。

0 1 2 3 4 5 6 7 8 9 10 11 12
---------------------------------------------------
1 14 1 19 23
55 20
84 27 68
77 11 10

3. 插入关键字23

h(23) = 10，哈希表第10个位置为空，将23插入该位置。

0 1 2 3 4 5 6 7 8 9 10 11 12
---------------------------------------------------
1 14 1 19 23 55
55 20
84 27 68
77 11 10

4. 插入关键字14

h(14) = 1，哈希表第1个位置已经被占用，使用线性探测法查找下一个空位置。

h'(14) = (h(14) + 1) % 13 = 2，哈希表第2个位置为空，将14插入该位置。

0 1 2 3 4 5 6 7 8 9 10 11 12
---------------------------------------------------
1 14 1 19 23 55
55 14 20
84 27 68
77 11 10

5. 插入关键字55

h(55) = 3，哈希表第3个位置为空，将55插入该位置。

0 1 2 3 4 5 6 7 8 9 10 11 12
---------------------------------------------------
1 14 1 19 23 55
55 14 20
84 27 68
77 11 10

6. 插入关键字20

h(20) = 7，哈希表第7个位置为空，将20插入该位置。

0 1 2 3 4 5 6 7 8 9 10 11 12
---------------------------------------------------
1 14 1 19 23 55
55 14 20
84 27 68
77 11 10

7. 插入关键字84

h(84) = 11，哈希表第11个位置为空，将84插入该位置。

0 1 2 3 4 5 6 7 8 9 10 11 12
---------------------------------------------------
1 14 1 19 23 55
55 14 20
84 27 68
77 11 10

8. 插入关键字27

h(27) = 1，哈希表第1个位置已经被占用，使用线性探测法查找下一个空位置。

h'(27) = (h(27) + 1) % 13 = 2，哈希表第2个位置已经被占用，继续查找下一个空位置。

h''(27) = (h'(27) + 1) % 13 = 3，哈希表第3个位置已经被占用，继续查找下一个空位置。

h'''(27) = (h''(27) + 1) % 13 = 4，哈希表第4个位置为空，将27插入该位置。

0 1 2 3 4 5 6 7 8 9 10 11 12
---------------------------------------------------
1 14 1 19 23 55
55 14 20
84 27 68
77 27 11 10

9. 插入关键字68

h(68) = 1，哈希表第1个位置已经被占用，使用线性探测法查找下一个空位置。

h'(68) = (h(68) + 1) % 13 = 2，哈希表第2个位置已经被占用，继续查找下一个空位置。

h''(68) = (h'(68) + 1) % 13 = 3，哈希表第3个位置已经被占用，继续查找下一个空位置。

h'''(68) = (h''(68) + 1) % 13 = 4，哈希表第4个位置已经被占用，继续查找下一个空位置。

h''''(68) = (h'''(68) + 1) % 13 = 5，哈希表第5个位置已经被占用，继续查找下一个空位置。

h'''''(68) = (h''''(68) + 1) % 13 = 6，哈希表第6个位置已经被占用，继续查找下一个空位置。

h''''''(68) = (h'''''(68) + 1) % 13 = 7，哈希表第7个位置已经被占用，继续查找下一个空位置。

h'''''''(68) = (h''''''(68) + 1) % 13 = 8，哈希表第8个位置已经被占用，继续查找下一个空位置。

h''''''''(68) = (h'''''''(68) + 1) % 13 = 9，哈希表第9个位置已经被占用，继续查找下一个空位置。

h'''''''''(68) = (h''''''''(68) + 1) % 13 = 10，哈希表第10个位置已经被占用，继续查找下一个空位置。

h''''''''''(68) = (h'''''''''(68) + 1) % 13 = 11，哈希表第11个位置已经被占用，继续查找下一个空位置。

h'''''''''''(68) = (h''''''''''(68) + 1) % 13 = 12，哈希表第12个位置为空，将68插入该位置。

0 1 2 3 4 5 6 7 8 9 10 11 12
---------------------------------------------------
1 14 1 19 23 55
55 14 20
84 27 68
77 27 11 10

10. 插入关键字11

h(11) = 11，哈希表第11个位置已经被占用，使用线性探测法查找下一个空位置。

h'(11) = (h(11) + 1) % 13 = 12，哈希表第12个位置为空，将11插入该位置。

0 1 2 3 4 5 6 7 8 9 10 11 12
---------------------------------------------------
1 14 1 19 23 55
55 14 20
84 27 68
77 27 11 10 11

11. 插入关键字10

h(10) = 10，哈希表第10个位置已经被占用，使用线性探测法查找下一个空位置。

h'(10) = (h(10) + 1) % 13 = 11，哈希表第11个位置已经被占用，继续查找下一个空位置。

h''(10) = (h'(10) + 1) % 13 = 12，哈希表第12个位置已经被占用，继续查找下一个空位置。

h'''(10) = (h''(10) + 1) % 13 = 0，哈希表第0个位置为空，将10插入该位置。

0 1 2 3 4 5 6 7 8 9 10 11 12
---------------------------------------------------
10 1 14 1 19 23 55
55 14 20
84 27 68
77 27 11 10 11

至此，哈希表构造完成。在成功查找和不成功查找的情况下，平均查找长度的计算方法如下：

成功查找的平均查找长度ASL = (1×1 + 2×2 + 3×3 + ... + n×n) / n，其中n为关键字个数。

不成功查找的平均查找长度ASL = (1×1 + 2×2 + 3×3 + ... + n×n) / (m-n)，其中m为哈希表长度，n为关键字个数。

按照上述公式计算可得：

成功查找的平均查找长度ASL = (1×1 + 2×2 + 2×3 + 2×4 + 1×5) / 11 = 23/12 = 1.92

不成功查找的平均查找长度ASL = (1×1 + 2×2 + 2×3 + 2×4 + 1×5 + 1×6) / (13-11) = 58/13 = 4.46

因此，该哈希表在成功查找和不成功查找的情况下的平均查找长度分别为1.92和4.46。

9.设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链接法构造散列表，散列函数为H（key）=key MOD 13,散列地址为1的链中有（）个记录。

将关键字用散列函数H(key)=key MOD 13计算散列地址，得到的散列地址如下：

| key | H(key) |
| --- | --- |
| 19 | 6 |
| 14 | 1 |
| 23 | 10 |
| 1 | 1 |
| 68 | 5 |
| 20 | 7 |
| 84 | 4 |
| 27 | 1 |
| 55 | 3 |
| 11 | 11 |
| 10 | 10 |
| 79 | 12 |

其中，散列地址为1的链中有3个记录，即14、1、27。