第7章-图练习题及标准答案.docx

第七章 图
一、单选题
（

C ）1.
A ． 1/2

在一个图中，所有顶点的度数之和等于图的边数的


倍。
2. 在一个有向图中，所有顶点的入数
II.
边数大于顶点个数减
1 III.
至少有一
个顶点的度为 1
I
B.
只有
和 II
和 III
20、假设一个有 n 个顶点和 e 条弧的有向图用邻接表表示 ,则删除与某个顶点 vi
相关的所有弧的时间复杂度是 ( ＣA．O(n) B．O(e)

)
C． O(n+e)

D．O(n*e)
21、无向图

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
22、在有向图 G的拓扑序列中， 若顶点 Vi 在顶点 Vj 之前，则下列情形不可能出
现的是（ D ）。
A． G中有弧 <Vi， Vj>

B ． G中有一条从

Vi

到

Vj

的路径
C．G中没有弧 <Vi,Vj>

D ．G中有一条从

Vj

到

Vi

的路
径
23、下面哪一方法可以判断出一个有向图是否有环（回路）

( B)
A．深度优先遍历 B. 拓扑排序 C. 求最短路径 D. 求关键路径
24、下列关于 AOE网的叙述中，不正确的是（ B ）。
A．关键活动不按期完成就会影响整个工程的完成时间
B．任何一个关键活动提前完成，那么整个工程将会提前完成
C．所有的关键活动提前完成，那么整个工程将会提前完成
D．某些关键活动提前完成，那么整个工程将会提前完成
25、设无向图 G 中有 n 个顶点 e 条边，则其对应的邻接表中的表头结点和表结点的个数分别为（ D ）。
(A) n ， e (B) e ， n (C) 2n ， e (D) n ， 2e
二、填空题
图有 邻接矩阵 、邻接表 、十字链表、邻接多重表等存储结构，其中邻接矩阵 、邻接表既用于存储有向图，也用于存储无向图。
遍历图 深度优先遍历、 广度优先遍历 等方法。
2. 有向图 G 用邻接表矩阵存储，其第 i 行的所有元素之和等于顶点 i 的 出
度 。
拓扑排序算法是通过重复选择具有 0 个前驱顶点的过程来完成的。
4. n 个顶点 e 条边的图，若采用邻接矩阵存储，则空间复杂度为 O(n2) ，若采
用邻接表存储，则空间复杂度为 O(n+e)。
n 个顶点 e 条边的图采用邻接