数据结构(C语言描述)第七章

1、习题7.1 选择题1、在一个图中，所有顶点的度数之和等于所有边数的（b）倍。a、1 b、2 c、3 d、4 2、对于有n 个顶点和e 条边的有向图和无向图，若采用边集数组表示，则存于数组的边数为（d）条。a、n ，n b、n，e c、2n，2e d、e，e 3、对用邻接矩阵表示的图进行任一种遍历时，其时间复杂度为（a） 。a、o（n2）b、o（e）c、o（n）d、o（n+e）4、n 个顶点的强连通图至少有（a ）边。a、n b、n-1 c、n+1 d、n (n-1) 5、在一个无向图中，所有顶点的度数之和等于所有边数的（b）倍；在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（c）倍。

2、a、1/2 b、2 c、1 d、 4 7.2 填空题1、设无向图g 的顶点数为n，图 g 最少有（ 0）边；最多有（ n(n-1)/2）条边。若g 为有向图，则图g 最少有（ 0）边，最多有（n(n-1)）边。具有n 个顶点的无向完全图，边的总数为（ n(n-1)/2） ；而具有n 个项点的有向完全图，边的总数为（n(n-1)） 。2、在一个图g 的邻接表表示中，每个顶点的邻接表中所含的结点数，对于有向图而言等于该顶点的（出度 ） ；而对于无向图而言等于该顶点的（度） 。3、采用邻接表存储的图的深度优先遍历算法类似于二叉树的（先根 ）遍历；广度优先遍历算法类似于二叉树的（按层 ）遍历。4、一个

3、具有n 个顶点的无向图中，要连通全部顶点至少需要（ n-1）条边；若是有向图，至少需要（ n）条边。5、在无向图g 的邻接矩阵a 中，若 aij=1 ，则 aji=（1） 。7.3 应用题1、 对于下面所示的图（a）和（ b） ，求出：0 3 4 1 2 4 1 2 3 0 （a）（b）图 7-20 （1）每一个图的二元组表示，对于带权图，可将边的权写在该边的后面；答： （a）图ga=(v ,e) v=0,1,2,3,4 e=(0,1),(0,2),(0,3),(0,4),(2,1),(2,3),(3,4) （b）图gb=(v ,e) v=0,1,2,3,4 e=,（2）在（ a）中的每个顶点

4、的度，以及每个顶点的所有邻接点和所有边；答：0：度为 4；邻接点1，2，3，4；边 (0,1),(0,2),(0,3),(0,4) 1：度为 2；邻接点0，2；边 (0,1),(1,2) 2：度为 3；邻接点0，1，3；边 (0,2),(1,2) ,(3,2) 3：度为 3；邻接点0，2，4；边 (0,3),(3,2) ,(3,4) 4：度为 2；邻接点0，3；边 (0,4),(3,4) （3）在（ b）中的每个顶点的入度、出度和度，以及每个顶点的所有入边和出边；答：0：入度 2；出度 2；度 4；入边 , ；出边 , 1：入度 2；出度 1；度 3；入边 , ；出边 2：入度 0；出度 4；

5、度 4；入边无；出边, 3：入度 2；出度 1；度 3；入边 , ；出边 4：入度 2；出度 0；度 2；入边 , ；出边无（4）在（ a）中从 0 到 4 的所有简单路径及相应路径长度；答： （04）1， （034）2， （ 0234）3， （01234）4（5）在（ b）中从 0 到 4 的所有简单路径及相应的带权路径长度；答： （034） 22、如图所示有向图，采用 dijkstra 算法求出从顶点0 到其它顶点的最短路径，并说明整个计算过程。图 7-21 解：1 4 2 3 5 0 6 4 6 6 1 4 2 3 5 0 6 4 6 2 7 （1）选 4 （2）选 1 1 4 2 3

6、5 0 6 4 6 2 7 4 1 4 2 3 5 0 6 4 6 2 7 4 8 （3）选 4 （4）选 6 1 4 2 3 5 0 6 4 6 2 7 4 8 1 4 2 3 5 0 6 4 6 2 7 4 8 6 （5）选 7 （6）选 8 或选 6 3、写出上图的一种拓扑序列，若在它的邻接表存储结构中，每个顶点邻接表中的边结点都是按照终点序号从大到小链接的，则按此给出惟一一种拓扑序列。解：任意的拓扑序列为：0312456 惟一拓扑序列为：0132456 4、对图 7-22 中所示图分别写出深度优先遍历和广度优先遍历的项点序列。如果确定图以邻接矩阵存储，则得到的遍历顶点序列是什么？解：

7、深度优先遍历： （a）01234 02341 （b） 01342 03412 广度优先遍历： （a）01234 04321 （b） 01342 03142 邻接矩阵存储时：深度优先遍历： （a）01234 （b）01342 广度优先遍历： （a）01234 （b）01342 5、对图 7-21 中所示图分别用克鲁斯卡尔算法和普里姆算法（从顶点2 开始）求出其最小生成树。解：用克鲁斯卡尔算法1 4 2 0 2 3 0 0 2 4 1 5 2 5 3 1 5 5 3 2 4 6 4 6 1 1 2 4 4 5 6 6 6 6 7 8 用普里姆算法1 4 2 3 5 0 6 6 1 4 6 2 1

8、4 2 3 5 0 6 4 1 4 6 2 初始状态（1）选 (1,2)1，进行修改1 4 2 3 5 0 6 4 1 4 6 2 1 4 2 3 5 0 6 4 1 4 6 2 （2）选 (2,3)2，无需修改（3）选 (1,0)4，无需修改1 4 2 3 5 0 6 4 1 4 1 2 8 1 4 2 3 5 0 6 4 1 4 1 2 6 （4）选 (2,5)4，进行修改（5）选 (4,5)1，进行修改1 4 2 3 5 0 6 4 1 4 1 2 6 （6）选 (4,6)6，结束7.4 算法题（不做要求）1、 在邻接表的存储结构上，实现图的深度优先搜索和广度优先搜索。（可做为上机实践题目）2、假定图采用邻接矩阵表示，编写出进行深度优先搜索遍历的非递归算法。3、根据下图，编