4-1

某二叉树的前序和后序遍历序列正好相反，则该二叉树一定是

(4分)

A.

空或只有一个结点

B.

高度等于其结点数

C.

任一结点无左孩子

D.

任一结点无右孩子

作者

DS课程组

单位

浙江大学

---

4-2

已知一棵二叉树的先序遍历结果是ABC，则以下哪个序列是不可能的中序遍历结果：

(4分)

A.

ABC

B.

BAC

C.

CBA

D.

CAB

作者

DS课程组

单位

浙江大学

---

4-3

如果二叉树的后序遍历结果是FDEBGCA，中序遍历结果是FDBEACG，那么该二叉树的前序遍历结果是什么？

(4分)

A.

ABCDEFG

B.

ABDFEGC

C.

ABDFECG

D.

ABDEFCG

作者

DS课程组

单位

浙江大学

---

4-4

给定二叉树如下图所示。设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。若遍历后的结点序列为3、1、7、5、6、2、4，则其遍历方式是：

(4分)

A.

NRL

B.

RNL

C.

LRN

D.

RLN

作者

DS课程组

单位

浙江大学

---

4-5

在下述结论中，正确的是：

①只有一个结点的二叉树的度为0;

②二叉树的度为2；

③二叉树的左右子树可任意交换；

④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。

(4分)

A.

①④

B.

②④

C.

①②③

D.

②③④

作者

DS课程组

单位

浙江大学

---

4-6

任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序

(4分)

A.

发生改变

B.

不发生改变

C.

不能确定

D.

以上都不对

作者

DS课程组

单位

浙江大学

---

4-7

按照二叉树的定义，具有3个结点的二叉树有几种？

(4分)

A.

3

B.

4

C.

5

D.

6

作者

DS课程组

单位

浙江大学

---

4-8

下面的函数PreOrderPrintLeaves(BinTree BT)按前序遍历的顺序打印出二叉树BT的所有叶子结点。则下列哪条表达式应被填在空中？

void PreOrderPrintLeaves( BinTree BT )
{  if (BT)  {if (___________________)  printf("  %d", BT->Data);PreOrderPrintLeaves( BT->Left  );PreOrderPrintLeaves( BT->Right );}
}

(4分)

A.

BT->Data != 0

B.

!BT->Right

C.

!BT->Left

D.

!(BT->Left || BT->Right)

作者

何钦铭

单位

浙江大学

---

4-9

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

(4分)

A.

只有左子树

B.

只有右子树

C.

结点的度均为1

D.

结点的度均为2

作者

考研试卷

单位

浙江大学

---

4-10

若将一棵树 T 转化为对应的二叉树 BT，则下列对 BT 的遍历中，其遍历序列与 T 的后根遍历序列相同的是：

(4分)

A.

先序遍历

B.

中序遍历

C.

后序遍历

D.

按层遍历

作者

考研真题

单位

浙江大学

---

保存

4-11 Isomorphic (10 分)

Two trees, T1 and T2, are isomorphic if T1 can be transformed into T2 by swapping left and right children of (some of the) nodes in T1. For instance, the two trees in Figure 1 are isomorphic because they are the same if the children of A, B, and G, but not the other nodes, are swapped. Give a polynomial time algorithm to decide if two trees are isomorphic.

Figure 1

Format of functions:

int Isomorphic( Tree T1, Tree T2 );

where Tree is defined as the following:

typedef struct TreeNode *Tree;
struct TreeNode {ElementType Element;Tree  Left;Tree  Right;
};

The function is supposed to return 1 if T1 and T2 are indeed isomorphic, or 0 if not.

Sample program of judge:

#include <stdio.h>
#include <stdlib.h>typedef char ElementType;typedef struct TreeNode *Tree;
struct TreeNode {ElementType Element;Tree  Left;Tree  Right;
};Tree BuildTree(); /* details omitted */int Isomorphic( Tree T1, Tree T2 );int main()
{Tree T1, T2;T1 = BuildTree();T2 = BuildTree();printf(“%d\n”, Isomorphic(T1, T2));return 0;
}/* Your function will be put here */

Sample Output 1 (for the trees shown in Figure 1):

1

结尾无空行

Sample Output 2 (for the trees shown in Figure 2):

0

Figure2

4-12 求二叉树高度 (10 分)

本题要求给定二叉树的高度。

函数接口定义：

int GetHeight( BinTree BT );

其中BinTree结构定义如下：

typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{ElementType Data;BinTree Left;BinTree Right;
};

要求函数返回给定二叉树BT的高度值。

裁判测试程序样例：

#include <stdio.h>
#include <stdlib.h>typedef char ElementType;
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{ElementType Data;BinTree Left;BinTree Right;
};BinTree CreatBinTree(); /* 实现细节忽略 */
int GetHeight( BinTree BT );int main()
{BinTree BT = CreatBinTree();printf("%d\n", GetHeight(BT));return 0;
}
/* 你的代码将被嵌在这里 */

输出样例（对于图中给出的树）：

4

 

4-13 先序输出叶结点 (10 分)

本题要求按照先序遍历的顺序输出给定二叉树的叶结点。

函数接口定义：

void PreorderPrintLeaves( BinTree BT );

其中BinTree结构定义如下：

typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{ElementType Data;BinTree Left;BinTree Right;
};

函数PreorderPrintLeaves应按照先序遍历的顺序输出给定二叉树BT的叶结点，格式为一个空格跟着一个字符。

裁判测试程序样例：

#include <stdio.h>
#include <stdlib.h>typedef char ElementType;
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{ElementType Data;BinTree Left;BinTree Right;
};BinTree CreatBinTree(); /* 实现细节忽略 */
void PreorderPrintLeaves( BinTree BT );int main()
{BinTree BT = CreatBinTree();printf("Leaf nodes are:");PreorderPrintLeaves(BT);printf("\n");return 0;
}
/* 你的代码将被嵌在这里 */

输出样例（对于图中给出的树）：

Leaf nodes are: D E H I

 

4-14 还原二叉树 (15 分)

给定一棵二叉树的先序遍历序列和中序遍历序列，要求计算该二叉树的高度。

输入格式:

输入首先给出正整数N（≤50），为树中结点总数。下面两行先后给出先序和中序遍历序列，均是长度为N的不包含重复英文字母（区别大小写）的字符串。

输出格式:

输出为一个整数，即该二叉树的高度。

输入样例:

9
ABDFGHIEC
FDHGIBEAC

结尾无空行

输出样例:

5

结尾无空行

 

4-15 根据后序和中序遍历输出先序遍历 (15 分)

本题要求根据给定的一棵二叉树的后序遍历和中序遍历结果，输出该树的先序遍历结果。

输入格式:

第一行给出正整数N(≤30)，是树中结点的个数。随后两行，每行给出N个整数，分别对应后序遍历和中序遍历结果，数字间以空格分隔。题目保证输入正确对应一棵二叉树。

输出格式:

在一行中输出Preorder: 以及该树的先序遍历结果。数字间有1个空格，行末不得有多余空格。

输入样例:

7
2 3 1 5 7 6 4
1 2 3 4 5 6 7

结尾无空行

输出样例:

Preorder: 4 1 3 2 6 5 7

结尾无空行