5．为什么图简答题5所示的结构都不是树形结构？详细说明理由。
6．分别画出含3个结点的树与二叉树的所有不同形态。
7．分别画出图简答题7-1所示二叉树的二叉链表、三叉链表和顺序存储结构。
8．分别写出图简答题4.1（a）所示二叉树的先根、中根和后根序列。 9.试找出分别满足下列条件的所有二叉树：
（1） 先根序列和中根序列相同； （2）中根序列和后根序列相同； （ 3 ）先根序列和后根序列相同。
10．已知一棵二叉树的中根序列和后根序列分别为BDCEAFHG和EDCBHGEA，试画出这棵二叉树。
11． 试分别画出图简答题11-1所示树的孩子链表、孩子兄弟链表和静态双亲链表。
31
12．分别给出简答题11.1图中树的先根、后根和层次遍历的结点访问序列。 13．将图简答题13-1所示的林转换成二叉树。
14．分别画出图简答题14-1所示各二叉树对应的林。
15．给定权值7，18，3，32，5，26，12，8，构造相应的哈夫曼树。
16．试以三种遍历为基础，分别写出在二叉树上查找直接前趋或直接后继的关键操作步骤。
17．已知一棵二叉树的前根序列和中根序列分别为ABDGHECFIJ及GDHBEACIJF，请画出这棵二叉树。
18．设某密码电文由8个字母组成，每个字母在电文中的出现频率分别是7，19，2，6，32，3，21，10，试为这8个字母设计相应的哈夫曼编码。 19．有一二叉树如图19-1所示，试画出它的顺序存储结构示意图。
32
20．将图简答20-1所示森林转换为二叉树。
第七章 图
一、 填空题
1.设x,y是图G中的两顶点，则（x,y）与（y,x）被认为________边，但
2.若顶点的偶对是有序的，此图为________图，有序偶对用________括号括起来；若顶点偶对是无序的，此图为________图，无序偶对用________括号括起来。
3.设x,y∈V，若
5.一个具有n个顶点的完全无向图的边数为________。一个具有n个顶点的完全有向图的弧度数为________。
6.图的边或弧附带的数值叫________。每条边或弧都带权的图称为________或________。 7.无向图中的顶点V的度是________，记为________。若G是一个有向图，则把以顶点V为终点的弧的数目称为V的________，记为________；把以顶点V为始点的弧的数目称为V的________，称为________。有向图中顶点V的度定义为D（V）=________。 8.路径长度定义为________。第一个顶点和最后一个顶点相同的路径称为________或________。序列中顶点不重复出现的路径称为________。除了第一个顶点和最后一个顶
33
点外，其余顶点不重复的回路，称为________或________。
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);
34
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); 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);
}
35