问题
单项选择题
长度为12的按关键字排序的查找表采用顺序组织方式。若采用二分查找方法，则在等概率情况下，查找失败时的ASL值是( )。
A．37/12
B．62/13
C．39/12
D．49/13
答案
参考答案：D
解析： 二分查找的判定树应为平衡树，如图13-5所示。
当查找到的分支为空时，查找失败。在5个叶子节点10个分支方向可能失败，3个单分支节点3个分支方向可能失败。所以查找失败平均查找长度ASL为(10×4+3×3)/13=49/13，见图13-5。