2. 计算机
  3. 在某个二叉查找树(即二叉排序树)中进行查找时，效率最差的情形是该二叉查找树是( )。

在某个二叉查找树(即二叉排序树)中进行查找时，效率最差的情形是该二叉查找树是( )。

admin2016-05-10  11
问题 在某个二叉查找树(即二叉排序树)中进行查找时，效率最差的情形是该二叉查找树是(   )。
选项 A、完全二叉树
B、平衡二叉树
C、单枝树
D、满二叉树
答案C
解析 本题考查数据结构基础知识。非空二叉查找树中的结点分布特点是左子树中的结点均小于树根，右子树中的结点均大于树根。因此，在二叉查找树中进行查找时，走了一条从树根出发到所找到结点的路径，到达一个空的子树则表明查找失败。根据定义，高度为h的满二叉树中有2h一1个结点，每一层上的结点数都达到最大值。完全二叉树的最高层只要求结点先占据左边的位置。例如，高度为3的满二叉树如下图(a)所示，具有6个结点的完全二叉树如下图(b)所示。

在平衡二叉树中，任何一个结点的左子树高度与右子树高度之差的绝对值不大于1。单枝树中给每个结点只有1个子树。例如，具有3个结点的单枝树如下图所示。

    显然，在结点数确定后，二叉查找树的形态为单枝树时查找效率最差。
转载请注明原文地址:https://kaotiyun.com/show/7tRZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

软件设计师上午基础知识考试

软考中级

相关试题推荐
随机试题
最新回复(0)