设有一组关键字 { 29，01， 13，15，56，20，87，27，69，9，10，74 }，散列函数为 h(key)=key%17，采用线性探测方法解决冲突。试在 0 到 18 的散列地址空间中对该关键字序列构造散列表，则成功查找的平均查找长度为 __

### 回答1：
根据散列函数 h(key)=key%17，将关键字序列散列到 到 16 的地址空间中，得到以下散列表：

: 15
1: 01
2: 13
3: 74
4: 56
5: 20
6: 27
7: 69
8: 9
9: 10
10: 29
11:
12:
13:
14:
15: 87
16:

其中，冲突的关键字 29 和 01 分别散列到了地址 10 和 1，需要采用线性探测方法解决冲突。具体地，将关键字 29 插入到地址 10 后面的空槽中，得到：

: 15
1: 01
2: 13
3: 74
4: 56
5: 20
6: 27
7: 69
8: 9
9: 10
10: 29
11:
12:
13:
14:
15: 87
16:

然后，将关键字 01 插入到地址 1 后面的空槽中，得到：

: 15
1: 01
2: 13
3: 74
4: 56
5: 20
6: 27
7: 69
8: 9
9: 10
10: 29
11:
12:
13:
14:
15: 87
16:

此时，散列表中所有关键字都已插入完成。对于任意一个关键字，查找的平均查找长度为：

(1*1 + 2*1 + 3*1 + 4*1 + 5*1 + 6*1 + 7*1 + 8*1 + 9*1 + 10*1 + 11*2) / 12 = 1.75

因此，成功查找的平均查找长度为 1.75。

### 回答2：
首先，我们根据散列函数h(key)=key mod 19将关键字映射到0到18的散列地址上。

29 -> 10
01 -> 1
13 -> 13
15 -> 15
56 -> 17
20 -> 1
87 -> 5
27 -> 8
69 -> 14
9 -> 9
10 -> 10
74 -> 16

接下来，按照线性探测方法，将关键字插入散列表中。如果某个位置已经被占用，就将检查下一个位置，直到找到一个空位置为止。

首先，将10插入散列表，位置10被占用，向下探测，插入16。

10 -> 29
16 -> 01
13 -> 13
15 -> 15
17 -> 56
1 -> 20
87 -> 5
8 -> 27
69 -> 14
9 -> 9
10 -> 10
74 -> 16

下一个关键字01被散列到位置1，位置1被占用，向下探测，插入20。

10 -> 29
16 -> 01
13 -> 13
15 -> 15
17 -> 56
1 -> 20
87 -> 5
8 -> 27
69 -> 14
9 -> 9
10 -> 10
74 -> 16

接下来，关键字13和15均被散列到空位置13和15。

10 -> 29
16 -> 01
13 -> 13
15 -> 15
17 -> 56
1 -> 20
87 -> 5
8 -> 27
69 -> 14
9 -> 9
10 -> 10
74 -> 16

关键字56被散列到位置17，位置17被占用，向下探测，插入5。

10 -> 29
16 -> 01
13 -> 13
15 -> 15
17 -> 56
1 -> 20
87 -> 5
8 -> 27
69 -> 14
9 -> 9
10 -> 10
74 -> 16

关键字20被散列到位置1，位置1已经被占用，向下探测，插入27。

10 -> 29
16 -> 01
13 -> 13
15 -> 15
17 -> 56
1 -> 20
87 -> 5
8 -> 27
69 -> 14
9 -> 9
10 -> 10
74 -> 16

关键字87被散列到位置5，位置5被占用，向下探测，插入14。

10 -> 29
16 -> 01
13 -> 13
15 -> 15
17 -> 56
1 -> 20
87 -> 5
8 -> 27
69 -> 14
9 -> 9
10 -> 10
74 -> 16

关键字27被散列到位置8，位置8被占用，向下探测，插入9。

10 -> 29
16 -> 01
13 -> 13
15 -> 15
17 -> 56
1 -> 20
87 -> 5
8 -> 27
69 -> 14
9 -> 9
10 -> 10
74 -> 16

最后，关键字69、9和10均被散列到空位置。

10 -> 29
16 -> 01
13 -> 13
15 -> 15
17 -> 56
1 -> 20
87 -> 5
8 -> 27
69 -> 14
9 -> 9
10 -> 10
74 -> 16

对于每个关键字，我们需要查找一次来确定它应该插入的位置。因此，成功查找的平均查找长度为：

(1+1+1+1+1+2+1+1+1+1+1)/11 = 1

因此，成功查找的平均查找长度为1。

### 回答3：
线性探测方法是一种解决冲突的散列表技术，它采用了线性搜索的方式来解决冲突。对于该题组的关键字 { 29，01， 13，15，56，20，87，27，69，9，10，74 }，我们采用散列函数 h(key)=key%18，映射到0到18的散列地址空间。

首先，我们将关键字29散列到地址11，该地址没有被占用，故可以直接存入该地址。关键字01散列到地址1，地址1被占用，发生了冲突。此时，我们通过线性探测的方式，逐一检查地址2、3、4..直到发现地址5未被占用，将01存入地址5处。同样地，13、15、56、20、27、69、9、10、74均被安置在散列表中。

因此，最终的散列表如下：

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

- 01 - - - 15 56 - - 69 10 29 20 - 13 - - 27 74

假设查找关键字的概率相等，则成功查找的平均查找长度为：

ASL = (1/12)*1 + (1/12)*2 + (1/12)*3 + (1/12)*4 + (1/12)*2 + (1/12)*1 + (1/12)*2 + (1/12)*2 + (1/12)*3 + (1/12)*4 + (1/12)*1 + (1/12)*1
= 1.83

因此，成功查找的平均查找长度为1.83。