2. 考研
  3. 在含有15个结点的平衡二叉树上，查找关键字为28(存在该结点)的结点，则依次比较的关键字有可能是( )。

在含有15个结点的平衡二叉树上，查找关键字为28(存在该结点)的结点，则依次比较的关键字有可能是( )。

admin2016-03-29  65
问题 在含有15个结点的平衡二叉树上，查找关键字为28(存在该结点)的结点，则依次比较的关键字有可能是(    )。
选项 A、30，36
B、38，48，28
C、48，18，38，28
D、60，30，50，40，38，36
答案C
解析 设Ni表示深度为h的平衡二叉树中含有的最少结点数，有：
    N0=0，N1=1，N2=2；
    计算的公式为：
    Nh=Nh-1+Nh-2+1；
    N3=N2+N1+1=4；
    N4=N3+N2+1=7；
    N5=N4+N3+1=12；
    N6=N5+N4+1=20＞15。
    也就是说，高度为6的平衡二叉树最少有20个结点，因此15个结点的平衡二叉树的高度为5，而最小叶子结点的层数为3，所以选项D错误。

    选项A在查找30后，指针应该指向左孩子，而不是右孩子；选项B与选项A存在同样的问题，因而选项A、B错误。而选项C的查找路径如下图所示：
转载请注明原文地址:https://jikaoti.com/ti/6OfjFFFM
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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