下列关于无向连通图特性的叙述中，正确的是

Ⅰ.所有顶点的度之和为偶数

Ⅱ.边数大于顶点个数

Ⅲ.至少有一个顶点的度为1

如下图所示为一个无向连通图：任何两个节点之前都是连通的，都存在一条路径，并且图中没有方向。

（1）顶点的度为顶点所连接的边的个数，无向连通图中的顶点的度之和 为边数*2所以顶点的度之和为偶数

（2）很显然边数可以等于顶点个数 比如上图为一个五边形；

（3）如果为一条边两个节点的话 ，存在了两个顶点的度都为1

答案为：I

用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关。

        T          F

答案是：F

临接矩阵存储空间为n平方 所以只和顶点个数有关 临接表是n加e

2.P 是顶点 S 到 T 的最短路径，如果该图中的所有路径的权值都加 1，P 仍然是 S 到 T 的最短路径。

假如说最短路径上一共有10条边，而另一条路径虽然比最短路径长，但它只有一条边，如果全加1，就会导致边少的路径成为新的最短路径。

3.对于带权无向图 G = (V, E)，M 是 G 的最小生成树，则 M 中任意两点 V1 到 V2 的路径一定是它们之间的最短路径。

最小生成树只能说明整个路径是最小，并不能说明到单个结点的路径是最小的。、

1、如果无向图G必须进行两次广度优先搜索才能访问其所有顶点，则G一定有2个连通分量。 (T)

解析：
进行一次广度优先搜索，则与之连通的结点都会遍历到。

2、在任一有向图中，所有顶点的入度之和等于所有顶点的出度之和。 (T)

解析：

一个结点的出度是相连结点的入度；

3、用邻接矩阵法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关。 (T)

4、若图G有环，则G不存在拓扑排序序列。 (T)

解析；

拓扑排序的前提是有向无环图；

5、Kruskal 算法是维护一个森林，每一步把两棵树合并成一棵。 (T)

6、Kruskal 算法是通过每步添加一条边及其相连的顶点到一棵树，从而逐步生成最小生成树。 (F)

解析：

• prim算法是通过每步添加一条边及其相连的顶点到一棵树，从而逐步生成最小生成树；

• Kruskal 算法是维护一个森林，每一步把两棵树合并成一棵；

7、Prim 算法是通过每步添加一条边及其相连的顶点到一棵树，从而逐步生成最小生成树。 (T)

8、无向连通图所有顶点的度之和为偶数。 (T)

解析：

无向图定义：

• 任何两个节点之前都是连通的，都存在一条路径，并且图中没有方向。

所以，有结论：

• 顶点的度为顶点所连接的边的个数，无向连通图中的顶点的度之和为边数*2所以顶点的度之和为偶数

详解：无向连通图

9、对于带权无向图 G = (V, E)，M 是 G 的最小生成树，则 M 中任意两点 V1 到 V2 的路径一定是它们之间的最短路径。 (F)

解析：

最小生成树的总权最小，不是其中的任意路径最小；

10、如果从有向图 G 的每一点均能通过深度优先搜索遍历到所有其它顶点，那么该图一定不存在拓扑序列。(T)

解析：
如果从有向图 G 的每一点均能通过深度优先搜索遍历到所有其它顶点，则该图是一个有环图；而拓扑排序的前提是有向无环图；

详解：拓扑排序

11、在一个有向图中，所有顶点的入度与出度之和等于所有边之和的2倍。 (T)

12、无向连通图边数一定大于顶点个数减1。 (F)

解析：

以两个结点的图为例，此图为连通图，边数为1，顶点数为2；边数一定没有大于顶点个数减1；

二、单选题

1、给定一个有向图的邻接表如下图，则该图有__个强连通分量。(B)

1. 4 {{0, 1, 5}, {2}, {3}, {4}}
2. 3 {{2}, {4}, {0, 1, 3, 5}}
3. 1 {0, 1, 2, 3, 4, 5}
4. 1 {0, 5, 1, 3}

解析：

 

构成强连通分量，前提是个环或一个结点；构成最大环的是1-3-0-5，其他都单个结点；

2-2

2、图的广度优先遍历类似于二叉树的：(D)

1. 先序遍历
2. 中序遍历
3. 后序遍历
4. 层次遍历

解析：

3、任何一个带权无向连通图的最小生成树—— ©

1. 是唯一的
2. 是不唯一的
3. 有可能不唯一
4. 有可能不存在

4、给定一有向图的邻接表如下。从顶点V1出发按深度优先搜索法进行遍历，则得到的一种顶点序列为： (B)

1. V1,V2,V3,V5,V4
2. V1,V3,V4,V5,V2
3. V1,V4,V3,V5,V2
4. V1,V2,V4,V5,V3

解析：

5、给定一有向图的邻接表如下。从顶点V1出发按广度优先搜索法进行遍历，则得到的一种顶点序列为： ©

1. V1,V2,V3,V4,V5
2. V1,V2,V3,V5,V4
3. V1,V3,V2,V4,V5
4. V1,V4,V3,V5,V2

解析：
如上图；

6、对于有向图，其邻接矩阵表示比邻接表表示更易于： (A)

1. 求一个顶点的入度
2. 求一个顶点的出边邻接点
3. 进行图的深度优先遍历
4. 进行图的广度优先遍历

解析：

对于邻接矩阵来说，求一个结点的度，只需要访问邻接矩阵的一行或一列就可以判断次结点的度；

7、使用迪杰斯特拉（Dijkstra）算法求下图中从顶点1到其他各顶点的最短路径，依次得到的各最短路径的目标顶点是：(B)

1. 5, 2, 3, 4, 6
2. 5, 2, 3, 6, 4
3. 5, 2, 4, 3, 6
4. 5, 2, 6, 3, 4

解析：

	1	2	3	4	5	6
{1}		L:5;p=1	L: ∞ \infty ∞;p=1	L: ∞ \infty ∞;p=1	L:4;pr=1	L: ∞ \infty ∞;pr=1
{1,5}		L:5;p=1	L: ∞ \infty ∞;p=1	L:11;p=5		L:10;p=5
{1,5,2}			L:7;p=2	L:11;p=5		L:10;p=5
{1,5,2,3}				L:11;p=5		L:10;p=5
{1,5,2,3,6}				L:11;p=5
{1,5,2,3,6,4}

8、下面给出的有向图中，有__个强连通分量。©

1. 1 ({0,1,2,3,4})
2. 1 ({1,2,3,4})
3. 2 ({1,2,3,4}, {0})
4. 5 ({0}, {1}, {2}, {3}, {4})

解析：

详解连通图;

9、在任一有向图中，所有顶点的入度之和与所有顶点的出度之和的关系是： (A)

1. 相等
2. 大于等于
3. 小于等于
4. 不确定

解析：

一个结点的入度就是相连结点的出度；

10、关于图的邻接矩阵，下列哪个结论是正确的？ (B)

1. 有向图的邻接矩阵总是不对称的
2. 有向图的邻接矩阵可以是对称的，也可以是不对称的
3. 无向图的邻接矩阵总是不对称的
4. 无向图的邻接矩阵可以是不对称的，也可以是对称的

解析：
无向图的邻接矩阵一定是对称的；

11、下面关于图的存储的叙述中，哪一个是正确的？ (A)

1. 用相邻矩阵法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关
2. 用相邻矩阵法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关
3. 用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关
4. 用邻接表法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关

解析：

相邻矩阵法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关；

邻接表法存储图，占用的存储空间数与图中结点个数和边数都有关；

12、数据结构中Dijkstra算法用来解决哪个问题？ (B)

1. 关键路径
2. 最短路径
3. 拓扑排序
4. 字符串匹配

解析：

最短路径算法：Dijkstra，Floyd

字符串匹配：Kmp

13、在用邻接表表示有N个结点E条边的图时，深度优先遍历算法的时间复杂度为： (B)

1. O(N)
2. O(N+E)
3. O( N 2 N^2 N2)
4. O( N 2 N^2 N2×E)

14、一个有N个顶点的强连通图至少有多少条边？ (B)

1. N−1
2. N
3. N+1
4. N(N−1)

解析：

形成一个边最小的强连通图（除了单个结点）一定是一个环；

15、给定有权无向图的邻接矩阵如下，其最小生成树的总权重是： (D)

1. 10
2. 11
3. 12
4. 14

解析：

 4+2+7+1=14;

通过Prim算法或Kruskal算法计算最小生成树的总权；

最小生成树的两种方法（Kruskal算法和Prim算法）

16、我们用一个有向图来表示航空公司所有航班的航线。下列哪种算法最适合解决找给定两城市间最经济的飞行路线问题？ (A)

1. Dijkstra算法
2. Kruskal算法
3. 深度优先搜索
4. 拓扑排序算法

17、设N个顶点E条边的图用邻接表存储，则求每个顶点入度的时间复杂度为： ©

1. O(N)
2. O( N 2 N^2 N2)
3. O(N+E)
4. O(N×E)

18、已知一个图的邻接矩阵如下，则从顶点V1出发按广度优先搜索法进行遍历，可能得到的一种顶点序列为： (A)

1. V1,V2,V3,V5,V4,V6
2. V1,V2,V4,V5,V6,V3
3. V1,V3,V5,V2,V4,V6
4. V1,V3,V5,V6,V4,V2

解析：

图的广度优先搜索（BFS）和深度优先搜索（DFS）算法解析

19、已知一个图的邻接矩阵如下，则从顶点V1出发按深度优先搜索法进行遍历，可能得到的一种顶点序列为： (B)

1. V1,V2,V3,V4,V5,V6
2. V1,V2,V4,V5,V6,V3
3. V1,V3,V5,V2,V4,V6
4. V1,V3,V5,V6,V4,V2

解析：

如上18题；

20、如果从无向图的任一顶点出发进行一次深度优先搜索可访问所有顶点，则该图一定是： (A)

1. 连通图
2. 完全图
3. 有回路的图
4. 一棵树

解析：

任一顶点出发进行一次深度优先搜索可访问所有顶点，说明任意两个结点连通，为连通图；

21、对下图进行拓扑排序，可以得到不同的拓扑序列的个数是： ()

1. 4

2. 3

3. 2

4. 1

解析：

 

以此类推，可构建：

abecd

abced

aebcd

三、填空题

1、对于给定的有向图如下，则每个顶点的入度和出度顺次为：（3/0 2/2 1/2 1/3 2/1 2/3）

2、图的深度优先搜索（DFS）使用了一种数据结构，这种数据结构是 (栈)。

3、使用迪杰斯特拉（Dijkstra）算法求下图中从 0 顶点出发到其它所有顶点的最短路径长度
是，即：

0->1
0->2
0->3
0->4
0->5
0->6
的最短路径长度分别是 （注意：前后不带空格，各最短路径长度间用英文逗号分隔）： (4,5,6,10,9,16)

	0	1	2	3	4	5	6
{0}		L:4;p=0	L:6;p=0	L:6;p=0	L: ∞ \infty ∞;p=0	L: ∞ \infty ∞;p=0	L: ∞ \infty ∞;p=0
{0,1}			L:5;p=1	L:6;p=0	L:11;p=1	L: ∞ \infty ∞;p=0	L: ∞ \infty ∞;p=0
{0,1,2}				L:6;p=0	L:11;p=1	L:9;p=2	L: ∞ \infty ∞;p=0
{0,1,2,3}					L:11;p=1	L:9;p=2	L: ∞ \infty ∞;p=0
{0,1,2,3,5}					L:10;p=5		L:17;p=5
{0,1,2,3,5,4}							L:16;p=4
{0,1,2,3,5,4,6}

若无向图G =（V，E）中含7个顶点，要保证图G在任何情况下都是连通的，则需要的边数最少是：

A.6        B.15        C.16        D.21

首先我想很多人一开始会疑惑为什么不能是 6 个边为最少的情况。请看下图：

可以看到，同样是给出 7 点 6 边，第二种情况并不能连通，也就不符合题目中“任何情况”的要求。

由此我们可以分析到，要让 7 个点都连通，那么先让 6 个点完全连通，所谓完全就是每个点能够支出的边是满的，这样 6 个点的情况下，边和点的关系是满的。其边的数量由公式 n*(n-1)/2 得出（无向完全连通图），也就是 6*5/2=15；

那么此时，我多了一个点，7 号点，只需要在那 6 个点的图中连一根边过来，7 号点就可以访问任意 6 点图中的点了。

 

2-3

具有5个顶点的有向完全图有多少条弧？

A.10        B.16        C.20        D.25

因为在有向完全图中，任何两个顶点之间都有2条弧所以在n个顶点中选取两个顶点的选法有n(n-1)/2所以共有2*n(n-1)/2=n(n-1)条弧。

强连通有向图，满足两个条件：

（1）没有孤点；

（2）任何两点A、B，至少存在1条路径，从A到B；也至少存在1条路径，从B到A。

A>B>C>D,A-->D,存在；D--->A不存在。

n个顶点排在一个圆周上，需要的弧最少。n条。

3.在N个顶点的无向图中，所有顶点的度之和不会超过顶点数的多少倍？

1. 1
2. 2
3. (N−1)/2
4. N−1

这个得分析，就是这种情况下只有是完全图的时候顶点度数之和才能最大，为N*（N-1），即顶点数乘以边数，而顶点数是N，所以一比就是N-1

若一个有向图用邻接矩阵表示，则第i个结点的入度就是：

A.第i行的元素个数

B.第i行的非零元素个数

C.第i列的非零元素个数

D.第i列的零元素个数

图的深度优先遍历类似于二叉树的：先序遍历（根左右）

在用邻接表表示有N个结点E条边的图时，深度优先遍历算法的时间复杂度为：O(N+E)

我们用一个有向图来表示航空公司所有航班的航线。下列哪种算法最适合解决找给定两城市间最经济的飞行路线问题？Dijkstra算法

AOE网是以边表示活动的有向无环网，在AOE网中，具有最大路径长度的路径称为关键路径，关键路径表示完成工程的最短工期。（从第一个事件到最后一个事件的最长路径）

如果G是一个有15条边的非连通无向图，那么该图顶点个数最少为多少？6*5/2=15，故7个结点

图的广度优先遍历类似于二叉树的：层次遍历

给定一个有向图的邻接表如下图，则该图有__个强连通分量。

A.4 {{0, 1, 5}, {2}, {3}, {4}}        B.3 {{2}, {4}, {0, 1, 3, 5}}        

C.1 {0, 1, 2, 3, 4, 5}                  D.1 {0, 5, 1, 3}

 

图的拓扑序必须要满足以下两点：

1. 每个顶点只出现一次。
2. 对于图中的任何一条边，起点必须在终点之前。

不是所有的有向图都是有拓扑序的，只有有向无环图才有拓扑序，所以有向无环图又被称为拓扑图。

具有 100 个顶点和 12 条边的无向图至多有多少个连通分量？（100-6）+1=95个

AOE网：1.最早发生时间：从前往后，前驱结点到当前结点所需时间，取最大值。

               2.最迟发生时间：从后往前，后继结点的最迟发生时间-边权值，取最小值。

对于给定的有向图如下，其强连通分量为：{1}, {2, 3, 4, 6}, {5}

给定无向带权图如下，以下哪个是从顶点 a 出发深度优先搜索遍历该图的顶点序列（多个顶点可以选择时按字母序）？ abcdefgh

 

给定如下有向图，该图的拓扑有序序列的个数是：1个