2019研计算机数据结构复习重点：关键路径

考研网

《数据结构(C语言版)》复习重点在二、三、六、七、九、十章，考试内容两大类：概念，算法，自从计算机专业课统考以后，专业课考试题型分为2类，一类选择题，一类综合应用题。接下来是新东方在线整理的2019考研计算机数据结构复习重点关键路径。
    　　关键路径：路径长度最长的路径。
    1、 如图，先求各事件的最早发生时间(顺序为V1~V9)
   

1604154457675516.png

    V1的最早发生时间为0，V2的最早发生时间为6，V3的最早发生时间为4，V4的最早发生时间为5。对于V5，需要V2，V3均发生，V2发生且完成的时间为6+1=7;V3发生且完成的时间为4+1=5，因而V5的最早发生时间为7。同理可求出各顶点的最早发生时间：
    V1 V2 V3 V4 V5 V6 V7 V8 V9
    e(i) 0 6 4 5 7 7 16 14 18
    2、 求各事件的最晚发生时间(顺序为V9~V1)
    V9的最晚时间为18，V8的最晚时间为18-a11=14，V7的最晚时间为18-a10=16，V6的最晚时间为14-a9=10，V5的最晚时间为V7的最晚时间减去a7和V8的最晚时间减去a8两者较小的，则V5的最晚时间为7，同理可得其他顶点的最晚发生时间：
    V1 V2 V3 V4 V5 V6 V7 V8 V9
    l(i) 0 6 6 8 7 10 16 14 18
    则l与e相等的事件即为关键事件
    即：V1，V2，V5，V7，V8，V9
    可得关键路径：V1，V2，V5，V7，V9或V1，V2，V5，V8，V9
    3、 求各活动的最早发生时间
    a1 a2 a3 a4 a5 a6
    a7 a8 a9 a10 a11
    e(i) 0 0 0 6 4 5
    7 7 7 16 14
    4、 求各活动的最晚发生时间
    a1 a2 a3 a4 a5 a6
    a7 a8 a9 a10 a11
    l(i) 6-6=0 6-4=2 8-5=3 7-1=6 7-1=6 10-2=8
    16-9=7 14-7=7 14-4=10 18-2=16 18-4=14
    则l与e相等的活动即为关键活动
    即：a1，a4，a7，a8，a10，a11
    可得关键路径：V1，V2，V5，V7，V9或V1，V2，V5，V8，V9