首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
(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
31
问题
(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
软件设计师下午应用技术考试
软考中级
相关试题推荐
请问无线局域网的工作模式有哪几种?当不使用AP时,必须把一组需要互相通信的无线网卡的什么值设为相同?
阅读以下说明,回答问题1、问题2、问题3和问题4,将解答填入对应栏内。[说明]现在,家居装修布线是一个大且细致的工程项目,除了要布设普通电源线、有线电视电缆和电话线、音响线、视频线等,越来越多的电脑爱好者家中的网络布线则是少不了的。如果不是
请指出现有虚拟局域网络的4种划分方式。在基于端口的VLAN划分中,交换机上的每一个端口允许以哪3种模式划入VLAN中,并简述它们的含义。
该企业网络的核心层采用了ATM技术,由3台ATM交换机互联构成。试对ATM网络技术的主要特点、协议分层结构和优点作简要叙述。(控制在100个字以内)图中用了两台路由器Router1,和Router2,简述路由器的技术特点,并说明Router1和Rout
将图2-2中(1)和(2)空缺名称填写在对应的解答栏内。ADSL有哪两种IP地址的分配方式?
阅读以下说明,回答问题1~4。【说明】A公司用一台Web服务器和一台应用服务器来管理销售信息。销售人员在办公室时通过PC机来访问应用服务器,若在公司以外,则通过具有数据显示功能的移动电话或PDA(PersonalDigitalAssi
结合图7-18所示的网络拓扑结构图,将以下路由器R1配置信息中(1)~(9)空缺处的内容填写完整,实现路由器R1的正确配置。Router>en(进入特权模式)Router#
阅读以下关于RIP动态路由配置的技术说明,结合网络拓扑图回答问题1至问题3。[说明]某大学城局域网的网络拓扑结构如图7-18所示,图中路由器R1、R2,R3均运行基于距离矢量算法的RIP路由协议,并且图中给出了路由器R1、R2、R3各端口的IP地
阅读以下关于FTTC宽带接入Internet的技术说明,根据要求回答问题1至问题5。【说明】光纤接入网(OpticalAccessNetwork,OAN)是以光纤为传输媒体,并利用光波作为光载波传送信号的接入网。FTTC+LAN是实现居民宽带
随机试题
分配定律不适用于溶质在水相和有机相中有多种存在形式,或在萃取过程中发生离解、缔合等反应的情况。()
一个充分条件假言判断“p→q”是假的,当且仅当_______。
A.肾上腺皮质腺瘤B.Cushing病C.异位ACTH综合征D.单纯性肥胖E.肾上腺皮质癌小剂量地塞米松抑制试验可被抑制
工程监理费是指监理单位在工程建设监理活动中所需要的全部成本,再加上应缴纳的税金和()。
《砌体工程施工质量验收规范》(GB50203—2002)规定,砌砖工程当采用铺浆法砌筑时,施工期间气温超过30℃时,铺浆长度最大不得超过()mm。
下列各项中,关于结转本年利润的方法表述不正确的是()。
邓小平理论中,判断各方面工作是非得失的“三个有利于"标准是指()。
f(x)=cos(ωx一,其中ω>0,则ω=_________.
【2015年山东省属.多选】关于流体智力和晶体智力说法正确的是()。
A、Regulardrivertraining.B、Improvedhighwaydesign.C、Strictertrafficregulations.D、Betterpublictransportation.B
最新回复
(
0
)