文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 小学教育 > 学科竞赛 > 习题12(图的应用)
侵权投诉

习题12(图的应用)

习题12(图的应用)

一、选择题

1、下面( B )方法可以判断出一个有向图是否有环。

A)深度优先遍历 B)拓扑排序 C)求最短路径 D)求关键路径

2、在图采用邻接表存储时,求最小生成树的 Prim 算法的时间复杂度为( C )

A)O(n) B)O(n+e) C)O(n*n) D)O(n*n*n)

3、在用邻接表表示图时,拓扑排序算法时间复杂度为( B )

A)O(n) B)O(n+e) C)O(n*n) D)O(n*n*n)

4、求解最短路径的Floyd算法的时间复杂度为( D )

A)O(n) B)O(n+e) C)O(n*n) D)O(n*n*n)

5、下面( A )算法适合构造一个稠密图G的最小生成树。

A) Prim算法 B)Kruskal算法 C)Floyd算法 D)Dijkstra算法

6、最小生成树指的是( C )

A)由连通网所得到的边数最少的生成树 B)由连通网所得到的顶点相对较少的生成树

C)连通网中所有生成树中权值之和为最小的树 D)连通网的极小连通子图

7、关键路径是事件结点网络中( A )

A)从源点到汇点的最长路径 B)从源点到汇点的最短路径 C)最长回路 D)最短回路

8、下列关于AOE网的叙述中,不正确的是( B )

A)关键活动不按期完成就会影响整个工程的完成时间

B)任何一个关键活动提前完成,那么整个工程将会提前完成

C)所有的关键活动提前完成,那么整个工程将会提前完成

D)某些关键活动提前完成,那么整个工程将会提前完成

9、求图中一个顶点到其它各个顶点最短路径的算法是( C )

A)Kruskal算法 B)Prim算法 C)Dijkstra算法 D)Floyd算法

10、下面关于求关键路径的说法不正确的是( C )

A)求关键路径是以拓扑排序为基础的

B)事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同

C)事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差

D)关键活动一定位于关键路径上

11、下面叙述中不正确的是( D )

(1) 求源点到其余顶点的Dijkstra最短路径算法中弧上权不能为负的原因是在实际应用中无意义;

(2) 利用Dijkstra求每一对不同顶点之间的最短路径的算法时间是O(n3);(图用邻接矩阵表示)

(3) Floyd求每对不同顶点对的算法中允许弧上的权为负,但不能有权和为负的回路。

A)(1),(2),(3) B)(1) C)(1),(3) D)(2),(3)

12、已知有向图G=(V,E),其中V={V1,V2,V3,V4,V5,V6,V7},

E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>},G的拓扑序列是( A )

A)V1V3V4V6V2V5V7 B)V1V3V2V6V4V5V7 C)V1V3V4V5V2V6V7 D)V1V2V5V3V4V6V7

13、在有向图G的拓扑序列中,若顶点Vi在顶点Vj之前,则下列情形不可能出现的是( D )

A)存在弧<Vi,Vj> B)有一条从Vi到Vj的路径

C)不存在弧<Vi,Vj> D)有一条从Vj到Vi的路径

14、下面关于有向图的运算的叙述中,哪个(些)是正确的( D )

Ⅰ.求有向图结点的拓扑序列,其结果必定是惟一的。

Ⅱ.求两个指定结点间的最短路径,其结果必定是惟一的。

Ⅲ.求事件结点网络的关键路径,其结果必定是惟一的。

A)只有Ⅰ B)Ⅰ和Ⅱ C)都正确 D)都不正确

第1页

你可能喜欢

  • 函数的应用练习题
  • 分数的应用练习题
  • 导数的应用练习题
  • 比例的应用练习题

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email