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

admin2015-06-03 23

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

选项 A、483
B、484
C、485
D、486

答案B

解析假设n₀为度为0的结点总数(即叶子结点数)，n₁为度为1的结点总数，n₂为度为
2的结点总数，由二叉树的性质可知
n=n₀+n₁+n₂ (1)
其中n为完全二叉树的结点总数。又根据二叉树的定义，有
n=n₁+2×n₂+1 (2)
由公式(1)和(2)可得
n₂=n₀-1 (3)
把(3)式代入(1)式，可得
n=2n₀+n₁-1 (4)
根据本题的条件，有967=2n₀+n₁1-1，即968-n₁=2n₀。现在只需确定n₁就能求得n₀了。根据完全二叉树的定义，一棵K层的完全二叉树，上面的K-1层为满二叉树，最后一层的结点都靠左边，又因为满二叉树中只有度为0和度为2的结点，没有度为1的结点，这也就意味着在完全二叉树中，只有倒数第二层，才可能有度为1的结点，这就限制了完全二叉树只可能有0个或1个度为1的结点，对于968-n₁=2n₀，n₁显然为0，所以n₀=968／2=484。

转载请注明原文地址:https://kaotiyun.com/show/F3RZ777K

本试题收录于：软件设计师上午基础知识考试题库软考中级分类

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

软考中级

相关试题推荐

随机试题

最新回复(0)

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

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

软考中级

数据字典是在结构化分析方法中的重要文档。数据字典的组成内容之一就是对加工的描述，常用的加工描述方法(6)。

渐霜风凄紧。

下面关于Word标题栏的叙述中，错误的是()

关于HELLP综合征，下列描述错误的是

钩体病早期出现的中毒症侯群有“三症状”，即_、_和全身乏力。

患者，女，37岁。月经量多，皮肤散在出血点，血象：血红蛋白120g／L，白细胞8×109／L，中性粒细胞0．7，淋巴细胞0．3，血小板50×109／L，骨髓片巨核细胞增多。应首先考虑的是()

在现代纸币制度下，引起货币失衡的原因主要是()。

【《战国策》】扬州大学2016年中国古代史真题

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

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

软考中级

数据字典是在结构化分析方法中的重要文档。数据字典的组成内容之一就是对加工的描述，常用的加工描述方法(6)。

渐霜风凄紧。

下面关于Word标题栏的叙述中，错误的是()

关于HELLP综合征，下列描述错误的是

钩体病早期出现的中毒症侯群有“三症状”，即_______、_______和全身乏力。

患者，女，37岁。月经量多，皮肤散在出血点，血象：血红蛋白120g／L，白细胞8×109／L，中性粒细胞0．7，淋巴细胞0．3，血小板50×109／L，骨髓片巨核细胞增多。应首先考虑的是()

在现代纸币制度下，引起货币失衡的原因主要是()。

【《战国策》】扬州大学2016年中国古代史真题

钩体病早期出现的中毒症侯群有“三症状”，即_、_和全身乏力。