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