资源描述：
《数据结构练习第七章图.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、个人收集整理勿做商业用途数据结构练习第七章图一、选择题１.设有６个结点的无向图,该图至少应有()条边才能确保是一个连通图。A．5 B.6 C．7 D.82. 设某完全无向图中有n个顶点，则该完全无向图中有( ）条边。Ａ.ｎ（ｎ-1）/2 B． ｎ(n-1)ﻩ Ｃ．n2 D.ｎ2-１3．设某有向图中有n个顶点，则该有向图对应的邻接表中有（ )个表头结点。A．n-１B.n C．n+１ﻩ D. 2n-１4.设无向图Ｇ中有ｎ个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为( ）。A．n，e Be,n C２n
2、,e D ｎ，2e5．设某强连通图中有n个顶点，则该强连通图中至少有(）条边。Ａ.n(n－1)ﻩ Ｂ．n＋１ ﻩC.n D． n(ｎ+1)6.设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为（)。Ａ.n B. e ﻩC. 2nﻩ D. 2ｅ7.设某有向图的邻接表中有n个表头结点和m个表结点,则该图中有(）条有向边。A. n B. ｎ-1ﻩ Ｃ． m D．ｍ-１8.设连通图G中的边集E={（a,b)，（ａ，e)，（a,c),（b，e)，(ｅ，d），（d,f)，(f,ｃ)}，则从顶点a出发可以
3、得到一种深度优先遍历的顶点序列为( ）。A. ａｂeｄfcﻩ Ｂ.acfebdC. aebdfcﻩ Ｄ.aedfcb９．设某无向图中有n个顶点e条边，则建立该图邻接表的时间复杂度为（ ）。A.O(n+e) B.O(n2) C.O(nｅ) ﻩD． Ｏ（n3)1０.设用邻接矩阵A表示有向图Ｇ的存储结构，则有向图G中顶点ｉ的入度为（ ）。A.第ｉ行非０元素的个数之和ﻩB.第i列非0元素的个数之和C.第ｉ行0元素的个数之和 Ｄ. 第i列0元素的个数之和1１．设某无向图有n个顶点,则该无向图的邻接表中有()个表头结点。Ａ.2nﻩ B.n
4、 C.n／２ Ｄ.n（ｎ-1）1２.设无向图G中有n个顶点,则该无向图的最小生成树上有（)条边。Ａ.ｎ B. ｎ-1 C．２nﻩ 个人收集整理勿做商业用途D.2n-11３．设无向图的顶点个数为n,则该图最多有()条边。A.n－１ B．n(n-1)/2C．n(ｎ＋1）／2 C.０14．设有向无环图G中的有向边集合E={<1,2>,<２,3>，<３,４>,<1，４>}，则下列属于该有向图G的一种拓扑排序序列的是（ )。A. 1,2，3,４ﻩ B. 2,3,4，1ﻩ C.1，4，2，3D.1，2,４，315.在一个具有
5、n个顶点的无向图中,要连通所有顶点则至少需要()条边。A.n B.2n C．n-1 D．n＋１16.在一个图中，所有顶点的度数之和等于所有边数的( ）倍。A.2 B．1 C．3 D.4１7.在用邻接表表示图时，对图进行深度优先搜索遍历的算法的时间复杂度为_＿__＿＿。A.O(n） B.O（n+e）C.Ｏ(n２) D．O(n3）(ｂ)在用邻接表存储图时,故整个算法的时间复杂度为O(ｎ+ｅ）。如果用邻接矩阵表示图,则算法的时间复杂度就是O(ｎ2)。１8.一个具有ｎ个顶点的无向连通图,它所包含的连通分量数为( ）A．0
6、ﻩﻩＢ.1ﻩ C.nﻩ D.不确定19.下列说法中不正确的是( ）A.无向图的极大连通子图称为连通分量B.连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点Ｃ.连通图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点D．有向图的遍历不可采用广度优先搜索算法２０.邻接矩阵为对称矩阵的图是( )A.有向图 B．带权有向图C.有向图或无向图ﻩ D. 无向图21．在一个具有n个顶点的无向图中,要连通全部顶点至少需要的边数为( )A.n-1 B．ｎﻩC.ｎ+１ﻩ D.22．有4个顶点的无向完全图的边数为( )A.6 Ｂ.12 C.16
7、 ﻩ D.2023．设图的邻接矩阵为，则该图为（ )Ａ.有向图 B.无向图 C.强连通图ﻩ D.完全图24.在一个具有n个顶点的无向图中,每个顶点度的最大值为（ ）A.n Ｂ.n－1 C.n+１ D.2(n-1）25．关于无向图的邻接矩阵的说法中正确的是（ )A.矩阵中非全零元素的行数等于图中的顶点数B.第i行上与第i列上非零元素总和等于顶点Vｉ的度数个人收集整理勿做商业用途Ｃ.矩阵中的非零元素个数等于图的边数D.第ｉ行上非零元素个数和第i列上非零元素个数一定相等26．有n个结点的有向完全图的弧数是()A．n2B
8、.2ｎ C.n（n-1)ﻩ D.2n(n＋１)27．设图的邻接链表如题12图所示,则该图的边的数目是（ ）
