数据结构——图(选择题).pdfVIP

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

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

简单，图的基本概念[单选题]*

A、1/2

B、1(正确答案)

C、2

D、4

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

小为（）。

简单，图的邻接表存储[单选题]*

A、n(正确答案)

B、n+1

C、n-1

D、n+e

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

简单，图的基本概念[单选题]*

A、n-1

B、n

C、n+1

D、n*(n-1)/2(正确答案)

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

得深度优先搜索的时间复杂度为（）。

简单，图的遍历[单选题]*

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

B、O(n)

C、O(ne)

D、O(n+e)

5.最小代价生成树（）。

简单，最小生成树[单选题]*

A、是唯一的

B、不是唯一的

C、唯一性不确定

D、唯一性与原树的边的权数有关(正确答案)

6.在无向图G的邻接矩阵A中，若A[i,j]等于1，则A[j,i]等于（）。

简单，图的邻接矩阵存储[单选题]*

A、i+j

B、i-j

C、1(正确答案)

D、0

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

简单，图的遍历[单选题]*

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

B、O(e)

C、O(n-e)

D、O(n+e)

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

入度数之和为（）。

简单，图的基本概念[单选题]*

A、s(正确答案)

B、s-1

C、s+1

D、N‘

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

度数之和为（）。

简单，图的基本概念[单选题]*

A、s

B、s-1

C、s+1

D、2s(正确答案)

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

（）。

简单，图的基本概念[单选题]*

A、n

B、e

C、n+e

D、2e(正确答案)

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

简单，图的基本概念[单选题]*

A、n

B、n(n-1)

C、n(n-1)/2(正确答案)

D、n(n+1)/2

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

简单，图的遍历[单选题]*

A、k

B、k+1(正确答案)

C、k+2

D、2k

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

无向图G的极大连通子图称为G的连通分量(ConnectedComponent)。任何连通图

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

简单，图的基本概念[单选题]*

A、0

B、1(正确答案)

C、n

D、n+1

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

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

简单，图的遍历[单选题]*

A、k(正确答案)

B、1

C、k-1

D、k+1

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

简单，图的基本概念[单选题]*

A、n

B、n+1

C、n-1(正确答案)

D、2n

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

为有效元素)的个数为（）。

简单，图的邻接矩阵存储[单选题]*

A、n

B、n×e

C、e

D、2×e(正确答案)

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

为（）。

简单，图的邻接矩阵存储[单选题]*

A、n

B、n×e

C、e(正确答案)

D、2×e

18