精品
第7章 图
一、单项选择题
1．在一个无向图G中，所有顶点的度数之和等于所有边数之和的______倍。 A．l/2 C．2
B．1 D．4
2．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的______倍。 A．l/2 C．2
B．1 D．4
3．一个具有n个顶点的无向图最多包含______条边。 A．n C．n-1
B．n＋1 D．n(n-1)/2
4．一个具有n个顶点的无向完全图包含______条边。 A．n(n-l) C．n(n-l)/2
B．n(n+l) D．n(n-l)/2
5．一个具有n个顶点的有向完全图包含______条边。 A．n(n-1) C．n(n-l)/2
B．n(n+l) D．n(n+l)/2
6．对于具有n个顶点的图，若采用邻接矩阵表示，则该矩阵的大小为______。A．n C．n-1
7．无向图的邻接矩阵是一个______。 A．对称矩阵 C．上三角矩阵
B．零矩阵 D．对角矩阵 B．n×n D．(n-l) ×(n-l)
8．对于一个具有n个顶点和e条边的无(有)向图，若采用邻接表表示，则表头向量的大小为______。
A．n C．2n
B．e D．2e
9．对于一个具有n个顶点和e条边的无(有)向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为______。
精品
A．n C．2n
B．e D．2e
10．在有向图的邻接表中，每个顶点邻接表链接着该顶点所有______邻接点。A．入边
C．入边和出边
B．出边
D．不是入边也不是出边
11．在有向图的逆邻接表中，每个顶点邻接表链接着该顶点所有______邻接点。 A．入边
C．入边和出边
B．出边
D．不是人边也不是出边
12．如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是______。
A．完全图 C．有回路
B．连通图 D．一棵树
13．采用邻接表存储的图的深度优先遍历算法类似于二叉树的______算法。 A．先序遍历
B．中序遍历
C．后序遍历 D．按层遍历
14．采用邻接表存储的图的广度优先遍历算法类似于二叉树的______算法。 A．先序遍历 B．中序遍历 C．后序遍历 D．按层遍历
15．如果无向图G必须进行二次广度优先搜索才能访问其所有顶点，则下列说
法中不正确的是______。 A．G肯定不是完全图
B．G一定不是连通图
C．G中一定有回路 D．G有二个连通分量 16．下列有关图遍历的说法不正确的是______。 A．连通图的深度优先搜索是一个递归过程
B．图的广度优先搜索中邻接点的寻找具有“先进先出”的特征 C．非连通图不能用深度优先搜索法 D．图的遍历要求每一顶点仅被访问一次 17．下列说法中不正确的是______。
A．无向图中的极大连通子图称为连通分量
精品
B．连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点 C．图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点 D．有向图的遍历不可采用广度优先搜索方法
18．一个有向图G的邻接表存储如下图7-1所示，现按深度优先搜索遍历，从顶点v1出发，所得到的顶点序列是______。
A．v1，v2，v3，v4，v5 B．v1，v2，v3，v5，v4 C．v1，v2，v4，v5，v3 D．v1，v2，v5，v3，v4
v1 v2 v3 v4 ∧ v5 2 3 5 ∧ 3 5 ∧ 4 ∧ 4 ∧ 图7-1 一个有向图的邻接表
19．对图7-2所示的无向图，从顶点1开始进行深度优先遍历，可得到顶点访问
序列______。
A．1，2，4，3，5，7，6 B．1，2，4，3，5，6，7 C．1，2，4，5，6，3，7 D．1，2，3，4，5，7，6
1 3 2 4 6 5 7 图7-2 一个无向图
20．对图7-2所示的无向图，从顶点1开始进行广度优先遍历，可得到顶点访问
序列______。
A．1，3，2，4，5，6，7
B．1，2，4，3，5，6，7
C．1，2，3，4，5，7，6 D．2，5，1，4，7，3，6 21．一个无向连通图的生成树是含有该连通图的全部顶点的______。