首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知有6个顶点(项点编号为0～5)的有向带权图G，其邻接矩阵A为上三角矩阵，按行为主序(行优先)保存在如下的一维数组中。 要求： 求图G的关键路径，并计算该关键路径的长度。
已知有6个顶点(项点编号为0～5)的有向带权图G，其邻接矩阵A为上三角矩阵，按行为主序(行优先)保存在如下的一维数组中。 要求： 求图G的关键路径，并计算该关键路径的长度。
admin
2015-12-30
112
问题
已知有6个顶点(项点编号为0～5)的有向带权图G，其邻接矩阵A为上三角矩阵，按行为主序(行优先)保存在如下的一维数组中。
要求：
求图G的关键路径，并计算该关键路径的长度。
选项
答案
按照算法，先计算各个事件的最早发生时间，计算过程如下： ve(0)=0； ve(1)=ve(0)+a
0→1
=4； ve(2)=max{ve(0))+a
0→1
，ve(1)+a
1→2
}=max(6，4+5)=9； ve(3)=ve(2)+a
2→3
=9+4=13； ve(4)=ve(2)+a
2→4
=9+3=12； ve(5)=max{ve(3)+a
3→5
，ve(4)+a
4→5
}=max(16，15：)=16； 接下来求各个时间的最迟发生时间，计算过程如下： vl(5)=ve(5)=16； vl(4)=vl(5)-a
4→5
=16-3=13； vl(3)=vl(5)-a
3→5
=16-3=13； vl(2)=min{vl(3)-a
2→3
，vl(4)-a
2→4
}=min(9，10)=9； vl(1)=vl(2)-a
1→2
=4； v1(0)=min{vl(2)-a
0→2
，Vl(1)-a
0→1
}=min(3，0)； 即ve()和vl()数组如下表所示： [*] 接下来计算所有活动的最早和最迟发生时间e()和l()： e(a
0→1
)=e(a
0→2
)=ve(0)=0； e(a
1→2
)ve(1)=4； e(a
2→3
)=e(a
2→4
)=ve(2)=9； e(a
3→5
)-ve(3)=13； e(a
4→5
)=ve(4)=12； l(a
4→5
)=vl(5)-a
4→5
=16-3=13； l(a
3→5
)=vl(5)-a
3→5
=16-3=13； l(a
2→4
)=vl(4)a
2→4
=13-3=10； l(a
2→3
)-vl(3)-a=
2→3
13-4=9； l(a
1→2
)=vl(2)-a
1→2
=9-5=4： l(a
0→2
)=vl(2)-a
0→2
=9-6=3； l(a
0→1
)=vl(1)-a
0→1
=4-4=0； e()和l()数组与它们的差值如下表所示： [*] 满足l()-e()=0的路径就是关键路径，所以关键路径为a
0-＞1
、a
1-＞2
、a
2-＞3
、a
3-＞5
，如下图所示(粗线表示)。 [*]
解析
转载请注明原文地址:https://kaotiyun.com/show/EBRi777K
本试题收录于：
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
广西壮族自治区的设立时间是()。
简述从欧共体成立到20世纪七八十年代．西欧同美国的关系。
《四库全书》编成后，纪昀等又写成()200卷，把每本书的渊源、版本、内容都作了提纲性的介绍，是一部重要的目录学著作。
战时共产主义政策中对后来的工农联盟最能构成威胁的是()。
下列几种排序方法中，要求内存量最大的是()。
某微机的寻址范围为64KB，其存储器选择器信号为M，接有8片8KB的存储器，试完成下列问题。(1)画出选片译码逻辑图。(2)写出每片RAM的寻址范围。(3)如果运行时发现不论往哪片存储器存放8KB数据，以4000H起始地址的存
大部分文件系统以硬盘作为文件存储器。某一个文件系统中，其磁盘物理块的大小为512B，有一个文件，包含了590个逻辑记录，每个记录占255B；其中，为检索方便，采用成组法存储，在每个物理块上只存放2个记录。，文件A在该文件目录中的位置如下图所示。
假定一台计算机的显示存储器用DRAM芯片实现，若要求显示分辨率为1600×1200，颜色深度为24位，帧频为85Hz，显存总带宽的50％用来刷新屏幕，则需要的显存总带宽至少约为____。
已知有6个顶点(顶点编号为0～5)的有向带权图G，其邻接矩阵A为上三角矩阵，按行为主序(行优先)保存在如下的一维数组中。要求：求图G的关键路径，并计算该关键路径的长度。
某数码相机内置128MB的存储空间，拍摄分辨率设定为1600×1200像素，颜色深度为24位，若不采用压缩存储技术，使用内部存储器最多可以存储的照片数是()。
随机试题
根据五行规律，脾病及肝属于
可同时了解肾积水患者的肾功能及梗阻程度检查
肝肿瘤中“牛眼”征一般多见于
创伤一期愈合的临床特点是()
对慢性疾病进行现状调查，最适宜计算的指标为
关于喇叭形态的特征，下列说法不正确的是( )。
从贷款发放或其他信贷业务发生之日起到贷款本息收回或信用结束之时止信贷管理行为的总称是()。
在北京天安门广场，每天升国旗的时刻与太阳升起的时刻相同。下列节日中，国旗升起时刻最早的是()。
150，75，50，37．5，30，()。
Themajorityofsmalltoothwhalesarecalleddolphins.Mostdolphinspeciesareabout6ftinlength,themalesaveraging4to
最新回复
(
0
)
