设有一组关键字 { 29,01, 13,15,56,20,87,27,69,9,10,74 },散列函数为 H(key)=key%17,采用平方探测方法解决冲突。试在 0 到 18 的散列地址空间中对该关键字序列构造散列表,则成功查找的平均查找长度为
时间: 2024-06-06 13:05:34 浏览: 111
首先,我们需要计算每个关键字在散列表中的地址:
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。
阅读全文