首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
(2013年上半年下午试题四)阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】 设有m台完全相同的机器运行n个独立的任务,运行任务i所需要的时间为tI,要求确定一个调度方案,使得完成所有任务所需要的时间最短。
(2013年上半年下午试题四)阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】 设有m台完全相同的机器运行n个独立的任务,运行任务i所需要的时间为tI,要求确定一个调度方案,使得完成所有任务所需要的时间最短。
admin
2018-07-27
55
问题
(2013年上半年下午试题四)阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。
【说明】
设有m台完全相同的机器运行n个独立的任务,运行任务i所需要的时间为t
I
,要求确定一个调度方案,使得完成所有任务所需要的时间最短。
假设任务已经按照其运行时间从大到小排序,算法基于最长运行时间作业优先的策略;按顺序先把每个任务分配到一台机器上,然后将剩余的任务一次放入最先空闲的机器。
【C代码】
下面是算法的C语言实现。
(1)常量和变量说明
m:机器数
n:任务数
t[]:输入数组,长度为n,其中每个元素表示任务的运行时间,下标从0开始
S[][]:二维数组,长度为m~n,下标从0开始,其中元素s
D]表示机器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)算法设计策略,时间复杂度为______()(用O符号表示)。
选项
答案
(5)贪心 (6)O(2m×n+2m)
解析
根据以上分析,该问题采用了贪心算法的策略,而时间复杂度由算法中的两个嵌套for循环和两个非嵌套for循环确定,即为O(2m×n+2m)。
转载请注明原文地址:https://www.kaotiyun.com/show/i7DZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
从下列的2道试题(试题5、试题6)中任选1道解答。如果解答的试题数超过1道,则题号小的1道解答有效。请认真阅读下列有关于路由器配置的技术说明,根据要求回答问题1至问题5。【说明】菜地市级水电站网络除了和远程子网172.20.0.0/24
阅读以下说明,回答问题1、问题2、问题3、问题4和问题5,将解答填入对应栏内。[说明]无源光网络(PON),是指在OLT(光线路终端)和ONU(光网络单元)之间的光分配网络(ODN)没有任何有源电子设备。PON(无源光网络)技术是一种一点对
请问无线局域网的工作模式有哪几种?当不使用AP时,必须把一组需要互相通信的无线网卡的什么值设为相同?
阅读以下说明,将应填入(n)处的解答填写在对应栏内。【说明】某网络结构如图5-7所示,如果Router3与网络4之间的线路突然中断,按照RIP路由协议的实现方法,路
将图2-2中(1)和(2)空缺名称填写在对应的解答栏内。ADSL有哪两种IP地址的分配方式?
目前,通过移动电话接入互联网所采用的主要技术是什么?进行一次查询的数据信息见表1-1,网络的基本通信服务费用见表1-2,总费用=网络租用费+通信费。根据表中给出的数据,试计算销售员每月至少应进行多少次查询,才能使得使用移动电话的总费用比使用PDA的总费
如何根据网络流量选择联网设备,给出所选设备的作用。如何规划防火墙,将内部业务服务器和部分PC机与Internet隔离?
由于面向3G移动电话的电子商务网站看不到用户进行销售服务,因此,对用户身份进行认证是必要。通常,在Internet中进行电子签名的认证过程如下:①文件的发送者将要发送的文件生成(1);②用发送者的(2)对摘要加密后,将其添加到文件中;
为了便于用户下载相关资料,特安装一台FTP服务器,其服务器端软件是Serv-U,假如要增加一个名为CIU10009的用户,对应目录为D盘,且要求加密,在图6-4中怎么设置?假如用户人数达到1000,为了保证100个用户同时正常下载,请问在图6-4中怎么
随机试题
属横产式胎位的是
水杨酸治疗风湿时,不合适的是
哮病与喘证的鉴别要点是()
小儿肺炎的主要临床表现为
宪法是国家根本法,具有最高法律效力。下列有关宪法法律效力的哪一项表述是正确的?()
关于化学反应速率常数k的说法正确的是:
有4个建设方案,各方案的年净现金流量见下表,设折现率为12%,请用净现值法比较,()方案为相对最优方案。各方案的年净现金流量(单位:万元)
监理工程师对施工组织设计进行审查,属于目标控制的()措施。
阀体流路简单、阻力小、重量轻,与同口径双座阀相比,流通能力增大20%,重量只有其1/3左右的气动执行器是( )。
为了保证公司网络的安全运行,预防计算机病毒的破坏,可以在计算机上采取的方法是
最新回复
(
0
)