第7章习题一、单项选择题1.在无向图中定义顶点的度为与它相关联的（）的数目。

A. 顶点B. 边C. 权D. 权值2.在无向图中定义顶点 v i与v j之间的路径为从v i到达v j的一个（）。

A. 顶点序列B. 边序列C. 权值总和D. 边的条数3.图的简单路径是指（）不重复的路径。

A. 权值B. 顶点C. 边D. 边与顶点均4.设无向图的顶点个数为n，则该图最多有（）条边。

A. n-1B. n(n-1)/2C. n(n+1)/2D. n(n-1)5.n个顶点的连通图至少有（）条边。

A. n-1B. nC. n+1D. 06.在一个无向图中，所有顶点的度数之和等于所有边数的 ( ) 倍。

A. 3B. 2C. 1D. 1/27.若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个 ( )。

A. 上三角矩阵B. 稀疏矩阵C. 对角矩阵D. 对称矩阵8.图的深度优先搜索类似于树的（）次序遍历。

A. 先根B. 中根C. 后根D. 层次9.图的广度优先搜索类似于树的（）次序遍历。

A. 先根B. 中根C. 后根D. 层次10.在用Kruskal算法求解带权连通图的最小（代价）生成树时，选择权值最小的边的原则是该边不能在图中构成（）。

A. 重边B. 有向环C. 回路D. 权值重复的边11.在用Dijkstra算法求解带权有向图的最短路径问题时，要求图中每条边所带的权值必须是（）。

A. 非零B. 非整C. 非负D. 非正12.设G1 = (V1, E1) 和G2 = (V2, E2) 为两个图，如果V1 ⊆ V2，E1 ⊆ E2，则称（）。

A. G1是G2的子图B. G2是G1的子图C. G1是G2的连通分量D. G2是G1的连通分量13.有向图的一个顶点的度为该顶点的（）。

A. 入度B. 出度C. 入度与出度之和D. (入度﹢出度))／214.一个连通图的生成树是包含图中所有顶点的一个（）子图。

A. 极小B. 连通C. 极小连通D. 无环15.n (n＞1) 个顶点的强连通图中至少含有（）条有向边。

A. n-1B. n n(n-1)/2 D. n(n-1)16.在一个带权连通图G中，权值最小的边一定包含在G的（）生成树中。

A. 某个最小B. 任何最小C. 广度优先D.深度优先17.对于具有e条边的无向图，它的邻接表中有（）个结点。

A. e-1B. eC. 2(e-1)D. 2e18.对于如图所示的带权有向图，从顶点1到顶点5的最短路径为（）。

A.1, 4, 5B. 1, 2, 3, 5C. 1, 4, 3, 5D. 1, 2, 4, 3, 519. 一个有n 个顶点和n 条边的无向图一定是（ ）。

A. 连通的B. 不连通的C. 无环的D. 有环的 20. 对于有向图，其邻接矩阵表示比邻接表表示更易于（ ）。

A. 求一个顶点的度 B. 求一个顶点的邻接点 C. 进行图的深度优先遍历 D. 进行图的广度优先遍历 21. 与邻接矩阵相比，邻接表更适合于存储（ ）图。

A. 无向B.连通C.稀疏D. 稠密图22. 为了实现图的广度优先遍历，BFS 算法使用的一个辅助数据结构是（ ）。

A. 栈 B. 队列 C. 二叉树 D. 树二、填空题1. 用邻接矩阵存储图，占用存储空间数与图中顶点个数________关，与边数________关。

2. n (n ﹥0) 个顶点的无向图最多有________条边，最少有________条边。

3. n (n ﹥0) 个顶点的连通无向图最少有________条边。

4. 若3个顶点的图G 的邻接矩阵为⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡010001010，则图G 一定是________向图。

5. n (n ﹥0) 个顶点的无向图中顶点的度的最大值为________。

6. (n ﹥0) 个顶点的连通无向图的生成树至少有________条边。

7. 在使用Kruskal 算法构造连通网络的最小生成树时，只有当一条候选边的两个端点不在同一个________上，才有可能加入到生成树中。

8. 求解带权连通图最小生成树的Prim 算法适合于________图的情形，而Kruskal 算法适合于________图的情形。

三、判断题1. 一个图的子图可以是空图，顶点个数为0。

2. 存储图的邻接矩阵中，矩阵元素个数不但与图的顶点个数有关，而且与图的边数也有关。

3. 对一个连通图进行一次深度优先搜索（depth first search ）可以遍访图中的所有顶点。

4. 有n (n ≥1) 个顶点的无向连通图最少有n-1条边。

5. 如果无向图中各个顶点的度都大于2，则该图中必有回路。

6. 如果有向图中各个顶点的度都大于2，则该图中必有回路。

7. 图的广度优先搜索（breadth first search ）算法不是递归算法。

8. 有n 个顶点、e 条边的带权有向图的最小生成树一般由n 个顶点和n-1条边组成。

9. 对于一个边上权值任意的带权有向图，使用Dijkstra 算法可以求一个顶点到其它各个顶点的最短路径。

10. 有回路的有向图不能完成拓扑排序。

11. 对任何用顶点表示活动的网络（AOV 网）进行拓扑排序的结果都是唯一的。

12. 用边表示活动的网络（AOE 网）的关键路径是指从源点到终点的路径长度最长的路径。

13. 对于AOE 网络，加速任一关键活动就能使整个工程提前完成。

14. 对于AOE 网络，任一关键活动延迟将导致整个工程延迟完成。

15. 在AOE 网络中，可能同时存在几条关键路径，称所有关键路径都需通过的有向边为桥。

如果加速这样的桥上的关键活动就能使整个工程提前完成。

16. 用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶点个数有关，而与图的边数无关。

17. 邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。

18.邻接矩阵只适用于稠密图（边数接近于顶点数的平方），邻接表适用于稀疏图（边数远小于顶点数的平方）19. 存储无向图的邻接矩阵是对称的，因此只要存储邻接矩阵的下（上）三角部分就可以了。

20. 连通分量是无向图中的极小连通子图。

21. 在AOE 网络中一定只有一条关键路径。

四、运算题1. 设连通图G 如图所示。

试画出该图对应的邻接矩阵表示，并给出对它执行从顶点V 0开始的广度优先搜索的结果。

2. 设连通图G 如图所示。

试画出该图及其对应的邻接表表示，并给出对它执行从V 0开始的深度优先搜索的结果。

3. 对于如图所示的有向图，试写出：(1) 从顶点①出发进行深度优先搜索所得到的深度优先生成树； (2) 从顶点②出发进行广度优先搜索所得到的广度优先生成树4. 设有向图G 如图所示。

试画出从顶点V 0开始进行深度优先搜索和广度优先搜索得到的DFS 生成森林和BFS 生成森林。

5. 设有一个连通网络如图所示。

试按如下格式，应用Kruskal 算法给出在构造最小生成树过程中顺序选出的各条边。

V 46V 4 61 V 7 65①② ③ ④ ⑤( 始顶点号，终顶点号， 权值 ) ( , , ) ( , , )( , , ) ( , , ) ( , , )6. 设有一个连通网络如图所示。

试采用prim 算法从顶点0开始构造最小生成树。

（写出加入生成树顶点集合S 和选择边Edge 的顺序）7. 有八项活动, 每项活动要求的前驱如下:(1) 试画出相应的AOV 网络, 并给出一个拓扑排序序列。

(2) 试改变某些结点的编号, 使得用邻接矩阵表示该网络时所有对角线以下的元素全为0。

8. 试对下图所示的AOE 网络(1) 这个工程最早可能在什么时间结束。

(2) 确定哪些活动是关键活动。

画出由所有关键活动构成的图，指出哪些活动加速可使整个工程提前完成。

9. 设带权有向图如图所示。

试采用Dijkstra 算法求从顶点0到其他各顶点的最短路径和最短路径长度。

第7章习题参考答案一、单项选择题参考答案： 1. B2.A3.B4.B5. A6. B7. D8.A9.D 10.C11. C 12.A 13.C 14.C 15. B 16. A 17.D 18. D 19.D20.A21. C22. B二、填空题参考答案： 1. 有, 无 2. n(n-1)/2, 0 3. n-1 4. 有5. (n-1)6. n-17. 连通分量8. 稠密，稀疏三、判断题参考答案： 1. 否2. 否3. 是4. 是5. 是6. 否7. 是8. 否9. 否 10. 是 11. 否 12. 是 13. 否 14. 是 15. 是 16. 是17. 否 18. 是 19. 是20. 否 21.否四、运算题参考答案：1. 图G 对应的邻接矩阵为⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡=001000000001001000110001000000000100000000010011000111000101001000011001000001110G.Edge执行广度优先搜索的结果为V 0V 1V 3V 2V 4V 7V 6V 5V 8，搜索结果不唯一。

2. 图G 对应的邻接表为：执行深度优先搜索的结果为：V 0V 1V 4V 3V 6V 7V 8V 2V 5，搜索结果不唯一。

3. 以顶点 ① 为根的深度优先生成树（不唯一）：以顶点 ② 为根的广度优先生成树：4. 深度优先生成森林为：应用Kruskal 算法顺序选出最小生成树的各条边为： ( 始顶点号，终顶点号， 权值 ) ( 0, 3, 1 )( 2, 5, 2 ) ( 1, 4, 3 ) ( 3, 5, 4 ) ( 3, 4, 5 )5. 采用prim 算法从顶点0开始构造最小生成树的过程：1 V 23V 7651V 23 V 765① ② ③ ④ ⑤ ①② ③④ ⑤ ①② ③ ④ ⑤6. 相应的AOV 网络为：一个拓扑排序序列为：A0,A1,A4,A2,A5,A3,A6,A7。

注意：拓扑排序结果不唯一。

按拓扑有序的次序对所有顶点从新编号：相应邻接矩阵为：76543210000000001000000001000000100000000011000000010000000001000010101076543210⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡=Edge7. 针对下图所示的AOE 网络各顶点（事件）的最早可能开始时间Ve(i)和最迟允许开始时间Vl(i)参看下表：顶点 1 2 3 4 5 6 Ve 0 19 15 29 38 43 Vl1915373843A7各边（活动）的最早可能开始时间Ee(k)和最迟允许开始时间El(k)参看下表：边<1,2> <1,3> <3,2> <2,5> <3,5> <2,4> <4,6> <5,6>Ee 0 0 15 19 15 19 29 38El 17 0 15 19 27 27 37 38如果活动k的最早可能开始时间Ee(k) 与最迟允许开始时间El(k)相等，则该活动是关键活动。