第 9 题
具有 12 个关键字的有序表中，对每个关键字的查找概率相同，折半查找查找成功和查找失败的平均查找长度依次为（ ）。
A. 37/12,49/13 B. 35/12,39/13 C. 37/13,49/13 D. 37/12,49/12
[tag_link]
正确答案：A
对于有序表折半查找，平均查找长度（ASL）需通过二叉判定树计算。 成功查找的 ASL 是找到每个关键字所需比较次数的平均值，失败查找的 ASL 是查找失败时比较次数的平均值。
首先构建 12 个关键字的判定树。 根节点为关键字 6（深度 1），左子树包含关键字 1~5，右子树包含关键字 7~12。 递归划分得到各关键字深度（即比较次数）：关键字 1、4、7、11 深度 3； 关键字 2、5、8、10、12 深度 4； 关键字 3、9 深度 2； 关键字 6 深度 1。 比较次数总和为 37，成功 ASL = 37/12。
失败查找对应判定树的外部节点，共 13 个。 外部节点的比较次数等于其父节点的深度：深度为 3 的父节点（关键字 1、4、7）对应 3 个外部节点，各比较 3 次； 深度为 4 的父节点（关键字 2、5、8、10、12）对应 10 个外部节点，各比较 4 次。 比较次数总和为 3×3 + 4×10 = 49，失败 ASL = 49/13。
因此，成功和失败的平均查找长度依次为 37/12 和 49/13，对应选项 A。