图习题及参考答案

1、A.非零B.非整C.非负D.非正12.设 G1=(V1,E1)和 G2=(V2,E2)13.A.GI是 G2的子图C.GI是 G2的连通分量有向图的一个顶点的度为该顶点的（A.入度C.入度与出度之和为两个图，如果 V11V2,E11E2,则称（B. G2是GI的子图D.G2是GI的连通分量）B.出度D.（入度+出度14. 一个连通图的生成树是包含图中所有顶点的一个（A.极小B.连通C.极小连通）/2）子图。D.无环15. n（n1）个顶点的强连通图中至少含有（A. n-1B. n）条有向边。n（n-1）/216. 在一个带权连通图 G 中，权值最小的边一定包含在 G 的（A.某个最小B.任何最

2、小C.广度优先D.n（n-1）生成树中。D.深度优先17. 对于具有 e 条边的无向图，它的邻接表中有（A.e-1B.e)个结点。C. 2(e-1)D.2e18. 对于如图所示的带权有向图，从顶点到顶点 5 的最短路径为（A.1,4,5C.1,4,3,5D. 1,2,4,3,5第7章习题10 .在用 Kruskal 算法求解带权连通图的最小（代价）生成树时，选择权值最小的边的原则是该边不能在11 .在用 Dijkstra 算法求解带权有向图的最短路径问题时，要求图中每条边所带的权值必须是（A.顶点B.边C. 权D.权值2.在无向图中定义顶点 v， i与Vj之间的路径为从Vi到达 Vj的一个（）

3、。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/2）的数目。1.7.若采用邻接矩阵法存储一个 n 个顶点的无向图，则该邻接矩阵是一个（、单项选择题在无向图中定义顶点的度为与它相关联的（8.A.上三角矢 I 阵 B.稀疏矩阵图的深度优先搜索类似于树的（A.

4、先根B.中根9.图的广度优先搜索类似于树的（A.先根B.中根C.对角矩阵）次序遍历。C.后根）次序遍历。C.后根D.对称矩阵D.层次D.层次图中构成（A.重边）B.有向环C.回路D.权值重复的边B.1,2,3,54953619 .一个有 n 个顶点和 n 条边的无向图一定是（）。A.连通的 B.不连通的 C.无环的 D.有环的20 .对于有向图，其邻接矩阵表示比邻接表表示更易于（）。A.求一个顶点的度 B.求一个顶点的邻接点C.进行图的深度优先遍历 D.进行图的广度优先遍历21 .与邻接矩阵相比，邻接表更适合于存储（）图。A.无向 B.连通 C.稀疏 D.稠密图22 .为了实现图的广度优先遍历

5、，BFS 算法使用的一个辅助数据结构是（）。A.栈 B.队列 C.二叉树 D.树二、填空题1 .用邻接矩阵存储图，占用存储空间数与图中顶点个数关，与边数关。2 .n（n0）个顶点的无向图最多有条边，最少有条边。3 .n（n0）个顶点的连通无向图最少有条边。0104 .若 3 个顶点的图 G 的邻接矩阵为卜00，则图 G 一定是向图。，10一5 .n（n0）个顶点的无向图中顶点的度的最大值为。6 .（n0）个顶点的连通无向图的生成树至少有条边。7 .在使用 Kruskal 算法构造连通网络的最小生成树时，只有当一条候选边的两个端点不在同一个上，才有可能加入到生成树中。8 .求解带权连通图最小生成

6、树的 Prim 算法适合于图的情形，而 Kruskal 算法适合于图的情形。三、判断题1 .一个图的子图可以是空图，顶点个数为 0。2 .存储图的邻接矩阵中，矩阵元素个数不但与图的顶点个数有关，而且与图的边数也有关。3 .对一个连通图进行一次深度优先搜索（depthfirstsearch）可以遍访图中的所有顶点。4 .有 n（n1）个顶点的无向连通图最少有 n-1 条边。5 .如果无向图中各个顶点的度都大于 2,则该图中必有回路。6 .如果有向图中各个顶点的度都大于 2,则该图中必有回路。7 .图的广度优先搜索（breadthfirstsearch）算法不是递归算法。8 .有 n 个顶点、e

7、条边的带权有向图的最小生成树一般由 n 个顶点和 n-1 条边组成。9 .对于一个边上权值任意的带权有向图，使用 Dijkstra 算法可以求一个顶点到其它各个顶点的最短路径。10 .有回路的有向图不能完成拓扑排序。11 .对任何用顶点表示活动的网络（AOV 网）进行拓扑排序的结果都是唯一的。12 .用边表示活动的网络（AOE 网）的关键路径是指从源点到终点的路径长度最长的路径。13 .对于 AOE 网络，加速任一关键活动就能使整个工程提前完成。14 .对于 AOE 网络，任一关键活动延迟将导致整个工程延迟完成。15 .在 AOE 网络中，可能同时存在几条关键路径，称所有关键路径都需通过的有向

8、边为桥。如果加速这样的桥上的关键活动就能使整个工程提前完成。16 .用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶点个数有关，而与图的边数无关。17 .邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。18 .邻接矩阵只适用于稠密图（边数接近于顶点数的平方），邻接表适用于稀疏图（边数远小于顶点数的平方）19 .存储无向图的邻接矩阵是对称的，因此只要存储邻接矩阵的下（上）三角部分就可以了。20 .连通分量是无向图中的极小连通子图。21 .在 AOE 网络中一定只有一条关键路径。四、运算题1.设连通图 G 如图所示。试画出该图对应的邻接矩阵表示

9、，并给出对它执行从顶点搜索的结果。3 .对于如图所示的有向图，试写出:(1)从顶点出发进行深度优先搜索所得到的深度优先生成树;(2)从顶点出发进行广度优先搜索所得到的广度优先生成树4 .设有向图 G 如图所示。试画出从顶点 V。开始进行深度优先搜索和广度优先搜索得到的 DFS 生成森林和 BFS 生成森林。V0开始的广度优先2.设连通图 G 如图所示。试画出该图及其对应的邻接表表示，并给出对它执行从V0开始的深度优先搜索的结果。5.设有一个连通网络如图所示。试按如下格式，应用出的各条边。Kruskal 算法给出在构造最小生成树过程中顺序选(始顶点号，终顶点号，权值)(,)(,)(,)(,)(,

10、)S:顶点号Edge:(顶点,顶点，权值)0(,)0(,)0(,)0(,)0(,)07 .有八项活动，每项活动要求的前驱如下活动A0A1A2A3A4A5A6A7前驱无前驱A0A0A0,A2A1A2,A4A3A5,A6(1)试画出相应的 AOV 网络，并给出一个拓扑排序序列。(2)试改变某些结点的编号，使得用邻接矩阵表示该网络时所有对角线以下的元素全为 0。8 .试对下图所示的 AOE 网络(1)这个工程最早可能在什么时间结束。(2)确定哪些活动是关键活动。画出由所有关键活动构成的图，指出哪些活动加速可使整个工程提前完成。9 .设带权有向图如图所示。试采用 Dijkstra 算法求从顶点6.设有

11、一个连通网络如图所示。试采用集合 S 和选择边 Edge 的顺序)prim 算法从顶点 0 开始构造最小生成树。(写出加入生成树顶点0 到其他各顶点的最短路径和最短路径长度。第7章习题参考答案一、单项选择题参考答案：1.B2.A3.B4.B5.A6.B7.D8.A9.D10.C11.C12.A13.C14.C15.B16.A17.D18.D19.D20.A21.C22.B二、填空题参考答案：1.有，无2.n(n-1)/2,03.n-14.有5.(n-1)6.n-17.连通分量8.稠密， 稀疏三、判断题参考答案：1.否2.否3.是4.是5.是6.否7.是8.否9.否10.是11.否12.是13.

12、否14.是15.是16.是 17.否 18.是 19.是 20.否 21.否四、运算题参考答案：执行广度优先搜索的结果为 V0V1V3V2V4V7V6V5V8,搜索结果不唯一。2 .图 G 对应的邻接表为：1.图 G 对应的邻接矩阵为G.Edge=0111010011000100101001000001100001010000001100000000000001000111001000001000123456执行深度优先搜索的结果为：V0V1V4V3V6V7V8V2V5,搜索结果不唯一。3 .以顶点为根的深度优先生成树（不唯一）：以顶点为根的广度优先生成树5.采用 prim 算法从顶点 0 开

13、始构造最小生成树的过程:S:顶点号Edge:（顶点,顶点，权值）0(0,19)0,1(13,5)0,1,3(12,7)0,1,3,2(2,4,6)0,1,3,2,4(2,5,7)0,1,3,2,4,5(0,3,1)(2,5,2)(1,4,3)(3,5,4)(3,4,5)4.应用 Kruskal 算法顺序选出最小生成树的各条边为：（始顶点号，终顶点号，权值）6.相应的 AOV 网络为:一个拓扑排序序列为：A0,A1,A4,A2,A5,A3,A6,A7。注意：拓扑排序结果不唯一。按拓扑有序的次序对所有顶点从新编号：原编号A0A1A4A2A5A3A6A7新编号A0A1A2A3A4A5A6A7相应邻接

14、矩阵为:3456710100-00000017.针对下图所示的Edge=0010030014010500160007各顶点(事件)的最早可能开始时间Ve(i)和最迟允许开始时间 Vl(i)参看下表:顶点123456Ve01915293843Vl01915373843各边(活动)的最早可能开始时间Ee(k)和最迟允许开始时间El(k)参看卜表边Ee00151915192938El170151927273738如果活动 k 的最早可能开始时间 Ee(k)与最迟允许开始时间日(k)相等，则该活动是关键活动。关键活动为,它们组成关键路径。这些关键活动中任一个提前完成，整个工程就能提前完成。本题的网络AOE整个工程最早在 43 天完成。由关键活动组成的 AOV 网络如图所示。V0到其他各顶点的最短路径 Path 和最短路径长度 Len 的步骤如下:步骤V0VIV2V3V4动作PathLenPathLenPathLenPathLen1V0V140