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

根据散列函数H(key)=key%11，我们可以将关键字序列的散列地址计算出来：

key    : 29  01  13  15  56  20  87  27  69  9   10  74
H(key) : 07  01  02  04  01  09  09  05  03  9   10  03

由于采用线性探测方法解决冲突，我们需要在散列表中寻找下一个可用的空位置。若当前位置已经被占用，则继续向后查找，直到找到一个空位置或者查找完整个散列表。

地址 :  0   1   2   3   4   5   6   7   8   9   10  11  12  13  14  15  16  17  18
     : [9] [1] [13]     [56] [20] [69] [29] [87]     [10]     [27] [74]  [3]

以上是构造出的散列表，用中括号括起来的数字表示该位置存储的关键字。例如，[9]表示散列地址为9的位置存储了关键字69。

接下来，我们可以计算成功查找的平均查找长度（ASL）。

对于每个关键字，它的查找长度是它在散列表中的位置与它原本的散列地址之差。例如，关键字10的查找长度为11-10=1。

成功查找的平均查找长度是所有关键字的查找长度之和除以关键字个数。在本例中，计算公式如下：

ASL = (1+1+1+1+2+1+1+1+1+1+1+1)/12 = 12/12 = 1

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

相关问题

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

### 回答1：
首先构造一个长度为18的散列表，初始时所有位置均为空。

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

接下来对每个关键字进行散列，计算其散列地址。由于散列函数为 H(key)=key % 17，因此：

- 29 % 17 = 12
- 01 % 17 = 1
- 13 % 17 = 13
- 15 % 17 = 15
- 56 % 17 = 5
- 20 % 17 = 3
- 87 % 17 = 4
- 27 % 17 = 10
- 69 % 17 = 4
- 9 % 17 = 9
- 10 % 17 = 10
- 74 % 17 = 8

然后按照线性探测法的规则，将每个关键字插入到其散列地址处，如果该位置已经被占用，则依次往后探测，直到找到一个空闲位置为止。具体过程如下：

- 29 -> 12
- 01 -> 1
- 13 -> 13
- 15 -> 15
- 56 -> 5
- 20 -> 3
- 87 -> 4
- 27 -> 10
- 69 -> 4 （冲突，线性探测）
- 9 -> 9
- 10 -> 10
- 74 -> 8

最终得到的散列表如下所示：

| 9 | 1 | 20 | 87 | 69 | 56 | 13 | 74 | 15 | 29 | 10 | 27 | 12 | | | 3 | | 4 |

其中，每个位置上的数字表示该位置存放的关键字，空位置用竖线“|”表示。

计算平均查找度的公式为：ASL = (成功查找时的平均查找长度 + 不成功查找时的平均查找长度) / 总记录数。

假设我们要查找关键字 20，由于 H(20) = 3，因此首先查找散列表中下标为 3 的位置。发现该位置存放的是关键字 20，因此查找成功，平均查找长度为 1。

对于不成功查找，可以假设要查找的关键字在散列表中不存在，此时需要从散列表中的每个位置依次开始搜索，直到找到一个空位置或搜索完整个散列表。由于这里的散列表长度比较小，我们可以手动模拟出所有可能的情况，并计算平均查找长度。不妨假设要查找的关键字为 99，那么所有可能的情况如下所示：

1. 0 -> 99 (ASL = 1)
2. 1 -> 99 (ASL = 2)
3. 2 -> 99 (ASL = 3)
4. 3 -> 空 (ASL = 4)
5. 4 -> 99 (ASL = 5)
6. 5 -> 99 (ASL = 6)
7. 6 -> 99 (ASL = 7)
8. 7 -> 99 (ASL = 8)
9. 8 -> 99 (ASL = 9)
10. 9 -> 空 (ASL = 10)
11. 10 -> 99 (ASL = 11)
12. 11 -> 99 (ASL = 12)
13. 12 -> 99 (ASL = 13)
14. 13 -> 99 (ASL = 14)
15. 14 -> 99 (ASL = 15)
16. 15 -> 99 (ASL = 16)
17. 16 -> 空 (ASL = 17)

根据公式，成功查找时的平均查找长度为 1，不成功查找时的平均查找长度为 (1+2+3+4+5+6+7+8+9+10+11+12+13+14+15+16+17) / 18 = 9。

因此，平均查找度为 (1+9) / 12 ≈ 0.83，即成功查找一次需要搜索 0.83 个位置。

### 回答2：
根据散列函数H(key) = key % 17，我们需要将关键字序列{29,01,13,15,56,20,87,27,69,9,10,74}映射到0到18的散列地址空间中。

首先，我们创建一个长度为19的散列表，初始化所有的位置为空。

然后，根据散列函数计算每个关键字的散列地址并插入到散列表中：

散列地址 = 关键字 % 17
29的散列地址 = 29 % 17 = 12，插入到地址为12的位置
01的散列地址 = 01 % 17 = 1，插入到地址为1的位置
13的散列地址 = 13 % 17 = 13，插入到地址为13的位置
15的散列地址 = 15 % 17 = 15，插入到地址为15的位置
...
依次类推

如果某个位置已经被占用，采用线性探测方法解决冲突，即往后寻找下一个空闲位置。

最终，散列表中的关键字分布如下：
0：空
1：01
2：15
3：15
4：空
5：56
6：20
7：空
8：空
9：69
10：10
11：空
12：29
13：13
14：空
15：27
16：74
17：87
18：空

计算成功查找的平均查找度，需要统计每个关键字在查找时的查找次数，并求平均值。

关键字29的查找次数为1
关键字01的查找次数为1
关键字13的查找次数为1
关键字15的查找次数为1
关键字56的查找次数为1
关键字20的查找次数为1
关键字87的查找次数为1
关键字27的查找次数为1
关键字69的查找次数为1
关键字9的查找次数为1
关键字10的查找次数为1
关键字74的查找次数为1

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

需要注意的是，由于散列函数和冲突解决方法的选择，该散列表具有较低的冲突率。若冲突较多，则平均查找度可能会有所提高。

### 回答3：
首先，我们需要创建一个大小为19的散列表（0到18的散列地址空间）。然后，按照散列函数H(key)=key % 17，将关键字序列依次插入到散列表中。

插入第一个关键字29：
H(29) = 29 % 17 = 12
散列表：[ , , , , , , , , , , , , 29, , , , , , ]

插入第二个关键字01：
H(01) = 01 % 17 = 1
散列表：[ , 01, , , , , , , , , , , 29, , , , , , ]

插入第三个关键字13：
H(13) = 13 % 17 = 13
散列表：[ , 01, , , , , , , , , , , 29, 13, , , , , ]

插入第四个关键字15：
H(15) = 15 % 17 = 15
散列表：[ , 01, , , , , , , , , , , 29, 13, 15, , , , ]

插入第五个关键字56：
H(56) = 56 % 17 = 5
散列表：[ , 01, , , , 56, , , , , , , 29, 13, 15, , , , ]

插入第六个关键字20：
H(20) = 20 % 17 = 3
散列表：[ , 01, , 20, , 56, , , , , , , 29, 13, 15, , , , ]

插入第七个关键字87：
H(87) = 87 % 17 = 9
散列表：[ , 01, , 20, , 56, , , , 87, , , 29, 13, 15, , , , ]

插入第八个关键字27：
H(27) = 27 % 17 = 10
散列表：[ , 01, , 20, , 56, , , , 87, 27, , 29, 13, 15, , , , ]

插入第九个关键字69：
H(69) = 69 % 17 = 4
散列表：[ , 01, , 20, 69, 56, , , , 87, 27, , 29, 13, 15, , , , ]

插入第十个关键字9：
H(9) = 9 % 17 = 9 （发生冲突）
线性探测法解决冲突，尝试下一个位置：
H(9) + 1 = 10
散列表：[ , 01, , 20, 69, 56, , , , 87, 27, 9, 29, 13, 15, , , , ]

插入第十一个关键字10：
H(10) = 10 % 17 = 10 （发生冲突）
线性探测法解决冲突，尝试下一个位置：
H(10) + 1 = 11
散列表：[ , 01, , 20, 69, 56, , , , 87, 27, 9, 10, 29, 13, 15, , , , ]

插入第十二个关键字74：
H(74) = 74 % 17 = 8
散列表：[ , 01, , 20, 69, 56, , , 74, 87, 27, 9, 10, 29, 13, 15, , , , ]

最终得到的散列表为：
[ , 01, , 20, 69, 56, , , 74, 87, 27, 9, 10, 29, 13, 15, , , , ]

成功查找的平均查找度计算方法如下：
查找度 = (查找成功时的比较次数 + 1) / 2
总的查找度 = 所有关键字的查找度之和

计算关键字29的查找度：(1+1)/2 = 1
计算关键字01的查找度：(1+1)/2 = 1
计算关键字13的查找度：(1+1)/2 = 1
计算关键字15的查找度：(1+1)/2 = 1
计算关键字56的查找度：(1+1)/2 = 1
计算关键字20的查找度：(1+1)/2 = 1
计算关键字87的查找度：(1+1)/2 = 1
计算关键字27的查找度：(1+1)/2 = 1
计算关键字69的查找度：(1+1)/2 = 1
计算关键字9的查找度：(2+1)/2 = 1.5
计算关键字10的查找度：(2+1)/2 = 1.5
计算关键字74的查找度：(1+1)/2 = 1

总的查找度 = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1.5 + 1.5 + 1 = 13
成功查找的平均查找度 = 总的查找度 / 插入关键字的数量 = 13 / 12 = 1.083

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

设有一组关键字 { 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。