给定结点的关键字序列为：19，14，23，1，68，20，84，27，55，11，10，79。 设散列表的长度为13，散列函数为：H（K）=K % 13。试画出线性探测再散列解决冲突时所构造的散列表，并求出其平均查找长度

### 回答1：
散列函数为 H(K) = K % 13，散列表的长度为13，因此散列表的下标范围为0~12。

首先，将给定的关键字序列按照散列函数的结果分配到散列表中：

| 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|------|---|---|---|---|---|---|---|---|---|---|----|----|----|
| 关键字 | 0 | 1 | | 19 | 14 | 55 | 27 | | 68 | 20 | 79 | 84 |

其中，空白表示该位置没有被占用。

接下来，对于发生冲突的关键字，采用线性探测再散列的方法解决冲突。具体做法是，如果散列表中的某个位置已经被占用，那么就继续往后查找，直到找到一个空白位置为止。

例如，关键字23在下标2处发生了冲突，因此需要继续往后查找。下一个位置是3，但是已经被关键字19占用了，因此继续往后查找。下一个位置是4，但是也被占用了，继续往后查找。最终，在下标7处找到了一个空白位置，将关键字23放入该位置：

| 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|------|---|---|---|---|---|---|---|---|---|---|----|----|----|
| 关键字 | 0 | 1 | 23 | 19 | 14 | 55 | 27 | | 68 | 20 | 79 | 84 |

同样地，对于关键字1、11、10也需要进行线性探测再散列：

| 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|------|---|---|---|---|---|---|---|---|---|---|----|----|----|
| 关键字 | 0 | 1 | 23 | 19 | 14 | 55 | 27 | 11 | 68 | 20 | 79 | 84 | 10 |

此时，所有的关键字都已经被正确地插入到了散列表中。平均查找长度为：

(1 + 2 + 3 + 4 + 5 + 6 + 7 + 1 + 1 + 1 + 1 + 1) / 12 ≈ 2.5

因此，平均查找长度为2.5。

### 回答2：
线性探测再散列是一种解决冲突的方法，当发生冲突时，按照线性的方式探测下一个位置，直到找到空闲位置为止。给定的关键字序列为：19，14，23，1，68，20，84，27，55，11，10，79。散列表长度为13，散列函数为：H（K）=K % 13。

首先，根据散列函数，计算每个关键字对应的散列地址：
19 % 13 = 6
14 % 13 = 1
23 % 13 = 10
1 % 13 = 1
68 % 13 = 7
20 % 13 = 7
84 % 13 = 4
27 % 13 = 1
55 % 13 = 3
11 % 13 = 11
10 % 13 = 10
79 % 13 = 2

然后，根据线性探测再散列方法，将关键字插入到对应的散列地址，如果该地址已经被占用，则向后探测，直到找到空闲位置：
6: 19
1: 14 1
10: 23 10
7: 68 20
4: 84
3: 55
11: 27
2: 79
5: 11
8: 27
9: 11

最终构造的散列表为：
索引 关键字
0:
1: 14 1
2: 79
3: 55
4: 84
5: 11
6: 19
7: 68 20
8: 27
9: 11
10: 23 10
11: 27
12:

平均查找长度是指在查找过程中平均需要查找的次数。根据已构造的散列表，对每个关键字进行查找并计算查找长度：
关键字 查找长度
19 1
14 1
23 1
1 1
68 1
20 2
84 1
27 1
55 1
11 1
10 1
79 1

总查找长度 = 1 + 1 + 1 + 1 + 1 + 2 + 1 + 1 + 1 + 1 + 1 = 11
平均查找长度 = 总查找长度 / 关键字个数 = 11 / 12 ≈ 0.917

因此，线性探测再散列所构造的散列表的平均查找长度约为0.917。