首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知有6个顶点(项点编号为0~5)的有向带权图G,其邻接矩阵A为上三角矩阵,按行为主序(行优先)保存在如下的一维数组中。 要求: 求图G的关键路径,并计算该关键路径的长度。
已知有6个顶点(项点编号为0~5)的有向带权图G,其邻接矩阵A为上三角矩阵,按行为主序(行优先)保存在如下的一维数组中。 要求: 求图G的关键路径,并计算该关键路径的长度。
admin
2015-12-30
50
问题
已知有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
学硕统考专业
相关试题推荐
关于大陆人民大规模达到台湾的第一次明确的记录出现在()。
()自幼随父在西域成长,深悉西域道里、风土和政治情况。他编著的《西域记》一书,是范晔撰《后汉书.西域传》的重要根据。
1946年5月,中共中央发布的实现“耕者有其田”政策的重要文件是()。
西汉初年,西域共有36国,其中以()人口最多。
中国共产党主张和平解决西安事变的主要目的是()。
关于分页系统,回答下列问题:(1)在页表中,哪些数据项是为实现换页而设置的?(2)设某系统为每个作业进程分配3个内存块,某作业进程在运行访问中的轨迹为1,4,3,1,6,8,1,且每一页都是按请求装入的。问:先进先出页面置换算法(FIF
某机字长32位,主存容量32MB,按字节编址;该机的Cache采用4路组相联映射方式,Cache容量为16KB,块长为4个字,试回答下列问题:(1)主存地址位数为多少?(2)画出主存地址格式示意图,注明各字段名称及位数。(3)设该Ca
设某计算机系统有一块CPU、一台输入设备、一台打印机。现有两个进程同时进入就绪状态,且进程A先得到CPU运行,进程B后运行。进程A的运行轨迹为:计算50ms,打印信息100ms,再计算50ms,打印信息100ms,结束。进程B的运行轨迹为:计算50
某一个计算机系统采用虚拟页式存储管理方式,当前在处理机上执行的某一个进程的页表如下所示,所有的数字均为十进制,每一项的起始编号是0,并且所有的地址均按字节计址,每页的大小为1024字节。(1)计算下列逻辑地址转换为物理地址,并说明为什么
已知有6个顶点(顶点编号为0~5)的有向带权图G,其邻接矩阵A为上三角矩阵,按行为主序(行优先)保存在如下的一维数组中。要求:画出有向带权图G。
随机试题
A.体位试验B.CRH兴奋试验C.小剂量地塞米松抑制试验D.大剂量地塞米松抑制试验鉴别单纯性肥胖和柯兴综合征选用
下述哪项体征不是急性化脓性腹膜炎所必需的
能引起心率减慢的降压药是
招标人对已发出的招标文件进行必要的澄清或者修改的时间是()。
五月“江南碧苍苍”,一个画家团来到了“人间天堂”——苏州,作为他们的地陪导游,请你为他们提供一些信息,以便于他们更合理地安排本次旅行,更深刻地感受“东方水城”的无穷魅力。首先,他们想去参观苏州最具有代表性的名园,它是()。
下列关于汉朝刑法适用原则的表述,正确的是()。
Theterm"fallacies"(Paragraph1)mostprobablymeansTheauthorofthetextmakesacomparisonin______.
下列程序的输出结果是______。#include<iostream)usingnamespaceStd;ClassTest{public:Test(){cnt++;}~Test(){cnt--;}s
Largeanimalsthatinhabitthedeserthaveevolvedanumberofadaptationsforreducingtheeffectsofextremeheat.Oneadaptat
Themainideaofthefirsttwoparagraphsisthatmanypeople______.ParagraphⅡ______.
最新回复
(
0
)