首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
(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
48
问题
(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代码,算法的时间复杂度为_____(6)(用O符号表示)。
选项
答案
O(m
2
n)
解析
从程序的循环层数即可看出算法的时间复杂度。程序的最高循环层数为3层。最外层循环变量的变化范围是1~n-1,次外层循环变量的变化范围是0~m,内层循环变量的变化范围是0~m,所以时间复杂度为O(m
2
n)。
转载请注明原文地址:https://kaotiyun.com/show/S7DZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
假如有一台PC连接在如图10-1所示的交换机(10/100M自适应的交换机)上,通信正常,但是将100M的网卡连到交换机上时显示红灯,通信不正常,请分析故障原因并给予解决。假如交换机设置了若干个VLAN,在不同VLAN内的机器在同一网段,它们可以通信吗
阅读以下说明然后完成问题1、问题2、问题3、问题4,把答案填入相应的对应栏内。[说明]如图10-1是Cisco1900交换机划分为两个vain拓扑图,把E0/10划分为vlan2,把E0/20划分为vlan3。[*]
请说出图9-1的拓扑结构名称与特点。根据IP地址与子网掩码,请判断它们是否属于同一个网段?如果不是,请说出他们分别属于哪个网段。
阅读以下说明,回答问题1、问题2、问题3、问题4和问题5,将解答填入对应栏内。[说明]某单位要拟建一个小型局域网,其图如9-1所示,PCI、PC3、PC5的IP地址分别为10.191.140.2,10.191.140.3,10.191.1
阅读以下说明,将应填入(n)处的解答填写在对应栏内。【说明】某网络结构如图5-7所示,如果Router3与网络4之间的线路突然中断,按照RIP路由协议的实现方法,路
将图2-2中(1)和(2)空缺名称填写在对应的解答栏内。在本质上,ADSL采用的什么多路复用方式?
阅读以下说明,回答问题1至问题3。【说明】路由器中IP访问控制列表能够帮助控制网上包的传输。
认真阅读下列有关Linux操作系统的Samba配置技术的说明,根据要求回答问题1至问题6。【说明】SMB(ServerMessageBlock,服务消息块)协议主要用于实现Windows和Linux操作系统中计算机之间共享打印机、共享串行接
为了便于用户下载相关资料,特安装一台FTP服务器,其服务器端软件是Serv-U,假如要增加一个名为CIU10009的用户,对应目录为D盘,且要求加密,在图6-4中怎么设置?假如用户人数达到1000,为了保证100个用户同时正常下载,请问在图6-4中怎么
随机试题
道德一般可分为__________、__________、__________三类。
以下关于补偿贸易的说法,错误的有()
《摸鱼儿》上片所描绘的整体景象是
关于阻塞型睡眠呼吸暂停综合征的典型临床特点,正确的是
患者男性48岁,3天前左上前牙持续剧烈跳痛,昨日疼痛缓解,但自下睑至下唇鼻旁颧部肿胀明显,皮肤红、热,此时应诊断为
利用收益还原法评估不动产价格,如果纯收益是折旧前的收益,由于纯收益内含有折旧费,这时的综合还原率要取()与建筑物还原率及建筑物折旧率确定的综合还原率。
Whenitcomestoblackpeopleandslaveryrevolution,weusuallythinkofapresident______andahero______.
近年来,部分城市建立了“婴儿安全岛”,这主要是为了维护儿童()。
阅读材料并结合背景知识回答问题: 材料一 农夫蚤出暮入,耕稼树襼,多聚菽粟,此其分事也。妇人夙兴夜寐,纺绩积饪,多治麻丝葛绪、捆布缪,此其分事也。 一一《墨子》 材料二 春耕,夏耘,秋获,冬藏,伐薪樵,治官府,给徭役,春不得避风尘,夏不得避暑热,
在名为Form1的窗体上建立一个名为Lab1的标签:两个名称分别为Cmd1和Cmd2,标题分别为“显示广和“显示2”的命令按钮。编写适当的事件过程,使程序运行后、若单击“显示广命令按钮,则在标签卜显示字符串Cmd;如果单击“显示2”命令按钮,则在标签上显示
最新回复
(
0
)