图习题及参考答案

第7章习题一、单项选择题1.在无向图中定义顶点的度为与它相关联的（）的数目。A.顶点B.边C.权D.权值2.在无向图中定义顶点vi与vj之间的路径为从vi到达vj的一个（）。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.nn(n-1)/2D.n(n-1)16.在一个带权连通图G中，权值最小的边一定包含在G的（）生成树中。A.某个最小B.任何最小C.广度优先D.深度优先17.对于具有e条边的无向图，它的邻接表中有（）个结点。A.e-1B.eC.2(e-1)D.2e18.对于如图所示的带权有向图，从顶点1到顶点5的最短路径为（）。,4,5B.1,2,3,5C.1,4,3,5D.1,2,4,3,51261381955412319.一个有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.对一个连通图进行一次深度优先搜索（depthfirstsearch）可以遍访图中的所有顶点。4.有n(n≥1)个顶点的无向连通图最少有n-1条边。5.如果无向图中各个顶点的度都大于2，则该图中必有回路。6.如果有向图中各个顶点的度都大于2，则该图中必有回路。7.图的广度优先搜索（breadthfirstsearch）算法不是递归算法。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如图所示。试画出该图对应的邻接矩阵表示，并给出对它执行从顶点V0开始的广度优先搜索的结果。2.设连通图G如图所示。试画出该图及其对应的邻接表表示，并给出对它执行从V0开始的深度优先搜索的结果。3.对于如图所示的有向图，试写出：(1)从顶点①出发进行深度优先搜索所得到的深度优先生成树；(2)从顶点②出发进行广度优先搜索所得到的广度优先生成树4.设有向图G如图所示。试画出从顶点V0开始进行深度优先搜索和广度优先搜索得到的DFS生成森林和BFS生成森林。5.设有一个连通网络如图所示。试按如下格式，应用Kruskal算法给出在构造最小生成树过程中顺序选出的各条边。V0V1V2V5V4V3V6V7V8V0V1V2V5V4V3V6V7V8V1V2V3V4V7V6V0V5①②③④⑤0123456618753426(始顶点号，终顶点号，权值)(,,)(,,)(,,)(,,)(,,)6.设有一个连通网络如图所示。试采用prim算法从顶点0开始构造最小生成树。（写出加入生成树顶点集合S和选择边Edge的顺序）S:顶点号Edge:(顶点，顶点，权值)0(，，)0(，，)0(，，)0(，，)0(，，)07.有八项活动,每项活动要求的前驱如下:活动A0A1A2A3A4A5A6A7前驱无前驱A0A0A0,A2A1A2,A4A3A5,A6(1)试画出相应的AOV网络,并给出一个拓扑排序序列。(2)试改变某些结点的编号,使得用邻接矩阵表示该网络时所有对角线以下的元素全为0。8.试对下图所示的AOE网络(1)这个工程最早可能在什么时间结束。(2)确定哪些活动是关键活动。画出由所有关键活动构成的图，指出哪些活动加速可使整个工程提前完成。9.设带权有向图如图所示。试采用Dijkstra算法求从顶点0到其他各顶点的最短路径和最短路径长度。11115191022344556612346509107511877182445912340第7章习题参考答案一、单项选择题参考答案：1.B5.A6.B7.D11.C15.B16.A18.D21.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.否14.是15.是16.是17.否18.是19.是20.否21.否四、运算题参考答案：1.图G对应的邻接矩阵为001000000001001000110001000000000100000000010011000111000101001000011001000001110G.Edge执行广度优先搜索的结果为V0V1V3V2V4V7V6V5V8，搜索结果不唯一。2.图G对应的邻接表为：31320310350126766213780V01V12V23V34V45V56V67V78V8∧∧∧∧∧∧∧∧∧执行深度优先搜索的结果为：V0V1V4V3V6V7V8V2V5，搜索结果不唯一。3.以顶点①为根的深度优先生成树（不唯一）：以顶点②为根的广度优先生成树：4.深度优先生成森林为：广度优先生成森林为：应用Kruskal算法顺序选出最小生成树的各条边为：(始顶点号，终顶点号，权值)(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,5V1V2V3V4V7V6V0V5V1V2V3V4V7V6V0V50123451534212346509757①②③④⑤①②③④⑤①②③④⑤6.相应的AOV网络为：一个拓扑排序序列为：A0,A1,A4,A2,A5,A3,A6,A7。注意：拓扑排序结果不唯一。按拓扑有序的次序对所有顶点从新编号：原编号A0A1A4A2A5A3A6A7新编号A0A1A2A3A4A5A6A7相应邻接矩阵为：76543210000000001000000001000000100000000011000000010000000001000010101076543210Edge7.针对下图所示的AOE网络各顶点（事件）的最早可能开始时间Ve(i)和最迟允许开始时间Vl(i)参看下表：顶点123456Ve01915293843Vl01915373843各边（活动）的最早可能开始时间Ee(k)和最迟允许开始时间El(k)参看下表：边1,21,33,22,53,52,44,65,6Ee00151915192938El170151927273738如果活动k的最早可能开始时间Ee(k)与最迟允许开始时间El(k)相等，则该活动是关键活动。本题A0A1A3A5A2A4A6A7111151910223445566的关键活动为1,3,3,2,2,5,5,6，它们组成关键路径。这些关键活动中任一个提前完成，整个工程就能提前完成。整个工程最早在43天完成。由关键活动组成的AOV网络如图所示。8.带权有向图如图所示：应用Dijkstra算法求从顶点V0到其他各顶点的最短路径Path和最短路径长度Len的步骤如下：步骤V0V1V2V3V4动作PathLenPathLenPathLenPathLen1V0V14—∞V0V37—∞选V0V1V0V14V0V1V28V0V37—∞参照V1调整2V0V14V0V1V28V0V37—∞选V0V3V0V14V0V1V28V0V37V0V3V412参照V3调整3V0V14V0V1V28V0V37V0V3V412选V0V1V2V0V14V0V1V28V0V37V0V1V2V410参照V2调整4V0V14V0V1V28V0V37V0V1V2V410选V0V1V2V41111519102234455667182445912340