设有一组关键字{29,01,13,15,56,20,87,27,69,9,10,74},散列函数为:H(key)=key % 17,采用线性测方法解决冲突。试在0到18的散列地址空间中对该关键字序列构造散列表,并计算成功查找的平均查找度。手写过程
时间: 2023-06-23 08:10:20 浏览: 70
首先,根据散列函数 H(key) = key % 17,将关键字映射到 0 到 16 的散列地址空间中。
关键字 | 散列地址
-------|--------
29 | 12
01 | 1
13 | 13
15 | 15
56 | 5
20 | 3
87 | 4
27 | 10
69 | 4
9 | 9
10 | 10
74 | 8
接下来,采用线性探测法解决冲突。对于一个关键字 key,如果它的散列地址 H(key) 已经被占用,那么就从 H(key)+1 开始依次往下查找,直到找到一个空闲的散列地址为止。具体地,对于关键字 69,由于它的散列地址 4 已经被关键字 87 占用了,所以需要从 5 开始往下查找。查找的顺序为:5 → 6 → 7 → 8 → 9,最终找到空闲的散列地址 9,将关键字 69 存入该位置。
下面是构造好的散列表:
散列地址 | 关键字
--------|-------
0 |
1 | 01
2 |
3 | 20
4 | 87
5 | 56
6 |
7 |
8 | 74
9 | 69
10 | 27, 10
11 |
12 | 29
13 | 13
14 |
15 | 15, 9
16 |
最后,计算成功查找的平均查找度。假设要查找关键字 k,那么平均查找度可以表示为:
ASL = (1/n) * [Σ(di+1)],其中 n 是关键字的总数,di 是查找到第 i 个关键字时所需的探测次数。
根据上表中的散列表,关键字总数为 12。对于每个关键字,我们都可以计算出查找时所需的探测次数。例如,查找关键字 87 时需要探测 0 次,查找关键字 69 时需要探测 1 次,查找关键字 10 时需要探测 0 次。将所有的探测次数加起来得到 12,再加上关键字总数 12,得到的结果是 24。因此,成功查找的平均查找度为:
ASL = (1/12) * (24) ≈ 2
平均查找度为 2,意味着在散列表中查找一个关键字平均只需要进行两次比较。