1 / 7
文档名称:

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

格式:docx   大小:129KB   页数:7页
下载后只包含 1 个 DOCX 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

文档介绍:第七章 图

一、单选题





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章-图练习题及标准答案.docx

上传人:森林书屋 2022/6/22 文件大小:129 KB

下载得到文件列表

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

相关文档