第7章-图习题及参考答案

PAGEPAGE4第7章习题一、单项选择题在无向图中定义顶点的度为与它相关联的（）的数目。A.顶点 B.边 C.权 D.权值在无向图中定义顶点vi与vj之间的路径为从vi到达vj的一个（）。A.顶点序列 B.边序列 C.权值总和 D.边的条数图的简单路径是指（）不重复的路径。A.权值 B.顶点 C.边 D.边与顶点均设无向图的顶点个数为n，则该图最多有（）条边。A.n-1 B.n(n-1)/2 C.n(n+1)/2 D.n(n-n个顶点的连通图至少有（）条边。A.n-1 B.n C.n+1 D.0在一个无向图中，所有顶点的度数之和等于所有边数的()倍。A.3 B.2 C.1 D.1/2若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个()。A.上三角矩阵 B.稀疏矩阵 C.对角矩阵 D.对称矩阵图的深度优先搜索类似于树的（）次序遍历。A.先根 B.中根 C.后根 D.层次图的广度优先搜索类似于树的（）次序遍历。A.先根 B.中根 C.后根 D.层次在用Kruskal算法求解带权连通图的最小（代价）生成树时，选择权值最小的边的原则是该边不能在图中构成（）。A.重边 B.有向环 C.回路 D.权值重复的边在用Dijkstra算法求解带权有向图的最短路径问题时，要求图中每条边所带的权值必须是（）。A.非零 B.非整 C.非负 D.非正设G1=(V1,E1)和G2=(V2,E2)为两个图，如果V1V2，E1E2，则称（）。 A.G1是G2的子图 B.G2是G1的子图 C.G1是G2的连通分量 D.G2是G1的连通分量有向图的一个顶点的度为该顶点的（）。 A.入度 B.出度C.入度与出度之和 D.(入度﹢出度))／2一个连通图的生成树是包含图中所有顶点的一个（）子图。 A.极小 B.连通 C.极小连通 D.无环n(n＞1)个顶点的强连通图中至少含有（）条有向边。 A.n-1 B.n n(n-1)/2 D.n(n-1)在一个带权连通图G中，权值最小的边一定包含在G的（）生成树中。 A.某个最小 B.任何最小 C.广度优先 D.深度优先对于具有e条边的无向图，它的邻接表中有（）个结点。 A.e-1 B.e C.2(e-1) D.2e对于如图所示的带权有向图，从顶点1到顶点5的最短路径为（）。 A.1,4,5 B.1,2,3,5 C.1,4,3,5 D.1,2,4,3,5112613819554123一个有n个顶点和n条边的无向图一定是（）。 A.连通的 B.不连通的 C.无环的 D.有环的对于有向图，其邻接矩阵表示比邻接表表示更易于（）。 A.求一个顶点的度 B.求一个顶点的邻接点 C.进行图的深度优先遍历 D.进行图的广度优先遍历与邻接矩阵相比，邻接表更适合于存储（）图。 A.无向 B.连通 C.稀疏 D.稠密图为了实现图的广度优先遍历，BFS算法使用的一个辅助数据结构是（）。 A.栈 B.队列 C.二叉树 D.树二、填空题用邻接矩阵存储图，占用存储空间数与图中顶点个数________关，与边数________关。n(n﹥0)个顶点的无向图最多有________条边，最少有________条边。n(n﹥0)个顶点的连通无向图最少有________条边。若3个顶点的图G的邻接矩阵为，则图G一定是________向图。n(n﹥0)个顶点的无向图中顶点的度的最大值为________。(n﹥0)个顶点的连通无向图的生成树至少有________条边。在使用Kruskal算法构造连通网络的最小生成树时，只有当一条候选边的两个端点不在同一个________上，才有可能加入到生成树中。求解带权连通图最小生成树的Prim算法适合于________图的情形，而Kruskal算法适合于________图的情形。三、判断题一个图的子图可以是空图，顶点个数为0。存储图的邻接矩阵中，矩阵元素个数不但与图的顶点个数有关，而且与图的边数也有关。对一个连通图进行一次深度优先搜索（depthfirstsearch）可以遍访图中的所有顶点。有n(n≥1)个顶点的无向连通图最少有n-1条边。如果无向图中各个顶点的度都大于2，则该图中必有回路。如果有向图中各个顶点的度都大于2，则该图中必有回路。图的广度优先搜索（breadthfirstsearch）算法不是递归算法。有n个顶点、e条边的带权有向图的最小生成树一般由n个顶点和n-1条边组成。对于一个边上权值任意的带权有向图，使用Dijkstra算法可以求一个顶点到其它各个顶点的最短路径。有回路的有向图不能完成拓扑排序。对任何用顶点表示活动的网络（AOV网）进行拓扑排序的结果都是唯一的。用边表示活动的网络（AOE网）的关键路径是指从源点到终点的路径长度最长的路径。对于AOE网络，加速任一关键活动就能使整个工程提前完成。对于AOE网络，任一关键活动延迟将导致整个工程延迟完成。在AOE网络中，可能同时存在几条关键路径，称所有关键路径都需通过的有向边为桥。如果加速这样的桥上的关键活动就能使整个工程提前完成。用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶点个数有关，而与图的边数无关。邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。邻接矩阵只适用于稠密图（边数接近于顶点数的平方），邻接表适用于稀疏图（边数远小于顶点数的平方）存储无向图的邻接矩阵是对称的，因此只要存储邻接矩阵的下（上）三角部分就可以了。连通分量是无向图中的极小连通子图。第7章习题参考答案一、单项选择题参考答案： 1.B 2.A 3.B 4.B 5.A6.B 7.D 8.A 9.D 10.C 11.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.否21. 否 四、运算题参考答案：图G对应的邻接矩阵为执行广度优先搜索的结果为V0V1V3V2V4V7V6V5V8，搜索结果不唯一。图G对应的邻接表为：331320310350126766213780V01V12V23V34V45V56V67V78V8∧∧∧∧∧∧∧∧∧执行深度优先搜索的结果为：V0V1V4V3V6V7V8V2V5，搜索结果不唯一。以顶点①为根的深度优先生成树（不唯一）：①②①②③④⑤①②③④⑤以顶点②为根的广度优先生成树：①①②③④⑤V1V2V1V2V3V4V7V6V0V5V1V2V3V4V7V6V0V5012301234515342 (始顶点号，终顶点号，权值) (0,3,1) (2,5,2) (1,4,3) (3,5,4) (3,4,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,5112346509757A0A1AA0A1A3A5A2A4A6A7一个拓扑排序序列为：A0,A1,A4,A2,A5,A3,A6,A7。注意：拓扑排序结果不唯一。按拓扑有序的次序对所有顶点从新编号：原编号A0A1A4A2A5A3A6A7新编号A0A1A2A3A4A5A6A7 相应邻接矩阵为：针对下图所示的AOE网络1111151910223445566各顶点（事件）的最早可能开始时间Ve(i)和最迟允许开始时间Vl(i)参看下表：顶点123456Ve01915293843Vl01915373843 各边（活动）的最早可能开始时间Ee(k)和最迟允许开始时间El(k)参看下表：边<1,2><1,3><3,2><2,5><3,5><2,4><4,6><5,6>Ee00151915192938El170151927273738 如果活动k的最早可能开始时间Ee(k)与最迟允许开始时间El(k)相等，则该活动是关键活动。本题的关键活动为<1,3>,<3,2>,<2,5>,<5,6>，它们组成关键路径。这些关键活动中任一个提前完成，整个工程就能提前完成。 整个工程最早在43天完成。由关键活动组成的AOV网络如图所示。1111151910223445566717182445912340 应用Dijkstra算法求从顶点V0到其他各顶点的最短路径Path和最短路径长度Len的步骤如下：步骤V0V1V2V