5．为什么图简答题5所示的结构都不是树形结构？详细说明理由。
(a)因为该图所示结构，有两个结点没有直接前趋，即有两个根结点，而树只能有一个根结点。 (b)因为找不到树的根结点，所以不满足树的定义。
(c)因为最上面一个结点的后继结点分不出两个不相交的子集，不满足树的定义。
6．分别画出含3个结点的树与二叉树的所有不同形态。
7．分别画出图简答题7-1所示二叉树的二叉链表、三叉链表和顺序存储结构。
8．分别写出图简答题4.1（a）所示二叉树的先根、中根和后根序列。
先根序列：A B C D E F G H I J; 中根序列：B C D A F E H J I G; 后根序列：D C B F J I H G E A。
9.试找出分别满足下列条件的所有二叉树：
（1） 先根序列和中根序列相同； （2）中根序列和后根序列相同； （ 3 ）先根序列和后根序列相同。
⑴二叉树中任意一个结点都无左孩子； ⑵二叉树中任意一个结点都无右孩子； ⑶至多只有一个结点的二叉树。
10．已知一棵二叉树的中根序列和后根序列分别为BDCEAFHG和EDCBHGEA，试画出这棵二叉树。
由后根遍历序列得到二叉树的根结点A（后根序列中最后一个结点）；在中序序列中，A的左力是A的左子树上的结点，A的右边是A的右子树上的结点；再到后根序列中找左子树和右子树的根结点，依次类推，直到画出该二叉树，如图简答题10所示。
11． 试分别画出图简答题11-1所示树的孩子链表、孩子兄弟链表和静态双亲链表。
11
12．分别给出简答题11.1图中树的先根、后根和层次遍历的结点访问序列。
先根序列：A B E F K L C G D H I J； 后根序列：E K L F B G C H I J D A； 层次序列：A B C D E F G H I J K L。 13．将图简答题13-1所示的林转换成二叉树。
14．分别画出图简答题14-1所示各二叉树对应的林。 (a)(b)(c)(d)(e)
15．给定权值7，18，3，32，5，26，12，8，构造相应的哈夫曼树。
16．试以三种遍历为基础，分别写出在二叉树上查找直接前趋或直接后继的关键操作步骤。
利用先根遍历方法查找结点*A的直接后继：
当A->lchild<>NULL时，A的先根后继结点是A->lchild；否则，当A->rchild<>NULL时，A的先根后继结点是A->rchild。 利用中根遍历方法查找结点*A的直接后继：
当A->lchild<>NULL时，*A的中根前趋是其左子树的“最右下结点”； 当A->rchild<>NULL时，*A的中根后继是其右子树的“最左下结点”。
利用后根遍历方法查找结点*A的直接前趋：
当A->rchild<>NULL时，A的后根前趋结点是A->rchild；否则，A->rchild<>NULL时，A的后根前趋结点是A->lchild；
17．已知一棵二叉树的前根序列和中根序列分别为ABDGHECFIJ及GDHBEACIJF，请画出这棵二叉树。
本题的解题过程如下：
①由前根序列各A是二叉树的根结点；由中根序列知GDHBE是A的左子树中的结点，CIJF是A的右子树中的结点。 ②由前根序列知B是A的左子树的根结点；由中根序列知GDH是B的左子树中的结点，E是B的右子树中的结点。 ③由前根序列知D是B的左子树的根结点；由中根序列知G是B的左子树中的结点，H是B的右子树中的结点 ④由前根序列知C是A的右子树的根结点；由中根序列知IJF是C的右子树
12
中的结点（C的左子树为空）。
⑤由前根序列知F是C的右子树的根结点；由中根序列知IJ是F的左子树中的结点，（F的右子树为空）。 ⑥由前根序列知I是F的左子树的根结点；由中根序列知J是F的右子树中的结点，（F的左子树为空）。 完整的二叉树如图简答题17所示。
18．设某密码电文由8个字母组成，每个字母在电文中的出现频率分别是7，19，2，6，32，3，21，10，试为这8个字母设计相应的哈夫曼编码。
第一步，先以给定的权值构造出哈夫曼树，如图简答题18所示。
第二步，假没规定哈夫曼树上所有的左指针用0表示，所有的右指针用1表示。
第三步，从根开始沿每一条通向叶子的路径上的数字，这些数字就是对应叶子结点所代表的字母的哈夫曼编码。8个字母所应的哈夫曼编码为：
13
7---0010 19---10 2---00000 6---0001 32---01 3---00001 21---11 10---0011
19．有一二叉树如图19-1所示，试画出它的顺序存储结构示意图。
20．将图简答20-1所示森林转换为二叉树。
第七章 图
一、 填空题
1.设x,y是图G中的两顶点，则（x,y）与（y,x）被认为________边，但
2.若顶点的偶对是有序的，此图为________图，有序偶对用________括号括起来；若顶点偶对是无序的，此图为________图，无序偶对用________括号括起来。
3.设x,y∈V，若
8.路径长度定义为________。第一个顶点和最后一个顶点相同的路径称为________或________。序列中顶点不重复出现的路径称为________。除了第一个顶点和最后一个顶点外，其余顶点不重复的回路，称为________或________。 9.在无向图中，如果从顶点v到顶点v’有路径，则称v和v’是_______的。如果对于图中的任意两个顶点vi,vj∈V，且vi和vj都是连通的，则称G为________。
10.连通分量是无向图中的________连通子图。
11.一个连通图的生成树是含有该连通图的全部顶点的一个________。
12.若连通图G的顶点个数为n，则G的生成树的边数为________。如果G的一个子图G’的边数________，则G’中一定有环。相反，如果G’的边数________，则G’一定不连通。
13.无向图的邻接矩阵是一个________矩阵，有向图的邻接矩阵不一定是________矩阵。
14.对于无向图的邻接矩阵，顶点vi的度是________________。对于有向图的邻接矩阵，顶点vi的出度OD（vi）为________________，顶点vi的入度ID(vi)是________________。
15.图的存储结构主要有________和________两种。
16.邻接表表示法是借助________来反映顶点间的邻接关系，所以称这个单链表为邻接表。
17.对无向图，若它有n顶点e条边，则其邻接表中需要________个结点。其中，________个结点构成邻接表，________个结点构成顶点表。
18.对有向图，若它有n顶点e条边，则其邻接表中需要________个结点。其中，________个结点构成邻接表，________个结点构成顶点表。
19.在邻接表上，无向图中顶点vi的度恰为________________。对有向图，顶点vi的出度是________________。为了求入度，必须遍历整个邻接表，在所有单链表中，其邻接点域的值为________的结点的个数是顶点vi的入度。 20.遍历图的基本方法有________优先搜索和________优先搜索两种。 21.以下是图的深度优先算法，请在________处填充适当的语句。 Dfs(GraphTp g,int v) { ArcNodeTp *p; printf(“%d”,v); visited[v]=1;
p=________________; while(p!=NULL)
{if(!________________) Dfs(g,p->adjvex);
p=________________; } }
22.以下是图的广度优先搜索算法，请在________处填充适当的语句。 Bfs(GraphTp g,int v) {QueptrTp Q;
ArcNodeTp *p; InitQueue(&Q); printf(“%d”,v);
14
visited[v]=1; ________________
while(!EmptyQueue(Q)) {________________;
p=g.adjlist[v].firstarc; while(p!=NULL)
{if(!visited[p->adjvex])
{printf(“%d”,p->>adjvex); visited[[->adjvex]=1; EnQueue(&Q,p->adjvex);
}
________________; } } }
23.深度优先搜索遍历类似于树的________遍历，它所用到的数据结构是________；广度优先搜索遍历类似于树的________遍历，它所用到的数据结构是________。
24.任何连通图的连通分量只有一个，即________。
25.对具有n个顶点的图其生成树有且仅有________条边，即生成树是图的边数________的连通图。 26.一个图的________的表示法是惟一的，而________表示法是不惟一的。 27.对无向图，其邻接矩阵是一个关于________对称的矩阵。
28.在有向图的邻接矩阵上，由第i行可得到第________个结点的出度，而由第j列可得到第________个结点的入度。 29.________的有向图，其全部顶点有可能排成一个拓扑序列。
30.一个有向图G中若有弧,
1.设有无向图G=（V，E）和G’=（V’,E’）,如G’为G的生成树，则下面不正确的说法是（ ）
①G’为G的子图 ②G’为G的连通分量 ③G’为G的极小连通子图且V’=V ④G’是G的无环子图
2.任何一个带权的无向连通图的最小生成树（ ）
①只有一棵 ②有一棵或多棵 ③一定有多棵 ④可能不存在 3.设图G采用邻接表存储，则拓扑排序算法的时间复杂度为（ ）
①O(n) ②O(n+e) ③O(n*n) ④O(n*e)
4.含n个顶点的连通图中的任意一条简单路径，其长度不可能超过 （ ）
①1 ② n/2 ③ n-1 ④n
5．一有向图G的邻接表存储结构如图单项选择5所示。现按深度优先遍历算法，从顶点V1出发，所得到的顶点序列是 （ ）
①V1,V3, V2 ,V4, V5 ②V1, V3, V4, V2, V5 ③V1,V2, V3, V4, V5 ④V1, V3, V4, V5 , V2 6.在无向图中，所有顶点的度数之和是所有边数的（ ）倍。
①0.5 ②1 ③2 ④4
7.在有向图中，所有顶点的入度之和是所有顶点出度之和的（ ）倍。 （ ）
①0.5 ② 1 ③ 2 ④4
8．在图的邻接表存储结构上执行深度优先搜索遍历类似于二叉树上的 （ ）
①先根遍历 ② 中根遍历 ③ 后根遍历 ④按层次遍历
9．在图的邻接表存储结构上执行广度优先搜索遍历类似于二叉树上的 （ ）
①先根遍历 ②中根遍历 ③后根遍历 ④按层次遍历
10．判断一个有向图是否存在回路，除了可以利用拓扑排序方法，还可以利用 （ ） ①求关键路径方法②求最短路径的Dijkstra方法③广度优先遍历方法④深度优先遍历方法 11．在图单项选择中，从顶点V1出发，按广度优先遍历图的顶点序列是 （ ） ①V1 V3 V5 V4 V2 V6 V7 ②V1 V2 V4 V7 V6 V5 V3 ③V1 V5 V3 V4 V2 V7 V6 ④V1 V4 V7 V2 V6 V5 V3
12.在图单项选择中，从顶点V1出发,广度遍历图的顶点序列是 （ ） ①V1 V5 V3 V4 V2 V6 V7 ②V1 V5 V3 V4 V2 V7 V6 ③V1 V7 V2 V6 V4 V5 V3 ④V1 V2 V4 V7 V6 V5 V3 13.设有6个结点的无向图，该图至少应有（ ）条边能确保是一个连通图。 （ ）
① 5 ② 6 ③ 7 ④ 8
14.以下说法正确的是 （ ） ①连通图的生成树，是该连通图的一个极小连通子图。
②无向图的邻接矩阵是对称的，有向图的邻接矩阵一定是不对称的。 ③任何一个有向图，其全部顶点可以排成一个拓扑序列。 ④有回路的图不能进行拓扑排序。
15以下说法错误的是 （ ）
①用相邻矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。 ②邻接表法只能用于有向图的存储，而相邻矩阵法对于有向图和无向图的存储都适用。 15