设有一组关键字 { 29,01, 13,15,56,20,87,27,69,9,10,74 },散列函数为 H(key)=key%17,采用平方探测方法解决冲突。试在 0 到 18 的散列地址空间中对该关键字序列构造散列表,则成功查找的平均查找长度为 __
时间: 2024-01-13 14:03:24 浏览: 182
首先,根据散列函数 H(key)=key%17,可以得到散列表的地址空间为 0 到 16,共 17 个位置。
接下来,采用平方探测方法解决冲突,即当关键字 key 在 H(key) 处产生冲突时,依次检查 H(key)+1,H(key)+4,H(key)+9,H(key)+16,...,直到找到一个空位置或者遍历完所有位置。其中,平方探测的步长为 i^2,即第一次探测步长为 1,第二次为 4,第三次为 9,以此类推。
下面是具体的构造过程:
1. 将散列表初始化为空表。
2. 将第一个关键字 29 插入表中,计算出其散列地址为 H(29)=12,将其插入散列表中。
3. 将第二个关键字 01 插入表中,计算出其散列地址为 H(01)=1,将其插入散列表中。
4. 将第三个关键字 13 插入表中,计算出其散列地址为 H(13)=13,将其插入散列表中。
5. 将第四个关键字 15 插入表中,计算出其散列地址为 H(15)=15,将其插入散列表中。
6. 将第五个关键字 56 插入表中,计算出其散列地址为 H(56)=5,将其插入散列表中。
7. 将第六个关键字 20 插入表中,计算出其散列地址为 H(20)=3,将其插入散列表中。
8. 将第七个关键字 87 插入表中,计算出其散列地址为 H(87)=4,将其插入散列表中。
9. 将第八个关键字 27 插入表中,计算出其散列地址为 H(27)=10,将其插入散列表中。
10.将第九个关键字 69 插入表中,计算出其散列地址为 H(69)=4,产生冲突,进行平方探测,依次检查 H(69)+1=5,H(69)+4=8,H(69)+9=13,找到空位置,将其插入散列表中。
11.将第十个关键字 9 插入表中,计算出其散列地址为 H(9)=9,将其插入散列表中。
12.将第十一个关键字 10 插入表中,计算出其散列地址为 H(10)=10,将其插入散列表中。
13.将第十二个关键字 74 插入表中,计算出其散列地址为 H(74)=8,产生冲突,进行平方探测,依次检查 H(74)+1=9,H(74)+4=12,H(74)+9=1,H(74)+16=4,H(74)+25=13,找到空位置,将其插入散列表中。
最终得到的散列表为:
```
0:
1: 01
2:
3: 20
4: 87 69
5: 56
6:
7: 29
8: 74
9: 9
10:27
11:
12:29
13:13 15
14:
15:
16:
```
其中,第一列为散列地址,第二列为插入的关键字。
平均查找长度(ASL)是指查找一个关键字时,需要访问的散列表中的位置数的期望值。对于本题,可以通过统计访问每个位置的次数来计算平均查找长度。具体计算方法如下:
1. 对于每个关键字,计算其访问的位置数,累加到总的访问次数中。
2. 将总的访问次数除以关键字的个数,即可得到平均查找长度。
根据上述方法,可以得到各个关键字的访问次数如下:
```
29: 1
01: 1
13: 1
15: 1
56: 1
20: 1
87: 1
27: 1
69: 3
9: 1
10: 1
74: 5
```
计算总的访问次数为 16,关键字的个数为 12,因此平均查找长度为 16/12 = 1.33。
因此,成功查找的平均查找长度为 1.33。
阅读全文