数据结构——图の选择题整理_修改递归方式实现的图的深度优先搜索(dfs)算法,将输出(访问)顶点信息的语句移动到

图的基本概念

1、若从无向图的任意顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（）
A、强连通图
B、连通图
C、有回路
D、一棵树

解析：选B
对于A，强连通图的概念是在有向图中的。
对于B，连通图证明任意两个顶点之间一定能够相连，因此一定可以到达。
对于C，有环图不一定是连通图不一定任意两个顶点均能到达。
对于D，树是可以，但是不是树也可以，题目中说的太肯定了，不能选，比如下图就不是树，但可以完成题目中要求的功能。

2、对于一个有n个顶点的图：若是连通无向图，其边的个数至少为（）；若是强连通有向图，其边的个数至少为（）
A、n - 1, n
B、n - 1, n(n - 1)
C、n, n
D、n, n(n - 1)

解析：选A
对于连通无向图，至少需要n-1条边。对于强连通有向图，只要能形成一个大环就可以从任意一点到另一点。

3、设有无向图G=(V, E)和G’=(V’, E’)，若G‘是G的生成树，则下列不正确的是（）
a.G’为G的连通分量
b.G’为G的无环子图
c.G’为G的极小连通子图且V’ = V
A、a和b
B、只有c
C、b和c
D、只有a

解析：选D
极大连通子图简称连通分量，生成树是极小连通子图。故a不对，c对。
生成树无环，故b对

---

图的存储及基本操作

1、带权有向图G用邻接矩阵存储，则v_i的入度等于邻接矩阵中（）
A、第 i 行非 ∞ 的元素个数
B、第 i 列非 ∞ 的元素个数
C、第 i 行非 ∞ 且非0的元素个数
D、第 i 列非 ∞ 且非0的元素个数

解析：选D
带权有向图的邻接矩阵中，非0和∞的数字表示两点间边的权值。入度计算列，出度计算行，因此v_i的入度等于邻接矩阵中第 i 列非 ∞ 且非0的元素个数。

2、一个有n个顶点的图用邻接矩阵A表示，若图为有向图，顶点v_i的入度是（）；若图为无向图，顶点v_i的度是（）
A、${\sum }_{i=1}^{n}A[i][j]$
B、${\sum }_{j=1}^{n}A[j][i]$
C、${\sum }_{i=1}^{n}A[j][i]$
D、${\sum }_{j=1}^{n}A[j][i]$或${\sum }_{i=1}^{n}A[i][j]$

解析：选B、D
有向图入=对应列的和，因此i不变，j变，故选B
对于无向图，度可以计算行也可以计算列，因此可以是第i行或第i列的数字和。

---

图的遍历

1、下列关于广度优先算法的说法中，正确的是（）
a.当各边的权值相等时，广度优先算法可以解决单源最短路径问题
b.当各边的权值不等时，广度优先算法可以解决单源最短路径问题
c.广度优先遍历算法类似于树中的后序遍历算法
d.实现图的广度优先算法时，使用的数据结构是队列
A、a和d
B、b、c和d
C、b和d
D、a、c和d

解析：选A
广度优先算法是一层一层的寻找顶点，无法根据边的权值决定访问谁，因此只能在各边的权值相等时，解决单源最短路径问题。
广度优先算法类似于树中的层次遍历。
实现图的广度优先算法时，顶点先进先出，因此使用的数据结构是队列。

2、用邻接表存储的图的深度优先遍历算法类似于树中的（），而其广度优先遍历算法类似于树中的（）
A、中序遍历
B、先序遍历
C、后序遍历
D、按层次遍历

解析：选B、D
用邻接表存储的图的深度优先遍历先访问根结点，再递归访问外层结点，因此类似于树中的先序遍历。
广度优先算法是一层一层的寻找顶点，类似于树中的层次遍历

3、设无向图G=(V, E)和G’=(V’, E’)，若G‘是G的生成树，则下列错误的是（）
A、G’为G的子图
B、G’为G的连通分量
C、G’为G的极小连通子图且V’ = V
D、G’为G的一个无环子图

解析：选B
极大连通子图简称连通分量，生成树是极小连通子图，因此B不对。

---

图的应用

1、下面的（）方法可以判断出一个有向图是否有环（回路）
a.深度优先遍历
b.拓扑排序
c.求最短路径
d.求关键路径
A、a、b和d
B、a、c和d
C、a、b和c
D、全都可以

解析：选A
如果有向图有环，则不能求拓扑序列，因为拓扑序列要求从入度为0的点开始，有环和话一定会在某个时候找不到入度为0点顶点。因此可以判断有向图是否有环。
如果对有环有向图进行深度遍历，则会进入循环，一直遍历一个环出不来。因此可以判断有向图是否有环。
求关键路径首先要求拓扑序列，因此也可以判断有向图是否有环。
求最短路径是允许有环的，因此不能判断有向图是否有环。

2、若是一个有向图的顶点不能排在一个拓扑序列中，则可判定该有向图（）
A、是一个有多根的有向图
B、是一个强连通图
C、含有多个入度为0的顶点
D、含有顶点数目大于1的强连通分量

解析：选D
由题干可知该有向图有环
对于A，有多根的有向图，拓扑序列可以是：A B C D E F G

对于B，强连通图中可以只包含一个顶点，如果只包含一个顶点，就可以放在一个拓扑序列里。如下图，拓扑序列为： A

对于C，有多个入度为0的顶点，拓扑序列可以是：A B D C E F G

对于D，顶点数目大于1的强连通分量，因此至少为两个顶点，故一定会有环，因此无法放在一个拓扑序列里。

3、下图所示有向图的拓扑序列共有（）个

A、4
B、6
C、5
D、7

解析：选C
A B C D E F G
A B C D F E G
A B D C E F G
A B D C F E G
A B C F D E G

4、下列关于图的说法中，正确的是（）
a.有向图的顶点V的度等于其邻接矩阵中第V行中1的个数
b.无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵
c.在图G的最小生成树G₁中，某条边的权值可能会超过未选边的权值
d.若有向无环图的拓扑序列唯一，则可以唯一确定该图
A、a、b和c
B、c和d
C、c
D、d

解析：选C
对于a，有向图的邻接矩阵中，非0和非∞表示的是两顶点之间边的权重。有向图的顶点V的度包括入度和出度，出度等于第V行中非0和非∞的个数，入度等于第V列中非0和非∞的个数。
对于b，无向图的邻接矩阵一定是对称矩阵，但有向图的邻接矩阵不一定是对称矩阵，当任意两个顶点之间都有指向对方的边，则邻接矩阵是对称矩阵，否则则不是。
对于c，若采用Kruskal算法，选择的是未相连的顶点之间权重最小的边，选择该边以后，不会形成环。如下图，BF间权值为1的边并未被选择，而CF间权值为6的边却被选择了。

对于d，有向无环图的拓扑序列唯一，也不能唯一确定该图。对于下面这两个图，拓扑序列都是唯一的：A B C D，但是并不能确定是哪种图。

5、若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是（）
A、存在，且唯一
B、存在，且不唯一
C、存在，可能不唯一
D、无法确定是否存在

解析：选C
邻接矩阵若是下图的样子，则图的样式为下图右图，拓扑序列有：V1 V2 V3 V4、V1 V3 V2 V4、V1 V3 V4 V2。由此可知，拓扑序列存在，但不唯一。

6、下图所示的AOE网表示一项包含8个活动的工程。活动d的最早开始时间和最迟开始时间分别是（）

A、3和7
B、12和12
C、12和14
D、15和15

解析：选C

7、修改递归方式实现的图的深度优先搜索（DFS）算法，将输出（访问）顶点信息的语句转移到退出递归前（即执行输出语句后立即退出递归）。采用修改后的算法遍历有向无环图G，若输出结果中包含G中的全部顶点，则输出的顶点序列是G的（）
A、拓扑有序序列
B、逆拓扑有序序列
C、广度优先搜索序列
D、深度优先搜索序列

解析：选B
DFS是一种递归算法，在访问v_i时，若其有子结点，则会将v_i入栈，等访问完其子结点后才出栈，因为执行输出语句后立即退出递归，所以是先输出子结点在输出v_i，因此是逆拓扑序列。