首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和C代码,回答以下问题,将解答写在答题纸的对应栏内。 【说明】 设有m台完全相同的机器运行n个独立的任务,运行任务i所需要的时间为ti,要求确定一个调度方案,是的完成所有任务所需要的时间最短。 假设任务已经按照其运行时间
阅读下列说明和C代码,回答以下问题,将解答写在答题纸的对应栏内。 【说明】 设有m台完全相同的机器运行n个独立的任务,运行任务i所需要的时间为ti,要求确定一个调度方案,是的完成所有任务所需要的时间最短。 假设任务已经按照其运行时间
admin
2013-07-09
53
问题
阅读下列说明和C代码,回答以下问题,将解答写在答题纸的对应栏内。
【说明】
设有m台完全相同的机器运行n个独立的任务,运行任务i所需要的时间为t
i
,要求确定一个调度方案,是的完成所有任务所需要的时间最短。
假设任务已经按照其运行时间从大到小排序,算法基于最长运行时间作业优先的策略;按顺序先把每个任务分配到一台机器上,然后将剩余的任务一次放入最先空闲的机器。
【C代码】
下面是算法的C语言实现。
(1)常量和变量说明
m:机器数。
n:任务数。
t[]:输入数组,长度为n,其中每个元素表示任务的运行时间,下标从0开始。
s[][]:二维数组,长度为m*n,下标从0开始,其中元素s
[j]表示机器i运行的任务j的编号。
d[]:数组,长度为m其中元素d
表示机器i的运行时间,下标从0开始。
count[]:数组,长度为m,下标从0开始,其中元素count
表示机器i运行的任务数。
i:循环变量。
j:循环变量。
k:临时变量。
max:完成所有任务的时间。
min:临时变量。
(2)函数schedule
void schedule(){
int i,j,k max=0;
for(i=0;i<m;i++){
d
=0;
for(j=0;j<n;j++){
s
[j]=0;
}
}
for(i=0;i<m;i++){ //分配前m个任务
s
[0]=i;
(1)
;
count
=1;
}
for(
(2)
;i<n;i++)( //分配后n-m个任务
int min=d[0];
k=0:
for(j=1;j<m;j++){ //确定空闲机器
if(min>d[j]){
min=d[j];
k=j; //机器k空闲
}
}
(3)
;
count[k]=count[k]+1;
d[k]=d[k]+t
;
for(i=0;i<m;i++){ //确定完成所有任务所需要的时间
if(
(4)
){
max=d
;
}
}
}
}
根据说明和C代码,该问题采用了
(5)
算法设计策略,时间复杂度为
(6)
(用O符号表示)
选项
答案
(5)贪心 (6)O(2m*n+2m)
解析
根据以上分析,(5)处采用了贪心算法的策略,而时间复杂度由算法中的两个嵌套for循环和两个非嵌套for循环确定,即为O(2m*n+2m),
转载请注明原文地址:https://kaotiyun.com/show/ziDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
运行Web浏览器的计算机与网页所在的计算机要建立(66)连接,采用(67)协议传输网页文件。
确定测试基线属于()活动。
下图是责任链设计模式的类图,该设计模式的目的是________。该图中,Handler和Handler之间是关联关系,Handler和ConcreteHandler之间是继承关系。
在C程序中,设有“inta=3,b=2,c=1;”,则表达式a>b>c的值是_________。
通常VLAN有静态和动态2种实现方式,这2种方式分别是如何实现的?各有什么特点?Switch1采用的是哪种实现方式?填充VLAN信息表如表9-3所示,将答案填写在答题纸相应位置。
阅读以下说明,回答问题1和问题2。说明二层隧道协议L2TP(Layer2TunnelingProtocol)是一种基于点对点协议PPP的二层隧道协议。某网络结构如图5-1所示,采用L2TP来实现网络安全。
将图2-1中(1)和(2)空缺名称填写在应的位置。使ADSL的传输速率更高有哪两个主要因素?
SSL协议使用(1)密钥体制进行密钥协商。在IIS5.0中,Web服务器管理员必须首先安装Web站点数字证书,然后Web服务器才能支持SSL会话,数字证书的格式遵循ITU-T(2)标准。通常情况下,数字证书需要由(3)颁发。如果Web服务器管理员准备预
根据图3-1所给出的网络连接方式及相关的网络参数,区域(A)与区域(B)中计算机的网络参数配置(如图3-2所示)为:区域(A)计算机“IP地址”(范围):(1):区域(A)计算机“子网掩码”;(2);区域(A)计算机“默认网关”:(
IIS安装的硬盘分区最好选用NTFS格式,是因为(1)和(2)。A.可以针对某个文件或文件夹给不同的用户分配不同的权限B.可以防止网页中的Applet程序访问硬盘中的文件C.可以使用系统自带的文件加密系统对文件或文件夹进行加密
随机试题
已知α1=(1,1,2,2,1),α2=(0,2,1,5,一1),α3=(2,0,3,一1,3),α4=(1,1,0,4,一1),则秩(α1T,α2T,α3T,α4T)=________.
PlayingorganizedsportsissuchacommonexperienceintheUnitedStatesthatmanychildrenandteenagerstakethemforgranted
患者女性,42岁,左侧面颊发作性电击样疼痛2年,每次10~20s,打呵欠时可以诱发,查体无阳性体征。首选哪种药物治疗
医师中止执业活动二年以上,当其中止的情形消失后,需要恢复执业活动的,应当经所在地县级以上卫生行政部门委托的机构或组织考核合格,并依法申请办理
属于阴的事物或现象是()
患者,女,39岁。口舌生疮,心烦失眠,小便黄赤,尿道灼热涩痛,口渴,舌红无苔,脉数。其病位在
(2010年)根据《中华人民共和国行政许可法》的规定,下列可以不设行政许可事项的是()。
2009年3月18日,最高人民检察院检察长曹建明指出,针对国家安全面临的新形势,全国检察机关认真贯彻宽严相济的刑事政策,依法履行职责,有力地维护了国家安全。人民检察院行使检察权时必须遵循的原则是()。①依法治国原则②对人民负责原则③民主集中制原则④
在数据库管理系统中,为保证并发事务的正确执行,需采用一定的并发控制技术。下列关于基于锁的并发控制技术的说法,错误的是()。
Acrosstherichworld,well-educatedpeopleincreasinglyworklongerthantheless-skilled.Some65%ofAmericanmenaged62-7
最新回复
(
0
)