1、1第 7 章习题一、单项选择题1. 在无向图中定义顶点的度为与它相关联的（ ）的数目。A. 顶点 B. 边 C. 权 D. 权值2. 在无向图中定义顶点 vi 与 vj 之间的路径为从 vi 到达 vj 的一个（ ） 。A. 顶点序列 B. 边序列 C. 权值总和 D. 边的条数3. 图的简单路径是指（ ）不重复的路径。A. 权值 B. 顶点 C. 边 D. 边与顶点均4. 设无向图的顶点个数为 n，则该图最多有（ ）条边。A. n-1 B. n(n-1)/2 C. n(n+1)/2 D. n(n-1)5. n 个顶点的连通图至少有（ ）条边。A. n-1 B. n C. n+1 D. 06.
2、 在一个无向图中，所有顶点的度数之和等于所有边数的 ( ) 倍。A. 3 B. 2 C. 1 D. 1/27. 若采用邻接矩阵法存储一个 n 个顶点的无向图，则该邻接矩阵是一个 ( )。A. 上三角矩阵 B. 稀疏矩阵 C. 对角矩阵 D. 对称矩阵8. 图的深度优先搜索类似于树的（ ）次序遍历。A. 先根 B. 中根 C. 后根 D. 层次9. 图的广度优先搜索类似于树的（ ）次序遍历。A. 先根 B. 中根 C. 后根 D. 层次10. 在用 Kruskal 算法求解带权连通图的最小（代价）生成树时，选择权值最小的边的原则是该边不能在图中构成（ ） 。A. 重边 B. 有向环 C. 回路
3、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.
4、 极小 B. 连通 C. 极小连通 D. 无环15. n (n1) 个顶点的强连通图中至少含有（ ）条有向边。A. n-1 B. n n(n-1)/2 D. n(n-1)16. 在一个带权连通图 G 中，权值最小的边一定包含在 G 的（ ）生成树中。A. 某个最小 B. 任何最小 C. 广度优先 D.深度优先17. 对于具有 e 条边的无向图，它的邻接表中有（ ）个结点。A. e-1 B. e C. 2(e-1) D. 2e18. 对于如图所示的带权有向图，从顶点 1 到顶点 5 的最短路径为（ ） 。A.1, 4, 5 B. 1, 2, 3, 5 C. 1, 4, 3, 5 D. 1, 2,
5、 4, 3, 51261 381955412 3219. 一个有 n 个顶点和 n 条边的无向图一定是（ ） 。A. 连通的 B. 不连通的 C. 无环的 D. 有环的20. 对于有向图，其邻接矩阵表示比邻接表表示更易于（ ） 。A. 求一个顶点的度 B. 求一个顶点的邻接点C. 进行图的深度优先遍历 D. 进行图的广度优先遍历21. 与邻接矩阵相比，邻接表更适合于存储（ ）图。A. 无向 B.连通 C.稀疏 D. 稠密图22. 为了实现图的广度优先遍历，BFS 算法使用的一个辅助数据结构是（ ） 。A. 栈 B. 队列 C. 二叉树 D. 树 二、填空题1. 用邻接矩阵存储图，占用存储空间数
6、与图中顶点个数_关，与边数_关。2. n (n0) 个顶点的无向图最多有_条边，最少有_条边。3. n (n0) 个顶点的连通无向图最少有_条边。4. 若 3 个顶点的图 G 的邻接矩阵为 ，则图 G 一定是_向图。015. n (n0) 个顶点的无向图中顶点的度的最大值为_。6. (n0) 个顶点的连通无向图的生成树至少有_条边。7. 在使用 Kruskal 算法构造连通网络的最小生成树时，只有当一条候选边的两个端点不在同一个_上，才有可能加入到生成树中。8. 求解带权连通图最小生成树的 Prim 算法适合于_图的情形，而 Kruskal 算法适合于_图的情形。三、判断题1. 一个图的子图可
7、以是空图，顶点个数为 0。2. 存储图的邻接矩阵中，矩阵元素个数不但与图的顶点个数有关，而且与图的边数也有关。3. 对一个连通图进行一次深度优先搜索（depth first search）可以遍访图中的所有顶点。4. 有 n (n1) 个顶点的无向连通图最少有 n-1 条边。5. 如果无向图中各个顶点的度都大于 2，则该图中必有回路。6. 如果有向图中各个顶点的度都大于 2，则该图中必有回路。7. 图的广度优先搜索（breadth first search）算法不是递归算法。8. 有 n 个顶点、e 条边的带权有向图的最小生成树一般由 n 个顶点和 n-1 条边组成。9. 对于一个边上权值任意
8、的带权有向图，使用 Dijkstra 算法可以求一个顶点到其它各个顶点的最短路径。10. 有回路的有向图不能完成拓扑排序。11. 对任何用顶点表示活动的网络（AOV 网）进行拓扑排序的结果都是唯一的。12. 用边表示活动的网络（AOE 网）的关键路径是指从源点到终点的路径长度最长的路径。13. 对于 AOE 网络，加速任一关键活动就能使整个工程提前完成。14. 对于 AOE 网络，任一关键活动延迟将导致整个工程延迟完成。15. 在 AOE 网络中，可能同时存在几条关键路径，称所有关键路径都需通过的有向边为桥。如果加速这样的桥上的关键活动就能使整个工程提前完成。16. 用邻接矩阵存储一个图时，在
9、不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶点个数有关，而与图的边数无关。17. 邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。18. 邻接矩阵只适用于稠密图（边数接近于顶点数的平方） ，邻接表适用于稀疏图（边数远小于顶点数的平方）319. 存储无向图的邻接矩阵是对称的，因此只要存储邻接矩阵的下（上）三角部分就可以了。20. 连通分量是无向图中的极小连通子图。21. 在 AOE 网络中一定只有一条关键路径。四、运算题1. 设连通图 G 如图所示。试画出该图对应的邻接矩阵表示，并给出对它执行从顶点 V0 开始的广度优先搜索的结果。2. 设连通图 G 如图所示。试
10、画出该图及其对应的邻接表表示，并给出对它执行从 V0 开始的深度优先搜索的结果。3. 对于如图所示的有向图，试写出：(1) 从顶点出发进行深度优先搜索所得到的深度优先生成树；(2) 从顶点出发进行广度优先搜索所得到的广度优先生成树4. 设有向图 G 如图所示。试画出从顶点 V0 开始进行深度优先搜索和广度优先搜索得到的 DFS 生成森林和 BFS 生成森林。5. 设有一个连通网络如图所示。试按如下格式，应用 Kruskal 算法给出在构造最小生成树过程中顺序选出的各条边。V0V1V2V5 V4V3V6V7V8V0V1V2V5 V4V3V6V7V8V1V2 V3V4V7V6V0V5 01 234
11、 56 618 753 4 264( 始顶点号，终顶点号， 权值 )( , , )( , , )( , , )( , , )( , , )6. 设有一个连通网络如图所示。试采用 prim 算法从顶点 0 开始构造最小生成树。 （写出加入生成树顶点集合 S 和选择边 Edge 的顺序）S: 顶点号 Edge: (顶点，顶点，权值)0 ( ， ， )0 ( ， ， )0 ( ， ， )0 ( ， ， )0 ( ， ， )0 7. 有八项活动, 每项活动要求的前驱如下:活动 A0 A1 A2 A3 A4 A5 A6 A7前驱 无前驱 A0 A0 A0, A2 A1 A2, A4 A3 A5, A6(
12、1) 试画出相应的 AOV 网络, 并给出一个拓扑排序序列。(2) 试改变某些结点的编号, 使得用邻接矩阵表示该网络时所有对角线以下的元素全为 0。8. 试对下图所示的 AOE 网络(1) 这个工程最早可能在什么时间结束。 (2) 确定哪些活动是关键活动。画出由所有关键活动构成的图，指出哪些活动加速可使整个工程提前完成。9. 设带权有向图如图所示。试采用 Dijkstra 算法求从顶点 0 到其他各顶点的最短路径和最短路径长度。 1111519102 23445 5661 23 46509 107511 8771824459123 405第 7 章习题参考答案一、单项选择题参考答案： 1. B
13、 2.A 3.B 4.B 5. A 6. B 7. D 8.A 9.D 10.C11. C 12.A 13.C 14.C 15. B16. A 17.D 18. D 19.D 20.A21. C 22. B 二、填空题参考答案： 1. 有, 无 2. n(n-1)/2, 0 3. n-1 4. 有5. (n-1) 6. n-1 7. 连通分量 8. 稠密，稀疏三、判断题参考答案： 1. 否 2. 否 3. 是 4. 是 5. 是6. 否 7. 是 8. 否 9. 否 10. 是11. 否 12. 是 13. 否 14. 是 15. 是16. 是 17. 否 18. 是 19. 是 20. 否
14、21. 否四、运算题参考答案：1. 图 G 对应的邻接矩阵为 0101010.Edge执行广度优先搜索的结果为 V0V1V3V2V4V7V6V5V8，搜索结果不唯一。2. 图 G 对应的邻接表为：31 3 20 3 10 3 50 1 2 6 766213 7 80 V01 V12 V23 V34 V45 V56 V67 V78 V86执行深度优先搜索的结果为：V 0V1V4V3V6V7V8V2V5，搜索结果不唯一。3. 以顶点 为根的深度优先生成树（不唯一）：以顶点 为根的广度优先生成树：4. 深度优先生成森林为： 广度优先生成森林为：应用 Kruskal 算法顺序选出最小生成树的各条边为：
15、( 始顶点号，终顶点号， 权值 )( 0, 3, 1 )( 2, 5, 2 )( 1, 4, 3 )( 3, 5, 4 )( 3, 4, 5 )5. 采用 prim 算法从顶点 0 开始构造最小生成树的过程：S: 顶点号 Edge: (顶点，顶点，权值)0 ( 0， 1， 9 )0, 1 ( 1， 3， 5 )0, 1, 3 ( 1， 2， 7 )0, 1, 3, 2 ( 2， 4， 6 )0, 1, 3, 2, 4 ( 2， 5， 7 )0, 1, 3, 2, 4, 5 V1V2 V3V4V7V6V0V5V1V2 V3V4V7V6V0V501 234 5153 4 21 23 4650975
16、 7 76. 相应的 AOV 网络为：一个拓扑排序序列为：A0,A1,A4,A2,A5,A3,A6,A7。 注意：拓扑排序结果不唯一。按拓扑有序的次序对所有顶点从新编号：原编号 A0 A1 A4 A2 A5 A3 A6 A7新编号 A0 A1 A2 A3 A4 A5 A6 A7相应邻接矩阵为： 7654321000101765432Edge7. 针对下图所示的 AOE 网络各顶点（事件）的最早可能开始时间 Ve(i)和最迟允许开始时间 Vl(i)参看下表：顶点 1 2 3 4 5 6Ve 0 19 15 29 38 43Vl 0 19 15 37 38 43各边（活动）的最早可能开始时间 Ee
17、(k)和最迟允许开始时间 El(k)参看下表：边 Ee 0 0 15 19 15 19 29 38El 17 0 15 19 27 27 37 38如果活动 k 的最早可能开始时间 Ee(k) 与最迟允许开始时间 El(k)相等，则该活动是关键活动。本题A0A1A3A5A2A4A6A71111519102 23445 5668的关键活动为, , , ，它们组成关键路径。这些关键活动中任一个提前完成，整个工程就能提前完成。整个工程最早在 43 天完成。由关键活动组成的 AOV 网络如图所示。8. 带权有向图如图所示：应用 Dijkstra 算法求从顶点 V0 到其他各顶点的最短路径 Path 和
18、最短路径长度 Len 的步骤如下：步骤 V0 V1 V2 V3 V4 动作Path LenPath LenPath LenPath Len1 V0V1 4 V0V3 7 选 V0V1V0V1 4 V0V1V2 8 V0V3 7 参照 V1 调整2 V0V1 4 V0V1V2 8 V0V3 7 选 V0V3V0V1 4 V0V1V2 8 V0V3 7 V0V3V4 12 参照 V3 调整3 V0V1 4 V0V1V2 8 V0V3 7 V0V3V4 12 选 V0V1V2V0V1 4 V0V1V2 8 V0V3 7 V0V1V2V4 10 参照 V2 调整4 V0V1 4 V0V1V2 8 V0V3 7 V0V1V2V4 10 选 V0V1V2V41111519102 23445 56671824459123 40
