首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
(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
75
问题
(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
软件设计师下午应用技术考试
软考中级
相关试题推荐
假如有一台PC连接在如图10-1所示的交换机(10/100M自适应的交换机)上,通信正常,但是将100M的网卡连到交换机上时显示红灯,通信不正常,请分析故障原因并给予解决。假如交换机设置了若干个VLAN,在不同VLAN内的机器在同一网段,它们可以通信吗
将图2-2中(1)和(2)空缺名称填写在对应的解答栏内。目前在使用ADSL访问Internet时,要不要收取电话费?
阅读以下说明,回答问题1~4。【说明】A公司用一台Web服务器和一台应用服务器来管理销售信息。销售人员在办公室时通过PC机来访问应用服务器,若在公司以外,则通过具有数据显示功能的移动电话或PDA(PersonalDigitalAssi
下面是某路由器的部分配置信息,解释(n)处标有下划线部分的含义。【配置路由器信息】Currentconfiguration:!version11.3noservicepassword
结合图7-18所示的网络拓扑结构图,将以下路由器R1配置信息中(1)~(9)空缺处的内容填写完整,实现路由器R1的正确配置。Router>en(进入特权模式)Router#
阅读以下关于RIP动态路由配置的技术说明,结合网络拓扑图回答问题1至问题3。[说明]某大学城局域网的网络拓扑结构如图7-18所示,图中路由器R1、R2,R3均运行基于距离矢量算法的RIP路由协议,并且图中给出了路由器R1、R2、R3各端口的IP地
由于面向3G移动电话的电子商务网站看不到用户进行销售服务,因此,对用户身份进行认证是必要。通常,在Internet中进行电子签名的认证过程如下:①文件的发送者将要发送的文件生成(1);②用发送者的(2)对摘要加密后,将其添加到文件中;
在安装RedhatLinux9.0操作系统的过程中,如果没有选择安装Web服务器,Apache服务器则需要手动安装。现从http://httpd.apache.org网站上免费下载了一个apache-2.2.3RPM格式的软件包,请将以下(1)空缺处
为了便于用户下载相关资料,特安装一台FTP服务器,其服务器端软件是Serv-U,假如要增加一个名为CIU10009的用户,对应目录为D盘,且要求加密,在图6-4中怎么设置?假如用户人数达到1000,为了保证100个用户同时正常下载,请问在图6-4中怎么
随机试题
内地居民同香港居民、澳门居民、台湾居民、华侨在中国内地自愿离婚的,当事人有下列哪些情形的,婚姻登记机关不予受理?()
错误选项为:C;正确写法为:VESSEL:GLORIAV.123DATEDAPRIL30,2004根据UCP600第20条,当提单上显示从起运港的船只是预期(INTENDED)船时,即使预期船只与实际装运船只一致,提单的装船批注(ONBOARD
对于商用房贷款抵押物,以下说法错误的是()。
以下关于可转换债券的说法中,正确的有()。(2004年)
材料:初二(3)班的汤老师在辅导学生上晚自习时因私事偷偷外出,快放学的时候才回来。他回来时发现小李正在偷偷写情书,为了让其他同学引以为戒,汤老师将小李的情书在班上念了出来,引得全班哄堂大笑。小李觉得没面子,请假回家休息了。班上的小敏喜欢
某次考试有一道多项选择题,共有A、B、C三个选项。参加考试的人中,共有20人选了A,15人选了B,10人选了C。其中选了两个选项的有5人,选了三个选项的有3人,还有2人未答此题。问有多少人参加考试?
马斯洛的需要层次理论中的最高层次是()。
Ayoungmangoingtojointhearmy(军队)andhadto【C1】________amedicalexamination.Thedoctorwassittingatadeskwhenhec
Whatrecommendationsdoesthetutormakeaboutthereferencebooks?AAllBResearchmethodCMainBodyDConclusionE
Tobereallyhappyandreallysafe,oneoughttohaveatleasttwoorthreehobbies,andtheymustallbereal.Itdoesn’tmatte
最新回复
(
0
)