一棵二叉树含有ABCDEFGH共8个结点，对其进行先序、中序、后序遍历的结果分别如下：#BC#E#GH、C#DA#GHF、#DB# #FEA，“#”表示不清楚是什么结点。那么该二叉树度为1的结点共有(7)个。

admin2013-05-11 47

问题一棵二叉树含有ABCDEFGH共8个结点，对其进行先序、中序、后序遍历的结果分别如下：#BC#E#GH、C#DA#GHF、#DB# #FEA，“#”表示不清楚是什么结点。那么该二叉树度为1的结点共有(7)个。

选项 A、5
B、4
C、3
D、2

答案C

解析后序遍历的最后一个结点A便是根结点，于是先序遍历便进一步明确为ABC#E #GH。在中序遍历中，根结点A将左右子树的结点刚好隔开，左子树结点为C并D，共3个结点，那么先序遍历中根结点A之后紧跟的3个结点BC#也是左子树结点，经对比我们显然可以推知左子树有结点B、C、D，于是先序遍历为ABCDE#GH，而中序遍历为 CBDA#GHF，此时，分别只剩下结点F、E，于是先序遍历为ABCDEFGH，而中序遍历为CBDAEGHF。在后序遍历中，显然前3个结点并DB是左子树结点(因为从中序遍历中可知根结点A之前有3个结点，便断定左子树共有三个结点)，接下来4个紧挨的结点# #FE是右子树结点，因此后序遍历便进一步明确为CDB# #FEA。右子树先序、后序遍历分别为EFGH、EGHF，又由二叉树的前序遍历可以确定该二叉树的根结点(序列的第一个结点)，在中序序列中该根结点将中序序列分为两部分，左边为其左子树的结点，右边为其右子树的结点，递归地操作下去便可以推知右子树的形状如图13-41所示。右子树的后序遍历为HGFE，于是整个树的后序遍历为CDBHGFEA。按同样的方法，我们可以得出整个二叉树的形状如图13-42所示。显然，度为1的结点为E、F、G共3个。

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

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

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

软考中级

相关试题推荐

随机试题

最新回复(0)

一棵二叉树含有ABCDEFGH共8个结点，对其进行先序、中序、后序遍历的结果分别如下：#BC#E#GH、C#DA#GHF、#DB# #FEA，“#”表示不清楚是什么结点。那么该二叉树度为1的结点共有(7)个。

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

软考中级

TCP是互联网中的(13)协议，使用(14)次握手协议来建立连接。当主动方发出SYN连接请求后，等待对方回答(15)。这种建立连接的方法可以防止(16)。TCP使用的流量控制协议应该是(17)。

某企业有独立工作的3台服务器，分别运行Web、E-mail、电子商务等业务，由1名网络工程师独立看管，1000小时内它们出故障的概率分别是0.1、0.2及0.15。那么这段时间出现机器故障不能得到及时维修的时间是(60)小时。

IIS安装的硬盘分区最好选用NTFS格式，这是因为(1)和(2)。A．可以针对某个文件或文件夹给不同的用户分配不同的权限B．可以防止网页中的Applet程序访问硬盘中的文件C．可以使用系统自带的文件加密系统对文件或文件夹进行加

IPv4地址可划分为{网络号，主机号}两部分。如果用0表示所有比特为0，用-1表示所有比特为1，则以下选项中，(53)只能用于内部网络。

单个磁头在向盘片的磁性涂料层上写入数据时，是以______　方式写入的。

在Linux系统中，采用(1)命令查看进程输出的信息，得到下图所示的结果。系统启动时最先运行的进程是(2)，下列关于进程xinetd的说法中正确的是(3)。(2009年下半年试题)(1)

在IPv4向IPv6的过渡期间，如果要使得两个IPv6结点可以通过现有的IPv4网络进行通信，则应该使用(58)；如果要使得纯IPv6结点可以与纯IPv4结点进行通信，则需要使用(59)。(59)

Withcircuitswitching,a(71)________________pathisestablishedbetweentwostationsforcommunication．Switchingandtransmissi

Melissa　and　LoveLetter　made　use　of　the　trust　that　exists　between　friends　or　colleagues.　Imagine　receiving　an(71)from　a　friend　wh

简述感性形象在美育中的重要作用。

窦性心动过缓时出现期前收缩町用何药治疗

下列说法正确的是

瓷嵌体与金属嵌体相比，最大的优点是

中国证监会内部设有()，具体承担基金监管职责。

我国现有的外汇贷款币种不包括()。

(2014年)关于企业库存与库存管理的说法，正确的是()。

简述教育为什么要“以人为本”。

下面关于虚函数的表述中正确的是()。

一棵二叉树含有ABCDEFGH共8个结点，对其进行先序、中序、后序遍历的结果分别如下：#BC#E#GH、C#DA#GHF、#DB# #FEA，“#”表示不清楚是什么结点。那么该二叉树度为1的结点共有(7)个。

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

软考中级

TCP是互联网中的(13)协议，使用(14)次握手协议来建立连接。当主动方发出SYN连接请求后，等待对方回答(15)。这种建立连接的方法可以防止(16)。TCP使用的流量控制协议应该是(17)。

某企业有独立工作的3台服务器，分别运行Web、E-mail、电子商务等业务，由1名网络工程师独立看管，1000小时内它们出故障的概率分别是0.1、0.2及0.15。那么这段时间出现机器故障不能得到及时维修的时间是(60)小时。

IIS安装的硬盘分区最好选用NTFS格式，这是因为(1)和(2)。A．可以针对某个文件或文件夹给不同的用户分配不同的权限B．可以防止网页中的Applet程序访问硬盘中的文件C．可以使用系统自带的文件加密系统对文件或文件夹进行加

IPv4地址可划分为{网络号，主机号}两部分。如果用0表示所有比特为0，用-1表示所有比特为1，则以下选项中，(53)只能用于内部网络。

单个磁头在向盘片的磁性涂料层上写入数据时，是以______ 方式写入的。

在Linux系统中，采用(1)命令查看进程输出的信息，得到下图所示的结果。系统启动时最先运行的进程是(2)，下列关于进程xinetd的说法中正确的是(3)。(2009年下半年试题)(1)

在IPv4向IPv6的过渡期间，如果要使得两个IPv6结点可以通过现有的IPv4网络进行通信，则应该使用(58)；如果要使得纯IPv6结点可以与纯IPv4结点进行通信，则需要使用(59)。(59)

Withcircuitswitching,a(71)________________pathisestablishedbetweentwostationsforcommunication．Switchingandtransmissi

Melissa and LoveLetter made use of the trust that exists between friends or colleagues. Imagine receiving an(71)from a friend wh

简述感性形象在美育中的重要作用。

窦性心动过缓时出现期前收缩町用何药治疗

下列说法正确的是

瓷嵌体与金属嵌体相比，最大的优点是

中国证监会内部设有()，具体承担基金监管职责。

我国现有的外汇贷款币种不包括()。

(2014年)关于企业库存与库存管理的说法，正确的是()。

简述教育为什么要“以人为本”。

下面关于虚函数的表述中正确的是()。

单个磁头在向盘片的磁性涂料层上写入数据时，是以______　方式写入的。

Melissa　and　LoveLetter　made　use　of　the　trust　that　exists　between　friends　or　colleagues.　Imagine　receiving　an(71)from　a　friend　wh