习题解答
样的，否则是不一样的。
图6-23 树示例
2．二叉树与树有什么不同？
答：二叉树是一种树，但是一种特殊的树。第一，二叉树的每个结点至多可以有两棵子树，但树的每个结点可以有多棵子树；第二，二叉树的子树有左、右之分（即是有序的），但树的子树通常是不分顺序的。 3．为什么对于二叉树有中序遍历，而对一般树却没有中序遍历？
答：二叉树有中序遍历，是因为二叉树的每个结点最多只有两个子树，且子树有左、右之分，因此可以规定在访问左子树和右子树的中间去访问子树的根结点。但对于一般的树，其结点可以有任意数目的子树，因此，无法规定怎样的访问顺序才算是“中序”。所以，对一般的树没有中序遍历。 4．对于树的各种遍历，哪一种遍历是（1）首先访问树的根结点？（2）位于最左边的结点最先访问？（3）根结点最后访问？（4）最右边的结点最后访问？
答：（1）层次遍历和先序遍历总是首先访问树的根结点；（2）后序遍历总是最先访问位于树最左边的结点；（3）后序遍历总是最后访问树的根结点；（4）前序遍历总是最后访问树的最右边的结点。 5．一棵度为2的树与一棵二叉树有什么区别？ 答：从形状上看，一棵度为2的树与一棵二叉树没有什么区别。但度为2的树结点的子树一般是无序的，没有左、右之分；而二叉树结点的子树是有序的，它们之间有左、右之分，不能随意换位。
四、应用
1．已知一棵树的孩子链表表示法如图6-24所示，试画出该树。
图6-24 一棵树的孩子链表表示法 图6-25 树示例
答：该树形状如下图所示。
2．已知一棵树如图6-25所示。请画出该树的以下存储结构：（1）双亲表示法；（2）带
- 26 -
习题解答
双亲的孩子链表表示法（我们介绍过双亲表示法和孩子链表表示法，没有介绍过带双亲的孩子链表表示法。望能够把两者结合起来）；（3）孩子/兄弟链表表示法。 答：（1）双亲表示法如下图(a)所示；（2）带双亲的孩子链表表示法如图下(b)所示；（3）孩子/兄弟链表表示法如下图(c)所示。
3．将图6-26所示的二叉树转换成相应的森林。
图6-26 二叉树示例 图6-27 树示例
答：转换成的森林如下图所示。
4．给出如图6-27所示树的先序遍历序列和后序遍历序列。 答：该树的先序遍历序列为：A-B-E-F-K-L-M-C-G-D-H-I-J；该树的后序遍历序列是：E-K-M-L-F-B-G-C-H-I-J-D-A。
- 27 -
习题解答
5．将图6-28所示的森林转换成对应的二叉树。
图6-28 森林示例 图6-29 树示例
答：对应的二叉树如下图所示。
6．将图6-29所示的树转换成相对应的二叉树。 答：对应的二叉树如下图所示
第7章习题解答
一、填空
1．由4个顶点组成的一个连通图，应该有边 6 条。 2．在一个具有4个顶点的无向图中，要连通全部顶点，，至少需要 3 条边。 3．在无向图中，若顶点vi和vj之间有一条边（vi，vj）存在，那么则称顶点vi和vj互为 邻接 点。 4．图中顶点vi的“度”，是指与它 相邻接 的顶点的个数，并记为D(vi)。
- 28 -
习题解答
5．在有向图中，把从顶点vi到顶点vj的弧记为 < vi，vj > ，而把从顶点vj到顶点vi的弧记为 < vj，vi > ，这是两条不同的弧。 6．对于一个无向图，其邻接矩阵中第i行（或第i列）里非零或非∞元素的个数，正好是第i个顶点vi的 度 。 7．对于一个有向图，其邻接矩阵中第i行里非零或非∞元素的个数，正好是第i个顶点vi的 出度 ；其邻接矩阵中第i列里非零或非∞元素的个数，正好是第i个顶点vi的 入度 。 8．在无向图中，若从顶点vi到顶点vj之间有 路径 存在，则称vi与vj是连通的。 9．如果无向图G中 任意 一对顶点之间都是连通的，则称该图G为连通图，否则是非连通图。
10．在无向图G中，尽可能多地从集合V及E里收集顶点和边，使它们成为该图的一个极大的连通子图，这个子图就被称为是无向图G的一个 连通分量 。 11．包含无向连通图G的所有n个顶点在内的极小连通子图，是这个图的 生成树 。 12．只要在无向连通图的生成树里减少任意一条边，它就成为了一个 非连通图 。 13．对图的广度优先搜索，类似于对树进行 按层次 遍历。 14．拓扑排序是得到AOV网的一个 线性 序列，使得网中所有顶点间的优先关系在序列中得以体现。 15．已知无向图的顶点个数为n，边数为e。那么，在其邻接表表示法中，链表结点数与单链表表头结点数之和是 n+2e 。
二、选择 1．在一个有n个顶点的无向图中，要连通全部顶点，至少需要 C 条边。 A．n B．n+1 C．n-1 D．n/2 2．对于一个无向完全图来说，它的每个不同顶点对之间，都存在有一条边。因此，有n个顶点的无向完全图包含有 C 条边。 A．n(n-1) B．n(n+1) C．n(n-1)/2 D．n(n+1)/2 3．对于一个有向完全图来说，它的每个不同顶点对之间，都存在有两条弧。因此，有n个顶点的有向完全图包含有 A 条边。 A．n(n-1) B．n(n+1) C．n(n-1)/2 D．n(n+1)/2 4．在一个无向图中，所有顶点的度数之和，是其所有边数之和的 C 倍。 A．1/2 B．1 C．2 D．4 5．在一个有向图中，所有顶点的入度之和 B 所有顶点的出度之和。 A．二分之一于 B．等于 C．两倍于 D．四倍于 6．一个无向连通网图的最小生成树 A 。 A．有一棵或多棵 B．只有一棵 C．一定有多棵 D．可能不存在 7．一个无向图有n个顶点，那么该图拥有的边数至少是 D 。 A．2n B．n C．n/2 D．0 8．一个有n个顶点的无向连通网图，其生成树里含有 C 条边。 A．4n-1 B．2n-1 C．n-1 D．n/2 9．下面关于图的存储的叙述中，正确的是 C 。 A．用邻接表存储图，所用存储空间大小只与图中顶点个数有关，与边数无关 B．用邻接表存储图，所用存储空间大小只与图中边数有关，与顶点个数无关 C．用邻接矩阵存储图，所用存储空间大小只与图中顶点个数有关，与边数无关 D．用邻接矩阵存储图，所用存储空间大小只与图中边数有关，与顶点个数无关 10．对如图7-21所示的无向图实施深度优先搜索遍历，可能的遍历序列是 B 。 - 29 -
习题解答
图7-21 无向图示例
三、问答
1． 试求图7-22所示的无向连通网图的MST。一个无向连通网图的MST唯一吗？
图7-22 无向连通网图示例 图7-23 无向图示例
答：其MST如图7-15(g)所示。如果使用边（v4, v6）代替边（v3, v6），就可以得到另一个MST。所以，MST不是唯一的。 2．试述简单回路、回路两者间的联系与不同。 答：简单回路的定义是“如果一条路径的第一个顶点和最后一个顶点相同，其他顶点不重复出现，那么这条路径称为简单回路”；回路的定义是“如果一条路径的第一个顶点和最后一个顶点相同，那么这条路径称为回路”。比较后可知，一条路径是简单回路，那么它一定是回路，因为回路只要求路径的起始顶点和终端顶点相同，简单路径是满足这一要求的；但一条路径是回路，则不一定是简单回路，因为回路时并不去理会路径中的其他顶点是否重复出现，可是简单路径是不允许其他顶点重复出现的。 3．有如图7-23所示的一个无向图，给出它的邻接矩阵以及从顶点v1出发的深度优先遍历序列。
答：它的邻接矩阵如图所示。从顶点v1出发的深度优先遍历序列为：
v1->v2->v4->v5->v7->v6->v3
注意，该序列是不唯一的。
4．构造最小生成树的Prim算法与求单源最短路径的Dijkstra算法十分相似，它们都把图中的顶点分成U和V-U两个部分，都是在V-U里挑选出一个顶点，并将它从V-U移到U中。那么，它们的主要区别是什么？
- 30 -