软考在线  |  计算机技术与软件专业技术资格(水平)考试   |   [请选择科目]
[ 成为 VIP会员 ]        登录  |  注册      我的  购物车
 
科目切换  联系我们 
    
  |   [请选择科目]

VIP:有效提升20分!  真题  历年真题 (可免费开通)/  百科全书/ 机考模拟平台/  最难真题榜/  自测/  攻打黄金十二宫/  真题检索/  真题下载/  真题词库
知识   必会知识榜/  最难知识榜/  知识点查询/      文档   学习计划/  精华笔记/  试题文档     纸质图书   《百科全书》HOT!!/         /        首页/  2025年上半年专区/  手机版/ 
免费智能真题库 > 历年试卷 > 软件设计师 > 2017年上半年 软件设计师 上午试卷 综合知识
  第18题      
  知识点:   拓扑排序和关键路径
  章/节:   计算机软件知识       

 
某软件项目的活动图如下图所示,其中顶点表示项目里程碑,连接顶点的边表示包含的活动,边上的数字表示活动的持续时间(天),则完成该项目的最早时间为(17)天。活动BD和HK最早可以从第(18)天开始。(活动AB、AE和AC最早从第1天开始)

 
 
  A.  3和10
 
  B.  4和11
 
  C.  3和9
 
  D.  4和10
 
 
 确定 并 查看答案解析     知识点讲解  我要标记      有奖找茬      上一题        下一题 
 

  相关试题:图          更多>  
 
  第59题    2011年下半年  
   41%
无向图中一个顶点的度是指图中与该顶点相邻接的顶点数。若无向图G中的顶点数为n,边数为e,则所有顶点的度数之和为(59)。
  第61题    2020年下半年  
   45%
某有向图如下所示,从顶点v1出发对其进行深度优先遍历,可能能得到的遍历序列是(60); 从顶点v1出发对其进行广度优先遍历,可能..
  第1题    2018年上半年  
   49%
对有n个结点、e条边且采用数组表示法(即邻接矩阵存储)的无向图进行深度优先遍历,时间复杂度为(1)。
   知识点讲解    
   · 拓扑排序和关键路径
 
       拓扑排序和关键路径
               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)。它是指在不推迟整个工程完成日期的前提下,允许该活动最晚开始的时间。
   题号导航      2017年上半年 软件设计师 上午试卷 综合知识   本试卷我的完整做题情况  
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题    在手机中做本题
    在线人数   共计 6808人 在线 
    zzx9920@ya..     754291844@..     405229777@..     junhua_w@s..     huminghu1@..     1546929@qq..
    dingwei619..     329005901@..     zcaiyi@163..     tanting121..     tjj555555@..     wgd1220@ya..
    chj868_szb..     wzq2008@21..     wwtld@qq.c..     390927286@..     xk@cimr.co..     jsgywj.stu..
    fogge520.a..     zhouzhuoli..     p_glasses_..     juhong.sun..     lmkhqgk@ya..     99908265@q..
    ljl7883256..     dx358@163...     binger8203..     pssqgc@163..     dyyangbo@1..     lixiaoting..
    xiadegui82..     tingting08..     wzh8238473..     wolfpeople..     shaoqinliu..     755252398@..
    yudakeji@1..     pamela.081..     zhongqiang..     faxx99@sin..     zgxlym123@..     rsong@inte..

本网站所有产品设计(包括造型,颜色,图案,观感,文字,产品,内容),功能及其展示形式,均已受版权或产权保护。
任何公司及个人不得以任何方式复制部分或全部,违者将依法追究责任,特此声明。
本站部分内容来自互联网或由会员上传,版权归原作者所有。如有问题,请及时联系我们。



京B2-20210865 | 京ICP备2020040059号-5 |京公网安备 11010502032051号 | 营业执照 | Copyright ©2000-2025 All Rights Reserved 软考在线版权所有