对长度为11的有序表(升序),给出折半查找的判定树,给出等概率情况下的平均查找长度。
时间: 2024-03-23 20:42:40 浏览: 49
下面是长度为11的有序表的折半查找的判定树:
```
6
/ \
/ \
/ \
3 9
/ \ / \
/ \ / \
1 4 7 10
/ \ / \
/ \ / \
2 5 8 11
```
对于等概率情况下的平均查找长度,可以使用以下公式进行计算:
$$ ASL = \sum_{i=1}^{n} p_i \cdot l_i $$
其中,$ASL$ 表示平均查找长度,$p_i$ 表示查找第 $i$ 个元素的概率,$l_i$ 表示查找第 $i$ 个元素时需要比较的关键字个数。
在这个问题中,$n=11$,$p_i=\frac{1}{11}$。对于 $l_i$,我们可以通过观察判定树得到:
- 查找第1个元素时需要比较1次;
- 查找第2个元素时需要比较2次;
- 查找第3个元素时需要比较2次;
- 查找第4个元素时需要比较3次;
- 查找第5个元素时需要比较3次;
- 查找第6个元素时需要比较3次;
- 查找第7个元素时需要比较3次;
- 查找第8个元素时需要比较4次;
- 查找第9个元素时需要比较4次;
- 查找第10个元素时需要比较4次;
- 查找第11个元素时需要比较4次。
因此,平均查找长度为:
$$ ASL = \frac{1}{11}(1+2+2+3+3+3+3+4+4+4+4) = \frac{24}{11} \approx 2.18 $$
因此,在等概率情况下,折半查找长度为11的有序表的平均查找长度为约2.18。
阅读全文