图练习题

1.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。

a.5 b.6 c.7 d.8

2. 设某完全无向图中有n个顶点，则该完全无向图中有（ ）条边。

a. n(n-1)/2 b. n(n-1) c. n d. n-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 1

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.连通图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点 d.有向图的遍历不可采用广度优先搜索算法 20．邻接矩阵为对称矩阵的图是( )

a. 有向图 b. 带权有向图 c. 有向图或无向图 d. 无向图<存储结构，则图的深度优先搜索类似于二叉树的（ ） a.先根遍历 b.中根遍历 c.后根遍历 d.层次遍历 2

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．非连通图不能用深度优先搜索法 d．图的遍历要求每一顶点仅被访问一次

32．设有向图有n个顶点和e条边，采用领接表作为其存储表示，在进行拓扑排序时，总的计算时间为（ ）。 a．o（nlog2e） b．o（n+e） c．o(ne) d．o(n2)

33．在一个无向图中，所有顶点的度数之和等于所有边数的（ ）倍。 a．3 b．2 c．1 d．1/2

34．图中有关路径的定义是（ a ）。

a．由顶点和相邻顶点序偶构成的边所形成的序列 b．由不同顶点所形成的序列 c．由不同边所形成的序列 d．上述定义都不是

35．要连通具有n个顶点的有向图，至少需要（b）条边。 a．n-l b．n c．n+l d．2n

36．一个有n个结点的图，最少有（b ）个连通分量，最多有（ d ）个连通分量。 a．0 b．1 c．n-1 d．n

37．在一个无向图中，所有顶点的度数之和等于所有边数（b ）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（c ）倍。

a．1/2 b．2 c．1 d．4 38．用邻接表存储图所用的空间大小（a）。

a.与图的顶点数和边数都有关 b.只与图的边数有关c.只与图的顶点数有关 d.与边数的平方有关 39．图的bfs生成树的树高比dfs生成树的树高（ a ） a.小或相等 b.小 c.大或相等 d.大 40．下列说法不正确的是（c ）。

a．图的遍历是从给定的源点出发每个顶点仅被访问一次b．遍历的基本方法有两种：深度遍历和广度遍历 c．图的深度遍历不适用于有向图d．图的深度遍历是一个递归过程 41．无向图g=(v,e),其中：v={a,b,c,d,e,f},e={(a,b),(a,e),(a,c), (b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（ d ）。

a．a,b,e,c,d,f b．a,c,f,e,b,d c．a,e,b,c,f,d d．a,e,d,f,c,b

42．在图采用邻接表存储时，求最小生成树的 prim 算法的时间复杂度为( )。 a. o(n) b. o(n+e) c. o(n2) d. o(n3)

43．在有向图的邻接表存储结构中，顶点v在链表中出现的次数是( )。 a.顶点v的度 b. 顶点v的出度 c. 顶点v的入度 d. 依附于顶点v的边数