首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和C代码,回答以下问题,将解答写在答题纸的对应栏内。 【说明】 设有m台完全相同的机器运行n个独立的任务,运行任务i所需要的时间为ti,要求确定一个调度方案,是的完成所有任务所需要的时间最短。 假设任务已经按照其运行时间
阅读下列说明和C代码,回答以下问题,将解答写在答题纸的对应栏内。 【说明】 设有m台完全相同的机器运行n个独立的任务,运行任务i所需要的时间为ti,要求确定一个调度方案,是的完成所有任务所需要的时间最短。 假设任务已经按照其运行时间
admin
2013-07-09
28
问题
阅读下列说明和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://jikaoti.com/ti/eji7FFFM
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
下图是①设计模式的类图,该设计模式的目的是②,图中,Abstraction和RefinedAbstraction之间是③关系,Abstraction和Implementor之间是④关系。②处应填入?
已知关系模式:图书(图书编号,图书类型,图书名称,作者,出版社,出版日期,ISBN),图书编号唯一识别一本图书。建立“计算机”类图书的视图Compute-BOOK,并要求进行修改、插入操作时保证该视图只有计算机类的图书。CREATE(1)
反映Web应用客户端交易处理性能的评估指标有(59)。 ①并发用户数 ②交易响应时间 ③交易通过率 ④吞吐量 ⑤点击率
下图是________________设计模式的类图,该设计模式的目的是________________,图中,Decorator和Component之间是________________关系,ConcreteDecorator和Decorator之间是_
确定测试基线属于()活动。
在进行可用性测试时关注的问题应包括()。①安装过程是否困难②错误提示是否明确③GUI接口是否标准④登录是否方便⑤帮助文本是否上下文敏感
给出关系R(A,B,C)和S(A,B,C),R和S的函数依赖集F={A→B,B→C}。若R和S进行自然连接运算,则结果集有3个属性。关系R和S________。
SSL协议使用(1)密钥体制进行密钥协商。在IIS5.0中,Web服务器管理员必须首先安装Web站点数字证书,然后Web服务器才能支持SSL会话,数字证书的格式遵循ITU-T(2)标准。通常情况下,数字证书需要由(3)颁发。如果Web服务器管理员准备预
FTTx+LAN接入方式采用什么拓扑结构?将图中(1)~(3)处空缺的传输介质名称填写到答题纸的相应位置。
启动init进程前,不需要经过______步骤。A.LIIO加载内核B.检测内存C.加载文件系统D.启动网络支持根据上述inittab文件的内容,系统在引导过程结束前,至少还要执行______进程。A.rc.sy
随机试题
二硫腙比色法测定锌含量是在碱性条件下进行的,加入硫代硫酸钠和盐酸羟胺是为了防止铜,汞,铅等其他金属离子的干扰。
为Samba的运行设定配置文件,命令#cd/etc/samba的功能是()
骨与关节结核患者为预防肺部感染采取的护理措施不正确的是
下列关于股票回购对上市公司影响的表述中,正确的有()。
商业银行的资本充足率指标体现其经营的()。
学生害怕在社交场合讲话,担心自己会因发抖、脸红、声音发颤、口吃而暴露自己的焦虑,觉得自己说话不自然,因而不敢抬头,不敢正视对方眼睛。这种心理症状是一种()。
学生主观能动性的最高表现是___________。
最能体现太平天国社会理想和这次农民起义特色的纲领性文件是()
设有一小山,取它的底面所在的平面为xOy坐标面,其底部所占区域为D={(x,y)丨x2+y2-xy≤75},小山的高度函数为h(x,y)=75-x2-y2+xy.现欲利用此小山开展攀岩活动,为此需要在山脚寻找一上山坡度最大的点作为攀登的起点,也就是说,
A、ProfessorPaulsonhasretired.B、Thecoursesmaynotbesogoodnow,C、Thecourseisdefinitelyworthwhile,D、ProfessorPaulso
最新回复
(
0
)