免费智能真题库 > 历年试卷 > 软件设计师 > 2013年下半年 软件设计师 上午试卷 综合知识
  第18题      
  知识点:   拓扑排序和关键路径
  章/节:   计算机软件知识       

 
下图是一个软件项目的活动图,其中顶点表示项目里程碑,连接顶点的边表示包含的活动,则里程碑(17)在关键路径上。若在实际项目进展中,活动AD在活动AC开始3天后才开始,而完成活动DG过程中,由于有临时事件发生,实际需要15天才能完成,则完成该项目的最短时间比原计划多了(18)天。
 
 
  A.  8
 
  B.  3
 
  C.  5
 
  D.  6
 
 
 

  相关试题:图          更多>  
 
  第18题    2015年下半年  
   24%
某软件项目的活动图如下图所示,其中顶点表示项目里程碑,连接顶点的边表示活动,边上的数字表示该活动所需的天数,则完成该项目..
  第17题    2015年下半年  
   51%
某软件项目的活动图如下图所示,其中顶点表示项目里程碑,连接顶点的边表示活动,边上的数字表示该活动所需的天数,则完成该项目..
  第16题    2012年下半年  
   29%
某软件项目的活动图如下所示。图中顶点表示项目里程碑,连接顶点的边表示包含的活动,则里程碑(16)在关键路径上,活动FG的松弛时..
   知识点讲解    
   · 拓扑排序和关键路径
 
       拓扑排序和关键路径
               AOV网
               在有向图中,若一顶点表示活动,用有向边表示活动之间的优先关系,则称这样的有向图为以顶点表示活动的网,简称AOV网。
               在AOV网中不应出现有向环。不存在回路的AOV网称为有向无环图或DAG图。检测的方法是对有向图构造其从顶点开始的拓扑有序序列,若图中所有顶点都在它的拓扑有序序列中,则该AOV网中必定不存在环。
               拓扑排序及其算法
               拓扑排序是将AOV网中所有顶点排成一个线性序列,该序列满足:若在AOV网中从顶点vivj有一条路径,则在该线性序列中,顶点vi必然在顶点vj之前。拓扑排序即指对AOV网构造拓扑序列的操作。
               对AOV网进行拓扑排序的方法如下。
               (1)在AOV网中选择一个入度为零的顶点且输出它。
               (2)从网中删除该顶点及与该顶点有关的所有边。
               (3)重复上述两步,直至网中不存在入度为零的顶点为止。
               若在AOV网中考察各顶点的出度,并按下列步骤进行排序,则称为逆拓扑排序。
               (1)在AOV网中选择一个没有后继的顶点且输出它。
               (2)从网中删除该顶点,并删去所有到达该顶点的弧。
               (3)重复上述两步,直至网中不存在出度为零的顶点为止。
               拓扑排序的时间复杂度为O(n+e)。
               AOE网
               若在带权有向图G中以顶点表示事件,以有向边表示活动,边上的权值表示该活动持续的时间,则这种带权有向图称为用边表示活动的网,简称AOE网。
               AOE网中不应存在有向回路。
               关键路径和关键活动
               从源点到汇点的路径中,长度最长的路径称为关键路径。关键路径上的所有活动均是关键活动。如果任何一项关键活动没有按期完成,则会影响整个工程的进度,而提高关键活动的速度可以缩短整个工程的工期。假设在n个顶点的AOE网中,顶点v0表示源点,顶点vn-1表示汇点,则计算关键活动及关键路径时可引入以下术语。
               .顶点事件的最早发生时间ve(j)。它是指从源点v0vj的最长路径长度(时间)。
               .顶点事件的最晚发生时间v1(i)。它是指在不推迟整个工程完成日期的前提下,事件vi所允许的最晚发生时间。
               .活动的最早开始时间e(k)。表示活动ak最早可开工时间。
               .活动的最晚开始时间l(k)。它是指在不推迟整个工程完成日期的前提下,允许该活动最晚开始的时间。
   题号导航      2013年下半年 软件设计师 上午试卷 综合知识   本试卷我的完整做题情况  
1 /
2 /
3 /
4 /
5 /
6 /
7 /
8 /
9 /
10 /
11 /
12 /
13 /
14 /
15 /
 
16 /
17 /
18 /
19 /
20 /
21 /
22 /
23 /
24 /
25 /
26 /
27 /
28 /
29 /
30 /
 
31 /
32 /
33 /
34 /
35 /
36 /
37 /
38 /
39 /
40 /
41 /
42 /
43 /
44 /
45 /
 
46 /
47 /
48 /
49 /
50 /
51 /
52 /
53 /
54 /
55 /
56 /
57 /
58 /
59 /
60 /
 
61 /
62 /
63 /
64 /
65 /
66 /
67 /
68 /
69 /
70 /
71 /
72 /
73 /
74 /
75 /
 
第18题    在手机中做本题