题14

题14

题目

Q:具有 12 个关键字的有序表中, 对每个关键字的查找概率相同, 折半查找算法查找成功的平均查找长度为 ( ) ,折半查找查找失败的平均查找长度为 ( )
A.
B.
C.
D.

分析

A:12个关键字，每个匹配成功的概率应该是相同的, 所以查找成功的平均查找长度应该是
我这里的公式用错了，ASL的公式是对应的树的高度的加权平均
我这个算法应该是ASL的算法吧，查找的平均长度是ASL这个公式的含义吗
看了答案以后，ASL就是查找成功的加权平均

解

A、D
假设有序表中元素为 ,不难画出对它进行折半查找的判定树如下图所示,圆圈是查找成功结点,方形是虚构的查找失败结点。从而可以求出查找成功的 37/12,查找失败的 。

注意
对于本类题目,应先根据所给 的值,画出如上图所示的折半查找判定树。
另外,查找失败结点的 ASL 不是到图中的方形结点, 而是到方形结点上一层的圆形结点。
其中，高度为4的，查找成功的结点有5个，所以是