目录
一、判断题
二、选择题
在开始之前，先为大家推荐四篇介绍该章四个主要算法的的文章，供大家参考。
Dijkstra算法求最短路径：Dijkstra算法原理_平凡的L同学的博客-CSDN博客_dijiesitela
Floyd算法求最短路径：Floyd算法求最短路径
Prim算法求最小生成树：Prim算法求最小生成树
Kruskal算法求最小上生成树：Kruskal算法求最小上生成树
一、判断题
1、用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关。F
解析：用邻接矩阵法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关，空间代价为O（n*n）；用邻接表法存储图，占用的存储空间数与图中结点个数和边数都有关，有向图为O（n+2e）,无向图为O（n+e）。
2、无向连通图所有顶点的度之和为偶数。T
解析：顶点的度为顶点所连接的边的个数，无向连通图中的顶点的度之和为边数*2所以顶点的度之和为偶数。
3、无向图的邻接矩阵可用一维数组存储。T
解析：习惯上无向图的邻接矩阵一般用二维数组存储，这样使用方便。当然，任意二维数组都是可以用一维数组存储的，只是用起来不方便。
4、若图G有环，则G不存在拓扑排序序列。T
解析：拓扑排序对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，存在拓扑排序和图是否有环是充分必要条件。
5、Prim 算法是通过每步添加一条边及其相连的顶点到一棵树，从而逐步生成最小生成树。T
解析：prim算法是通过每步添加一条边及其相连的顶点到一棵树，从而逐步生成最小生成树；
Kruskal 算法是维护一个森林，每一步把两棵树合并成一棵。
6、用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中结点个数有关，而与图的边数无关。T
解析：用邻接矩阵法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关，空间代价为O（n*n）。
7、在一个有向图中，所有顶点的入度与出度之和等于所有边之和的2倍。T
解析：有一条边就会有两个顶点分别增加一个入度和出度，所以所有顶点的入度与出度之和等于所有边之和的2倍。
8、连通分量指的是有向图中的极大连通子图。F
解析：连通图和连通分量都是针对无向图而言的。在有向图中，任意两个顶点都有一条从1到2和一条从2到1的有向路径，则称该图为强连通图。有向图中的极大连通子图称为该有向图中的强连通分量。
9、在任一有向图中，所有顶点的入度之和等于所有顶点的出度之和。T
解析：在有向图中，一条边必然会对应一个顶点的出和一个顶点的入，所以入度等于出度。
10、从n个顶点的连通图中选取n-1条权值最小的边即可构成最小生成树。F
解析：一个有N个顶点的连通图的生成树有N-1条边，但是含N个顶点N-1条边的图不一定是生成树。且最小生成树的总权最小，不是其中的任意路径最小。
11、对于带权无向图 G = (V, E)，M 是 G 的最小生成树，则 M 中任意两点 V1 到 V2 的路径一定是它们之间的最短路径。F
解析：最小生成树的总权最小，不是其中的任意路径最小。
12、如果从有向图 G 的每一点均能通过深度优先搜索遍历到所有其它顶点，那么该图一定不存在拓扑序列。T
解析：如果从有向图 G 的每一点均能通过深度优先搜索遍历到所有其它顶点，则该图是一个有环图；而拓扑排序的前提是有向无环图。
二、选择题
1、数据结构中Dijkstra算法用来解决哪个问题？
A.字符串匹配
B.拓扑排序
C.最短路径
D.关键路径
解析：
最短路径算法：Dijkstra，Floyd
最小生成树：Prim，Kruskal
字符串匹配：Kmp
拓扑排序：对有向无环图进行
2、给定有权无向图的邻接矩阵如下，其最小生成树的总权重是：
A.11
B.14
C.10
D.12
解析：
3、已知一个图的邻接矩阵如下，则从顶点V1出发按广度优先搜索法进行遍历，可能得到的一种顶点序列为：
A.V1,V2,V3,V5,V4,V6
B.V1,V3,V5,V6,V4,V2
C.V1,V3,V5,V2,V4,V6
D.V1,V2,V4,V5,V6,V3
解析：
4、对于一个具有N个顶点的无向图，要连通所有顶点至少需要多少条边？
A.N
B.N/2
C.N−1
D.N+1
解析：连通是两个顶点之间有路径即连通，N-1条就够了。
5、关于图的邻接矩阵，下列哪个结论是正确的？
A.有向图的邻接矩阵总是不对称的
B.无向图的邻接矩阵可以是不对称的，也可以是对称
C.有向图的邻接矩阵可以是对称的，也可以是不对称的
D.无向图的邻接矩阵总是不对称的
解析：有向图的邻接矩阵可以是不对称的，也可以是对称的；无向图的邻接矩阵一定是对称的。
6、在用邻接表表示有N个结点E条边的图时，深度优先遍历算法的时间复杂度为：
A.O(N+E)
B.O(N2×E)
C.O(N2)
D.O(N)
解析：深度和广度优先优先遍历的时间复杂度一样，采用邻接表表示法，有向图为O(n+2e)，无向图为O(n+e)；邻接矩阵法O(n*n)。
7、 给定一个有向图的邻接表如下图，则该图有__个强连通分量。
A.4 {{0, 1, 5}, {2}, {3}, {4}}
B.1 {0, 1, 2, 3, 4, 5}
C.1 {0, 5, 1, 3}
D.3 {{2}, {4}, {0, 1, 3, 5}}
解析：
8、对于有向图，其邻接矩阵表示比邻接表表示更易于：
A.求一个顶点的出边邻接点
B.进行图的广度优先遍历
C.进行图的深度优先遍历
D.求一个顶点的入度
解析：对于邻接矩阵来说，求一个结点的度，只需要访问邻接矩阵的一行或一列就可以判断次结点的度。
9、对下图进行拓扑排序，可以得到不同的拓扑序列的个数是：
A.4
B.3
C.1
D.2
解析：个数是3，分别是abced,abecd,aebcd。先统计所有节点的入度，对于入度为0的节点就可以分离出来，然后把这个节点指向的节点的入度减一。一直做改操作，直到所有的节点都被分离出来。如果最后不存在入度为0的节点，那就说明有环，不存在拓扑排序，也就是很多题目的无解的情况。
10、任何一个带权无向连通图的最小生成树——
A.有可能不唯一
B.有可能不存在
C.是唯一的
D.是不唯一的
解析：最小生成树不一定唯一，但如果边的权值都不相等，则一定唯一。
11、下面给出的有向图中，有__个强连通分量。
A.1 ({1,2,3,4})
B.2 ({1,2,3,4}, {0})
C.1 ({0,1,2,3,4})
D.5 ({0}, {1}, {2}, {3}, {4})
解析：其实就是有几个最大的环。
12、下面关于图的存储的叙述中，哪一个是正确的？
A.用相邻矩阵法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关
B.用相邻矩阵法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关
C.用邻接表法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关
D.用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关
解析：邻接矩阵只与结点个数有关，与边数无关；而邻接表表示法与结点和边的个数都有关系。 文章来源：https://www.toymoban.com/news/detail-487635.html
上面的题目均是博主在期末考试前总结的重难点，欢迎各位大佬指正错误或者给出更优质的解析。文章来源地址https://www.toymoban.com/news/detail-487635.html
到了这里，关于算法与数据结构 第六章 图（详解）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
![[数据结构 -- 手撕排序算法第六篇] 递归实现快速排序（集霍尔版本，挖坑法，前后指针法为一篇的实现方法，很能打）](https://imgs.yssmx.com/Uploads/2024/02/589845-1.png)
