第 7 章 图
一、单选题
1、 在一个图中，所有顶点的度数之和等于图的边数的 倍。
A. 1/2 B.1 C. 2 D. 4
2、 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 A. 1/2 B.1 C. 2 D. 4 3、 有8个结点的无向图最多有 条边。
倍。
A. 14 B. 28 C. 56 D. 112 4、 有 8 个结点的有向完全图有 条边（弧）。
A. 14 B. 28 C. 56 D． 112 5、 用邻接表表示图进行广度优先遍历时，通常采用 来实现算法的。
A．栈 B．队列 C. 树 D．图 6、 用邻接表表示图进行深度优先遍历时，通常采用 来实现算法的。
A．栈 B．队列 C. 树 D．图 7、 深度优先遍历类似于二叉树的 。
A．先序遍历 B．中序遍历 C．后序遍历 D．层次遍历 8、 广度优先遍历类似于二叉树的 。
A．先序遍历 B．中序遍历 C．后序遍历 D．层次遍历 9、 对如下图所示的无向图 G ，若从顶点 Vl 开始，按深度优先搜索法进行遍历，则可能
的访问顺序为
。
A. Vl V2 V5 V8 V4 V6 V7 V3 B. Vl V2 V3 V4 V5 V6 V7 V8 C. VI V2 V3 V4 V8 V5 V6 V7 D. Vl V2 V4 V5 V8 V3 V6 V7
顺序为
。
10、对如图所示的无向图，若从顶点 V1开始，按广度优先搜索法进行遍历，则可能访问的
A. VI V2 V3 V4 V5 V6 V7 V8 B. VI V2 V6 V3 V4 V7 V8 V5 C. VI V2 V6 V3 V4 V5 V7 V8 D. VI V2 V4 V7 V3 V8 V6 V5
- 25 -
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 -