C、所有的关键活动提前完成，那么整个工程将会提前完成 D、某些关键活动提前完成，那么整个工程将会提前完成
11、已知图的邻接矩阵如下，根据算法，则从顶点0出发，按广度优先遍历的结点序列是（ C ）
?0?1??1?1??1??0??1100100110001001100110101101000011011??1?0??0?0??1?0??A 0 2 4 3 1 6 5 B、0 1 3 5 6 4 2 C、0 1 2 3 4 6 5 D、0 1 2 3 4 5 6
12、已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是（ D ）
A、0 1 3 2 B、0 2 3 1 C、0 3 2 1 D、0 1 2 3
13、已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是（ A ）
A、0 3 2 1 B、0 1 2 3 C、0 1 3 2 D、0 3 1 2
14、深度优先遍历类似于二叉树的（ A ）。
A、先序遍历 B、中序遍历 C、后序遍历 D、层次遍历 15、广度优先遍历类似于二叉树的（ D ）
A、先序遍历 B. 中序遍历 C、 后序遍历 D、层次遍历 16、下面结构中最适于表示稀疏无向图的是（ D ）。
A、邻接矩阵 B、逆邻接表 C、十字链表 D、邻接表
26
17、下列（ B ）的邻接矩阵是对称矩阵。
A、有向图 B、无向图 C、AOV网 D、AOE网 18、下面哪一方法可以判断出一个有向图是否有环（回路）( B)。 A、深度优先遍历 B、拓扑排序 C、求最短路径 D、求关键路径
19、在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（ D ）。 A、G中有弧
二、填空题
1、图有 邻接矩阵 、邻接表 等存储结构，遍历图 深度优先遍历、 广度优先遍历 等方法。 2、有向图G用邻接表矩阵存储，其第i行的所有元素之和等于顶点i的 出度 。 3、拓扑排序算法是通过重复选择具有 0 个前驱顶点的过程来完成的。
4、n个顶点e条边的图，若采用邻接矩阵存储，则空间复杂度为O(n2)，若采用邻接表存储，则空间复杂度为O(n+e)。
5、n个顶点e条边的图采用邻接矩阵存储，广度优先遍历算法的时间复杂度为 O(n2) ；若采用邻接表存储，该算法的时间复杂度为O(n+e)。
6、设有一稀疏图G，则G采用 邻接表 存储较省空间，设有一稠密图G，则G采用邻接矩阵存储较省空间。
7、用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度递增的次序来得到最短路径的。
8、n个顶点的连通无向图，其边的条数至少为__ n-1____。若用n表示图中顶点数目，则有___
n(n-1)/2____条边的无向图成为完全图。
9、具有8个顶点的有向完全图有 56条弧。具有10个顶点的无向图，边的总数最多为_ 45_。 10、在无向图G的邻接矩阵A中，若A[i][j]等于1，则A[j][i]等于 1 。 11、G是一个非连通无向图，共有28条边，则该图至少有_9_个顶点。
12、为了实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点外，还需_队列存放被访问的结点以实现遍历。
13、一无向图G（V，E），其中V（G）={1,2,3,4,5,6,7}，E（G）={（1,2）,(1,3），（2,4），（2,5），（3,6），（3,7），（6,7）（5,1）},对该图从顶点3开始进行遍历，去掉遍历中未走过的边，得一生成树G’(V，E’）,V（G’）=V（G），E（G’）={（1,3），（3,6），（7,3），（1,2），（1,5），（2,4）}，则采用的遍历方法是___广度优先遍历___ 14、在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的_度_；对于有向图来说等于该顶点的_出度_。
15、 已知一无向图G=（V，E），其中V={a,b,c,d,e } E={(a,b),(a,d),(a,C、,(d,C、,(b,e)}
27
现用某一种图遍历方法从顶点a开始遍历图，得到的序列为abecd，则采用的是__深度优先遍历方法。
三、判断题
1、在拓朴序列中，如果结点Vi排在结点Vj的前面，则一定存在从Vi到Vj的路径。(? ) 2、用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。(√ )
3、拓扑排序是按AOE网中每个结点事件的最早发生时间对结点进行排序。(× ) 4、采用邻接表存储的图的深度优先遍历算法类似二叉树的按层次遍历算法。（× ） 5、若一个有向图的邻接矩阵中对角线以下元素均为零，则该图的拓扑有序序列必定存在。(√ )
6、在n个结点的无向图中，若边数大于n-1,则该图必是连通图。（× ） 7、有e条边的无向图，在邻接表中有e个结点。（× ）
8、有向图中顶点V的度等于其邻接矩阵中第V行中的1的个数。（× ） 9、强连通图的各顶点间均可达。（√ ）
10、连通分量指的是有向图中的极大连通子图。（×）
11、任何有向图的结点都可以排成拓扑排序，而且拓扑序列不唯一。（×） 12、用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。（×）
13、有n个顶点的无向图, 采用邻接矩阵表示, 图中的边数等于邻接矩阵中非零元素之和的一半。（√）
14、当改变网上某一关键路径上任一关键活动后，必将产生不同的关键路径(× ) 15、不同的求最小生成树的方法最后得到的生成树是相同的.（× ）
四、简答题
1、请对下图的无向带权图：
（1） 写出它的邻接矩阵，并按普里姆算法求其最小生成树；
（2） 写出它的邻接表，并按克鲁斯卡尔算法求其最小生成树。
解：设起点为a。可以直接由原始图画出最小生成树，而且最小生成树只有一种（类）!
邻接矩阵为：
最小生成树→ ?043????40559??3505????55076??9?703?630 ???????5?2???54??????5?206????5?4?????6?0??28
2、已知二维数组表示的图的邻接矩阵如下图所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。
2、给定下列
网G:
A B———————C
试着找出网G的最小生成树，画出其逻辑结构图； 解：
3、图2表示一个地区的通讯网，边表示城市间的通讯线路，边上的权值表示架设线路花费的代价，请找出能连通每个城市、且总代价最省的n-1条线路。
E————F G————D
答： 图2
29
4、B = (K, R), K = {k1, k2, ?, k9}
R={
分别对关系r中的开始结点，举出一个拓扑序列的例子。
解：开始结点：（入度为0）K1，K2，终端结点（出度为0）K6，K7。 拓扑序列K1，K2，K3，K4，K5，K6，K8，K9，K7 K2，K1，K3，K4，K5，K6，K8，K9，K7
规则：开始结点为K1或K2，之后，若遇多个入度为0的顶点，按顶点编号顺序选择。 5、已知有向图如下所示，对该图进行拓扑排序。
G B A C E H I D F
答：拓扑序列为：A、B、C、D、E、F、G、H、I（不唯一） 6.已知图的邻接矩阵为： V1 V2 V3 V4 V5 V6 V7 V8 V9 V10 V1 0 1 1 1 0 0 0 0 0 0 V2 0 0 0 1 1 0 0 0 0 0 V3 0 0 0 1 0 1 0 0 0 0 V4 0 0 0 0 0 1 1 0 1 0 V5 0 0 0 0 0 0 1 0 0 0 V6 0 0 0 0 0 0 0 1 1 0 V7 0 0 0 0 0 0 0 0 1 0 V8 0 0 0 0 0 0 0 0 0 1 V9 0 0 0 0 0 0 0 0 0 1 30