数据结构题目收录（七）

1、在二叉树中有两个结点m和n，若m是n的祖先，则使用（）可以找到从m到n的路径。

• A：先序遍历
• B：中序遍历
• C：后序遍历
• D：层序遍历

解析

在后序遍历退回时访问根结点，就可以从下向上把从n到m的路径上的结点输出，若采用非递归的算法，则后序遍历访问到n时，栈中把从根到n的父指针的路径上的结点都记忆下来，也可以找到从m到n的路径。

答案：C

2、前序为A，B，C，后序为C，B，A的二叉树共有（）。

• A：1棵
• B：2棵
• C：3棵
• D：4棵

解析

前序为A、B、C的不同二叉树共有5种，其中后序为C、B、A的有4种（前4种），都是单支树。如下图所示。

答案：D

3、若二叉树中结点的先序序列是…a…b…，中序序列是…b…a…，则（）。

• A：结点a和结点b分别在某结点的左子树和右子树中
• B：结点b在结点a的右子树中
• C：结点b在结点a的左子树中
• D：结点a和结点b分别在某结点的两棵非空子树中

解析

答案：C

4、线索二叉树是一种（）结构。

• A：逻辑
• B：逻辑和存储
• C：物理
• D：线性

解析

二叉树是一种逻辑结构，但线索二叉树是加上线索后的链表结构，即它是二叉树在计算机内部的一种存储结构，所以是一种物理结构。

答案：C

5、一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是（）。

• A：不确定
• B：0个
• C：1个
• D：2个

解析

对左子树为空的二叉树进行先序线索化，根结点的左子树为空并且也没有前驱结点（先遍历根结点），先序遍历的最后一个元素为叶结点，左、右子树均为空且有前驱无后继结点，故线索化后，树中空链域有2个。

答案：D

6、（）的遍历仍需要栈的支持。

• A：前序线索树
• B：中序线索树
• C：后序线索树
• D：所有线索树

解析

后序线索树遍历时，最后访问根节点，若从右孩子x返回访问父结点，则由于结点x的右孩子不一定为空（右指针无法指向其后继），因此通过指针可能无法遍历整棵树。如下图所示，结点中的数字表示遍历的顺序，图c中结点6的右指针指向其右孩子5，而不指向其后序后继结点7，因此后序遍历还需要栈的支持，而图a和图b均可遍历。

答案：C

7、先序序列为a,b,c,d的不同二叉树的个数是（）。

• A：13
• B：14
• C：15
• D：16

解析

根据二叉树前序遍历和中序遍历的递归算法中递归工作栈的状态变化得出：前序序列和中序序列的关系相当于以前序序列为入栈次序，以中序序列为出栈次序。因为前序序列和中序序列可以唯一地确定一棵二叉树，所以题意相当于“以序列a,b,c,d为入栈次序，则出栈序列的个数为？”，对于n个不同元素进栈，出栈序列的个数为$\frac{1}{n+1}$$C_{2n}^n$=14。

答案：B

8、某二叉树的树形如右图所示，其后序序列为e,a,c,b,d,g,f,树中与结点a同层的结点是（）。

• A：c
• B：d
• C：f
• D：g

解析

后序序列是先左子树，接着右子树，最后父结点，递归进行。根结点左子树的叶结点首先被访问，它是e。接下来是它的父结点a，然后是a的父结点c。接着访问根结点的右子树。它的叶结点b首先被访问，然后是b的父结点d，再后是d的父结点g，最后是根结点f，如图所示。d与a同层。

答案：B

9、要使一棵非空二叉树的先序序列与中序序列相同，其所有非叶结点须满足的条件是（）。

• A：只有左子树
• B：只有右子树
• C：结点的度均为1
• D：结点的度均为2

解析

先序序列先父结点，接着左子树，然后右子树。中序序列先左子树，接着父结点，然后右子树，递归进行。若所有非叶结点只有右子树，则先序序列和中序序列都是先父结点，然后右子树，递归进行，因此B正确。

答案：B

10、利用二叉链表存储森林时，根结点的右指针是（）。

• A：指向最左兄弟
• B：指向最右兄弟
• C：一定为空
• D：不一定为空

解析

森林与二叉树具有对应关系，因此，我们存储森林时应先将森林转换成二叉树，转换的方法就是“左孩子右兄弟”，与树不同的是，若存在第二棵树，则二叉链表的根结点的右指针指向的是森林中的第二棵树的根结点。若此森林只有一棵树，则根结点的右指针为空。因此，右指针可能为空也可能不为空。

答案：D

学海无涯苦作舟