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

admin2013-05-11 25

问题一棵二叉树含有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://jikaoti.com/ti/KTf7FFFM

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

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

软考中级

相关试题推荐

随机试题

最新回复(0)

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

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

软考中级

在配置访问控制列表的规则时，关键字“any”代表的通配符掩码是(32)。

在Windows2003操作系统的cmd窗口中，键入(48)命令将获得如图7-3所示的系统输出信息。

主存储器和CPU之间增加高速缓冲存储器(Cache)的目的是(1)。

在SNMPv1管理框架中，如果代理需要向管理站报告一个异常事件，则代理发出trap报文。以下事件中不属于异常事件的是(37)。

PC机不能接入因特网，这时采用抓包工具捕获的以太网接口发出的信息如下：可以看出该PC机的IP地址为(68)，默认网关的IP地址为(69)。PC不能接入Internet的原因可能是(70)。(70)

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

对于氮氧化物的监测，下面说法错误的是()。

在仓库中是根据商品的(　)进行分区分类存放的。

一个工程项目交付使用的时间目标是()项目管理的目标。

下列有关工程进度款支付的说法中，正确的有()。

特殊情况下，专业报关企业和代理报关企业可经所在地海关同意，且经海关总署审批后，方可进行异地报关业务，但其中申请手续与自理报关企业的申请手续略有不同。()

关于账面资本、监管资本和经济资本之间的关系，下列说法错误的有()。

什么是美术教育?

阅读以下关于“我国南北气温的差异”的教学过程设计，回答问题。问题：为减少这些弊端的影响，利用计算机辅助地理教学时应把握好哪些方面?

定义部门关系模式：部门(部门号，部门名，部门成员，部门总经理)，使它不满足第一范式的属性是

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

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

软考中级

在配置访问控制列表的规则时，关键字“any”代表的通配符掩码是(32)。

在Windows2003操作系统的cmd窗口中，键入(48)命令将获得如图7-3所示的系统输出信息。

主存储器和CPU之间增加高速缓冲存储器(Cache)的目的是(1)。

在SNMPv1管理框架中，如果代理需要向管理站报告一个异常事件，则代理发出trap报文。以下事件中不属于异常事件的是(37)。

PC机不能接入因特网，这时采用抓包工具捕获的以太网接口发出的信息如下：可以看出该PC机的IP地址为(68)，默认网关的IP地址为(69)。PC不能接入Internet的原因可能是(70)。(70)

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

对于氮氧化物的监测，下面说法错误的是()。

在仓库中是根据商品的( )进行分区分类存放的。

一个工程项目交付使用的时间目标是()项目管理的目标。

下列有关工程进度款支付的说法中，正确的有()。

特殊情况下，专业报关企业和代理报关企业可经所在地海关同意，且经海关总署审批后，方可进行异地报关业务，但其中申请手续与自理报关企业的申请手续略有不同。()

关于账面资本、监管资本和经济资本之间的关系，下列说法错误的有()。

什么是美术教育?

阅读以下关于“我国南北气温的差异”的教学过程设计，回答问题。问题：为减少这些弊端的影响，利用计算机辅助地理教学时应把握好哪些方面?

定义部门关系模式：部门(部门号，部门名，部门成员，部门总经理)，使它不满足第一范式的属性是

在仓库中是根据商品的(　)进行分区分类存放的。