有关键字序列147,7,29,11,16,92,22,8,3,散列函数h(key)=key mod 11,分别画出线性探测法和拉链法处理冲突得到的散列表,并分别计算查找成功和失败时的ASL
时间: 2023-10-08 11:05:39 浏览: 130
线性探测法和拉链法处理散列表冲突
5星 · 资源好评率100%
好的,我明白了。以下是回答:
对于散列函数h(key)=key mod 11和关键字序列147,7,29,11,16,92,22,8,3,我们可以构造出以下两个散列表:
1. 线性探测法处理冲突的散列表:
| | | | | 7 | | 8 | 3 | 11 | 16 | 92 | 22 | 29 | | | | | | | | |
|:-:|---|---|---|:-:|---|---|:-:|----|----|----|----|----|---|---|---|---|---|---|---|---|
| 0 | | | | | | | | | | | | | | | | | | | | |
| 1 | | | | | | | | | | | | | | | | | | | | |
| 2 | | | | | | | | | | | 22 | | | | | | | | | |
| 3 | | | | | | | | | | | | | | | | | | | | |
| 4 | | | | | | | | 16 | | | | | | | | | | | | |
| 5 | | | | | | | | | | | | | | | | | | | | |
| 6 | | | | | | | | | 92 | 3 | | | | | | | | | | |
| 7 | | | | | | 8 | | | | | | | | | | | | | | |
| 8 | | | | | | | | | | | | | | | | | | | | |
| 9 | | | | | | | | | | | | | | | | | | | | |
|10 |147| | | | | | | | | | | 29 | | | | | | | | |
其中,ASL(查找成功) = 2/9 = 0.222,ASL(查找失败) = (2*1 + 1*2 + 1*3)/9 = 8/9 = 0.889。
2. 拉链法处理冲突的散列表:
| | | | | | | | | | |
|:-:|-------|---------|---------|---------|----------|----------|------|---|-------|
| 0 | 11 | | | | | | | | |
| 1 | 92 -> | | | | | | | | |
| 2 | 22 -> | | | | | | | | |
| 3 | 3 | | | | | | | | |
| 4 | 16 | | | | | | | | |
| 5 | | | | | | | | | |
| 6 | | 29 -> 7 | | | | | | | |
| 7 | 8 | | | | | | | | |
| 8 | | | | | | | | | |
| 9 | | | | | | | | | |
|10 | 147 | | -> 92 -> | -> 3 | -> 11 -> | -> 16 -> | 7 -> | 8 | 22 -> |
其中,ASL(查找成功) = (1*1)/9 = 0.111,ASL(查找失败) = (1*1 + 1*2 + 1*2 + 1*2 + 2*3)/9 = 11/9 = 1.222。
希望这个回答能够帮到你!
阅读全文