首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
(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
73
问题
(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,在同一VLA_N内的机器不在同一网段上,它们可以通信吗
请说出图9-1的拓扑结构名称与特点。PC2、PC4与PCI、PC3、PC5要连网且能相互访问,需要增添什么设备?
阅读以下说明,回答问题1、问题2、问题3、问题4和问题5,将解答填入对应栏内。[说明]无源光网络(PON),是指在OLT(光线路终端)和ONU(光网络单元)之间的光分配网络(ODN)没有任何有源电子设备。PON(无源光网络)技术是一种一点对
请问无线局域网的工作模式有哪几种?平时所用的手机可漫游在不同的基站之间,WLAN工作站也可漫游,请问WLAN的“漫游”含义是什么?
请问无线局域网的工作模式有哪几种?常见的无线网络协议有哪些?
请指出现有虚拟局域网络的4种划分方式。以下为Cisco以太网交换机Catalyst2924(ws-c2924xlA,拥有24个10/100Mbit/s自适应端口)的VLAN划分命令,请解释(1)~(3)处的标有下划线部分配置命令的含义。(“//”后为
目前,通过移动电话接入互联网所采用的主要技术是什么?进行一次查询的数据信息见表1-1,网络的基本通信服务费用见表1-2,总费用=网络租用费+通信费。根据表中给出的数据,试计算销售员每月至少应进行多少次查询,才能使得使用移动电话的总费用比使用PDA的总费
在安装RedhatLinux9.0操作系统的过程中,如果没有选择安装Web服务器,Apache服务器则需要手动安装。现从http://httpd.apache.org网站上免费下载了一个apache-2.2.3RPM格式的软件包,请将以下(1)空缺处
在图8-12所示的拓扑结构中的代理服务器上依次单击“开始→程序→管理工具→路由与远程访问,并在系统弹出的界面中打开“IP路由选择”目录树,然后用鼠标右键单击“NAT/基本防火墙”,选择[新增接口]命令。接着若选择接口1的“本地连接”,最后进行如图8-13所
在图8-12所示的拓扑结构中的代理服务器上依次单击“开始→程序→管理工具→路由与远程访问,并在系统弹出的界面中打开“IP路由选择”目录树,然后用鼠标右键单击“NAT/基本防火墙”,选择[新增接口]命令。接着若选择接口1的“本地连接”,最后进行如图8-13所
随机试题
A、兼有抗麻风病作用B、治疗量可出现神经系统功能障碍C、单用细菌不易对其产生耐药性D、过量可引起造血系统障碍E、大量使用可引起视神经炎关于异烟肼正确的叙述是
一定时期内的储存成本总额,等于该期内______与______的乘积。
剥脱性唇炎多见于
消毒后100ml牛奶中大肠杆菌最近似值不得超过
乌梅的功效是()乌贼骨的功效是()
不宜喷涂的漆料为( )。
下列关于记账方法说法错误的是()。
某小区原来有一片敞开式绿地。绿地上亭栅多姿,花木茂盛,风景优美,小区的许多住户都喜欢傍晚来此散步,然而,其中也有一些不自觉的人,随意在草地上穿行、坐卧、嬉戏,导致绿地局部草皮倒伏,植被破坏,黄土裸露,不得不反复种植,成为小区管理中的一个难题。【问
求曲线y=x4一2x3+1的凹凸区间和拐点.
Windows98 提供了监视系统工作状况的多种系统工具。在下列系统工具中,可以用来查看当前可用内存大小的是( )。
最新回复
(
0
)