根据有向图的广优先搜索遍历算法.pptx

图练习图练习一、选择题一、选择题1.一个有一个有n个顶点的无向图最多有（个顶点的无向图最多有（）条）条边。边。A.nB.n(n-1)C.n(n-1)/2D.2nC2.具有具有6个顶点的无向图至少应有（个顶点的无向图至少应有（）条条边边才才能确保是一个连通图。能确保是一个连通图。A.5B.6C.7D.8A3.具具有有n个个顶顶点点且且每每一一对对不不同同的的顶顶点点之之间间都都有有一一条边的图被称为（条边的图被称为（）A.线性图线性图B.无向完全图无向完全图C.无向图无向图D.简单图简单图B4.具有具有4个顶点的无向完全图有（个顶点的无向完全图有（）条边。）条边。A.6B.12C.16D.20A5.G是一个非连通无向图，共有是一个非连通无向图，共有28条边，条边，则该图至少有（则该图至少有（）个顶点。）个顶点。A.6B.7C.8D.9D6.存储稀疏图的数据结构常用的是（存储稀疏图的数据结构常用的是（）A.链接矩阵链接矩阵B.三元组三元组C.链接表链接表D.十字链表十字链表C7.对对一一个个具具有有n个个顶顶点点的的图图，采采用用链链接接矩阵表示则该矩阵的大小为（矩阵表示则该矩阵的大小为（）A.nB.(n-1)2C.(n+1)2D.n2D8.设连通图设连通图G的顶点数为的顶点数为n，则则G的生成的生成树的边数为（树的边数为（）A.n-1B.nC.2nD.2n-1A9.N个个顶顶点点的的无无向向图图的的链链接接表表中中结结点点总总数数最多有（最多有（）个。）个。A.2nB.nC.n/2D.n(n-1)D10.对对于于一一个个具具有有n个个顶顶点点和和e条条边边的的无无向向图图，若若采采用用链链接接表表表表示示，则则表表向向量量的的大大小小为为（），所所有有顶顶点点链链接接表表的的结结点点总总数数为为（）。）。A.nB.n+1C.n-1D.2nE.e/2F.eG.2eH.n+eAG11.从从链链接接矩矩阵阵可可以以看看出出，该该图图共有（共有（）个个顶顶点点。如如果果是是有有向向图，该图共有（图，该图共有（）条条弧弧；如如果果是有向图，则共有（是有向图，则共有（）条边。）条边。A.9B.3C.6D.1E.5F.4G.2H.0BFG12.在有向图的链接表存储结构中，顶在有向图的链接表存储结构中，顶点点V在表结点中出现的次数是（在表结点中出现的次数是（）A.顶点顶点v的度的度B.顶点顶点v的出度的出度C.顶点顶点v的入度的入度D.依附于顶点依附于顶点v的边的边C13.在用链接表表示图的情况下，建立在用链接表表示图的情况下，建立图的算法的时间复杂度为（图的算法的时间复杂度为（）A.O(n+e)B.O(n2)C.O(n*e)D.O(n3)A14.用用DFS遍历一个无环有向图，并在遍历一个无环有向图，并在DFS算法退栈返回时，打印出相应的算法退栈返回时，打印出相应的顶点，则输出的顶点序列是（顶点，则输出的顶点序列是（）。）。A.逆拓扑有序的逆拓扑有序的B.拓扑有序的拓扑有序的C.无序的无序的A15.已知一个图如图已知一个图如图7-13所示，若从顶点所示，若从顶点a出发按出发按深度优先搜索法进行遍历，则可能得到的是一深度优先搜索法进行遍历，则可能得到的是一种顶点序列为（种顶点序列为（）；按广度优先搜索法进行）；按广度优先搜索法进行遍历，则可能得到的一种顶点序列为（遍历，则可能得到的一种顶点序列为（）。）。(1)A.abecdfB.acfebdC.acebfdD.acfdeb(2)A.abcedfB.abcefdC.abedfcD.acfdebDBabcedf图7-1316.采用链接矩阵时，遍历图时的顶点所需时间采用链接矩阵时，遍历图时的顶点所需时间为（为（），采用链接表时，遍历图的顶点所需），采用链接表时，遍历图的顶点所需时间为（时间为（）（注：设图有）（注：设图有n个顶点，个顶点，e条边）条边）A.O(n)B.O(n2)C.O(e)D.O(n*e)E.O(n+e)BE17.采用链接表存储的图的深度优先搜采用链接表存储的图的深度优先搜索遍历算法类似于二叉树的（索遍历算法类似于二叉树的（）A.中序遍历中序遍历 B.先序遍历先序遍历C.后序遍历后序遍历 D.按层遍历按层遍历B18.采用链接表存储的图的广度优先搜采用链接表存储的图的广度优先搜索遍历算法类似于二叉树的（索遍历算法类似于二叉树的（）A.中序遍历中序遍历B.先序遍历先序遍历C.后序遍历后序遍历 D.按层遍历按层遍历D19.已知一有向图的链接表存储结构如图已知一有向图的链接表存储结构如图7-14（见下页）所示。（见下页）所示。（1）根根据据有有向向图图的的深深度度优优先先搜搜索索遍遍历历算算法法，从从顶顶点点V1出出发发，所所得得到到的的顶顶点点序序列列是（是（）。）。A.v1,v2,v3,v5,v4B.v1,v2,v3,v4,v5C.v1,v2,v3,v5,v4D.v1,v4,v3,v5,v2（2）根根据据有有向向图图的的广广度度优优先先搜搜索索遍遍历历算算法法，从从顶顶点点V1出出发发，所所得得到到的的顶顶点点序序列列是（是（）。）。A.v1,v2,v3,v5,v4B.v1,v3,v2,v4,v5C.v1,v2,v3,v5,v4D.v1,v4,v3,v5,v2CBv1v2v3v4v5213341301234图7-1420.已知有已知有8个顶点值为个顶点值为A，B，C，D，E，F，G，H的无向图，其邻接矩阵的存储结的无向图，其邻接矩阵的存储结构如图构如图7-15所示（见下页）。由此结构，所示（见下页）。由此结构，从从A顶点开始深度优先搜索遍历，得到的顶点开始深度优先搜索遍历，得到的顶点序列是（顶点序列是（）。）。A.ABCDGHFEB.ABCDGFHEC.ABGHFECDD.ABFHEGDCE.ABEHFGDCF.ABEHGFCDBABCDEFGHA01010000B10101110C01010000D10100010E01 000001F01000011G01010101H00001110图7-1521.已知一个图如图已知一个图如图7-16（见下页）所示，（见下页）所示，在该图的最小生成树中各条边上权值之和在该图的最小生成树中各条边上权值之和为（为（），在该图的最小生成树中，），在该图的最小生成树中，从顶点从顶点V1到顶点到顶点V6的路径为（的路径为（）A.31B.38C.36D.43E.v1,v3.v6F.v1,v4,v6G.v1,v5,v4,v6 H.v1,v4,v3,v6CG图图7-163125461215201098864522.已知一个图如图已知一个图如图7-17所示，则依据所示，则依据迪杰斯特拉算法将按照（迪杰斯特拉算法将按照（）顶点次）顶点次序依次求出从顶点序依次求出从顶点V1到其余各顶点的到其余各顶点的最短路径。最短路径。A.v2,v5,v4,v6,v3B.v2,v5,v4,v3,v6C.v2,v3,v5,v4,v1D.v5,v4,v6,v3,v2B图图7-17312546312756151023.在一个有在一个有n个顶点的无向网中，有个顶点的无向网中，有条边，则应该选用条边，则应该选用()算法来求这个网的最小生成树，从而算法来求这个网的最小生成树，从而使计算时间较少。使计算时间较少。A.PrimB.KruskalB24.关键路径是事件结点网络中的（关键路径是事件结点网络中的（）A.从源点到汇点的最长路径从源点到汇点的最长路径B.从源点到汇点的最短路径从源点到汇点的最短路径C.最长回路最长回路D.最短回路最短回路A25.正确的正确的AOE网而言，必须是（网而言，必须是（），），AOE中，某边权值应当是（中，某边权值应当是（）权值）权值为零的边表示（为零的边表示（）（1）A.完全图完全图 B.哈密尔顿图哈密尔顿图C.无环图无环图 D.强连通图强连通图（2）A.实数实数B正整数正整数C.正数正数D.非负数非负数（3）A.为决策而增加的活动为决策而增加的活动B.为计算方便而增加的活动为计算方便而增加的活动C.表示活动间的时间顺序关系表示活动间的时间顺序关系D.该活动为关键活动该活动为关键活动CDB26.当各边上权值（当各边上权值（）时，）时，BFS算算法可以用解决单源点最短路径的问题。法可以用解决单源点最短路径的问题。A.均相等均相等B.均不相等均不相等C.不一定相等不一定相等A27.已知一个图如图已知一个图如图7-18所示，则由该所示，则由该图得到的一种拓扑序列为（图得到的一种拓扑序列为（）A.v1,v4,v6,v2,v5,v3 A.v1,v4,v6,v2,v5,v3 B.v1,v2,v3,v4,v5,v6 B.v1,v2,v3,v4,v5,v6 C.v1,v4,v2,v3,v6,v5 C.v1,v4,v2,v3,v6,v5 D.v1,v2,v4,v6,v3,v5 D.v1,v2,v4,v6,v3,v5 A图7-1831254628.判断一个有向图是否存在回路，除了可判断一个有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用以利用拓扑排序方法外，还可以利用（）。A.求关键路径的方法求关键路径的方法B.求最短路径的求最短路径的Dijksra方法方法C.深度优先搜索遍历算法深度优先搜索遍历算法D.广度优先搜索遍历算法广度优先搜索遍历算法C29.下面结论中正确的是（下面结论中正确的是（）A.在无向图中，边的条数是结点度数之和。在无向图中，边的条数是结点度数之和。B.在在图图结结构构中中，结结点点可可以以没没有有任任何何前前趋趋和和后继后继.。C.在在n个个结结点点的的无无向向图图中中，若若边边数数大大于于n-1，则该图必是连通图。则该图必是连通图。D.图的链接矩阵必定是对称矩阵图的链接矩阵必定是对称矩阵B30.下面结论中正确的是（下面结论中正确的是（）A.若若有有向向图图的的链链接接矩矩阵阵中中对对角角线线以以下下元元素素均为零，则该图的拓扑排序必定存在均为零，则该图的拓扑排序必定存在B.网络的最小代价生成树是惟一的网络的最小代价生成树是惟一的C.在在拓拓扑扑排排序序序序列列中中，任任意意两两个个相相继继结结点点vi和和vj都存在从都存在从vi到到vj的路径的路径 D.D.在有向图中，从一个结点到另一个结点在有向图中，从一个结点到另一个结点的最短路径是惟一的的最短路径是惟一的A31.下面结论中不正确的是（下面结论中不正确的是（）A.无无向向图图的的连连通通分分量量是是该该图图的的极极大大连连通通子图子图B.有有向向图图用用链链接接矩矩阵阵表表示示，容容易易实实现现求求结点度数的操作。结点度数的操作。C.无无向向图图用用邻邻接接矩矩阵阵表表示示，图图中中的的边边数数等于邻接矩阵元素之和的一半等于邻接矩阵元素之和的一半D.有向图的邻接矩阵必定不是对称矩阵有向图的邻接矩阵必定不是对称矩阵D32.下面结论中正确的是（下面结论中正确的是（）A.按按深深度度优优先先搜搜索索遍遍历历图图时时，与与始始点点相连的结点先于不在始点相连的结点访问。相连的结点先于不在始点相连的结点访问。B.一一个个图图按按深深度度优优先先搜搜索索法法遍遍历历的的结结果是唯一的。果是唯一的。C.若若有有向向图图G中中包包含含一一个个环环，则则G的的结点间不存在在拓扑序列。结点间不存在在拓扑序列。D.图的拓扑排序序列是唯一的。图的拓扑排序序列是唯一的。C33.下面结论中不正确的是（下面结论中不正确的是（）A按按广广度度优优先先搜搜索索遍遍历历图图时时，与与始始点点相相连的结点先于不于始点相连的结点访问。连的结点先于不于始点相连的结点访问。B一一个个图图按按广广度度优优先先搜搜索索法法遍遍历历的的结结果果是唯一的。是唯一的。C无无向向图图的的链链接接表表表表示示法法中中，表表中中结结点点的数目是图中边的条数的数目是图中边的条数2倍。倍。D图图的的多多重重链链接接表表表表示示法法中中，表表中中结结点点的数目是图中边的条数。的数目是图中边的条数。B34.下面结论中正确的是（下面结论中正确的是（）A.在在无无向向图图中中，边边的的条条数数是是结结点点度度数数之之和。和。B用用Prim算算法法和和Kruskal算算法法求求得得的的图图最小生成树相同。最小生成树相同。C在在图图的的连连接接多多重重表表表表示示中中，任任意意一一条条边，边，只用一个表目表示。只用一个表目表示。D在在拓拓扑扑排排序序序序列列中中，任任意意两两个个相相距距结结点点Vi和和Vj之间都存在一条路径。之间都存在一条路径。C二、填空题二、填空题1.N个顶点的连通图至少个顶点的连通图至少_条边。条边。n-1n-12.一一个个无无向向图图有有n n个个顶顶点点和和e e条条边边，则则所所有有顶顶点点的的度数之和即度数之和即didi（didi表示顶点表示顶点I I的度）的度）=_=_。2e2e3.在在图图形形结结构构中中，每每个个结结点点的的前前趋趋结结点点数数和和后后续续结点数可以结点数可以_ _。任意多个任意多个4.若无向图若无向图G G的顶点度数的最小值大于或等于的顶点度数的最小值大于或等于_时，时，G G至少有一条回路。至少有一条回路。2 2 5.设无向图设无向图G G的顶点数为的顶点数为n,n,图图G G最少有最少有_ _ _边，边，最多有最多有_条边，若条边，若G G为有向图，有为有向图，有n n个顶个顶点，则图点，则图G G最少最少_条边条边 ，最多有，最多有_条边。具有条边。具有n n个顶点的无向完全图，边的总数为个顶点的无向完全图，边的总数为_条，而具有条，而具有n n个顶点的有向完全个顶点的有向完全图中，边数有图中，边数有_条。条。0 0n(n-1)/2n(n-1)/20 0n(n-n(n-1)1)n(n-1)/2n(n-1)/2n(n-1)n(n-1)6.在在无无权权图图G G的的链链接接矩矩阵阵A A中中，若若（Vi,VjVi,Vj）或或 Vi,Vj属属于于图图G G的的边边集集合合，则则对对应应元元素素AijAij等于等于_，否则等于，否则等于_。1 10 07.在在 无无 向向 图图 G G的的 链链 接接 矩矩 阵阵 A A中中，若若AijAij等等于于1 1，则则AjiAji等等于于_。1 1 8.已已知知一一个个图图的的链链接接矩矩阵阵表表示示，计计算算第第i i个结点的入度的方法是个结点的入度的方法是_。求矩阵第求矩阵第i i列非零元素之和列非零元素之和9.在在一一个个图图G G的的链链接接表表表表示示中中，每每个个顶顶点点的的链链接接表表中中所所含含的的结结点点数数，对对于于有有向向图图而而言言等等于于该该顶顶点点的的_，而而对对于于无向图而言等于该顶点的无向图而言等于该顶点的_。出度数出度数度数度数10.假假定定一一个个无无向向图图，有有n n个个顶顶点点e e条条边边，则则在在链链接接矩矩阵阵表表示示中中，求求任任一一个个顶顶点点度度数数的的时时间间复复杂杂度度为为_；用用链链接接表表表表示示中中，访访问问一一个个顶顶点点的的所有链接点的时间复杂度为所有链接点的时间复杂度为_。O(nO(n)O(e*nO(e*n)11.已已知知图图G G的的链链接接表表如如图图7-19(7-19(见见下下页页)所所示示，其其从从顶顶点点 V1V1出出发发的的深深度度优优先先搜搜索索序序列列为为_，其其从从顶顶点点 V1出出 发发 的的 广广 度度 优优 先先 搜搜 索索 序序 列列 为为_。v1,v2,v3,v6,v5,v4v1,v2,v3,v6,v5,v4v1,v2,v5,v4,v3,v6v1,v2,v5,v4,v3,v6 图图7-19v1v2v3v4v5v614324012345535212.设设图图G G有有n n个个顶顶点点和和e e条条边边，以以链链接接表表作作存存储储结结构构时时，进进行行深深度度优优先先搜搜索索遍遍历历的的时时间间复复杂杂度度为为_ _；以以链链接接矩矩阵阵作作存存储储结结构构时时，进进行行广广度度优优先先搜搜索索遍遍历历的的时时间间复复杂度为杂度为_。O(n+eO(n+e)O(nO(n2 2)13.对对用用链链接接矩矩阵阵表表示示的的图图进进行行深深度度优优先先或或广广度度优优先先搜搜索索遍遍历历的的时时间间复复杂杂度度为为_，对对用用链链接接表表表表示示的的图图进进行行深深度度优优先先或或广广度度优优先先搜搜索索遍遍历历时时是是时时间间复复杂杂度度为为_，图图的的深深度度优优先先或或广广度优先搜索遍历的空间复杂度为度优先搜索遍历的空间复杂度为_。O(n+eO(n+e)O(nO(n2 2)O(n)O(n)14.n n个个顶顶点点的的弱弱连连通通有有向向图图G G，最最多多有有_条边，最少有条边，最少有_条边。条边。n(n-n(n-1)1)n-1n-115.在在n n个个顶顶点点、e e条条边边的的连连通通图图中中，连连通通分分量量个个数是数是_。1 1 16.任任何何_的的有有向向图图，其其所所有有结结点点都都可可以以排排在在一一个个拓拓扑扑序序列列中中。拓拓扑扑排排序序的的方方法法是是先先从从图图中中选选一一个个_为为0 0的的结结点点且且输输出出，然然后后从从图图中中删删除除此此结结点点及及其其_。反反复复执执行，直至所有结点都输出为止。行，直至所有结点都输出为止。无环无环 前趋前趋 所有以它为尾的弧所有以它为尾的弧 17.一个连通图的一个连通图的_是一个极小连通子图。是一个极小连通子图。生成树生成树 18.在在AOEAOE网网中中，从从源源点点到到汇汇点点各各活活动动时时间间总总和和最最长的路径称为长的路径称为_。关键路径关键路径 19.KruskalKruskal算算法法的的时时间间复复杂杂度度_，它它对对_图较为合适。图较为合适。O(elogO(elog2 2e)e)边稀疏边稀疏 20.对对于于含含有有n n个个顶顶点点e e条条边边的的无无向向连连通通图图，利利用用普普里里姆姆算算法法生生成成最最小小生生成成树树的的时时间间复复杂杂度度为为_，利利用用克克鲁鲁斯斯卡卡算算法法生生成成最最小小生生成成树树的的时时间间复复杂杂度度为为_，在在具具有有n n个个顶顶点点的的图的生成树中，含有图的生成树中，含有_条边。条边。O(nO(n2 2)O(elogO(elog2 2e)e)n-1n-1 21.设设有有向向图图G G有有n n个个顶顶点点e e条条边边，进进行行拓拓扑扑排排序序时时的总的计算时间为的总的计算时间为_。O(n+e)O(n+e)22.已已知知一一个个图图如如图图7-7-20所所示示，则则从从v1到到v2，v5，v6的的最最短短路路径径长长度度分分别别为为_，_和和_，从从v1v1到到图图中中每每个个顶顶点点的的最最短短路路径径长长度度之之和为和为_。151512125 54040图图7-202153463236815106102312