题目
设散列表的地址范围为0~17,散列函数为:H(key) = key%16。用线性探测法处理冲突，输入关键字序列: (10, 24,32, 17,31,30,46, 47,40,63, 49),构造散列表，试回答下列问题:①画出散列表的示意图。②若查找关键字63,需要依次与哪些关键字进行比较?③若查找关键字60，需要依次与哪些关键字进行比较?④假定每个关键字的查找概率相等，求查找成功时的平均查找长度[1]。
设散列表的地址范围为0~17,散列函数为:
H(key) = key%16。用线性探测法处理冲突，输入关键字序列: (10, 24,32, 17,31,30,46, 47,40,63, 49),构造散列表，试回答下列问题:
①画出散列表的示意图。
②若查找关键字63,需要依次与哪些关键字进行比较?
③若查找关键字60，需要依次与哪些关键字进行比较?
④假定每个关键字的查找概率相等，求查找成功时的平均查找长度[1]。
题目解答
答案
1）10%16=10,24%=8,32%10=0,17%16=1,31%16=15
30%16=14,46%16=14，47%16=15,40%16=8,
63%16=15,49%16=1,其中46，47，40，63，49需要向后寻找空位插入。散列图如下所示：
2）查找关键字63，63%16=15，应该先从15位置查起，由图可以知道63不在15位置上，因此需要往后查询，因此对比的关键字有：31，46，47，32，17
3）同理查找关键字60，60%16=12，12位置为空，所以查找结束，没有对比的关键字。
4）平均查找长度为
解析
步骤 1：计算散列值并处理冲突
根据散列函数 H(key) = key % 16，计算每个关键字的散列值，并使用线性探测法处理冲突。具体步骤如下：
- 10 % 16 = 10，直接放入位置10。
- 24 % 16 = 8，直接放入位置8。
- 32 % 16 = 0，直接放入位置0。
- 17 % 16 = 1，直接放入位置1。
- 31 % 16 = 15，直接放入位置15。
- 30 % 16 = 14，直接放入位置14。
- 46 % 16 = 14，位置14已满，向后探测，放入位置15。
- 47 % 16 = 15，位置15已满，向后探测，放入位置16。
- 40 % 16 = 8，位置8已满，向后探测，放入位置9。
- 63 % 16 = 15，位置15已满，向后探测，放入位置17。
- 49 % 16 = 1，位置1已满，向后探测，放入位置2。
步骤 2：绘制散列表
根据上述计算结果，绘制散列表如下：
```
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
32 17 49 0 0 0 0 0 24 40 10 0 0 0 30 31 47 63
```
步骤 3：查找关键字63
查找关键字63，计算散列值63 % 16 = 15，从位置15开始查找，依次与31，46，47，63进行比较。
步骤 4：查找关键字60
查找关键字60，计算散列值60 % 16 = 12，从位置12开始查找，位置12为空，查找结束，没有比较的关键字。
步骤 5：计算平均查找长度
平均查找长度为所有关键字查找长度之和除以关键字总数。根据散列表，计算每个关键字的查找长度，然后求平均值。
```
关键字：10, 24, 32, 17, 31, 30, 46, 47, 40, 63, 49
查找长度：1, 1, 1, 1, 1, 1, 2, 3, 2, 4, 2
总查找长度：1 + 1 + 1 + 1 + 1 + 1 + 2 + 3 + 2 + 4 + 2 = 20
平均查找长度：20 / 11 ≈ 1.82
```
根据散列函数 H(key) = key % 16，计算每个关键字的散列值，并使用线性探测法处理冲突。具体步骤如下：
- 10 % 16 = 10，直接放入位置10。
- 24 % 16 = 8，直接放入位置8。
- 32 % 16 = 0，直接放入位置0。
- 17 % 16 = 1，直接放入位置1。
- 31 % 16 = 15，直接放入位置15。
- 30 % 16 = 14，直接放入位置14。
- 46 % 16 = 14，位置14已满，向后探测，放入位置15。
- 47 % 16 = 15，位置15已满，向后探测，放入位置16。
- 40 % 16 = 8，位置8已满，向后探测，放入位置9。
- 63 % 16 = 15，位置15已满，向后探测，放入位置17。
- 49 % 16 = 1，位置1已满，向后探测，放入位置2。
步骤 2：绘制散列表
根据上述计算结果，绘制散列表如下：
```
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
32 17 49 0 0 0 0 0 24 40 10 0 0 0 30 31 47 63
```
步骤 3：查找关键字63
查找关键字63，计算散列值63 % 16 = 15，从位置15开始查找，依次与31，46，47，63进行比较。
步骤 4：查找关键字60
查找关键字60，计算散列值60 % 16 = 12，从位置12开始查找，位置12为空，查找结束，没有比较的关键字。
步骤 5：计算平均查找长度
平均查找长度为所有关键字查找长度之和除以关键字总数。根据散列表，计算每个关键字的查找长度，然后求平均值。
```
关键字：10, 24, 32, 17, 31, 30, 46, 47, 40, 63, 49
查找长度：1, 1, 1, 1, 1, 1, 2, 3, 2, 4, 2
总查找长度：1 + 1 + 1 + 1 + 1 + 1 + 2 + 3 + 2 + 4 + 2 = 20
平均查找长度：20 / 11 ≈ 1.82
```