数据结构-图（选择题）

数据结构——图（选择题）

1.在一个有向图中，所有顶点的入度和等于所有结点的出度之和的（）倍。

简单，图的基本概念，02707001［单选题］*

A、1/2

B、1（正确答案）

C、2

D、4

2.对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大

小为0o

简单，图的邻接表存储，（）27（）7003［单选题］*

A、n

B、n+1

C、n-1

D、n+e

3.具有n个顶点的无向完全图，边的总数为（）条。

简单，图的基本概念，02707001［单选题］*

A、n-1

B、n

C、n+1

D、n*（n-l）/2（正确答案）

4.设图G有n个顶点和e条边，当G是非孤立顶点的连通图时，有2史n,故可推

得深度优先搜索的时间复杂度为()O

简单，图的遍历，02707006［单选题］*

A、O(e)(正确答案)

B、O(n)

C、O(ne)

D、O(n+e)

5.最小代价生成树()。

简单，最小生成树，02707007［单选题］*

A、是唯一的

B、不是唯一的

C、唯一性不确定

D、唯一性与原树的边的权数有关

6.在无向图G的邻接矩阵A中，若等于1,则等于()o

简单，图的邻接矩阵存储，()2707()02［单选题］*

A、i+j

B、i-j

C、1

D、0

7.图的深度优先或广度优先遍历的空间复杂性均为()。(访问标志位数组空间)

简单，图的遍历，()2707006［单选题］*

A、O(n)：确答案।

B、0(e)

C、O(n-e)

D、O（n+e）

8.在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s,则所有顶点的

入度数之和为（）O

简单,图的基本概念,02707001［单选题］*

A、s；

B、s-1

C、s+1

D、N'

9.在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s,则所有顶点的

度数之和为（）。

简单，图的基本概念，02707001［单选题］*

A、s

B、s-1

C、s+1

D、2s（正确答案）

10.在一个具有n个顶点的无向图中，若具有e条边，则所有顶点的度数之和为

（）。

简单，图的基本概念，（）2707001［单选题］*

A、n

B、e

C、n+e

D、2e（正确答案）

11.在一个具有n个顶点的无向完全图中，所含的边数为（）。

简单，图的基本概念，02707001［单选题］*

A、n

B、n（n-l）

C、n（n-l）/2

D、n（n+l）/2

12.在一个无向图中，若两顶点之间的路径长度为k,则该路径上的顶点数为（）。

简单，图的遍历，02707006］单选题］*

A、k

B、k+1（正确答案）

C、k+2

D、2k

13.对于一个具有n个顶点的无向连通图，它包含的连通分量的个数为（）。

无向图G的极大连通子图称为G的连通分量（ConnectedComponent）o任何连通图

的连通分量只有一个，即是其自身，非连通的无向图有多个连通分量。

简单，图的基本概念，02707001［单选题］*

A、0

B、1（正确答案）

C、n

D、n+1

14.若一个图中包含有k个连通分量，若要按照深度优先搜索的方法访问所有顶

点，则必须调用（）次深度优先搜索遍历的算法。

简单，图的遍历，（）2707006［单选题］*

A、k（正确答案）

B、1

C、k-1

D、k+1

15.若要把n个顶点连接为一个连通图，则至少需要()条边。

简单，图的基本概念，02707001［单选题］*

A、n

B、n+1

C、n-l(正确答案)

D、2n

16.在一个具有n个顶点和e条边的无向图的邻接矩阵中，表示边存在的元素(又称

为有效元素)的个数为()O

简单，图的邻接矩阵存储，027()7002［单选题］*

A、n

B、nxe

C、e

D、2xe

17.在一个具有n个顶点和e条边的有向图的邻接矩阵中，表示边存在的元素个数

为0o

简单，图的邻接矩阵存储，()2707()02［单选题］*

A、n

B、nxe

C、e

D、2xe

18.在一个具有n个顶点和e条边的有向图的邻接表中，保存顶点单链表的表头指

针向量的大小至少为()O

简单，图的邻接表存储，02707003［单选题］*

A、n

B、2n

C、e

D、2e

19.在一个无权图的邻接表示中，每个边结点至少包含（）域。

简单，图的邻接表存储，02707003［单选题］*

A、1

B、2（正确答案）

C、3

D、4

20.对于一个有向图，若一个顶点的度为kl,出度为k2,则对应邻接表中该顶点单

链表中的边结点数为（）。

简单，图的基本概念，02707001［单选题］*

A、kl

B、k2

C、kl-k2

D、kl+k2

21.对于一个有向图，若一个顶点的度为kl,出度为k2,则对应逆邻接表中该顶点

单链表中的边结点数为（）O

简单，图的邻接表存储，（）2707003［单选题］*

A、kl

B、k2

C、kl-k2

D、kl+k2

22.对于一个无向图，下面()种说法是正确的。

简单，图的基本概念，02707001［单选题］*

A、每个顶点的入度等于出度

B、每个顶点的度等于其入度与出度之和

C、每个顶点的入度为。

D、每个顶点的出度为0

23.在一个有向图的邻接表中，每个顶点单链表中结点的个数等于该顶点的()o

简单，图的邻接表存储，()27()7003［单选题］*

A、出度数(正确答案)

B、入度数

C、度数

D、度数减1

24.若一个图的边集为{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)},则从顶点A开始对该

图进行深度优先搜索，得到的顶点序列可能为()O

简单，图的遍历，02707006［单选题］*

A、A,B,C,F,D,E

B、A,C,F,D,E,B(正确答案)

C、A,B,D,C,F,E

D、A,B,D,F,E,C

25.若一个图的边集为{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)},则从顶点A开始对该

图进行广度优先遍历，得到的顶点序列可能为0O

简单，图的遍历，02707006［单选题］*

A、A,B,C,D,E,F

B、A,B,C,F,D,E

C、A,B,D,C,E,F

D、A,C,B,F,D,ED答案）

26.若一个图的边集为{<1,2>,<1,4>,<2,5>,<3/>,<3,5>,<4,3>},则从顶点1开始对该

图进行深度优先遍历，得到的顶点序列可能是（）O

有向图

简单，图的遍历，02707006］单选题］*

A、125,4,3确答案）

B、1,2,3,4,5

C、1,2,5,3,4

D、1,4,325

27.若一个图的边集为{<1,2>,<1,4>,<2,5>,<3,1>,<3,5>,<4,3>},则从顶点1开始对该

图进行广度优先搜索，得到的顶点序列可能为（）O

有向图

简单，图的遍历，02707006［单选题］*

A、1,2,3,4,5

B、1,2,4,3,5

C、1,2,4,5,3（正确答案）

D、1,4,2,5,3

28.由一个具有n个顶点的连通图生成的最小生成树中，具有（）条边。

简单，最小生成树，02707（）07［单选题］*

A、n

B、n-1沟答案）

C、n+1

D、2xn

29.已知一个有向图的边集为{<a,b>,<a,c>,<a,d>,<b,d>,<b,e>,<d,e>},则由该图产生

的一种可能的拓扑序列为（）O

一般，拓扑排序和关键路径，02707009［单选题］*

A、a,b,c,d,e

B