单选题
1.无向图中的一条边，在其邻接表存储结构中对应两个弧结点。
对
2.有n-1条边的图肯定都是生成树。
错
3.任何无向图都存在生成树。
错
4.一个无向图G，若某顶点v到其它每个顶点都有至少一条路径，则图G只有1个连通分量。
对
5.无向连通图所有顶点的度之和为偶数。
对
6.用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关。
错
7.在一个有向图中，所有顶点的入度与出度之和等于所有边之和的2倍。
对
8.在任一有向图中，所有顶点的入度之和等于所有顶点的出度之和。
对
9.AOE图的关键路径就是最长的路径
对
10.拓扑排序的有向图中，最多存在一个环路。
错
11.若有向图G存在拓扑排序序列，则G一定不是强连通的。
对
选择题
1.具有5个顶点的有向完全图有多少条弧？
20
2.关于图的邻接矩阵，下列哪个结论是正确的？
有向图的邻接矩阵可以是对称的，也可以是不对称的
3.在一个有向图中，所有顶点的入度与出度之和等于所有边之和的多少倍？
2
4.下面给出的有向图中，有__个强连通分量。
2 ({1,2,3,4}, {0})
5.给定一个有向图的邻接表如下图，则该图有__个强连通分量。
3 {
{2}, {4}, {0, 1, 3, 5}}
6.设无向图为 G=(V，E)，其中 V={v1,v2,v3,v4}，E={(v1,v2)，(v3,v4)，(v4,v1)，(v2,v3)，(v1,v3)}。则每个顶点的度依次为：
3, 2, 3, 2
7.在一个图中，所有顶点的度数之和等于图的边数的（ ）倍
2
8.有关路径的定义是（ ）。
由顶点和相邻顶点序偶构成的边所形成的序列
9.若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点，则该图一定是（ ）图。
连通
10.下面（ ）算法适合构造一个稠密图G的最小生成树。
Prim算法
11.已知图的邻接矩阵如图所示，则从顶点v0出发按深度优先遍历的结果是（ ）
0134256
12.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ ）倍。
1
13.个顶点的连通图用邻接矩阵表示时，该矩阵至少有（ ）个非零元素。
2（n-1）
14.在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（ ）。
G中有一条从Vj到Vi的路径
15.关键路径是事件结点网络中（ ）。
从源点到汇点的最长路径
16.具有N（N>0）个顶点的无向图至多有多少个连通分量？
N
17.用邻接表表示图进行广度优先遍历时，通常借助（ ）来实现算法。
队列
18.已知图的邻接表如图所示，则从顶点v0出发按广度优先遍历的结果是（ ）。
0123
19.下面（ ）方法可以判断出一个有向图是否有环。
拓扑排序
20.使用迪杰斯特拉（Dijkstra）算法求下图中从顶点1到其他各顶点的最短路径，依次得到的各最短路径的目标顶点是：
5, 2, 3, 6, 4
21.设无向图的顶点个数为n，则该图最多有（ ）条边。
n(n-1)/2
22.下列哪一种图的邻接矩阵是对称矩阵？（ ）
对称矩阵
23.G是一个非连通无向图，共有28条边，则该图至少有（）个顶点。
9
24.用邻接表表示图进行深度优先遍历时，通常借助（ ）来实现算法。
栈
25.图的深度优先遍历类似于二叉树的：
先序遍历
26.图的广度优先遍历类似于二叉树的：
层序遍历
27.已知图的邻接表如下所示，则从顶点v0出发按深度优先遍历的结果是
0123
28.已知图的邻接表如下所示，则从顶点v1出发按深度优先遍历的结果是
1023
29.下图为一个AOV网，其可能的拓扑有序序列为：
ABCEDF
30.给定有权无向图如下。关于其最小生成树，下列哪句是对的？
最小生成树不唯一，其总权重为23