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

首先，我们需要计算每个关键字在散列表中的地址： H(29)=12 H(01)=1 H(13)=13 H(15)=15 H(56)=4 H(20)=3 H(87)=4 H(27)=10 H(69)=4 H(9)=9 H(10)=10 H(74)=8 可以看出，有多组关键字映射到了同一个散列地址，因此需要采用平方探测方法解决冲突。 接下来，我们按照平方探测方法将关键字插入散列表中。具体过程如下： 1. 将 29 插入散列表，位置为 12。 2. 将 01 插入散列表，位置为 1。 3. 将 13 插入散列表，位置为 13。 4. 将 15 插入散列表，位置为 15。 5. 将 56 插入散列表，位置为 4。 6. 将 20 插入散列表，位置为 3。 7. 将 87 插入散列表，发现位置 4 已经被占用，因此进行平方探测，插入位置为 2。 8. 将 27 插入散列表，位置为 10。 9. 将 69 插入散列表，发现位置 4 和位置 2 都已经被占用，因此进行平方探测，插入位置为 5。 10.将 9 插入散列表，位置为 9。 11.将 10 插入散列表，发现位置 10 已经被占用，因此进行平方探测，插入位置为 11。 12.将 74 插入散列表，发现位置 8 已经被占用，因此进行平方探测，插入位置为 0。 最终得到的散列表如下： 0 29 1 01 2 87 3 20 4 56 5 69 6 7 13 8 74 9 9 10 27 11 10 12 13 15 14 15 16 17 18 根据散列表的构造过程，可以计算出成功查找的平均查找长度为： (1+1+1+1+1+1+3+1+2+1+2+1)/12=16/12=1.33 因此，成功查找的平均查找长度为 1.33。

### 回答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。