《数据结构》习题汇编07第七章图试题 .doc

《《数据结构》习题汇编07第七章图试题 .doc》由会员分享，可在线阅读，更多相关《《数据结构》习题汇编07第七章图试题 .doc（24页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第七章 图 试题一、单项选择题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)/2C. n(n+1)/2 D. n(n-1) 5. n个顶点的连通图至少有（ ）条边。A. n-1 B. nC. n+1D. 06. 在一个无向图中，所有顶点的度数之和等于所

2、有边数的 ( ) 倍。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. 在用Kruskal算法求解带权连

3、通图的最小（代价）生成树时，选择权值最小的边的原则是该边不能在图中构成（ ）。A. 重边B. 有向环C. 回路D. 权值重复的边12. 在用Dijkstra算法求解带权有向图的最短路径问题时，要求图中每条边所带的权值必须是（ ）。A. 非零B. 非整C. 非负D. 非正13. 在一个连通图中进行深度优先搜索得到一棵深度优先生成树，树根结点是关节点的充要条件是它至少有（ ）子女。A. 1B. 2C. 3D. 014. 设有向图有n个顶点和e条边，采用邻接表作为其存储表示，在进行拓扑排序时，总的计算时间为（ ）。A. O(nlog2e)B. O(n+e)C. O(ne)D. O(n2)15. 设有

4、向图有n个顶点和e条边，采用邻接矩阵作为其存储表示，在进行拓扑排序时，总的计算时间为（ ）。A. O(nlog2e)B. O(n+e)C. O(ne)D. O(n2)16. 设G1 = (V1, E1) 和G2 = (V2, E2) 为两个图，如果V1 V2，E1 E2，则称（ ）。 A. G1是G2的子图 B. G2是G1的子图 C. G1是G2的连通分量 D. G2是G1的连通分量17. 有向图的一个顶点的度为该顶点的（ ）。 A. 入度 B. 出度C. 入度与出度之和 D. (入度出度)218. 一个连通图的生成树是包含图中所有顶点的一个（ ）子图。 A. 极小B. 连通C. 极小连通D

5、. 无环19. n (n1) 个顶点的强连通图中至少含有（ ）条有向边。 A. n-1 B. nn(n-1)/2D. n(n-1)20. 在一个带权连通图G中，权值最小的边一定包含在G的（ ）生成树中。 A. 某个最小B. 任何最小C. 广度优先D.深度优先21. 对于具有e条边的无向图，它的邻接表中有（ ）个边结点。 A. e-1B. e C. 2(e-1) D. 2e22. 对于如图所示的带权有向图，从顶点1到顶点5的最短路径为（ ）。 A.1, 4, 5B. 1, 2, 3, 5C. 1, 4, 3, 5D. 1, 2, 4, 3, 51261381955412323. 具有n个顶点的有

6、向无环图最多可包含（ ）条有向边。 A. n-1B. n C. n(n-1)/2 D.n(n-1)24. 一个有n个顶点和n条边的无向图一定是（ ）。 A. 连通的 B. 不连通的 C. 无环的 D. 有环的25. 在n个顶点的有向无环图的邻接矩阵中至少有（ ）个零元素。 A. nB. n(n-1)/2 C. n(n+1)/2D. n(n-1)26. 对于有向图，其邻接矩阵表示比邻接表表示更易于（ ）。 A. 求一个顶点的度 B. 求一个顶点的邻接点 C. 进行图的深度优先遍历 D. 进行图的广度优先遍历27. 在一个有向图的邻接矩阵表示中，删除一条边需要耗费的时间是（ ）。 A. O(1)

7、B. O(i) C. O(j) D. O(i+j)28. 与邻接矩阵相比，邻接表更适合于存储（ ）图。 A. 无向B.连通C.稀疏 D. 稠密图29. 设一个有n个顶点和e条边的有向图采用邻接矩阵表示，要计算某个顶点的出度所耗费的时间是（ ）。 A. O(n) B. O(e) C. O(n+e) D. O(n2)30. 为了实现图的广度优先遍历，BFS算法使用的一个辅助数据结构是（ ）。 A. 栈 B. 队列C. 二叉树 D. 树参考答案：1. B2. A3. B4. B5. A 6. B7. D8. A9. D10. C11.C12. C13. B14. B15. D16. A17. C18

8、. C 19. B 20. A21. D 22. D 23. C24. D 25. C26. A 27. A 28. C 29. A 30. B 二、填空题1. 图的定义包含一个顶点集合和一个边集合。其中，顶点集合是一个有穷_集合。2. 用邻接矩阵存储图，占用存储空间数与图中顶点个数_关，与边数_关。3. n (n0) 个顶点的无向图最多有_条边，最少有_条边。4. n (n0) 个顶点的连通无向图最少有_条边。5. 若3个顶点的图G的邻接矩阵为，则图G一定是_向图。6. n (n0) 个顶点的连通无向图各顶点的度之和最少为_。7. 设图G = (V, E)，V = V0, V1, V2, V

9、3, E = (V0, V1), (V0, V2), (V0, V3), (V1, V3)，则从顶点V0开始的图G的不同深度优先序列有_种，例如_。8. 设图G = (V, E)，V = P, Q, R, S, T, E = , , , ，从顶点P出发，对图G进行广度优先搜索所得的所有序列为_和_。9. n (n0) 个顶点的无向图中顶点的度的最大值为_。10. 在重连通图中每个顶点的度至少为_。11. 在非重连通图中进行深度优先搜索，则深度优先生成树的根为关节点的充要条件是它至少有_个子女。12. (n0) 个顶点的连通无向图的生成树至少有_条边。13. 101个顶点的连通网络N有100条边

10、，其中权值为1, 2, 3, 4, 5, 6, 7, 8, 9, 10的边各10条，则网络N的最小生成树各边的权值之和为_。14. 在使用Kruskal算法构造连通网络的最小生成树时，只有当一条候选边的两个端点不在同一个_上，才有可能加入到生成树中。15. 深度优先生成树的高度比广度优先生成树的高度_。16. 求解带权连通图最小生成树的Prim算法适合于_图的情形，而Kruskal算法适合于_图的情形。17. 求解最短路径的Dijkstra算法适用于各边上的权值_的情形。若设图的顶点数为n，则该算法的时间复杂度为_。18. 若对一个有向无环图进行拓扑排序，再对排在拓扑有序序列中的所有顶点按其先

11、后次序重新编号，则在相应的邻接矩阵中所有_元素将集中到对角线以上。参考答案：1. 非空2. 有, 无3. n(n-1)/2, 04. n-15. 有 6. 2(n-1)7. 4，V0V1V3V2（或V0V2V1V3, V0V2V3V1, V0V3V1V2）8. PQRST和PRQTS9. n-110. 211. 212. n-1 13. 55014. 连通分量15. 高16. 稠密，稀疏17. 非负，O(n2)18. 非零（或值为1的）三、判断题1. 一个图的子图可以是空图，顶点个数为0。2. 存储图的邻接矩阵中，矩阵元素个数不但与图的顶点个数有关，而且与图的边数也有关。3. 一个有1000个

12、顶点和1000条边的有向图的邻接矩阵是一个稀疏矩阵。4. 对一个连通图进行一次深度优先搜索（depth first search）可以遍访图中的所有顶点。5. 有n (n1) 个顶点的无向连通图最少有n-1条边。6. 有n (n1) 个顶点的有向强连通图最少有n条边。7. 图中各个顶点的编号是人为的，不是它本身固有的，因此可以因为某种需要改变顶点的编号。8. 如果无向图中各个顶点的度都大于2，则该图中必有回路。9. 如果有向图中各个顶点的度都大于2，则该图中必有回路。10. 图的深度优先搜索（depth first search）是一种典型的回溯搜索的例子，可以通过递归算法求解。11. 图的广

13、度优先搜索（breadth first search）算法不是递归算法。12. 有n个顶点、e条边的带权有向图的最小生成树一般由n个顶点和n-1条边组成。13. 对于一个边上权值任意的带权有向图，使用Dijkstra算法可以求一个顶点到其它各个顶点的最短路径。14. 对一个有向图进行拓扑排序（topological sorting），一定可以将图的所有顶点按其关键码大小排列到一个拓扑有序的序列中。15. 有回路的有向图不能完成拓扑排序。16. 对任何用顶点表示活动的网络（AOV网）进行拓扑排序的结果都是唯一的。17. 用边表示活动的网络（AOE网）的关键路径是指从源点到终点的路径长度最长的路径

14、。18. 对于AOE网络，加速任一关键活动就能使整个工程提前完成。19. 对于AOE网络，任一关键活动延迟将导致整个工程延迟完成。20. 在AOE网络中，可能同时存在几条关键路径，称所有关键路径都需通过的有向边为桥。如果加速这样的桥上的关键活动就能使整个工程提前完成。21. 用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶点个数有关，而与图的边数无关。22. 邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。23. 邻接矩阵只适用于稠密图（边数接近于顶点数的平方），邻接表适用于稀疏图（边数远小于顶点数的平方）24. 存储无向图的邻接矩阵是对称

15、的，因此只要存储邻接矩阵的下（上）三角部分就可以了。25. 连通分量是无向图中的极小连通子图。26. 强连通分量是有向图中的极大强连通子图。27. 在AOE网络中一定只有一条关键路径。参考答案：1. 否2. 否3. 是4. 是5. 是6. 否7. 是8. 是9. 否10. 是11. 是12. 否13. 否14. 否15. 是16. 否17. 是18. 否19. 是20. 是21. 是22. 否23. 是24. 是25. 否26. 是27. 否四、运算题V0V1V2V5V4V3V6V7V81. 设连通图G如图所示。试画出该图对应的邻接矩阵表示，并给出对它执行从顶点V0开始的广度优先搜索的结果。V

16、0V1V2V5V4V3V6V7V82. 设连通图G如图所示。试画出该图及其对应的邻接表表示，并给出对它执行从V0开始的深度优先搜索的结果。V0V1V2V5V4V3V6V7V83. 设连通图G如图所示。试画出从顶点V0出发的深度优先生成树，指出图G中哪几个顶点是关节点（即万一它失效则通信网络将发生故障）。4. 设连通图G如图所示， (1) 如果有关节点，请找出所有的关节点。(2) 如果想把该连通图变成重连通图，至少在图中加几条边？如何加？5. 对于如图所示的有向图，试写出：(1) 从顶点出发进行深度优先搜索所得到的深度优先生成树；(2) 从顶点出发进行广度优先搜索所得到的广度优先生成树V1V2V

17、3V4V7V6V0V56. 设有向图G如图所示。试画出从顶点V0开始进行深度优先搜索和广度优先搜索得到的DFS生成森林和BFS生成森林。7. 表示图的另一种方法是使用关联矩阵INC 。其中，一行对应于一个顶点，一列对应于一条边。因此，如果边j依附于顶点i，则INCij=1。如果ADJ是图G =（V, E）的邻接矩阵，INC是关联矩阵，试说明在什么条件下将有ADJ = INCINCT-I，其中，INCT是矩阵INC的转置矩阵，I是单位矩阵。两个nn的矩阵的乘积C = AB定义为公式中的 定义为按位加， 定义为按位乘。设无向图G如图所示。试画出该图的邻接矩阵和关联矩阵。01234567e0e1e2

18、e3e4e5e7e6e8e901234566187534268. 设有一个连通网络如图所示。试按如下格式，应用Kruskal算法给出在构造最小生成树过程中顺序选出的各条边。 ( 始顶点号，终顶点号， 权值 )( , , )( , , )( , , )( , , )( , , )9. 设有一个连通网络如图所示。试采用prim算法从顶点0开始构造最小生成树。（写出加入生成树顶点集合S和选择边Edge的顺序）1234650910751187S:顶点号Edge:(顶点，顶点，权值)0( ， ， )0( ， ， )0 ( ， ， )0( ， ， )0( ， ， )0 10. 计算连通网的最小生成树的Di

19、jkstra算法可简述如下：将连通网所有的边以方便的次序逐条加入到初始为空的生成树的边集合T中。每次选择并加入一条边时，需要判断它是否会与先前加入T中的边构成回路。如果构成了回路，则从这个回路中将权值最大的边退选。如果以邻接矩阵作为连通网的存储结构（仅使用矩阵的上三角部分），并在邻接矩阵的下三角部分记录最小生成树的边信息。试以如下所示的图G为例，画出构造出最小生成树及其邻接矩阵，并在括号内填入每次选择的边和可能去掉的边。26211118141619956选 择 的 边去 掉 的 边（顶点,顶点,权值）（顶点,顶点,权值）（ , , ）（ , , ）（ , , ）（ , , ）（ , , ）（

20、, , ）（ , , ）（ , , ）（ , , ）（ , , ）（ , , ）（ , , ）（ , , ）（ , , ）（ , , ）（ , , ）（ , , ）（ , , ）（ , , ）（ , , ）11. 有八项活动, 每项活动要求的前驱如下:活动A0A1A2A3A4A5A6A7前驱无前驱A0A0A0, A2A1A2, A4A3A5, A6 (1) 试画出相应的AOV网络, 并给出一个拓扑排序序列。(2) 试改变某些结点的编号, 使得用邻接矩阵表示该网络时所有对角线以下的元素全为0。12. 试对下图所示的AOE网络(1) 这个工程最早可能在什么时间结束。 (2) 确定哪些活动是关键活动

21、。画出由所有关键活动构成的图，指出哪些活动加速可使整个工程提前完成。11115191022344556613. 设带权有向图如图所示。试采用Dijkstra算法求从顶点0到其他各顶点的最短路径和最短路径长度。 718244591234014. 一项工程由六个子工程p1, p2, , p6组成。这些子工程之间有下列关系：p1 p2, p3 p6, p4 p3, p2 p6, p4 p5, p1 p3, p5 p6。符号“”表示“领先于”的关系。例如，p2 p6表示p2完成后p6才能开始。试给出该工程的三种可能的施工顺序。15. 设一有向图如下所示，请问该有向图是否为强连通图，并画出该有向图所有的

22、强连通分量。gfecabd 参考答案：1. 图G对应的邻接矩阵为执行广度优先搜索的结果为V0V1V3V2V4V7V6V5V8，搜索结果不唯一。2. 图G对应的邻接表为：31320310350126766213780 V01 V12 V23 V34 V45 V56 V67 V78 V8执行深度优先搜索的结果为：V0V1V4V3V6V7V8V2V5，搜索结果不唯一。3. 图GV0V1V2V5V4V3V6V7V8中，从V0出发的深度优先生成树为：图G中的关节点为：V1, V2, V3, V6。4. (1) 关节点为 , , , , (2) 至少加四条边 (1, 10), (3, 4), (4, 5)

23、, (5, 6)。从 的子孙结点到的祖先结点引一条边，从 的子孙结点 到根 的另一分支 引一条边，并将 的子孙结点 、 与结点 连结起来，可使其变为重连通图。（解答不唯一）5. 以顶点 为根的深度优先生成树（不唯一）：以顶点 为根的广度优先生成树：V1V2V3V4V7V6V0V56. 深度优先生成森林为：V1V2V3V4V7V6V0V5广度优先生成森林为：7. 当图中的顶点个数等于边的条数时，ADJ = INC*INCT-I成立。图G对应的邻接矩阵为：对应的关联矩阵为：8. 应用Kruskal算法顺序选出最小生成树的各条边为：01234515342 ( 始顶点号，终顶点号， 权值 ) ( 0,

24、 3, 1 ) ( 2, 5, 2 ) ( 1, 4, 3 ) ( 3, 5, 4 ) ( 3, 4, 5 )9. 采用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 1234650975710. 最小生成树及其邻接矩阵如图所示14165611选 择 的 边去 掉 的 边（顶点,顶点,权值）（顶点,顶点,权值）（ 2 , 1 , 16 ）（ ,

25、 , ）（ 5 , 1 , 14 ）（ , , ）（ 6 , 1 , 21 ）（ , , ）（ 6 , 2 , 19 ）（ 6 , 1 , 21 ）（ 6 , 4 , 11 ）（ , , ）（ 6 , 5 , 26 ）（ 6 , 5 , 26 ）（ 5 , 4 , 18 ）（ 6 , 2 , 19 ）（ 4 , 2 , 9 ）（ 5 , 4 , 18 ）（ 3 , 2 , 5 ）（ , , ）（ 4 , 3 , 6 ）（ 4 , 2 , 9 ）选择顺序不唯一。11. 相应的AOV网络为：A0A1A2A3A4A5A6A7一个拓扑排序序列为：A0,A1,A4,A2,A5,A3,A6,A7。 注意：

26、拓扑排序结果不唯一。按拓扑有序的次序对所有顶点从新编号：原编号A0A1A4A2A5A3A6A7新编号A0A1A2A3A4A5A6A7A0A1A3A5A2A4A6A7相应邻接矩阵为：12. 针对下图所示的AOE网络111151910223445566各顶点（事件）的最早可能开始时间Ve(i)和最迟允许开始时间Vl(i)参看下表：顶点123456Ve01915293843Vl01915373843各边（活动）的最早可能开始时间Ee(k)和最迟允许开始时间El(k)参看下表：边Ee00151915192938El170151927273738如果活动k的最早可能开始时间Ee(k) 与最迟允许开始时间

27、El(k)相等，则该活动是关键活动。本题的关键活动为, , , ，它们组成关键路径。这些关键活动中任一个提前完成，整个工程就能提前完成。整个工程最早在43天完成。由关键活动组成的AOV网络如图所示。111151910223445566718244591234013. 带权有向图如图所示： 应用Dijkstra算法求从顶点V0到其他各顶点的最短路径Path和最短路径长度Len的步骤如下：步骤V0V1V2V3V4动作PathLenPathLenPathLenPathLen1V0V14V0V37选V0V1V0V14V0V1V28V0V37参照V1调整2V0V14V0V1V28V0V37选V0V3V0

28、V14V0V1V28V0V37V0V3V412参照V3调整3V0V14V0V1V28V0V37V0V3V412选V0V1V2V0V14V0V1V28V0V37V0V1V2V410参照V2调整4V0V14V0V1V28V0V37V0V1V2V410选V0V1V2V4p1p2p6p4p5p314. 图G为可能的施工顺序有：p1, p2, p4, p3, p5, p6p1, p4, p2, p3, p5, p6p4, p5, p1, p3, p2, p615. 该图的强连通分量分别为： ecabgfd五、算法分析题1. 已知有向图的邻接矩阵表示及其一个算法描述如下：A =0 1 1 1 10 0 1

29、 0 00 0 0 1 11 1 0 0 00 0 1 1 0const int MaxVertices = 5;struct Graph /图的邻接矩阵表示int EdgeMaxVerticesMaxVertices; /有向图邻接距阵int CurrentNode; /有向图当前结点数int CurrentEdges; /当前边数int unknown ( int i ) int d = 0;for ( int j = 0; j CurrentNode; j+) if ( Edgeij != 0 ) d+;if ( Edgeji != 0 ) d+;return d;(1) 若定义图的一个

30、对象Graph G，则执行操作G.unknown (3) 后的返回值是多少？(2) 试说明该算法的功能及时间复杂度。2. 已知有向图的邻接矩阵表示及其一个操作算法描述如下：A =0 1 1 0 10 0 0 0 00 0 0 1 11 1 0 0 00 0 0 1 0const int MaxVertices = 5;struct Graph /图的邻接矩阵表示int EdgeMaxVerticesMaxVertices; /有向图邻接距阵int CurrentNode; /有向图当前结点数int CurrentEdges; /当前边数void unknown ( int i ) int d,

31、 j;d = 0;for ( j = 0; j CurrentNode; j+ ) if ( Edgeij ) d+; Edgeij = 0; if ( Edgeji ) d+; Edgeji = 0; CurrentEdges -= d;若定义图的一个对象Graph G，试写出执行操作G.unknown (3) 后该图的邻接矩阵，并说明该算法的功能。3. 已知有向图的邻接表类的表示的形式描述如下：struct Edge /邻接表中边结点的定义int dest; /邻接的结点float cost; /边的权值Edge * link;template struct Vertex /邻接表中顶点的

32、定义Type data;Edge *adj;template struct Graph /邻接表Vertex * NodeTable; /顶点表int NumVertices; /当前顶点个数 int NumEdges; /当前边数int DegreeMaxVertices; /各个顶点的度的记录数组/下列算法是计算有向图中各个顶点的度，并保存在数组Degree 中。请在 处/填入合适的内容，使其成为一个完整的算法。void FindDegree ( ) int i; Edge * p = NULL;for ( i = 0; i NumVertices; i+ ) Degreei = (1) ; for ( i = 0; i link ) (2) ; (3) ; ;4. 已知有向图的邻接表类的表示的形式描述如下：struct Edge /邻接表中边结点的定义int dest; /邻接的结点float cost; /边的权值Edge * link;template struct Vertex /邻接表中顶点的定义Type data;Edge *adj;template