1.用邻接矩阵法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关。 T
在一个有向图中，所有顶点的入度与出度之和等于所有边之和的2倍。 T
在任一有向图中，所有顶点的入度之和等于所有顶点的出度之和。 T
如果无向图G必须进行两次广度优先搜索才能访问其所有顶点，则G一定有2个连通分量。 T
在一个有权无向图中，若b到a的最短路径距离是12，且c到b之间存在一条权为2的边，则c到a的最短路径距离一定不小于10。 T
Kruskal 算法是维护一个森林，每一步把两棵树合并成一棵。T
Prim 算法是通过每步添加一条边及其相连的顶点到一棵树，从而逐步生成最小生成树。 T
若图G有环，则G不存在拓扑排序序列。T
若图G为连通图且不存在拓扑排序序列，则图G必有环。T
如果从有向图 G 的每一点均能通过深度优先搜索遍历到所有其它顶点，那么该图一定不存在拓扑序列。T
如果 e 是有权无向图 G 唯一的一条最短边，那么边 e 一定会在该图的最小生成树上。T
2.用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关。 F
如果无向图G必须进行两次广度优先搜索才能访问其所有顶点，则G中一定有回路。 F
P 是顶点 S 到 T 的最短路径，如果该图中的所有路径的权值都加 1，P 仍然是 S 到 T 的最短路径。 F
3.下列关于无向连通图特征的叙述中，正确的是：
所有顶点的度之和为偶数
边数大于顶点个数减1
至少有一个顶点的度为1
4.若无向图G =（V，E）中含7个顶点，要保证图G在任何情况下都是连通的，则需要的边数最少是：16
有n个顶点的强连通图最多有n（n-1）/2条边，最少有n-1条边。
n(n-1)/2+1=16 ,n=6
5.具有5个顶点的有向完全图有多少条弧？20
有n(n-1)条边的有向图称为有向完全图
6.在
N个顶点的无向图中，所有顶点的度之和不会超过顶点数的多少倍 （ N-1 ） 7.对于有向图，其邻接矩阵表示比邻接表表示更易于：
8.若一个有向图用邻接矩阵表示，则第i个结点的入度就是：i列的非零元素个数
9.下面关于图的存储的叙述中，哪一个是正确的？
B.用相邻矩阵法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关
C.用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关
D.用邻接表法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关
10.关于图的邻接矩阵，下列哪个结论是正确的？
无向图的邻接矩阵可以是不对称的，也可以是对称的
11.图的深度优先遍历类似于二叉树的：
先序遍历
图的广度优先遍历类似于二叉树的：
层次遍历
12.在用邻接表表示有
N个结点E条边的图时，深度优先遍历算法的时间复杂度为： O(N+E) 13. 已知一个图的邻接矩阵如下，则从顶点V1出发按深度优先搜索法进行遍历，可能得到的一种顶点序列为：
（感谢湘潭大学朱江老师斧正）
V1,V3,V5,V6,V2,V4
14.数据结构中Dijkstra算法用来解决哪个问题？ （ 最短路径问题 ）
15.给定有权无向图的邻接矩阵如下，其最小生成树的总权重是：14
16.在AOE网中，什么是关键路径？
17.下面给出的有向图中，各个顶点的入度和出度分别是：
18.若要检查有向图中有无回路，除了可以利用拓扑排序算法外，下列哪种算法也可以用？深度优先算法
19.给定有权无向图的邻接矩阵如下，其最小生成树的总权重是：
20.给定一个有向图的邻接表如下图，则该图有__个强连通分量。
21.给定有权无向图的邻接矩阵如下，其最小生成树的总权重是：
22.给定有向图的邻接矩阵如下：
顶点2（编号从0开始）的出度和入度分别是： 0, 2
23.给定有权无向图如下。关于其最小生成树，下列哪句是对的？
24.下列选项中，不是如下有向图的拓扑序列的是：
5, 2, 1, 6, 3, 4
25.具有 100 个顶点和 12 条边的无向图至多有多少个连通分量？ 95
6个顶点的完全无向图的边为15，即6个顶点连为12条边的图，剩下94个点无边，共95个连通分量。
26.具有 50 个顶点和 17 条边的无向图至多有多少个连通分量？44
27.使用迪杰斯特拉（Dijkstra）算法求下图中从顶点1到其他各顶点的最短路径，依次得到的各最短路径的目标顶点是：
28.
