(数据结构练习第七章图.docVIP

数据结构练习 第七章 图 一、选择题 1.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。 A.5 B.6 C.7 D.8 2. 设某完全无向图中有n个顶点，则该完全无向图中有（ ）条边。 A. n(n-1)/2 B. n(n-1) C. n2 D. n2-1 3．设某有向图中有n个顶点，则该有向图对应的邻接表中有（ ）个表头结点。 A. n-1 B. n C. n+1 D. 2n-1 4．设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为（ ）。 A. n，e B e，n C 2n，e D n，2e 5．设某强连通图中有n个顶点，则该强连通图中至少有（ ）条边。 A. n(n-1) B. n+1 C. n D. n(n+1) 6．设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为（ ）。 A .n B. e C. 2n D. 2e 7．设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（ ）条有向边。 A. n B. n-1 C. m D. m-1 8．设连通图G中的边集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发可以得到一种深度优先遍历的顶点序列为（ ）。 A. abedfc B. acfebd C. aebdfc D. aedfcb 9．设某无向图中有n个顶点e条边，则建立该图邻接表的时间复杂度为（ ）。 A. O(n+e) B. O(n2) C. O(ne) D. O(n3) 10．设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为（ ）。 A. 第i行非0元素的个数之和 B. 第i列非0元素的个数之和 C. 第i行0元素的个数之和 D. 第i列0元素的个数之和 11．设某无向图有n个顶点，则该无向图的邻接表中有（ ）个表头结点。 A. 2n B. n C. n/2 D. n(n-1) 12．设无向图G中有n个顶点，则该无向图的最小生成树上有（ ）条边。 A. n B. n-1 C. 2n D. 2n-1 13．设无向图的顶点个数为n，则该图最多有（）条边。 A．n-1 B．n(n-1)/2 C．n(n+1)/2 C．0 14．设有向无环图G中的有向边集合E={1，2，2，3，3，4，1，4}，则下列属于该有向图G的一种拓扑排序序列的是（ ）。 A. 1，2，3，4 B. 2，3，4，1 C. 1，4，2，3 D. 1，2，4，3 15．在一个具有n个顶点的无向图中，要连通所有顶点则至少需要（ ）条边。 A．n B．2n C．n-1 D．n+1 16．在一个图中，所有顶点的度数之和等于所有边数的（ ）倍。 A．2 B．1 C．3 D．4 17．在用邻接表表示图时, 对图进行深度优先有哪些信誉好的足球投注网站遍历的算法的时间复杂度为______。 A. Ｏ(n) B. Ｏ(n+e) C. Ｏ(n2)　 D. Ｏ(n3) (b) 在用邻接表存储图时，故整个算法的时间复杂度为O(n+e)。如果用邻接矩阵表示图，则算法的时间复杂度就是O(n2)。 18．一个具有n个顶点的无向连通图，它所包含的连通分量数为（　　　） A.0 B.1 C.n D.不确定 19．下列说法中不正确的是（　　　） A.无向图的极大连通子图称为连通分量 B.连通图的广度优先有哪些信誉好的足球投注网站中一般要采用队列来暂存刚访问过的顶点 C.连通图的深度优先