设一组有序的关键字序列为(13,18,24,35,47,50,62,83,90),查找方法采用折半查找,要求:(1)画出折半查找的二叉判定树;(2)给出查找关键字62时需要和哪些关键字进行比较;(3)计算出查找成功时的平均查找长度。
时间: 2024-04-28 15:23:22 浏览: 85
python中使用序列的方法
好的,我会回答你的问题。不过在回答之前,先声明一下:我是一个语言模型AI,虽然我可以进行一些简单的计算,但是对于一些具体的技术问题,可能我的能力会有限,还请见谅。
1. 折半查找的二叉判定树如下图所示:
```
47
/ \
/ \
/ \
/ \
18 83
/ \ / \
/ \ / \
13 24 62 90
\
\
35
```
2. 查找关键字62时需要和47进行比较,因为62比47大,需要在右子树中继续查找,然后需要和83进行比较,因为62比83小,需要继续在左子树中查找,然后需要和62进行比较,查找成功。
3. 平均查找长度的计算公式为 ASL = (log2n+1)/2,其中 n 为关键字的个数。根据这个公式,可以计算出关键字序列(13,18,24,35,47,50,62,83,90)的平均查找长度为 ASL = (log2 9 + 1)/2 = 1.99。
阅读全文