4.4 图的基本应用及其复杂度分析

4.4 图的基本应用及其复杂度分析


4.4 图的基本应用及其复杂度分析
  考试大纲涉及本节的知识点有:最小生成树定义、最短路径、拓扑排序和关键路…

4.4 图的基本应用及其复杂度分析

4.4 图的基本应用及其复杂度分析

  考试大纲涉及本节的知识点有:最小生成树定义、最短路径、拓扑排序和关键路径。

一、选择题

  1.选择题题目部分
  ● 数据结构中的迪杰斯特拉(Dijkstra)方法是用来求 (1)
  (1)A.关键路径 B.最短路径 C.拓扑排序 D.字符串匹配
  ● 关键路径是指AOE网中 (2)
  (2)A.从开始节点到完成节点的最长的路径 B.最长的回路
  C.从开始节点到完成节点的最短的路径 D.最短的回路
  ● 判定一个有向图是否存在回路,除了可以利用拓扑排序的方法外,还可以利用 (3)
  (3)A.求关键路径的方法 B.求最短路径的Dijkstra方法
  C.深度优先遍历算法 D.广度优先遍历算法
  ● 设有向图有n个顶点和e条边,进行拓扑排序时,总的计算时间为 (4)
  (4)A.O(n ) B.O(en) C.O(e ) D.O(n+e)
  ● 以下哪个是有向图图4-10的拓扑排序序列 (5) 。                                                                              
  (5)A.ABCDE B.ACDEB C.ABDCE D.ACBED
  ● 图4-10所示的有向图所有拓扑排序序列有 (6) 个。
    
  (6)A.2 B.4 C.6 D.7 
  ● 下列关于AOE网的叙述中,不正确的是 (7)
  (7)A.关键活动不按期完成就会影响整个工程的完成时间
  B.任何一个关键活动提前完成,那么整个工程将会提前完成
  C.所有的关键活动提前完成,那么整个工程将会提前完成
  D.某些关键活动提前完成,那么整个工程将会提前完成
  ●(a)求从指定源点到其余各顶点的迪杰斯特拉(Dijkstra)最短路径算法中弧上权不能为负的原因是在实际应用中无意义。
  (b)利用Dijkstra求每一对不同顶点之间的最短路径的算法时间是O(n3)(图用邻接矩阵表示)。
  (c)Floyd求每对不同顶点对的算法中允许弧上的权为负,但不能有权和为负的回路。
  上面说法不正确的是 (8)
  (8)A.(a),(b),(C) B.(a) C.(a),(c) D.(b),(c)
   2.选择题练习答案与分析
  题号(1)
  答案 B
  习题分析:
  迪杰斯特拉(Dijkstra)算法是求图中某一顶点到其他各顶点最短路径的算法。
  题号(2)
  答案 A
  习题分析:
  关键路径是指AOE网中从开始点到完成点的最长路径的长度,所谓路径的长度是指该条路径上所有弧的权值之和,而不是路径的数量。
  题号(3)
  答案 C
  习题分析:
  除了拓扑排序可以用来判断有向图是否有回路外,利用图的深度优先遍历方法,也可以判断图中是否有回路。
  题号(4)
  答案 D
  习题分析:
  对于有n个顶点和e条边的有向图而言,若该图无环,根据拓扑排序算法,则每个顶点进一次栈,出一次栈,入度减1的操作在循环语句处要执行e次。因此,总的时间复杂度为O(n+e)。
  题号(5)
  答案 A
  习题分析:
  拓扑排序不改变顶点之间的前后关系,在图4-10中存在以下关系:
  (1)A≤B、C、D、E (2)B≤D、E (3)C≤D、E (4)D≤E
  其中“A≤B”表示A领先于B,即在拓扑排序序列中,A处于B之前。
  选项B中,D≤B、E≤B,不正确;
  选项C中,D≤C,不正确;
  选项D中,E≤D ,不正确。
  因此,答案 为A。
  题号(6)
  答案 A
  习题分析:
  观察图4-10所示有向图,其拓扑排序序列,有如下规定:
  (1)A必须是序列第一个元素;(2)E必须是序列最后一个元素;(3)D必须是序列倒数第二个元素。即序列形如:A??DE,其中?为B或D,所以共两种拓扑排序序列。
  题号(7)
  答案 B
  习题分析:
  对于关键路径,需要牢记以下两点。
  (1)关键路径上所有的活动都是关键活动。因此提前完成非关键活动并不能加快工程的速度。
  (2)网络中的关键路径并不唯一,对于有几条关键路径的网来说,仅仅提高某一条关键路径上关键活动的速度,是不能缩短整个工程工期的,而必须同时提高几条关键路径上关键活动的速度。
  所以,并不是网中任何一个关键活动的提前完成,整个工程都能提前完成。
  题号(8)
  答案 C
  习题分析:
  分别对各个选项做出分析:
  (a)最短路径算法要求网中弧的权值必须为正数,但是在Dijsktra算法中,权值不能为负的,并不是因为在实际应用中无意义,而是算法本身的适应条件不允许权值为负数。所以(a)错误。
  (b)重复利用Dijsktra算法n次即可求得每一对不同顶点间的最短路径,Dijsktra算法的时间复杂度为O(n2),那么对此算法执行n次的时间复杂度为O(n3)。所以(b)正确。
  (c)由对(a)的分析可知,(c)错误。
  3.训练自测表(如表4-7所示)
 

表4-7  应用题练习自测表

题    号

考  查  点

得    分

(1) 迪杰斯特拉算法  
(2) 关键路径的定义  
(3) 拓扑排序、深度优先遍历算法  
(4)~(6) 拓扑排序的应用  
(7) 关键活动的应用  
(8) Dijkstra算法以及Floyd算法  

  4.4 图的基本应用及其复杂度分析

    关于作者: admin

    这里可以再内容模板定义一些文字和说明,也可以调用对应作者的简介!或者做一些网站的描述之类的文字活着HTML!

    为您推荐

    发表评论

    电子邮件地址不会被公开。 必填项已用*标注

    评论列表 人参与

    联系我们

    联系我们

    8888-88888888

    在线咨询: QQ交谈

    邮箱: email@admin.com

    工作时间:周一至周五,9:00-17:30,节假日休息

    关注微信
    微信扫一扫关注我们

    微信扫一扫关注我们

    关注微博
    返回顶部