软考知识点——Gant图与Pert图、McCabe复杂度计算

目录

一、Gant图与Pert图

1.Gant图与Pert图的概念

2.关键路径、总时差、松弛时间

3.真题

（1）2021下半年软考上午真题18~19

（2）2021上半年软考上午真题17~18

二、McCabe复杂度计算

1.McCabe复杂度计算公式

2.真题

一、Gant图与Pert图

1.Gant图与Pert图的概念

甘特图能够消晰描述每个任务的开始/结束时间及各任务之间的并行性，也可以动态地反映项目的开发进展情况，但难以反映多个任务之间存在的逻辑关系；
PERT利用项目的网络图和各活动所需时间的估计值（通过加权平均得到的）去计算项目总时间，强调任务之间的先后关系，但不能反映任务之间的并行性，以及项目的当前进展情况。

甘特图（Gantt图）不能（ ）。
A.作为项目进度管理的一个工具

B.清晰地描述每个任务的开始和截止时间

C.清晰地获得任务并行进行的信息

D.清晰地获得各任务之间的依赖关系

所属知识点：项目管理>Gant图与Pert图

答案解析：甘特图是一种能清晰描述每个任务的开始和截止时间，能有效获得任务并行进行的信息的项目进度管理工具。

2.关键路径、总时差、松弛时间

PEAT图能清晰描述每个任务从何时开始、到何时结束、各任务之间的依赖关系。
关键路径是图中源点至汇点的最长路径，关键路径的时间称之为项目工期，也表述为项目完成所需的最少时间。
总时差：在不延误总工期的前提下，该活动的机动时间，一般在图中，以最晚结束时间减去最早结束时间求取，或以最晚开始时间减去最早开始时间求取。
松弛时间：不影响完工前提下可能被推迟完成的最大时间。例如，求AB活动的松弛时间，先求AB活动通过的路径（如果有两条不同的路径应该选择最大的一条），用关键路径减去该路径的长度，表示该活动的松弛时间。

3.真题

（1）2021下半年软考上午真题18~19

18、19、下图是一个软件项目的活动图，其中顶点表示项目里程碑，连接顶点的边表示活动，边上的权重表示完成该活动所需要的时间(天)，则活动(1)不在关键路径上。活动BI和EG的松弛时间分别是(2)。

(1)A、BD

B、BI

C、GH

D、KL

(2)A、0和1

B、1和0

C、0和2

D、2和0

所属知识点：项目管理>Gant图与Pert图

答案解析：

考查项目管理计算问题。

对于关键路径有两条分别是：ABDIJKL和AEGHKL两条关键路径，长度为20.

针对第一问，不在关键路径上的活动是BI，其余的BD，GH，KL都在关键路径上。

针对第二问，要求BI和EG的松弛时间，BI活动通过的路径有两条ABIJKL和ABIJL，其中两条路径的长度都为19，（如果有两条不同的路径应该选择最大的一条），用关键路径减去该路径ABIJL的长度20-19=1，表示该活动的松弛时间。

活动EG位于该关键路径AEGHKL上，没办法延误，即松弛时间为0。

（2）2021上半年软考上午真题17~18

17、18、下面是一个软件项目活动图，其中顶点表示项目里程碑，连接顶点的边表示包含的活动，边上的权重表示活动的持续时间（天），则关键路径长度为（17），在该活动图中，活动（18）晚 16 天开始不会影响上班。

（1）A、20

B、25

C、27

D、48

（2）A、AC

B、BE

C、FI

D、HJ

所属知识点：项目管理>Gant图与Pert图

答案解析：

本题是对进度网络图分析的考查。

将各个活动的最早开始和完成时间、最晚开始和完成时间、持续时间和总时差分别进行标注，结果如下：

其中最长路径为A-D-F-J,即为关键路径，其时间为完成整个项目的最短时间，也就是项目工期，结果为48天，选择D选项。

第二空关于总时差的分析：

A选项AC的总时差是8天，超过8天延误会推迟工期；

B选项BE的总时差是21天，延误16天并没有超过21天，不会影响最终工期，本题选择B选项。C选项F的总时差为14天，超过14天延误会推迟工期；D选项HJ是关键路径活动，总时差为0，不能有任何延误。
第二空的图有点乱，不用看上面的图也能算出来，看以下第二空的简洁解释：

第二空就是求松弛时间，例如，求AB活动的松弛时间，先求AB活动通过的路径（如果有两条不同的路径应该选择最大的一条），用关键路径减去该路径的长度，表示该活动的松弛时间。

关键路径是ADFHJ，长度是48。

A选项的AC活动，该活动通过的路径最长的是ACFHJ，长度是6+4+20+10=40，48-40=8<16，不符合要求。

B选项的BE活动，该活动通过的路径最长的是ABEGJ，长度是3+15+2+7=27，48-27=21>16，符合要求，选B。

C选项的FI活动，该活动通过的路径最长的是ADFIJ，长度是10+8+4+12=34，48-34=14<16，不符合要求。

D选项的HJ活动，该活动在关键路径ADFHJ上，总时差为0，0<16不符合要求。

二、McCabe复杂度计算

1.McCabe复杂度计算公式

McCabe复杂度计算公式：V(G) = m-n+2，其中m是有向弧的条数，n是结点数。
对于伪代码可以先转换为程序流程图，对程序流程图可以最终转换为结点图处理，转换时注意将交点的地方标注为新的结点，以最终的结点图带入公式结算其McCabe复杂度。

2.真题

2021下半年软考上午真题34~35

34、35、如下所示代码(用缩进表示程序块)，要实现语句覆盖，至少需要(1)个测试用例。采用McCabe度量法计算该代码对应的程序流程图的环路复杂性为(2)。

input A,n for i=2 to n key=A[i] j=i-1 while j>0 and A[j]>key A[j+1]=A[j] j=j-1 A[j+1]=key

(1)A、1

B、2

C、3

D、4

(2)A、2

B、1

C、3

D、4

所属知识点：软件工程>McCabe复杂度计算

答案解析：

本题考查环路复杂度和Mccabe度量计算的结合考查。

针对于伪代码而言，我们具体能够根据其关系判断，做得应该是将一组数据，按照从小到大的顺序进行排序的过程，实质是属于插入排序的算法。

首先对于第一个问题，要实现语句覆盖，至少需要多少个测试用例，我们只需要一组数据就能够得到不断重复排序后的输出结果。

对于第二个问题，计算环路复杂度，我们需要做个相关简图，如下图所示，可以根据环路公式V（G）=m-n+2也可以直接数闭环+1，得出其结果为3

今天的文章
软考知识点——Gant图与Pert图、McCabe复杂度计算分享到此就结束了，感谢您的阅读。