设哈希表的地址范围为0~13,哈希函数为:H(key)=key%12。用线性探测法处理冲突,输入关键字序列:(10,24,32,17,31,30,46),构造哈希表,查找关键字46,需要比较( )次才能找到。
时间: 2024-03-26 13:37:11 浏览: 227
好的,让我算一下。首先,按照哈希函数将关键字序列插入哈希表中,得到如下表格:
|地址|关键字|
|---|---|
|0|30|
|1|31|
|2|32|
|3|10|
|4|24|
|5|17|
|6|46|
|7||
|8||
|9||
|10||
|11||
|12||
其中,关键字30、31、32、10、24、17、46分别被插入了地址0、1、2、3、4、5、6处。接下来进行查找关键字46,由于它被插入的地址是6,因此先比较地址6处的关键字,发现就是要找的关键字46,所以只需要比较1次就能找到。
因此,查找关键字46需要比较1次才能找到。
相关问题
设哈希表的地址范围为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 次。
阅读全文