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