11、对如图所示的有向图 G ,它的拓扑序列是 。
A. a , b , c , d B. a , d , b , c C. a , b , d , c D. b , a , d , c 12、对如下所示的图，它的生成树有
棵。
A. 1 B. 5 C. 6 D．不确定
13、如图所示的有向图的顶点可以排成 个不同的拓扑序列。
A．3 B．5 C. 7 D.9 14、一个有n个结点的图，最少有
个连通分量，最多有 个连通分量。
A．0 B．1 C．n-1 D．n 15、用有向无环图描述表达式(A+B)*（（A+B）/A），至少需要顶点的数目为 A．5 B．6 C．8 D．9 16、下列说法不正确的是 。
。
A．图的遍历是从给定的源点出发每一个顶点仅被访问一次 B．遍历的基本算法有两种：深度遍历和广度遍历
- 26 -
C．图的深度遍历不适用于有向图 D．图的深度遍历是一个递归过程
17、无向图G=(V,E),其中：V={a,b,c,d,e,f}, E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进
行深度优先遍历，得到的顶点序列正确的是
。
A．a,b,e,c,d,f B．a,c,f,e,b,d C．a,e,b,c,f,d D．a,e,d,f,c,b 18、下面 方法可以判断出一个有向图是否有环（回路）：
A．深度优先遍历 B. 拓扑排序 C. 求最短路径 D. 求关键路径 19、在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为 A. O(n) B. O(n+e) C. O(n2) D. O(n3) 20、求解最短路径的Floyd算法的时间复杂度为 。
。
A．O（n） B. O（n+c） C. O（n*n） D. O（n*n*n） 21、已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，
E={
。
A．V1,V3,V4,V6,V2,V5,V7 B．V1,V3,V2,V6,V4,V5,V7 C．V1,V3,V4,V5,V2,V6,V7 D．V1,V2,V5,V3,V4,V6,V7
22、在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是
。
A．G中有弧
。
A. O(n) B. O(n＋e) C. O(n*n) D. O(n*n*n) 二、判断题
1、 在n个结点的无向图中，若边数大于n-1,则该图必是连通图。 2、 有e条边的无向图，在邻接表中有e个结点。
3、 有向图中顶点V的度等于其邻接矩阵中第V行中的1的个数。 4、 强连通图的各顶点间均可达。
5、 用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。
6、 有n个顶点的无向图, 采用邻接矩阵表示, 图中的边数等于邻接矩阵中非零元素之和的
- 27 -
一半。
7、 有向图的邻接矩阵是对称的。 8、 任何无向图都存在生成树。
9、 一个有向无环图的拓扑排序序列是唯一的。 10、关键路径是AOE网中从源点到终点的最长路径。
三、填空题
1、 设有一稀疏图 G ，则 G 采用__________存储比较节省空间；
设有一稠密图 G ，则 G 采用__________存储比较节省空间。
2、 n 个顶点 e 条边的图采用邻接矩阵存储，深度优先搜索遍历算法的时间复杂度为
____________，采用邻接表存储，深度优先搜索遍历算法的时间复杂度为___________。 3、 n 个顶点的完全图有___________条边。
4、 有 n 个顶点的无向连通图至少有 条边，有 n 个顶点的有向强连通图至少
有 条弧。
5、 用邻接矩阵表示无向图时，若图中有 n = 500 个顶点， m = 500 条边，则形成的邻接
矩阵共有 个元素，其中 个为非零元素。
6、 判断一个无向图是一棵树的条件是 。 7、 若用n表示图中顶点数目，则有_______条边的无向图成为完全图。 8、 G是一个非连通无向图，共有28条边，则该图至少有______个顶点。
9、 在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶
点的______；对于有向图来说等于该顶点的______。
10、 对于一个具有n个顶点e条边的无向图的邻接表的表示，则表头向量大小为______，邻接表的边结点个数为______。
11、已知一无向图G=（V，E），其中V={a,b,c,d,e } E={(a,b),(a,d),(a,c),(d,c),(b,e)}现用某一
种图遍历方法从顶点a开始遍历图，得到的序列为abecd，则采用的是______遍历方法。 12、为了实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点外，还需______存放被访问的结点以实现遍历。
13、Prim（普里姆）算法适用于求______的网的最小生成树；kruskal（克鲁斯卡尔）算法适
用于求______的网的最小生成树。
14、克鲁斯卡尔算法的时间复杂度为______,它对______图较为适合。
- 28 -
四、解答题
1、 已知无向图的邻接表如下，①在给出顶点的图上，画出这个图的边；②写出该图的邻接
矩阵A；③根据邻接表，写出从顶点V1出发，深度优先遍历该图所得到的顶点序列。
1 2 3 4 5
提示：
V1 V3 V4 V2 V5 2、 己知一无向图有 6 个结点， 9 条边，这 9 条边依次为（ 0 , l ) , ( 0 , 2 ) , ( 0 , 4 ) , ( 0 ,
5 ) ,( l , 2 ) , ( 2 , 3 ) , ( 2 , 4 ) , ( 3 , 4 ) , ( 4 , 5 ）。试画出该无向图，并从顶点 0 出发分别写出按深度优先搜索和广度优先搜索进行遍历的结点序列。 3、 已知如图1 所示的有向图，给出该图的：
① 每个顶点的出度和入度； ② 强连通分量； ③ 最长的简单路径； ④ 最长的简单回路；
⑤ 进行拓扑排序，给出顶点的拓扑序列。
4、 对如图2所示的连通图，列出分别从顶点 A 、 D 开始，深度优先和广度优先搜索遍
历该图所得到的顶点序列，画出相应的生成树。
图1 图2
5、 设无向图G=（V，E），其中V={1，2，3，4，5}，E={（1，2，4），（2，5，5），
（1，3，2），（2，4，4），（3，4，1），（4，5，3），（1，5，8）}，每条边由一个三元组表示，三元组中前两个元素为与该边关联的顶点，第三个元素为该边的权。请写出图G中从顶点1到其余各点的了短路径的求解过程。要求列出最短路径上的顶点，并计算路径长度。
- 29 -
6、 下图是以边为活动的网（AOE_网），以V1为开始点，以V10为终止点，计算该AOE_
网的关键路径长度（即，从开始点到终止点的最长路径长度）。
7、 对如下无向图，试给出：
① 用普里姆算法构造最小生成树的过程 ② 用克鲁斯卡尔算法构造最小生成树的过程
五、算法设计题
1、 图G为有向无权图，试在邻接矩阵存储结构上实现删除一条边(v,w)的操作：
DeleteArc(G,v,w)。若无顶点v或w，返回“ERROR”；若成功删除，则边数减1，并返回“OK”。（提示：删除一条边的操作，可以将邻接矩阵的第i行全部置0 ），完成该算法。 Status DeleteArc(MGraph &G,char v,char w) //在邻接矩阵表示的图G上删除边(v,w) { if ((i=LocateVex(G, v))<0) return if ((j=LocateVex(G, w))<0) return if (G.arcs[i][j].adj)
{ G.arcs[i][j].adj= ;
G.arcnum ; （或 G.arcnum=G.arcnum-1 ） } return }
;
; ;
3 E B 5 6 6 4 F 6 A 1 C 5 2 5 D - 30 -