数据结构练习 第七章 图

《数据结构练习 第七章 图》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构练习第七章图一、选择题1.设有6个结点的无向图，该图至少应有()条边才能确保是一个连通图。A.5B.6C.7D.82.设某完全无向图中有n个顶点，则该完全无向图中有（）条边。A.n(n-1)/2B.n(n-1)C.n2D.n2-13．设某有向图中有n个顶点，则该有向图对应的邻接表中有（）个表头结点。A.n-1B.nC.n+1D.2n-14．设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为（）。A.n，eBe，nC2n，eDn，2e5．设某强连通图中有n个顶点，则该强连通图中至少有（）条边。A.n(n-1)B.n+1C.nD.n(n+1)6．设某无向图

2、中有n个顶点e条边，则该无向图中所有顶点的入度之和为（）。A.nB.eC.2nD.2e7．设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（）条有向边。A.nB.n-1C.mD.m-18．设连通图G中的边集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发可以得到一种深度优先遍历的顶点序列为（）。A.abedfcB.acfebdC.aebdfcD.aedfcb9．设某无向图中有n个顶点e条边，则建立该图邻接表的时间复杂度为（）。A.O(n+e)B.O(n2)C.O(ne)D.O(n3)10．设用邻接矩阵A表示有向图G的存储

3、结构，则有向图G中顶点i的入度为（）。A.第i行非0元素的个数之和B.第i列非0元素的个数之和C.第i行0元素的个数之和D.第i列0元素的个数之和11．设某无向图有n个顶点，则该无向图的邻接表中有（）个表头结点。A.2nB.nC.n/2D.n(n-1)12．设无向图G中有n个顶点，则该无向图的最小生成树上有（）条边。A.nB.n-1C.2nD.2n-113．设无向图的顶点个数为n，则该图最多有（）条边。A．n-1B．n(n-1)/2C．n(n+1)/2C．014．设有向无环图G中的有向边集合E={<1，2>，<2，3>，<3，4>，<1，4>}，则下列属于该有向图G的一种拓扑排序序列的是

4、（）。A.1，2，3，4B.2，3，4，1C.1，4，2，3D.1，2，4，315．在一个具有n个顶点的无向图中，要连通所有顶点则至少需要（）条边。55A．nB．2nC．n-1D．n+116．在一个图中，所有顶点的度数之和等于所有边数的（）倍。A．2B．1C．3D．417．在用邻接表表示图时,对图进行深度优先搜索遍历的算法的时间复杂度为______。A.Ｏ(n)B.Ｏ(n+e)C.Ｏ(n2)　D.Ｏ(n3)(b)在用邻接表存储图时，故整个算法的时间复杂度为O(n+e)。如果用邻接矩阵表示图，则算法的时间复杂度就是O(n2)。18．一个具有n个顶点的无向连通图，它所包含的连通分量数为（　　

5、　）A.0B.1C.nD.不确定19．下列说法中不正确的是（　　　）A.无向图的极大连通子图称为连通分量B.连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点C.连通图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点D.有向图的遍历不可采用广度优先搜索算法20．邻接矩阵为对称矩阵的图是()A.有向图B.带权有向图C.有向图或无向图D.无向图21．在一个具有n个顶点的无向图中，要连通全部顶点至少需要的边数为()A.n-1B.nC.n+1D.22．有4个顶点的无向完全图的边数为()A.6B.12C.16D.2023．设图的邻接矩阵为，则该图为()A.有向图B.无向图C.强连通图D.完全

6、图24．在一个具有n个顶点的无向图中，每个顶点度的最大值为（）A．nB.n-1C.n+1D.2(n-1)25．关于无向图的邻接矩阵的说法中正确的是（）A．矩阵中非全零元素的行数等于图中的顶点数B.第i行上与第i列上非零元素总和等于顶点Vi的度数C.矩阵中的非零元素个数等于图的边数D.第i行上非零元素个数和第i列上非零元素个数一定相等26．有n个结点的有向完全图的弧数是（　　）A.n2B.2nC.n(n-1)D.2n(n+1)27．设图的邻接链表如题12图所示，则该图的边的数目是（　）题12图55A.4B.5C.10D.2028．若采用邻接表存储结构，则图的深度优先搜索类似于二叉树的（　　

7、）A.先根遍历B.中根遍历C.后根遍历D.层次遍历29．具有n个顶点的无向图，若要连通全部顶点，至少需要（　　）A.（n-1）条边B.n条边C.n(n-1)条边D.n(n-1)/2条边30．一个带权的无向连通图的最小生成树（　　　）A．有一棵或多棵B．只有一棵C．一定有多棵D．可能不存在31．下列有关图遍历的说法中不正确的是（　　）A．连通图的深度优先搜索是一个递归过程B．图的广度优先搜索中邻接点的寻找具有“先进先出”的特征C．非连