设有一组关键字{29,01,13,15,56,20,87,27,69,9,10,74},散列函数为:H(key)=key 00000000% 17,采用线性测方法解决冲突。试在0到18的散列地址空间中对该关键字序列构造散列表,并计算成功查找的平均查找度。手写过程在0到18的散列地址空间中
时间: 2023-06-20 14:08:11 浏览: 160
首先,我们需要明确散列表的大小为18(0到17共18个地址)。
然后,根据散列函数H(key)=key 00000000% 17,可以得到每个关键字的散列地址:
29:H(29) = 29 00000000 % 17 = 12
01:H(01) = 01 00000000 % 17 = 1
13:H(13) = 13 00000000 % 17 = 13
15:H(15) = 15 00000000 % 17 = 15
56:H(56) = 56 00000000 % 17 = 5
20:H(20) = 20 00000000 % 17 = 3
87:H(87) = 87 00000000 % 17 = 4
27:H(27) = 27 00000000 % 17 = 10
69:H(69) = 69 00000000 % 17 = 4
9:H(9) = 9 00000000 % 17 = 9
10:H(10) = 10 00000000 % 17 = 10
74:H(74) = 74 00000000 % 17 = 8
可以发现,有两个关键字(87和69)的散列地址相同,即发生了冲突。
根据线性探测方法,当发生冲突时,我们从当前位置开始依次往下寻找空闲的散列地址。因此,我们将87放在散列地址4的位置,将69放在散列地址5的位置,其他关键字按照散列地址直接放置。
最终,散列表如下:
0:
1:01
2:
3:20
4:87
5:56 69
6:
7:74
8:74
9:9
10:27 10
11:
12:29
13:13
14:
15:15
16:
接下来,我们需要计算成功查找的平均查找度(ASL)。
ASL的计算公式为:
ASL = (成功查找的所有关键字在散列表中的查找长度之和) / 成功查找的关键字数量
因此,我们需要先模拟查找每个关键字的过程,并记录查找长度,最后计算平均查找度。
以查找关键字69为例:
1. 根据散列函数H(key),计算出69的散列地址为5;
2. 在散列地址5的位置找到56,发现不是要查找的关键字;
3. 继续往下查找,找到69,成功查找;
4. 查找长度为2。
按照上述方式,模拟查找所有关键字,并记录查找长度,结果如下:
01:1
13:1
15:1
20:1
29:1
74:1
9:1
27:2
10:1
56:1
87:1
69:2
成功查找的关键字数量为12,所有关键字在散列表中的查找长度之和为13。因此,平均查找度为13/12=1.08。
因此,在本题中,成功查找的平均查找度为1.08。
阅读全文