设散列函数H(k)=key mod 7, 散列表的地址空间为0到6，对关键字序列{14，21,24, 31，39，6，40}，请按照线性探测再散列构造散列表，并计算查找成功的平均查找长度。

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

首先，按照散列函数H(k)=key mod 7，对关键字序列{14，21,24, 31，39，6，40}进行散列，得到的散列地址分别为{0，0，3，3，4，6，5}。其中，14和21的散列地址都是0，因此需要进行线性探测再散列。

根据线性探测再散列的方法，当出现冲突时，将关键字向后移动一位，重新计算散列地址，直到找到一个空闲位置为止。具体地，14的散列地址为0，但是位置已经被占用，因此需要向后查找。经过一次探测后，14被移到了位置1。21的散列地址也为0，但是位置已经被占用，需要向后查找。经过两次探测后，21被移到了位置2。

此时散列表的情况如下：

0: 21 14
1: 24
2: 31
3: 39 6
4: 40
5:
6:

以此类推，依次将关键字插入散列表中。最终得到的散列表为：

0: 21 14
1: 24
2: 31
3: 39 6
4: 40
5:
6:

查找成功的平均查找长度ASL为：

ASL = (1/7) * [(1+2+1+2+1+1+1)] = 1.29

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

相关问题

{29,01,13,15,56,20,87,27,69,9,10,74},散列函数为：h(key)=key % 17,采用平方探测方法解决冲突。试在0到18的散列地址空间中对该关键字序列构造散列表。

### 回答1：
我们可以先创建一个长度为 19 的散列表，其中第 0 个位置不存储数据，因为散列函数 h(key) 的值最大为 16。

1. 对于第一个关键字 29，计算它的散列地址 h(key) = 12，将 29 存储在散列表的第 12 个位置。此时散列表为：[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 29, 0, 0, 0, 0, 0, 0, 0]

2. 对于第二个关键字 01，计算它的散列地址 h(key) = 1，将 01 存储在散列表的第 1 个位置。此时散列表为：[0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 29, 0, 0, 0, 0, 0, 0, 0]

3. 对于第三个关键字 13，计算它的散列地址 h(key) = 13，将 13 存储在散列表的第 13 个位置。此时散列表为：[0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 29, 13, 0, 0, 0, 0, 0, 0]

4. 对于第四个关键字 15，计算它的散列地址 h(key) = 15，将 15 存储在散列表的第 15 个位置。此时散列表为：[0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 29, 13, 0, 0, 15, 0, 0, 0]

5. 对于第五个关键字 56，计算它的散列地址 h(key) = 5，将 56 存储在散列表的第 5 个位置。此时散列表为：[0, 1, 0, 0, 0, 56, 0, 0, 0, 0, 0, 29, 13, 0, 0, 15, 0, 0, 0]

6. 对于第六个关键字 20，计算它的散列地址 h(key) = 3，将 20 存储在散列表的第 3 个位置。此时散列表为：[0, 1, 0, 20, 0, 56, 0, 0, 0, 0, 0, 29, 13, 0, 0, 15, 0, 0, 0]

7. 对于第七个关键字 87，计算它的散列地址 h(key) = 4，将 87 存储在散列表的第 4 个位置。此时散列表为：[0, 1, 0, 20, 87, 56, 0, 0, 0, 0, 0, 29, 13, 0, 0, 15, 0, 0, 0]

8. 对于第八个关键字 27，计算它的散列地址 h(key) = 10，将 27 存储在散列表的第 10 个位置。此时散列表为：[0, 1, 0, 20, 87, 56, 0, 0, 0, 0, 27, 29, 13, 0, 0, 15, 0, 0, 0]

9. 对于第九个关键字 69，计算它的散列地址 h(key) = 4，发现第 4 个位置已经被占用了，因此需要采用平方探测方法解决冲突。首先尝试散列地址 h(key) + 1 = 5，发现该位置已经被占用了，因此继续平方探测，计算散列地址 (h(key) + 1^2) % 19 = 6，发现该位置为空，因此将 69 存储在散列表的第 6 个位置。此时散列表为：[0, 1, 0, 20, 87, 56, 69, 0, 0, 0, 27, 29, 13, 0, 0, 15, 0, 0, 0]

10. 对于第十个关键字 9，计算它的散列地址 h(key) = 9，将 9 存储在散列表的第 9 个位置。此时散列表为：[0, 1, 0, 20, 87, 56, 69, 0, 0, 9, 27, 29, 13, 0, 0, 15, 0, 0, 0]

11. 对于第十一个关键字 10，计算它的散列地址 h(key) = 10，发现第 10 个位置已经被占用了，因此需要采用平方探测方法解决冲突。首先尝试散列地址 h(key) + 1 = 11，发现该位置已经被占用了，因此继续平方探测，计算散列地址 (h(key) + 1^2) % 19 = 12，发现该位置已经被占用了，因此继续平方探测，计算散列地址 (h(key) + 2^2) % 19 = 15，发现该位置已经被占用了，因此继续平方探测，计算散列地址 (h(key) + 3^2) % 19 = 4，发现该位置为空，因此将 10 存储在散列表的第 4 个位置。此时散列表为：[0, 1, 0, 20, 87, 56, 69, 0, 0, 9, 27, 29, 13, 0, 10, 15, 0, 0, 0]

12. 对于第十二个关键字 74，计算它的散列地址 h(key) = 8，将 74 存储在散列表的第 8 个位置。此时散列表为：[0, 1, 0, 20, 87, 56, 69, 74, 0, 9, 27, 29, 13, 0, 10, 15, 0, 0, 0]

最终构造出的散列表为：[0, 1, 0, 20, 87, 56, 69, 74, 0, 9, 27, 29, 13, 0, 10, 15, 0, 0, 0]。

### 回答2：
散列函数h(key) = key % 17，表示关键字key通过求余17得到散列地址。
平方探测的方法是，如果关键字发生冲突，即在求得的散列地址已经被占用，则通过平方计算来寻找下一个可用的散列地址。

给定关键字序列{29, 01, 13, 15, 56, 20, 87, 27, 69, 9, 10, 74}，将它们依次插入散列表中。

1. 将第一个关键字29插入散列表中，计算散列地址h(29) = 29 % 17 = 12，此地址为空，所以将关键字29插入到散列地址12的位置。

散列表：[ , , , , , , , , , , , 29, , , , , , , ]

2. 将第二个关键字01插入散列表中，计算散列地址h(01) = 1 % 17 = 1，此地址为空，所以将关键字01插入到散列地址1的位置。

散列表：[ , 01, , , , , , , , , , 29, , , , , , , ]

3. 将第三个关键字13插入散列表中，计算散列地址h(13) = 13 % 17 = 13，此地址为空，所以将关键字13插入到散列地址13的位置。

散列表：[ , 01, , , , , , , , , , 29, , 13, , , , , ]

4. 将第四个关键字15插入散列表中，计算散列地址h(15) = 15 % 17 = 15，此地址为空，所以将关键字15插入到散列地址15的位置。

散列表：[ , 01, , , , , , , , , , 29, , 13, , 15, , , ]

5. 将第五个关键字56插入散列表中，计算散列地址h(56) = 56 % 17 = 5，此地址为空，所以将关键字56插入到散列地址5的位置。

散列表：[ , 01, , , , 56, , , , , , 29, , 13, , 15, , , ]

6. 将第六个关键字20插入散列表中，计算散列地址h(20) = 20 % 17 = 3，此地址为空，所以将关键字20插入到散列地址3的位置。

散列表：[ , 01, , 20, , 56, , , , , , 29, , 13, , 15, , , ]

7. 将第七个关键字87插入散列表中，计算散列地址h(87) = 87 % 17 = 10，此地址为空，所以将关键字87插入到散列地址10的位置。

散列表：[ , 01, , 20, , 56, , , , 87, , 29, , 13, , 15, , , ]

8. 将第八个关键字27插入散列表中，计算散列地址h(27) = 27 % 17 = 10，此地址已被占用，使用平方探测方法计算下一个可用的散列地址。

第一次平方探测：h(27) + 1^2 = 10 + 1 = 11。散列地址11为空，所以将关键字27插入到散列地址11的位置。

散列表：[ , 01, , 20, , 56, , , , 87, 27, 29, , 13, , 15, , , ]

9. 将第九个关键字69插入散列表中，计算散列地址h(69) = 69 % 17 = 4，此地址为空，所以将关键字69插入到散列地址4的位置。

散列表：[ , 01, , 20, 69, 56, , , , 87, 27, 29, , 13, , 15, , , ]

10. 将第十个关键字9插入散列表中，计算散列地址h(9) = 9 % 17 = 9，此地址为空，所以将关键字9插入到散列地址9的位置。

散列表：[ , 01, , 20, 69, 56, , , 9, 87, 27, 29, , 13, , 15, , , ]

11. 将第十一个关键字10插入散列表中，计算散列地址h(10) = 10 % 17 = 10，此地址已被占用，使用平方探测方法计算下一个可用的散列地址。

第一次平方探测：h(10) + 1^2 = 10 + 1 = 11。散列地址11已被占用，继续平方探测。

第二次平方探测：h(10) + 2^2 = 10 + 4 = 14。散列地址14为空，所以将关键字10插入到散列地址14的位置。

散列表：[ , 01, , 20, 69, 56, , , 9, 87, 27, 29, , 13, , 15, , 10, , ]

12. 将第十二个关键字74插入散列表中，计算散列地址h(74) = 74 % 17 = 8，此地址为空，所以将关键字74插入到散列地址8的位置。

散列表：[ , 01, , 20, 69, 56, , , 9, 87, 27, 29, , 13, 74, 15, , 10, , ]

最终，该关键字序列构造的散列表为：[ , 01, , 20, 69, 56, , , 9, 87, 27, 29, , 13, 74, 15, , 10, , ]。

### 回答3：
散列表是一种常用的数据结构，用于快速查找和插入数据。根据给定的散列函数h(key) = key % 17和平方探测方法，我们需要构造一个包含关键字序列{29, 01, 13, 15, 56, 20, 87, 27, 69, 9, 10, 74}的散列表。散列表的地址空间为0到18。

步骤如下：

1. 创建一个包含18个空槽的散列表。
2. 将关键字29插入散列表。
- 由于h(29) = 29 % 17 = 12，12号槽为空，将29插入该槽。
3. 将关键字01插入散列表。
- 由于h(01) = 01 % 17 = 1，1号槽为空，将01插入该槽。
4. 将关键字13插入散列表。
- 由于h(13) = 13 % 17 = 13，13号槽为空，将13插入该槽。
5. 将关键字15插入散列表。
- 由于h(15) = 15 % 17 = 15，15号槽为空，将15插入该槽。
6. 将关键字56插入散列表。
- 由于h(56) = 56 % 17 = 5，5号槽为空，将56插入该槽。
7. 将关键字20插入散列表。
- 由于h(20) = 20 % 17 = 3，3号槽为空，将20插入该槽。
8. 将关键字87插入散列表。
- 由于h(87) = 87 % 17 = 4，4号槽为空，将87插入该槽。
9. 将关键字27插入散列表。
- 由于h(27) = 27 % 17 = 10，10号槽为空，将27插入该槽。
10. 将关键字69插入散列表。
- 由于h(69) = 69 % 17 = 4，4号槽被占用，采用平方探测方法探测下一个位置。
- 探测到6号槽为空，将69插入该槽。
11. 将关键字9插入散列表。
- 由于h(9) = 9 % 17 = 9，9号槽为空，将9插入该槽。
12. 将关键字10插入散列表。
- 由于h(10) = 10 % 17 = 10，10号槽被占用，采用平方探测方法探测下一个位置。
- 探测到11号槽为空，将10插入该槽。
13. 将关键字74插入散列表。
- 由于h(74) = 74 % 17 = 8，8号槽为空，将74插入该槽。

最终构造的散列表如下所示：
0：空
1：01
2：空
3：20
4：87
5：56
6：69
7：27
8：74
9：9
10：10
11：空
12：29
13：13
14：空
15：15
16：空
17：空
18：空

这样，我们成功地将关键字序列构造为了一个散列表。

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

首先，根据散列函数 H(key)=key%17，可以得到散列表的地址空间为 0 到 16，共 17 个位置。

接下来，采用平方探测方法解决冲突，即当关键字 key 在 H(key) 处产生冲突时，依次检查 H(key)+1，H(key)+4，H(key)+9，H(key)+16，...，直到找到一个空位置或者遍历完所有位置。其中，平方探测的步长为 i^2，即第一次探测步长为 1，第二次为 4，第三次为 9，以此类推。

下面是具体的构造过程：

1. 将散列表初始化为空表。
2. 将第一个关键字 29 插入表中，计算出其散列地址为 H(29)=12，将其插入散列表中。
3. 将第二个关键字 01 插入表中，计算出其散列地址为 H(01)=1，将其插入散列表中。
4. 将第三个关键字 13 插入表中，计算出其散列地址为 H(13)=13，将其插入散列表中。
5. 将第四个关键字 15 插入表中，计算出其散列地址为 H(15)=15，将其插入散列表中。
6. 将第五个关键字 56 插入表中，计算出其散列地址为 H(56)=5，将其插入散列表中。
7. 将第六个关键字 20 插入表中，计算出其散列地址为 H(20)=3，将其插入散列表中。
8. 将第七个关键字 87 插入表中，计算出其散列地址为 H(87)=4，将其插入散列表中。
9. 将第八个关键字 27 插入表中，计算出其散列地址为 H(27)=10，将其插入散列表中。
10.将第九个关键字 69 插入表中，计算出其散列地址为 H(69)=4，产生冲突，进行平方探测，依次检查 H(69)+1=5，H(69)+4=8，H(69)+9=13，找到空位置，将其插入散列表中。
11.将第十个关键字 9 插入表中，计算出其散列地址为 H(9)=9，将其插入散列表中。
12.将第十一个关键字 10 插入表中，计算出其散列地址为 H(10)=10，将其插入散列表中。
13.将第十二个关键字 74 插入表中，计算出其散列地址为 H(74)=8，产生冲突，进行平方探测，依次检查 H(74)+1=9，H(74)+4=12，H(74)+9=1，H(74)+16=4，H(74)+25=13，找到空位置，将其插入散列表中。

最终得到的散列表为：

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

其中，第一列为散列地址，第二列为插入的关键字。

平均查找长度（ASL）是指查找一个关键字时，需要访问的散列表中的位置数的期望值。对于本题，可以通过统计访问每个位置的次数来计算平均查找长度。具体计算方法如下：

1. 对于每个关键字，计算其访问的位置数，累加到总的访问次数中。
2. 将总的访问次数除以关键字的个数，即可得到平均查找长度。

根据上述方法，可以得到各个关键字的访问次数如下：

29: 1
01: 1
13: 1
15: 1
56: 1
20: 1
87: 1
27: 1
69: 3
9: 1
10: 1
74: 5

计算总的访问次数为 16，关键字的个数为 12，因此平均查找长度为 16/12 = 1.33。

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