第7章 图 7.1 选择题
1．对于一个具有n个顶点和e条边的有向图，在用邻接表表示图时，拓扑排序算法时间复杂度为（ ）
A） O(n) B） O(n+e) C） O(n*n) D） O(n*n*n) 【答案】B
2．设无向图的顶点个数为n，则该图最多有（ ）条边。 A）n-1 B）n(n-1)/2 C） n(n+1)/2 D）n2 【答案】B
3．连通分量指的是（ ） A） 无向图中的极小连通子图 B） 无向图中的极大连通子图 C） 有向图中的极小连通子图 D） 有向图中的极大连通子图 【答案】B
4．n个结点的完全有向图含有边的数目（ ） A）n*n B）n（n+1） C）n/2 D）n*（n-1） 【答案】D
5．关键路径是（ ）
A） AOE网中从源点到汇点的最长路径 B） AOE网中从源点到汇点的最短路径 C） AOV网中从源点到汇点的最长路径 D） AOV网中从源点到汇点的最短路径 【答案】A
6．有向图中一个顶点的度是该顶点的（ ）
A）入度 B） 出度 C） 入度与出度之和 D） （入度+出度）/2 【答案】C
7．有e条边的无向图，若用邻接表存储，表中有（ ）边结点。 A） e B） 2e C） e-1 D） 2(e-1) 【答案】B
8．实现图的广度优先搜索算法需使用的辅助数据结构为（ ） A） 栈 B） 队列 C） 二叉树 D） 树 【答案】B
9．实现图的非递归深度优先搜索算法需使用的辅助数据结构为（ ） A） 栈 B） 队列 C） 二叉树 D） 树 【答案】A
10．存储无向图的邻接矩阵一定是一个（ ）
A） 上三角矩阵 B）稀疏矩阵 C） 对称矩阵 D） 对角矩阵 【答案】C
11．在一个有向图中所有顶点的入度之和等于出度之和的（ ）倍 A） 1/2 B）1 C） 2 D） 4 【答案】B
12．在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为（ ） A） O(n) B） O(n+e) C） O(n2) D） O(n3)
【答案】B
13．下列关于AOE网的叙述中，不正确的是（ ） A）关键活动不按期完成就会影响整个工程的完成时间
B）任何一个关键活动提前完成，那么整个工程将会提前完成 C）所有的关键活动提前完成，那么整个工程将会提前完成 D）某些关键活动提前完成，那么整个工程将会提前完成 【答案】B
14．具有10个顶点的无向图至少有多少条边才能保证连通（ ） A） 9 B）10 C） 11 D） 12 【答案】A
15．在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（ ） A） e B）2e C） n2-e D）n2-2e 【答案】D 7.2 填空题
1．无向图中所有顶点的度数之和等于所有边数的_____________倍。 【答案】2 2．具有n个顶点的无向完全图中包含有_____________条边，具有n个顶点的有向完全图中包含有_____________条边。 【答案】（1）n(n-1)/2 （2） n(n-1)
3．一个具有n个顶点的无向图中，要连通所有顶点则至少需要_____________条边。 【答案】n-1
4．假定一个图具有n个顶点和e条边，则采用邻接矩阵、邻接表表示时，其相应的空间复杂度分别为_____________和_____________。 【答案】（1）O(n2) （2） O(n+e)
5．对用邻接矩阵表示的图进行任一种遍历时，其时间复杂度为_____________，对用邻接表表示的图进行任一种遍历时，其时间复杂度为_____________。 【答案】（1）O(n2) （2） O(e)
6．对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别为_____________和_____________条。 【答案】（1）e （2）2e
7． 在有向图的邻接表和逆邻接表表示中，每个顶点的边链表中分别链接着该顶点的所有_____________和_____________结点。 【答案】（1）出边 （2） 入边
8． 对于一个具有n个顶点和e条边的无向图，当分别采用邻接矩阵、邻接表表示时，求任一顶点度数的时间复杂度依次为_____________和_____________。 【答案】（1）O(n) （2）O(e+n)
9．对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为_____________和_____________。 【答案】（1）n （2） n-1
10．Prim算法和Kruscal算法的时间复杂度分别为_____________和_____________。 【答案】（1）O(n2) （2）O(eloge)
11．针对下图所示的连通网络，试按如下格式给出在Kruscal算法构造最小生成树过程中顺
序选出的各条边。
【答案】设边的信息表示为（始点，终点，权值），则在Kruscal算法构造最小生成树过程中顺序选出的各条边为：（3 ，5，1），（2，4，2），（1，5，3），（1，2，3）。 7.3 判断题
1．图是一种非线性结构，所以只能用链式存储。（ ） 【答案】×
2．图的最小生成树是唯一的。（ ） 【答案】×
3．如果一个图有n个顶点和小于n-1 条边，则一定是非连通图。（ ） 【答案】√
4．有n-1 条边的图一定是生成树。（ ） 【答案】×
5．用邻接矩阵表示图时，矩阵元素的个数与顶点个数相关，与边数无关。（ ） 【答案】√
6．用邻接表表示图时，顶点个数设为n，边的条数设为e，在邻接表上执行有关图的遍历操作时，时间代价为O(n+e)。（ ） 【答案】√
7．逆邻接表只能用于有向图，邻接表对于有向图和无向图的存储都适用。（ ） 【答案】√
8．任何一个关键活动提前完成, 那么整个工程将会提前完成。（ ） 【答案】×
9．在AOE网络中关键路径只有一条。（ ） 【答案】×
10．在AOV网络中如果存在环，则拓扑排序不能完成。（ ） 【答案】√
11．图的邻接矩阵存储是唯一的，邻接表存储也是唯一的。（ ） 【答案】×
12．假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个顶点vi相关的所有弧的时间复杂度是O(n*e) 。（ ） 【答案】×
13．任意一个图都是其自身的子图。（ ） 【答案】√
14．一个无向连通图的生成树是含有该连通图的全部顶点的极大连通子图。（ ） 【答案】× 7.4 应用题 1．设有一有向图为G=(V，E)。其中，V={ v1, v2, v3, v4, v5}，E={
（1）边集E中
（2）强连通图是任意两顶点间都存在路径的有向图。 【答案】该有向图是强连通图，表示如下：
2．画出1个顶点、2个顶点、3个顶点、4个顶点和5个顶点的无向完全图。并说明在n个顶点的无向完全图中，边的条数为n(n-1)/2。 【答案】
【解析】因为在有n个顶点的无向完全图中，每一个顶点与其它任一顶点都有一条边相连，所以每一个顶点有n-1条边与其他顶点相连，则 n个顶点有n(n-1)条边。但在无向图中，顶点i到顶点j与顶点j到顶点i是同一条边，所以总共有n(n-1)/2条边。 3．对n个顶点的无向图G，采用邻接矩阵表示，如何判别下列有关问题： （1）图中有多少条边?
（2）任意两个顶点i和j是否有边相连? （3）任意一个顶点的度是多少? 【答案】
（1）无向图的邻接矩阵是对称的，故它的边数应是上三角或下三角的非0元个数。 （2）邻接矩阵中如果第i行第j列的元素非0则表示顶点i与顶点j相连。 （3）任意一个顶点vi的度是第i行或第i列上非0元的个数。
4．熟悉图的存储结构，画出下面有向图的邻接矩阵、邻接表、逆邻接表、十字链表。写出邻接表表示的图从顶点A出发的深度优先遍历序列和广度优先遍历序列。
【答案】
邻接矩阵如下： 邻接表如下：
逆邻接表如下：
十字链表如下：
深度优先遍历序列为ABCFED，广度优先遍历序列为ABDCEF
5．已知下面是某无向图的邻接表，画出该无向图，并分别给出从A出发的深度优先搜索生成树和广度优先搜索生成树。