首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
(2013年上半年下午试题四)阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】 设有m台完全相同的机器运行n个独立的任务,运行任务i所需要的时间为tI,要求确定一个调度方案,使得完成所有任务所需要的时间最短。
(2013年上半年下午试题四)阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】 设有m台完全相同的机器运行n个独立的任务,运行任务i所需要的时间为tI,要求确定一个调度方案,使得完成所有任务所需要的时间最短。
admin
2018-07-27
22
问题
(2013年上半年下午试题四)阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。
【说明】
设有m台完全相同的机器运行n个独立的任务,运行任务i所需要的时间为t
I
,要求确定一个调度方案,使得完成所有任务所需要的时间最短。
假设任务已经按照其运行时间从大到小排序,算法基于最长运行时间作业优先的策略;按顺序先把每个任务分配到一台机器上,然后将剩余的任务一次放入最先空闲的机器。
【C代码】
下面是算法的C语言实现。
(1)常量和变量说明
m:机器数
n:任务数
t[]:输入数组,长度为n,其中每个元素表示任务的运行时间,下标从0开始
S[][]:二维数组,长度为m~n,下标从0开始,其中元素s
D]表示机器i运行的任务
j的编号
d[]:数组,长度为m,其中元素d
表示机器i的运行时间,下标从0开始
count[]:数组,长度为m,下标从0开始,其中元素count
表示机器i运行的任务数
i:循环变量
j:循环变量
k:临时变量
max:完成所有任务的时间
min:临时变量
(2)函数schedule
void Schedule(){
int i,j,k,max=0;
for(i=0;i<m;i++){
d
=0;
for(j=0;j<n;j++){
s
[j]=0;
}
}
for(i=0;i<m;i++){ //分配前m个任务
s
[0]=i;
______(1)
count
=1;
}
for(______(2);i<n;i++){ //分配后n-m个任务
int min=d[0];
k=0;
for(j=1;j<m;j++){ //确定空闲机器
if(min>d[j]){
min=d[j];
k=j; //机器k空闲
}
}
______(3);
count[k]=count[k]+1;
d[k]=d[k]+t
;
for(i=0;i<m;i++){ //确定完成所有任务所需要的时间
if(____(4){
max=d
;
}
}
}
}
根据说明和C代码,该问题采用了______(5)算法设计策略,时间复杂度为______()(用O符号表示)。
选项
答案
(5)贪心 (6)O(2m×n+2m)
解析
根据以上分析,该问题采用了贪心算法的策略,而时间复杂度由算法中的两个嵌套for循环和两个非嵌套for循环确定,即为O(2m×n+2m)。
转载请注明原文地址:https://kaotiyun.com/show/i7DZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
阅读以下说明,回答问题1、问题2、问题3、问题4和问题5,将解答填入对应栏内。[说明]某单位要拟建一个小型局域网,其图如9-1所示,PCI、PC3、PC5的IP地址分别为10.191.140.2,10.191.140.3,10.191.1
从图7-1中可以看出采用什么拓扑结构与设计方法?为了进一步简化系统,有人建议把“电脑模块”与“电话模块”合成一个模块,其传输介质共用,这可以实现吗?
阅读以下说明,回答问题1和问题2。【说明】二层隧道协议L2TP(Layer2TunnelingProtocol)是一种基于点对点协议PPP的二层隧道协议。某网络结构如图2-7所示,采用L2TP来实现网络安全。
如何根据网络流量选择联网设备,给出所选设备的作用。在我国,目前可供选择大的用户选择的接入方式有哪些,各自的接入速率为多少?
结合图7-18所示的网络拓扑结构图,将以下路由器R1配置信息中(1)~(9)空缺处的内容填写完整,实现路由器R1的正确配置。Router>en(进入特权模式)Router#
请用蒙特卡罗错误随机植入模型估算出被测程序模块中将会遗留下多少个未被发现的隐藏错误。请简要列出计算式子及计算过程。信息部门的吴总工程师向谢工程师建议了另一种测试方案作为“错误随机植入”测试方法的补充。即由A和B两组测试人员同时相互独立地测试同一份宽带路
阅读以下关于FTTC宽带接入Internet的技术说明,根据要求回答问题1至问题5。【说明】光纤接入网(OpticalAccessNetwork,OAN)是以光纤为传输媒体,并利用光波作为光载波传送信号的接入网。FTTC+LAN是实现居民宽带
在安装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)空缺处
为了便于用户下载相关资料,特安装一台FTP服务器,其服务器端软件是Serv-U,假如要增加一个名为CIU10009的用户,对应目录为D盘,且要求加密,在图6-4中怎么设置?假如要封闭某用户的账号,请问在图6-4中怎么设置?
随机试题
在如图所示PLC梯形图中,FX2N系列PLC程序可以实现脉冲输出。()
有关消除半衰期的概念错误的是
某快速干道工程,工程开、竣工时间分别为当年4月1日和9月30日。业主根据该工程的特点及项目构成情况,将工程分为3个标段。其中第3标段造价为4150万元,第3标段中的预制构件由甲方提供(直接委托构件厂生产)。A监理公司承担了第3标段的监理任务,委托监
甲公司2×16年1月1日发行面值总额为10000万元的债券,取得的款项专门用于建造厂房。该债券系分期付息、到期还本债券,期限为4年,票面年利率为10%,实际年利率为8%,每年12月31日支付当年利息。债券发行价格总额为10662.10万元.款项已存入银行。
下列不属于企业财务报表分析主体的是()。
某游客因父亲亡故,需要他立即回国料理后事,他中途退团后未享受的旅游综合服务费,除合同另有规定外,应该()。
公司拖欠员工姜某劳动报酬3万余元,姜某可以向当地劳动争议仲裁委员会申请支付令。()
根据以下资料。回答以下题。2009年1--10月份,城镇固定资产投资150710亿元,同比增长33.1%,比上年同期加快5.9个百分点,比1--9月回落0.2个百分点。其中,国有及国有控股投资654.18亿元,增长39.0%;房地产开发投资28440亿
经济规律是经济现象和经济过程内在的、本质的、必然的联系。经济规律的客观性表现在
A、AbdeslamwasattackingStadedeFrance.B、Abdeslamwasthrowingthreesuicidebombers.C、AbdeslamwasatapetrolstationinB
最新回复
(
0
)