习题12(图的应用)

习题 12（图的应用） 一、选择题 1、 下面（ B ） 方法可以判断出一个有向图是否有环。 A）深度优先遍历 B）拓扑排序 C）求最短路径 D）求关键路径 2、 在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为（ C ） A）O(n) B）O(ne) C）O(n*n) D）O(n*n*n) 3、 在用邻接表表示图时，拓扑排序算法时间复杂度为（ B ） A）O(n) B）O(ne) C）O(n*n) D）O(n*n*n) 4、 求解最短路径的 Floyd 算法的时间复杂度为（ D ） A）O(n) B）O(ne) 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=,G 的拓扑序列是（ A ） A）V1V3V4V6V2V5V7 B）V1V3V2V6V4V5V7 C）V1V3V4V5V2V6V7 D）V1V2V5V3V4V6V7 13、 在有向图 G 的拓扑序列中，若顶点 Vi 在顶点 Vj 之前，则下列情形不可能出现的是（ D ） A）存在弧 B）有一条从 Vi 到 Vj 的路径 C）不存在弧 D）有一条从 Vj 到 Vi 的路径 14、 下面关于有向图的运算的叙述中，哪个（些）是正确的（ D ） .求有向图结点的拓扑序列，其结果必定是惟一的。 .求两个指定结点间的最短路径，其结果必定是惟一的。 .求事件结点网络的关键路径，其结果必定是惟一的。 A）只有 B）和 C）都正确 D）都不正确 二、填空题 1、Prim 算法的时间复杂度是（ o(n*n) ），适用于求（ 稠密 ）图的最小生成树；kruskal 算法的时间复杂度是（ O（eloge） ），适用于求（ 稀疏 ）图的最小生成树。 2、实现构造最小生成树的 Prim 算法需附设一个（ 辅 助 数 组 ） ，用来记录（ 从 U 到 v-u 具 体 最 小 代 价 的 边 ） ，在（ 辅 助 数 组 ） 中存在一个分量，它包括（ 2 ） 个域。 3、拓扑排序是从每个集合上的一个（ 偏 序 ） 得到该集合上的一个（ 全 序 ） 。 4、有向图 G 可拓扑排序的判别条件是（ 不 存 在 环 ） 。 5、设有向图有 n 个顶点和 e 条边，进行拓扑排序时，时间复杂度为（ O（ n+e） ） 。 6、已知有向图 G=(V，E)，其中 V=V1，V2，V3，V4， E=，图 G 的拓扑序列是（ V1， V3， V2， V4 ） 。 7、AOE 网为边表示活动的网，是一个带权的（ 有 向 无 环 图 ） ，其长度最长的路径称为（ 关 键 路 径 ） 。 8、在 AOE 网中，从源点到汇点路径上各活动时间总和最长的路径称为（ 关 键 路 径 ） 。 9、AOV 网中,结点表示（ 活 动 ） ,边表示（ 活 动 时 间 的 优 先 关 系 ） 。AOE 网中,结点表示（ 事 件 ） ,边表示（ 活 动 ） 。 10、在 AOV网 中，存在环意味着（ 某 项 活 动 应 以 自 己 为 先 决 条 件 ） ，这是（ 荒 谬 ） 的；对程序 的数据流图来说，它表明存在（ 死 循 环 ） 。 11、求最短路径的 Dijkstra 算法的时间复杂度为（ O(n*n) ） 。 12、Dijkstra 提出的求最短路径方法，引进一个辅助向量 dist，它的每个分量 distI表示当前所找到的 从（ 源 点 ） 到每个（ 终 点 ） 的最短路径的（ 长 度 ） 。 13、求从某源点到其余各顶点的 Dijkstra 算法在图的顶点数为 10，用邻接矩阵表示图时计算时间约为 10ms,则在图的顶点数为 40，计算时间约为（ 160 ） ms。 14、 Dijkstra 最短路径算法从源点到其余各顶点的最短路径的路径长度按（ 严 格 递 增 ） 次序 依次产生，该算法弧上的权出现（ 权 值 为 负 ） 情况时，不能正确产生最短路径。 三、应用题 1、利用 Dijkstra 算法求图 1 中从顶点 a 到其他个顶点间的最短路径，写出执行算法过程中各步的状态。 2、对图 2 所示的 AOE-网，求每个活动的最早开始时间和最迟开始时间，并确定关键活动及整个工程的最 早结束时间。 图 1 图 2 3、按 Kruthkal 算法写出求图 3 最小生成树的过程。按 Prim 算法写出求图 4 最小生成树的过程。 图 3 图 4 4、求出图5中顶点1到其余各顶点的最短路径长度，写出所有拓扑有序序列，并指出应用拓扑排序算法得 到的是哪一个？ 5、求出图 6 所示 AOE 网的关键路径（要求写出各条弧代表的活动的最早、最迟开始时间） 。 图 5 图 6 6、下表给出了某工程各工序之间的优先关系和各工序所需时间。 （1）画出相应的 AOE 网。 （2）列出各事件的最早发生时间，最迟发生时间。 （3）找出关键路径并指明完成该工程所需最短时间。 7、下图是带权的有向图 G 的邻接表表示法，其中出边表中的每个结点均含有三个字段，依次为边的另一 个顶点在顶点表中的序号、边上的权值和指向下一个边结点的指针。求： （1）以 V1 出发深度遍历图所得结点序列； （2）以 V1 出发广度遍历图所得结点序列； （3）从 V1 到 V8 的最短路径； （4）从 V1 到 V8 的关键路径； （7）写出至少 2 个拓扑序列。 四、算法设计题 工序代号 A B C D E F G H I J K L M N 所需时间 15 10 50 8 15 40 300 15 120 60 15 30 20 40 先驱工作 - - A，B B C,D B E G E I F H