首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
(2012年上半年下午试题四)阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】 用两台处理机A和B处理n个作业。设A和B处理第i个作业的时间分别为ai和bi。由于各个作业的特点和机器性能的关系,对某些作业,在
(2012年上半年下午试题四)阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】 用两台处理机A和B处理n个作业。设A和B处理第i个作业的时间分别为ai和bi。由于各个作业的特点和机器性能的关系,对某些作业,在
admin
2018-07-27
38
问题
(2012年上半年下午试题四)阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。
【说明】
用两台处理机A和B处理n个作业。设A和B处理第i个作业的时间分别为a
i
和b
i
。由于各个作业的特点和机器性能的关系,对某些作业,在A上处理时间长,而对某些作业,在B上处理时间长。一台处理机在某个时刻只能处理一个作业,而且作业处理是不可中断的,每个作业只能被处理一次。现要找出一个最优调度方案,使得n个作业被这两台处理机处理完毕的时间(所有作业被处理的时间之和)最少。
算法步骤:
(1)确定候选解上界为R短的单台处理机处理所有作业的完成时间m,有
(2)用p(x,y,k)=1表示前k个作业可以在A用时不超过x且在B用时不超过y时间内处理完成,则p(x,y,k)=p(x-ak,y,k-1)||p(x,y-bk,k-1)(||表示逻辑或操作)。
(3)得到最短处理时间为min(max(x,y))。
【C代码】
下面是该算法的C语言实现。
(1)常量和变量说明
n:作业数
m:候选解上界
a:数组,长度为n,记录n个作业在A上的处理时间,下标从0开始
b:数组,长度为n,记录n个作业在B上的处理时间,下标从0开始
k:循环变量
p:三维数组,长度为(m+1)×(m+1)×(n+1)
temp:临时变量
max:最短处理时间
(2)C代码
#include<stdio.h>
int n,m;
int a[60],b[60],p[100][100][60];
void read(){/*输入n、a、b,求出m,代码略*/}
void schedule(){/*求解过程*/
int x,y,k;
for(x=0;x<=m;x++){
for(y=0;y<m;y++){
_____(1)
for(k=1;k<n;k++)
p[x][y][k]=0;
}
}
for(k=1;k<n;k++){
for(x=0;x<=m;x++){
for(y=0;y<=m;y++){
if(x-a[k-1]>=0)______(2);
if(______(3))p[x][y][k]=(p[x][y][k]||p[x][y-b[k-1]][k-1]);
}
}
}
}
void write(){/*确定最优解并输出*/
int X,Y,temp,max=m;
for(x=0;x<=m;x++){
for(y=0;y<=m;y++){
if(_____(4)){
temp=______(5);
if(temp
}
}
}
printf(’’\n%d\n’’,max);
}
void main(){read();schedule();write();}
根据以上说明和C代码,填充C代码中的空(1)~(5)。
选项
答案
(1)p[x][y][0]=1 (2)p[x][y][k]=p[x-a[k-1]][y][k-1] (3)y-b[k-1]>=0 (4)p[x][y][n]==1或p[x][y][n]或p[x][y][n]!=0 (5)(x>=y)?x:y
解析
从schedule()函数的第一个程序段可以看出,该段程序主要进行初始化第一个作业,下标以0开始,即空(1)处应填入p[x][y][0]=1,内层循环里的p[x][y][k]=0用于初始化后面的n-1个作业。第二个程序段是对后面的n-1个作业,确定p(x,y,k)的值。x-a[k-1]>=0的判定条件若成立,则表示第k个作业由机器A处理,完成k一1个作业时机器A花费的时间是x-a[k-1],即空(2)处应填入p[x][y][k]=p[x-a[k-1]][y][k-1]。空(3)处要求填入一判定条件,由其后的执行语句可知,第k个作业由机器B处理,因此空(3)处应填入y-b[k-1]>=0。
write()程序段用于确定最优解并输出结果,即得到最短处理时间min(max(x,y))。空(4)处的判定条件是任务n完成,因此应填入p[x][y][n]==1或其等价形式。空(5)处表达max(x,y),应填入(x>=y)?x:y。
转载请注明原文地址:https://kaotiyun.com/show/v7DZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
请说出图9-1的拓扑结构名称与特点。当增加了[问题3]中的设备后(此设备设置正确,且PC3与PC2是连通的,PCI与PC3也是连通的,经测试PCI与PC2物理连接正常),但PCIPing不通PC2。请问是什么原因?
请说出图9-1的拓扑结构名称与特点。PC2、PC4与PCI、PC3、PC5要连网且能相互访问,需要增添什么设备?
阅读以下说明,回答问题1、问题2、问题3和问题4,将解答填入对应栏内。[说明]GPRS作为GSM分组数据的一种业务,很大程度上拓展了GSM无线数据业务空间。下面将结合中国移动近期准备在中国移动网上开展的业务介绍GPRS业务解决方案,主要包括
从图7-1中可以看出采用什么拓扑结构与设计方法?上述拓扑结构的特点是什么?
阅读以下说明,将应填入(n)处的解答填写在对应栏内。【说明】某网络结构如图5-7所示,如果Router3与网络4之间的线路突然中断,按照RIP路由协议的实现方法,路
某单位拟建立一个Intranet,建立自己的Web服务器、DNS服务器,E-mail服务器和内部业务服务器,有一批客户机联网,要求这些机器有的可以到Internet上,只允许访问自己的Web服务器。请你做出规划,解决如下问题。
阅读以下关于网络应用系统可靠性分析方面的技术说明,根据要求回答问题1至问题4。【说明】可靠性是一个网络应用系统能正常工作的能力,一般用平均故障间隔时间(MTBF)来度量。某网络应用软件研发公司正在开发一个嵌入式实时应用软件——宽带路由器的NanO
在安装RedhatLinux9.0操作系统的过程中,如果没有选择安装Web服务器,Apache服务器则需要手动安装。现从http://httpd.apache.org网站上免费下载了一个apache-2.2.3RPM格式的软件包,请将以下(1)空缺处
在安装RedhatLinux9.0操作系统的过程中,如果没有选择安装Web服务器,Apache服务器则需要手动安装。现从http://httpd.apache.org网站上免费下载了一个apache-2.2.3RPM格式的软件包,请将以下(1)空缺处
在安装RedhatLinux9.0操作系统的过程中,如果没有选择安装Web服务器,Apache服务器则需要手动安装。现从http://httpd.apache.org网站上免费下载了一个apache-2.2.3RPM格式的软件包,请将以下(1)空缺处
随机试题
婴儿7个月,发热2天,体温39~40℃,稍咳,一般情况佳,除流涕及咽部微充血外,未见其他异常,家长给予口服速效感冒灵。本病的诊断已明确,其病原为下列哪一种
截止阀阀杆转动不灵活是由于阀杆弯曲变形或阀杆、螺纹、螺母有损伤而造成的,其处理的方法是()。
变电站中,500kV并联电抗器额定电流2000A,三相电抗不平衡引起的中性点电流,中性点小电抗的额定电流选择值应大于()。
个人理财规划要解决的首要问题是保障财务安全。( )
目前许多大学生毕业后不是直接参加工作,而是继续读研究生,请你运用人力资本投资的有关理论,完成下列问题:下列属于人力资本投资的涌动的有()。
我国新课改倡导的发展性评价的基本内涵主要有()
简述名誉权与荣誉权的区别。[中山大学2015年研;中南财大2014年研]
二元函数f(x,y)=在点(0,0)处
Humanbeingsareafraidofratsmainlybecause______.Thetextismainlytotellus______.
FewmenhaveinfluencedthedevelopmentofAmericanEnglishtotheextentthatNoahWebsterdid.BorninWestHartford,Connecti
最新回复
(
0
)