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

admin2015-06-03 13

问题一个具有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://jikaoti.com/ti/mDf7FFFM

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

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

软考中级

相关试题推荐

随机试题

最新回复(0)

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

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

软考中级

在Linux网络配置中，(9)命令是用来设置主机名字的；在不使用DNS和NIS进行地址解析时，将所使用的主机名字写入(10)文件中可以保证解析器能找到主机的IP地址；解析器的功能是(11)；Linux中(12)提供名字服务；配置文件“host.conf”的

动态主机配置协议DHCP具有(158)机制，这是与BOOTP的主要区别。DHCP协议支持的中继代理(Relay　Asent)是一种(159)，可以在不同的网段之间传送报文。在DHCP的地址分配方案，(160)是最适合移动终端的分配方案。使用Windows2

SDLC、HDLC和LLC都是在OSI模型的(16)卫上层上操作的协议。传输层的功能是(17)。会话层的功能是(18)。邮件服务和目录服务是通过(19)提供给用户的。X.25协议属　OSI(20)上的操作。

客户/服务器模式产生于20世纪(27)上年代，它是基于(28)的要求而发展起来的。客户/服务器模式的第一个软件产品是(29)系统，客户/服务器模式通常在(30)环境下运行，客户端的软件具有(31)。

The　grid　computing　is　a　new(66)technology　connecting　the　distributed　and(67)resources　to　the　high-speed　network　and　integrating

上颌尖牙V类阻生上颌尖牙Ⅳ类阻生

如果凭样品买卖的买方不知道样品有瑕疵,则损失由()

盈利能力()。

批复的写作要求包括()。

某公司生产了两个级别的同一种产品，一级品比二级品每个贵200元，3个一级品和4个二级品的价格相等。问9600元可以买多少个二级品？

我国诸民族语言主要分属_______、_、_、_、_________等五个语系。

雇佣童工从事危重劳动罪中“童工”是指()

CRC码的产生和校验需要生成多项式，若生成多项式最高为n次幂，则校验值有(　　　)位。

下列不属于浏览器对Applet的安全限制的一项是______。

有3个关系R、S和T如下：则关系T是由关系R和S通过某种操作得到的，该操作为()。

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

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

软考中级

动态主机配置协议DHCP具有(158)机制，这是与BOOTP的主要区别。DHCP协议支持的中继代理(Relay Asent)是一种(159)，可以在不同的网段之间传送报文。在DHCP的地址分配方案，(160)是最适合移动终端的分配方案。使用Windows2

SDLC、HDLC和LLC都是在OSI模型的(16)卫上层上操作的协议。传输层的功能是(17)。会话层的功能是(18)。邮件服务和目录服务是通过(19)提供给用户的。X.25协议属 OSI(20)上的操作。

客户/服务器模式产生于20世纪(27)上年代，它是基于(28)的要求而发展起来的。客户/服务器模式的第一个软件产品是(29)系统，客户/服务器模式通常在(30)环境下运行，客户端的软件具有(31)。

The grid computing is a new(66)technology connecting the distributed and(67)resources to the high-speed network and integrating

上颌尖牙V类阻生上颌尖牙Ⅳ类阻生

如果凭样品买卖的买方不知道样品有瑕疵,则损失由()

盈利能力()。

批复的写作要求包括()。

某公司生产了两个级别的同一种产品，一级品比二级品每个贵200元，3个一级品和4个二级品的价格相等。问9600元可以买多少个二级品？

我国诸民族语言主要分属_______________、_______________、_______________、_______________、_______________等五个语系。

雇佣童工从事危重劳动罪中“童工”是指()

CRC码的产生和校验需要生成多项式，若生成多项式最高为n次幂，则校验值有( )位。

下列不属于浏览器对Applet的安全限制的一项是______。

有3个关系R、S和T如下：则关系T是由关系R和S通过某种操作得到的，该操作为()。

动态主机配置协议DHCP具有(158)机制，这是与BOOTP的主要区别。DHCP协议支持的中继代理(Relay　Asent)是一种(159)，可以在不同的网段之间传送报文。在DHCP的地址分配方案，(160)是最适合移动终端的分配方案。使用Windows2

SDLC、HDLC和LLC都是在OSI模型的(16)卫上层上操作的协议。传输层的功能是(17)。会话层的功能是(18)。邮件服务和目录服务是通过(19)提供给用户的。X.25协议属　OSI(20)上的操作。

The　grid　computing　is　a　new(66)technology　connecting　the　distributed　and(67)resources　to　the　high-speed　network　and　integrating　

我国诸民族语言主要分属_______、_、_、_、_________等五个语系。

CRC码的产生和校验需要生成多项式，若生成多项式最高为n次幂，则校验值有(　　　)位。