1） 已知出栈序列，写出可能的入栈序列并分析操作过程。
2） 已知入栈序列，写出可能的出栈序列并分析操作过程。
[2004/1]如下图所示，输入元素为（A , B , C）,在栈的输出端得到一个输出序列 ABC ,
求出在栈的输入端所有可能的输入序列。

ABC
输入端

【分析】A，B，C三个字符排成的序列可以有： ABC、ACB、BAC、BCA、CAB、
CBA六种，按堆栈操作的先进后出（或后进先出）的原则，只有输入序列为 BCA时，
输出无法得到 ABC。因为输入序列为 BCA时，要想先输出 A，必须BCA均入栈，但这 样只能得
到序列 ACB。其余五种输入序列都可在输出端得到序列 ABC。
【解答】ABC、ACB、BAC、CAB、CBA
2 •队列的操作
分析顺序队中元素入队出队操作及队列的状态。 （考过）
[2003/10] 设有一顺序队列 sq ,容量为5，初始状态时sq • front=sq • rear=0，画出做完 下列操作
后队列及其头尾指针的状态变化情况，若不能入队，请简述其理。
(1)
d, e, b入队

(2)
d, e出队

(3)
i, j入队
(4) b出队

(5) n , o, p入队
【解答】队列及其头尾指针的状态变化情况如下图所示

3 .二叉树的存储结构
1）给出一棵二叉树，画出二叉链表示意图及顺序存储示意图。 [2004/10]考过） [2003/10] 画出下列二叉树的二叉链表表示图。输出端 j - Sq.rear j i i b ~Sq.rear b -—Sq.rear b e ■*- Sq.front "-Sq.front d Sq.fr ont -Sq.rear H— Sq.fro nt （a）初态 （b） d, e, b入队 第5步操作无法进行，因队列已满。 (d) i, j入队 (e) b出队 ([2000/10] [2003/10]

*- Sq.rear
Sq.fro
nt
【解答】二叉树的二叉链表表示
【分析】按
照给出的顺
序存储结
构，先绘制
出一棵包括
空结点的完
全二叉树，

然后去掉
空结点就是所求的二叉树。
【解答】

A B C D A A A A E A A A A A A A A F G
（[2005/1]考过） 2)给出二叉树的顺序存储示意图，画出二叉树。
[2005/1]已知某二叉树的顺序存储结构如下所示，试画出该二叉树。

______
A
B

A E A

J
A H A

A
C

F
A
D
4 .二叉树的遍历
1 )给出一棵二叉树，写出对该二叉树进行先根遍历、中根遍历及后根遍历的序列。
([2001/10] [2004/1] [2005/10] 考过)
[2005/10]对于如下图所示二叉树，分别写出其先根遍历、中根遍历和后根遍历的结点访问 序列。
【分析】根据二叉树三种遍历方法的原理， 很容易写出该二叉树的先根遍历、 中根遍历
和后根遍历的结点访问序
【解答】先根遍历的结点访问序： A, B , D , E , F,
C
中根遍历的结点访问序： B , F , E , D , A,
C

后根遍历的结点访问序： F , E , D , B , C,
A

2 ）给出一棵二叉树的先根遍历和中根遍历序列，恢复二叉树，写出后根遍历的序列。
（［2002/10］考过）
［2002/10］ 现有某二叉树，按先根遍历的序列为 ABDEFCGH ，按中根遍历的序列为
DEFBGHCA ，试画出此二叉树。
【分析】由先根遍历和中根遍历恢复二叉树的方法： 在先根序列中确定根结点（最前面
那个结点一定是根结点），然后根据根结点在中根序列中的位置分出根结点的左、 右子树（根
结点前面的那些结点为根结点的左子树上的结点， 根结点后面的那些结点为根结点的右子树
上的结点）。恢复该二叉树的任何一棵子树的过程仍然遵循这个原则。 【解答】

3 ）给出一棵二叉树的后根遍历和中根遍历序列，恢复二叉树，写出先根遍历的序列。 （未
考过，但可能考注意第四章的考核知识点的讲解）
5 •树的存储结构
1 ）给出一棵树，画出该树的双亲表示法、孩子链表表示法、带双亲的孩子链表表示法及孩 子兄弟链
表表示法的示意图。 （［2000/4］考过）

2）给出一棵树的某一种存储结构的示意图，画出对应的树。 （未考过）
6 .树的遍历
给出一棵树，写出对该树进行先根遍历、后根遍历及层次遍历的序列。 （未考过）
7 .二叉树与树、林的相互转换

1） 将一棵二叉树转换为树。 （未考过）
2） 将一棵树转换为二叉树。 （未考过）
3） 将林转换为一棵二叉树。（未考过）
4） 将二叉树转换为林。（未考过）
8 .够造哈夫曼树

给出一组权值，构造一棵哈夫曼树并求带权路径长度。 （未考过）
9 .图的存储结构

1）给出一个图，画出该图的邻接矩阵或邻接表存储示意图。 （考过）
[2005/10] 试给出下图的邻接矩阵和邻接表表示。

【分析】邻接矩阵存储方法是用一个二维数组存放顶点之间关系的信息。 对于不带权的有
向图，如果一个顶点到另一个顶点有边，用 1表示；否则，用0表示；对于带权的有图，
如果一个顶点到另一个顶点有边，用边的权值表示；否则，用R表示。 邻接表存储方法的
核心思想是对于具有 n个顶点的图建立n个线性链表。每一个链表最前面都分别设置一个 称之为表
头结点的结点，n个结点构成一个数组结构。第 i个链表中的每一个链结点称之为 表结点。对带权的
图，其邻接表中的每个表结点都要增加一个权值域。
【解答】题中图的邻接矩阵为：
vV1 2 4 6
vV2 8
v
V

3

2

vV4 7 11

vV5 13
v0 v1 v2 v3 v
V1 V2 V3 V4 V
5

题中图的邻接表为：

2）给出一个图的邻接表，画出该图的所有连通分量。 （考过）
[2002/10]已知无向图G的邻接表如下图所示，请画出其所有的连通分量。

V1 3
I 5 | :A
|

V2 4
A
V3 5
肓|
| 1 |
| A
*

V
4

' - ►

‘ 2
A

V5 1 ------ 1
.1
:3 |
,A

【分析】根据邻接表，很容易画出其所有的连通分量。
【解答】画出的连通分量如下图所示
3 ）给出一个图的邻接矩阵，画出该图的所有连通分量。 （考过）
[2003/1]已知无向图G的邻接矩阵如下图。假设对其访问时每行元素必须从右到左，请画 出其所有
的连通分量，并且写出按深度优先搜索时各连通分量的访问序列。

VV0 0 0 0 1 0
vv1 o o i o 1
VV2 0 1 0 0 0
VV3 1 0 0 0 0
VV4 0 1 0 0 0
V0 V1 V2 V
3
V

V0 V1 V2 V3 V4 【分析】根据邻接表，很容易画出其所有

的连通分量。
【解答】画出的连通分量如下图所示

(J)

深度优先搜索时各连通分量的访问序列： V1V2V4 V0V
3

10 .图的遍历
1 ）给出一个图的邻接表， 写出从某一点出发进行广度优先搜索和深度优先搜索的遍历序列。
（[2000/10] [2001/10] [2004/1] [2004/10] 考过）
[2004/1]已知无向图G的邻接表如下图所示， 请写出其从顶点 V2开始的深度优先搜索的
序列。

2 ）给出一个图的邻接矩阵，写出从某一点出发进行广度优先搜索和深度优先搜索的遍历序
列。（[2003/10] 考过）
[2003/10]
已知无向图G的邻接矩阵如下图所示， 假设对其每行兀素访问时必须从右到左,

请写出从
V0开始的深度优先搜索的序列。

v
V

0
0 1 1 0 0

V
V

1
1 0 1 1 1

也
2
1 1 0 1 1

【解答】深度优先搜索序列： V2V5V3V1V
4
(V)

【分析】根据深度优先搜索的算法思想和题中给定的存储结构, 一
的。

【解答】深度优先搜索序列： V0V2V4V3V
1

11 .最小生成树
给出一个带权图，画出所有可能的最小生成树。 ([2005/1] [2006/1]

【解答】构造最小生成树过程如下图所示
[2006/1]
试用Prim

所得到的遍历序列是惟
考过)
(V)
V
(a)