2. 计算机
  3. 一个具有967个结点的完全二叉树，其叶子结点个数为(22)。

一个具有967个结点的完全二叉树，其叶子结点个数为(22)。

admin2015-06-03  37
问题 一个具有967个结点的完全二叉树，其叶子结点个数为(22)。
选项 A、483
B、484
C、485
D、486
答案B
解析 假设n0为度为0的结点总数(即叶子结点数)，n1为度为1的结点总数，n2为度为
2的结点总数，由二叉树的性质可知
    n=n0+n1+n2    (1)
    其中n为完全二叉树的结点总数。又根据二叉树的定义，有
    n=n1+2×n2+1    (2)
    由公式(1)和(2)可得
    n2=n0-1    (3)
    把(3)式代入(1)式，可得
    n=2n0+n1-1    (4)
    根据本题的条件，有967=2n0+n11-1，即968-n1=2n0。现在只需确定n1就能求得n0了。根据完全二叉树的定义，一棵K层的完全二叉树，上面的K-1层为满二叉树，最后一层的结点都靠左边，又因为满二叉树中只有度为0和度为2的结点，没有度为1的结点，这也就意味着在完全二叉树中，只有倒数第二层，才可能有度为1的结点，这就限制了完全二叉树只可能有0个或1个度为1的结点，对于968-n1=2n0，n1显然为0，所以n0=968／2=484。
转载请注明原文地址:https://www.kaotiyun.com/show/F3RZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

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

软考中级

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