题7

题7

题目

Q:折半查找过程所对应的判定树是一棵 ( ).
A. 最小生成树
B. 平衡二又树
C. 完全二叉树
D. 满二叉树

分析

A:平衡二叉树是指左右子树的高度差不超过 1 的二叉树, 完全二叉树是指除了最后一层外, 其他层的结点数都达到最大, 满二叉树是指每一层的结点数都达到最大, 折半查找过程所对应的判定树是一棵完全二叉树。

解

B
A 显然排除。对于选项 ,考点精析示例中的判定树就不是完全二叉树。
由选项 也可排除选项 ,且满二叉树对结点数有要求。只可能选 。
事实上,由折半查找的定义不难看出,每次把一个数组从中间结点分割时, 总是把数组分为结点数相差最多不超过 1 的两个子数组, 从而使得对应的判定树的两棵子树高度差的绝对值不超过 1 , 所以应是平衡二叉树。