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

admin2015-06-03 10

问题一个具有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)。

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

软考中级

Kerberos是一种对服务请求进行认证的方法，下列(19)不是Kerberos的设计目标。

IEEE802．11定义的AdHoe网络是由无线移动结点组成的对等网，这种网络的特点是(62)。在这种网络中使用的DSDV(Destination-SequencedDistanceVector)路由协议是一种(63)。(62)

下列关于私有地址个数和地址的描述中，都正确的是________________。

Morethan10millionChineseculturalrelicshavebeenlostoverseas,lotsofwhichwerestolenandillegallyshippedoutofChi

钢与铝及铝合金焊接时，铝与铁可形成多种金属间化合物，例如FeAl、FeAl2、FeAl3、Fe2Al7、Fe3Al、Fe2Al5等，其中()最脆。

患者，男，19岁，因车祸导致四肢乏力1个月余入院，出生后确诊为呆小症，现四肢乏力，右眼视物模糊，鼻粱两侧疼痛，咽喉肿痛，头颅CT提示颅脑损伤，筛窦炎。呆小症是由于幼儿

悬挑结构未进行抗倾覆验算，属于常见质量缺陷中的()。

下列哪些机构必须任用具有期货从业人员资格的人员从事期货业务?()[2014年9月真题]

下列纠纷中，属于《劳动争议调解仲裁法》受案范围的是()。

______是幼儿园的基本活动，也是德育的基本形式()

(2017年真题)根据现行宪法，下列关于土地所有权、使用权的表述，正确的有()。

关于SSL协议的描述中，正确的是()。