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

admin2013-05-11 53

问题一棵二叉树含有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://kaotiyun.com/show/XoRZ777K

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

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

软考中级

相关试题推荐

随机试题

最新回复(0)

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

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

软考中级

CMM模型的第三级为已定义级，其主要过程是关于项目和组织的策略。以下属于该级别定义的关键过程域是(12)。

采用UML进行软件设计时，可用(5)关系表示两类事物之间存在的特殊/一般关系，用聚集关系表示事物之间存在的整体/部分关系。

在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

破坏下列哪一脑区，动物会出现食欲增加而逐渐肥胖?

垂体性侏儒症的诊断下列哪项错误

依据《突发事件应对法》的规定，下列关于突发事件的预防与应急准备的方法，正确的是()。

监理人在履行本合同的义务期间，做到了认真、勤奋地工作。但是，因被监理单位的违反合同行为导致工程竣工时间的延长，监理单位(　　)。

根据《水利水电建设工程验收规程》SL223—2008，分部工程验收工作组可由()主持。

某企业2015年12月31日购入一项专利权，购买价款为180万元，相关税费为10万元，为宣传该专利生产的产品支付广告费10万元，则该项无形资产的入账价值为()万元。

我国古代的许多人为民族融合与发展做出了杰出贡献。下列各人物与其功绩对应有误的一项是()。

有人认为：“双方当事人意思表示一致才能成立民事法律行为。”请运用民事法律行为理论对该说法加以辨析。

Asetofgenesplayaroleinlearningtoreadanddomath,butthisabilityisnotjustgene-driven,【C1】______schoolingandhel

TheexampleoftheEnglishschoolboywasusedtoshowthat______.Ifonewantstogetmorepersonalinformationfromothers,t

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

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

软考中级

CMM模型的第三级为已定义级，其主要过程是关于项目和组织的策略。以下属于该级别定义的关键过程域是(12)。

采用UML进行软件设计时，可用(5)关系表示两类事物之间存在的特殊/一般关系，用聚集关系表示事物之间存在的整体/部分关系。

在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

破坏下列哪一脑区，动物会出现食欲增加而逐渐肥胖?

垂体性侏儒症的诊断下列哪项错误

依据《突发事件应对法》的规定，下列关于突发事件的预防与应急准备的方法，正确的是()。

监理人在履行本合同的义务期间，做到了认真、勤奋地工作。但是，因被监理单位的违反合同行为导致工程竣工时间的延长，监理单位( )。

根据《水利水电建设工程验收规程》SL223—2008，分部工程验收工作组可由()主持。

某企业2015年12月31日购入一项专利权，购买价款为180万元，相关税费为10万元，为宣传该专利生产的产品支付广告费10万元，则该项无形资产的入账价值为()万元。

我国古代的许多人为民族融合与发展做出了杰出贡献。下列各人物与其功绩对应有误的一项是()。

有人认为：“双方当事人意思表示一致才能成立民事法律行为。”请运用民事法律行为理论对该说法加以辨析。

Asetofgenesplayaroleinlearningtoreadanddomath,butthisabilityisnotjustgene-driven,【C1】______schoolingandhel

TheexampleoftheEnglishschoolboywasusedtoshowthat______.Ifonewantstogetmorepersonalinformationfromothers,t

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

监理人在履行本合同的义务期间，做到了认真、勤奋地工作。但是，因被监理单位的违反合同行为导致工程竣工时间的延长，监理单位(　　)。