/ 知识库     / 试卷库

等级2017年春程序员软考( )

某二叉树的先序遍历(根、左、右)序列为 EFHIGJK、中序遍历(左、根、右)序列为HFIEJKG,则该二叉树根结点的左孩子结点和右孩子结点分别是【 】

A、I、K

B、F、I

C、F、G

D、I、G

F、G

对于一个非空的二叉树,其先序遍历序列、中序遍历序列和后序遍历序列都是唯一确定的。先序遍历是首先访问根结点,其次是先序遍历左子树,最后再先序遍历右子树,因此先序序列第一个元素是根结点。中序遍历是首先中序遍历左子树,然后访问根结点,最后中序遍历右子树,因此在已知根结点的情况下,可将左子树和右子树的结点区分开。

本题中根据先序遍历序列可知 E 是根结点,在中序遍历序列中 E之前是左子树的中序遍历序列,E 之后是右子树的中序遍历序列。再到先序遍历序列中确定 FHI为左子树的先序遍历序列、GJK 为右子树的先序遍历序列。从而确定F为E的左孩子结点、G 为E的右孩子结点。

考试2016年秋程序员软考( )

对于一般的树结构,可以采用孩子-兄弟表示法,即每个结点设置两个指针域,一个指针(左指针)指示当前结点的第一个孩子结点,另一个指针(右指针)指示当前结点的下一个兄弟结点。某树的孩子-兄弟表示如下图所示。以下关于结点 D 与 E 的关系的叙述中,正确的是【 】。

A、结点 D与结点E是兄弟

B、结点 D 是结点 E 的祖父结点

C、结点E的父结点与结点 D 的父结点是兄弟

D、结点E 的父结点与结点 D 是兄弟

结点E 的父结点与结点 D 是兄弟

等级2016年春程序员软考( )

某二又树的先序遍历序列为 ABCDFGE,中序遍历序列为 BAFDGCE。以下关于该二又树的叙述中,正确的是【 】。

A、该二叉树的高度(层次数)为4

B、该二叉树中结点D是叶子结点

C、该二叉树是满二叉树(即每层的结点数达到最大值)

D、该二叉树有5个叶子结点

该二叉树的高度(层次数)为4

根据一个二叉树的先序遍历序列和中序遍历序列可以重构该二叉树。先序遍历序列可以确定二叉树(包括子二叉树)的根结点,然后在中序遍历序列中找到根结点,从而可以分出左子树和右子树中各自的结点。题中的二叉树的根结点是A,其左子树上有1个结点为B,其右子树上有5个结点。然后根据右子树的先序遍历序列 CDFGE和中序遍历序列 FDGCE再确定各个结点的位置,该二叉树如下图所示。

等级2016年春程序员软考( )

对二叉树中的结点如下编号:树根结点编号为1,根的左孩子结点编号为2、右孩子结点编号为3,以此类推,对于编号为i的结点,其左孩子编号为2i、右孩子编号为2i+1。例如,下图所示二又树中有6个结点,结点a、b、c、d、e、f的编号分别为1、2、3、5、7、11。那么,当结点数为n(n>0)的【 】时,其最后一个结点编号为2n-1。

A、二叉树为满二叉树(即每层的结点数达到最大值)

B、二叉树中每个内部结点都有两个孩子

C、二叉树中每个内部结点都只有左孩子

D、二又树中每个内部结点都只有右孩子

二又树中每个内部结点都只有右孩子

当二叉树为满二叉树时,第i层上最后一个结点的编号为2i-1,第2层最后一个结点的编号为22-1,第3层最后一个节点的编号为23-1。

要使得结点数n与高度一致,应使得每层只有一个结点,并且每层的结点都是其所是的最右结点,也就是每个内部结点都只有右孩子。

等级2016年春程序员软考( )

与算术表达式3-(2+7)/4对应的二又树为【 】。

A、

B、

C、

D、

题目中选项A所示的二叉树,其表达式为(3-2+7)4;与选项B所示二叉树对应的表达式为3-(2+7)/4;与选项C所示二叉树对应的表达式(3-(2+7)/4;与选项D所示二叉树对应的表达式为(3-2)+7/4。