2. 考研
  3. 下列说法中，正确的是( )。 Ⅰ．具有10个叶子结点的二叉树中有9个度为2的结点 Ⅱ．设高度为5的二叉树上只有度为0和度为2的结点，则该二叉树巾所包含的结点数至少为9 Ⅲ．一棵完全二叉树上有1001个结点，则可知叶子结点的个数

下列说法中，正确的是( )。 Ⅰ．具有10个叶子结点的二叉树中有9个度为2的结点 Ⅱ．设高度为5的二叉树上只有度为0和度为2的结点，则该二叉树巾所包含的结点数至少为9 Ⅲ．一棵完全二叉树上有1001个结点，则可知叶子结点的个数

admin2019-12-10  29
问题 下列说法中，正确的是(    )。
    Ⅰ．具有10个叶子结点的二叉树中有9个度为2的结点
    Ⅱ．设高度为5的二叉树上只有度为0和度为2的结点，则该二叉树巾所包含的结点数至少为9
    Ⅲ．一棵完全二叉树上有1001个结点，则可知叶子结点的个数为501个
    Ⅳ．高度为h的完全二叉树最少有2h个结点
选项 A、仅Ⅰ、Ⅱ
B、仅Ⅱ、Ⅲ、Ⅳ
C、仅Ⅰ、Ⅲ、Ⅳ
D、仅Ⅰ、Ⅱ、Ⅲ
答案D
解析 Ⅰ：二叉树叶子结点的个数比度为2的结点的个数多1，故I正确。
    总结：这个性质在选择题中常有体现，并且需要灵活运用。比如题目可能问，二叉树中总的结点数为n，则树中空指针的个数是多少?我们可以将所有的空指针看作叶子结点，则图中原有的所有结点都成了双分支结点。因此可得空指针域的个数为树中所有结点个数加1，即n+1个。
    这个性质还可以扩展，即在一棵度为m的树中，度为1的结点数为n1，度为2的结点数为n2……度为m的结点数为nm，则叶子结点数n0=1+n2+2n3+…+(m-1)nm。推导过程如下：
    总结点=-n0+n1+n2+n3+…+nm    ①
    总分支数=1×n1+2×n2+…+m×nm(度为m的结点引出m条分支)   ②
    总分支数=总结点数-1   ③
    将式①和式②代入式③并化简得
n0=1+n2+2n3+…+(m-1)nm
    Ⅱ：最少结点的情况应该是除根结点层只有1个结点外，其余4层都有2个结点，因此结点总数为2×(5-1)+1=9。如图6-4所示，故Ⅱ正确。

    Ⅲ：由二叉树的性质可知：n0=n2+1，且完全二叉树度为1的结
点个数要么为0，要么为1。又因为二叉树的总结点个数n=n0+n1+n2。将n0=n2+1代入，可得n=2n0+n1-1；由于n=1001，得到2n0=1002+n1。
    ①当n1=1时，无解。
    ②当n1=0时，可解得n0=501
    故Ⅲ正确。
    Ⅳ：高度为h的完全二叉树中，第1层～第h-1层构成一个高度为h-1的满二叉树，结点个数为2h-1-1。第h层至少有一个结点，所以最少的结点个数=(2h-1-1)+1=2h-1，故Ⅳ错误。
转载请注明原文地址:https://kaotiyun.com/show/wm3i777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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