设哈希表的地址范围为0～17，哈希函数为：H（key）=key%16。用线性探测法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49），构造哈希表，试回答下列问题：假定每个关键字的查找概率相等，求查找成功时的平均查找长度。

好的，根据输入的关键字序列，我们先通过哈希函数计算它们在哈希表中的地址，如下所示：

10→10，24→8，32→0，17→1，31→15，30→14，46→14，47→15，40→8，63→15，49→1

其中，有三组关键字产生了冲突，即(31, 47)，(30, 46)，(49, 17)。对于每组冲突的关键字，我们采用线性探测法来解决，即从产生冲突的位置开始，依次往后查找，直到找到一个空闲位置为止。因此，最终的哈希表如下所示：

0 32
1 17
2
3
4
5
6
7
8 24 40
9
10 10
11
12
13
14 30 46
15 31 47 63

接下来，我们来计算查找成功时的平均查找长度。由于每个关键字的查找概率相等，所以平均查找长度可以用所有关键字的查找长度之和除以关键字总数来表示。具体地，我们可以先计算出每个关键字在哈希表中的查找长度，然后将它们相加并除以关键字总数即可。如下所示：

10：1
24：1
32：1
17：1
31：2
30：1
46：2
47：3
40：1
63：3
49：3

平均查找长度 = (1+1+1+1+2+1+2+3+1+3) / 11 = 18 / 11 ≈ 1.64

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

相关问题

设哈希表的地址范围为0～17，哈希函数为：h（key）=key%16。用线性探测法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49），构造哈希表，试回答下列

### 回答1：
问题：

1. 哈希表中哪些位置被占用了？

答：哈希表中被占用的位置为：、1、2、3、4、5、6、7、8、9、10、11、12、13、14、15、16。

2. 哈希表中哪些位置发生了冲突？

答：哈希表中发生冲突的位置为：1、2、3、4、5、6、7、8、9、10、11、12、13、14、15、16。

3. 哈希表中每个关键字的存储位置是什么？

答：关键字10存储在位置10，关键字24存储在位置8，关键字32存储在位置，关键字17存储在位置1，关键字31存储在位置15，关键字30存储在位置14，关键字46存储在位置14（线性探测法向后查找），关键字47存储在位置15（线性探测法向后查找），关键字40存储在位置8（线性探测法向后查找），关键字63存储在位置15（线性探测法向后查找），关键字49存储在位置1（线性探测法向后查找）。

4. 哈希表中是否存在空闲位置？

答：哈希表中不存在空闲位置。

### 回答2：
1. 哈希表的长度是多少？
哈希表的长度为18，地址范围是0~17。

2. 如何计算关键字10的哈希值？
根据哈希函数h(key) = key % 18，把关键字10带入计算是h(10) = 10 % 18 = 10。

3. 插入关键字10时，哈希表的对应位置是否已经被占用？
插入关键字10时，哈希表的位置10还没有被占用。

4. 插入关键字10时，哈希表的位置10是否是其最终位置？
插入关键字10时，哈希表的位置10是其最终位置。

5. 插入关键字24时，哈希表的对应位置是否已经被占用？
插入关键字24时，哈希表的位置6还没有被占用。

6. 插入关键字24时，哈希表的位置6是否是其最终位置？
插入关键字24时，哈希表的位置6是其最终位置。

7. 插入关键字32时，哈希表的对应位置是否已经被占用？
插入关键字32时，哈希表的位置14还没有被占用。

8. 插入关键字32时，哈希表的位置14是否是其最终位置？
插入关键字32时，哈希表的位置14是其最终位置。

9. 插入关键字17时，哈希表的对应位置是否已经被占用？
插入关键字17时，哈希表的位置17还没有被占用。

10. 插入关键字17时，哈希表的位置17是否是其最终位置？
插入关键字17时，哈希表的位置17是其最终位置。

11. 插入关键字31时，哈希表的对应位置是否已经被占用？
插入关键字31时，哈希表的位置13还没有被占用。

12. 插入关键字31时，哈希表的位置13是否是其最终位置？
插入关键字31时，哈希表的位置13是其最终位置。

13. 哈希表中最终插入了几个关键字？
哈希表中最终插入了11个关键字。

14. 哈希表中位置为40的槽是否被占用？
哈希表中位置为40的槽没有被占用。

15. 哈希表中位置为40的槽是否可以插入关键字？
哈希表中位置为40的槽可以插入关键字。

16. 哈希表中位置为49的槽是否被占用？
哈希表中位置为49的槽没有被占用。

17. 哈希表中位置为49的槽是否可以插入关键字？
哈希表中位置为49的槽可以插入关键字。

18. 构造的哈希表如下：
0: 空
1: 空
2: 空
3: 空
4: 空
5: 空
6: 24
7: 空
8: 空
9: 10
10: 40
11: 空
12: 30
13: 31
14: 32
15: 17
16: 空
17: 63
18: 46
19: 47
20: 49

注意：这个哈希表是在处理冲突时使用线性探测法构建的，所以有的位置可能不是最初计算的哈希值，而是后续线性探测的结果。

### 回答3：
1. 构造哈希表的过程为：

初始时，将哈希表中所有的地址都设为空。

首先，将关键字10插入哈希表中，由于h(10)=10，在哈希表中的地址10为空，所以将10插入该地址。

接下来，插入关键字24，由于h(24)=24，地址24为空，将24插入该地址。

再插入关键字32，h(32)=32，地址32为空，将32插入。

对于关键字17，h(17)=17，但地址17不为空，发生冲突。根据线性探测法，从地址17开始逐个往后探测，直到找到一个空的地址，插入关键字17。

依次插入关键字31、30、46、47、40、63、49，根据哈希函数计算地址，并遇到冲突时使用线性探测法将关键字插入对应的地址。最终构造出的哈希表为：

0: 40
1: 63
2: 32
3: 17
4: 47
5: 30
6: 10
7: 49
8:
9:
10: 24
11: 46
12:
13:
14: 31
15:
16:
17:

2. 这个哈希表中有多少个关键字？

根据构造的哈希表，可以看到有11个关键字已经插入成功。

3. 使用线性探测法处理冲突时，最多需要探测几次？

由于哈希表的地址范围是0～17，而输入的关键字序列中最大的关键字是63，所以最多需要探测的次数为17次。

4. 如果输入的关键字序列中有关键字73，应该将其插入哈希表的哪个位置？

根据哈希函数h(key)=key%18，可计算出关键字73对应的地址为73%18=1。因此，将关键字73插入哈希表的位置为地址1。但由于该地址已经被关键字63占用，发生冲突。根据线性探测法，需要从地址1开始逐个往后探测，直到找到一个空的地址，插入关键字73。

设哈希表的地址范围为0～17，哈希函数为：H（key）=key%16。用线性探测法处理冲突，输入关键字序列：（10，24，32，17，63，30，46，47，40，31，49），若查找31需要比较的次数是几次？

根据哈希函数 H(key) = key % 18，将输入的关键字序列转换成哈希表的下标序列为：(10, 6, 14, 17, 9, 12, 10, 11, 4, 13, 15)。其中，10 和 17 发生了冲突，需要进行线性探测。因为是线性探测，所以依次查找的下标为 10，11，12，13，14，15，16，17。在经过 5 次查找后，找到了关键字 31，所以查找 31 需要比较的次数是 5 次。