资源描述：
《根据有向图广度优先搜索遍历算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、图练习一、选择题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个顶点的图，
2、采用链接矩阵表示则该矩阵的大小为（）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
3、.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出发按深度优先搜索法进行遍历，则可能得到的是一种顶点序列为（）；按广度优先搜索法进行遍历，则
4、可能得到的一种顶点序列为（）。(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.中序
5、遍历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,v2CBv1v2^v3v4^v5213^34^13^01234
6、图7-1420.已知有8个顶点值为A，B，C，D，E，F，G，H的无向图，其邻接矩阵的存储结构如图7-15所示（见下页）。由此结构，从A顶点开始深度优先搜索遍历，得到的顶点序列是（）。A.ABCDGHFEB.ABCDGFHEC.ABGHFECDD.ABFHEGDCE.ABEHFGDCF.ABEHGFCDBABCDEFGHA01010000B10101110C01010000D10100010E01000001F01000011G01010101H00001110图7-1521.已知一个图如图7-16（见下页）所示，在该图的最小生成树中各条边上权值之和为（），在该图的最小生
7、成树中，从顶点V1到顶点V6的路径为（）A.31B.38C.36D.43E.v1,v3.v6F.v1,v4,v6G.v1,v5,v4,v6H.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个顶点的无向
