首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和C代码,回答以下问题,将解答写在答题纸的对应栏内。 【说明】 设有m台完全相同的机器运行n个独立的任务,运行任务i所需要的时间为ti,要求确定一个调度方案,是的完成所有任务所需要的时间最短。 假设任务已经按照其运行时间
阅读下列说明和C代码,回答以下问题,将解答写在答题纸的对应栏内。 【说明】 设有m台完全相同的机器运行n个独立的任务,运行任务i所需要的时间为ti,要求确定一个调度方案,是的完成所有任务所需要的时间最短。 假设任务已经按照其运行时间
admin
2013-07-09
50
问题
阅读下列说明和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
软件设计师下午应用技术考试
软考中级
相关试题推荐
某系统中,模块A处理与销售相关的所有细节,仅需要发送一个包含销售量、价格和时间的报表到模块B,则这两个模块之间为()耦合。
广义的软件测试由“确认”、“验证”、“测试”三个方面组成,其中“确认”是______。A.想证实在一个给定的外部环境中软件的逻辑正确性,检查软件在最终的运行环境上是否达到预期的目标B.检测软件开发的每个阶段、每个步骤的结果是否正确无误,是否与软件开发各
软件可靠性管理把软件可靠性活动贯穿于软件开发的全过程,成为软件工程管理的一部分。确定软件的可靠性目标在()阶段。
在进行可用性测试时关注的问题应包括()。①安装过程是否困难②错误提示是否明确③GUI接口是否标准④登录是否方便⑤帮助文本是否上下文敏感
在软件评审中,设计质量是指设计的规格说明书符合用户的要求。设计质量的评审内容不包括______。
(60)是功能测试工具。
一个程序的控制流图中有5个结点,8条边,在测试用例数最少的情况,确保程序中每个可执行语句至少执行一次所需要的测试用例数的上限是_______。
数据库是按照一定的数据模型组织、存储和应用的______的集合。
在C程序中,设有“inta=3,b=2,c=1;”,则表达式a>b>c的值是_________。
甲怀疑乙发给他的信息已遭人篡改,同时怀疑乙的公钥也是被人冒充的。为了消除甲的疑虑,甲、乙需要找一个双方都信任的第三方,即______来签发数字证书。
随机试题
下列关于人本治疗模式的自我概念的描述中,错误的是()。
A.外环扩大B.坠入阴囊C.两者均有D.两者均无腹股沟直疝
男性,37岁,腹胀、纳差、乏力3个月,7小时前突然呕吐鲜血约800ml。查体:血压75/50mmHg,脉搏120次/分,巩膜黄染,肝脾肋下未及,腹水征(+)。化验ALB26g/L,TBil22.6μmmol/L,HBsAg(+)。应首选哪种治疗
张亮于2014年3月在本市一火锅城与妻子、九岁儿子一起进餐时,燃气灶突然爆炸,将张亮妻子、九岁儿子烧成三度重伤,导致终身残疾,同时将邻桌的王刚烧伤。事后,张亮找火锅城索赔,火锅城认为是燃气灶本身的缺陷所致,应找商家和厂家赔偿。但张亮到电子商场多次交涉,电子
按发生时间的先后顺序,下列选项中关于教育事件排序正确的是()。
以三刺断庶民狱讼之中。一曰讯群臣,二曰讯群吏,三曰讯万民,听民之所刺宥,以施上服下服之刑。——《周礼.秋官.小司寇》请运用中国法制史的知识和理论,分析上述材料并回答下列问题:上述材料反映了西周时期的何种审判程序?
请在【答题】菜单下选择【进入考生文件夹】命令,并按照题目要求完成下面的操作。注意:以下的文件必须都保存在考生文件夹下。作为中国海军博物馆讲解员的小张,受领了制作“辽宁号航空母舰”、简介演示幻灯片的任务,需要对演示幻灯片内容进行精心设计和
AnswerQuestions71to80byreferringtothefollowingfourarticlesconcerningmentalillness.Answereachquestionbychoosin
Thepassagemainlydiscusses______.Thewriter’smainpurposeofwritingParagraph4is______.
Permanentsecretaryrequiredforestablishedteamworkingonmajornewproject.-Ownoffice-Flexible
最新回复
(
0
)