下载此文档

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


文档分类:汽车/机械/制造 | 页数:约7页 举报非法文档有奖
1/7
下载提示
  • 1.该资料是网友上传的,本站提供全文预览,预览什么样,下载就什么样。
  • 2.下载该文档所得收入归上传者、原创者。
  • 3.下载的文档,不会出现我们的网址水印。
1/7 下载此文档
文档列表 文档介绍
第七章 图
一、单选题


C )1.
A . 1/2

在一个图中,所有顶点的度数之和等于图的边数的
B.1 C.2 D.4

倍。
2. 在一个有向图中,所有顶点的入数
II.
边数大于顶点个数减
1 III.
至少有一
个顶点的度为 1
A.只有 I
B.
只有 IIC.I
和 II
D.I 和 III
20、假设一个有 n 个顶点和 e 条弧的有向图用邻接表表示 ,则删除与某个顶点 vi
相关的所有弧的时间复杂度是 ( CA.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 条边的图采用邻接

第7章-图练习题及标准答案 来自淘豆网www.taodocs.com转载请标明出处.