首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
(2013年上半年下午试题四)阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】 设有m台完全相同的机器运行n个独立的任务,运行任务i所需要的时间为tI,要求确定一个调度方案,使得完成所有任务所需要的时间最短。
(2013年上半年下午试题四)阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】 设有m台完全相同的机器运行n个独立的任务,运行任务i所需要的时间为tI,要求确定一个调度方案,使得完成所有任务所需要的时间最短。
admin
2018-07-27
52
问题
(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代码,填充C代码中的空(1)~(4)。
选项
答案
(1)d[i]=d[i]+t[i](2)i=m(k)s[k][0]=i(4)max<d[i]
解析
本题考查算法的设计和分析技术中的贪心算法。
贪心算法是一种不追求最优解,只希望得到较为满意解的方法。贪心算法一般可以快速得到满意的解,因为它省去了为找到最优解要穷尽所有可能而必须耗费的大量时间。贪心算法常以当前情况为基础做出最优选择,而不考虑各种可能的整体情况,所以贪心算法不要回溯。
根据上述思想和题中的说明,首先将s[][]和d[]数组初始化为0,然后将前m个运行时间最长的任务分给m个机器,空(1)处需要表示此时每个机器运行的时间,即当前已经运行的时间加上此时所运行任务的时间,可以推断空(1)处应填入d
=d
+t
。此后需将剩下的n-m个任务按顺序分配给空闲的机器,故空(2)处将i初始化为以m为起始的仟务,即应填入i=m。空(3)处根据空闲的机器分配任务,所以需记录第k个空闲机器所运行任务的编号,即应填入s[k][0]=i。空(4)处已经完成了任务的运行,此处需要统计所有机器所运行任务的最长时间,机器i的运行时间为d
,若有d
大于当前的最大时间max,就将当前机器的运行时间d
赋给max,即应填入max<d
。
转载请注明原文地址:https://kaotiyun.com/show/a7DZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
阅读以下说明,回答问题1、问题2、问题3、问题4和问题5,将解答填入对应栏内。[说明]无源光网络(PON),是指在OLT(光线路终端)和ONU(光网络单元)之间的光分配网络(ODN)没有任何有源电子设备。PON(无源光网络)技术是一种一点对
阅读以下说明,将应填入(n)处的解答填写在对应栏内。【说明】某网络结构如图5-7所示,如果Router3与网络4之间的线路突然中断,按照RIP路由协议的实现方法,路
请指出现有虚拟局域网络的4种划分方式。在基于端口的VLAN划分中,交换机上的每一个端口允许以哪3种模式划入VLAN中,并简述它们的含义。
目前,通过移动电话接入互联网所采用的主要技术是什么?公司网络中的设备或系统(包括存储商业机密的数据库服务器、邮件服务器,存储资源代码的PC、应用网关、存储私人信息的PC、电子商务系统)中,哪些应放在DMZ中,哪些应放在内网中?并请给予简要说明。
阅读以下说明,回答问题1至问题3。【说明】路由器中IP访问控制列表能够帮助控制网上包的传输。
阅读以下关于RIP动态路由配置的技术说明,结合网络拓扑图回答问题1至问题3。[说明]某大学城局域网的网络拓扑结构如图7-18所示,图中路由器R1、R2,R3均运行基于距离矢量算法的RIP路由协议,并且图中给出了路由器R1、R2、R3各端口的IP地
请用蒙特卡罗错误随机植入模型估算出被测程序模块中将会遗留下多少个未被发现的隐藏错误。请简要列出计算式子及计算过程。信息部门的吴总工程师向谢工程师建议了另一种测试方案作为“错误随机植入”测试方法的补充。即由A和B两组测试人员同时相互独立地测试同一份宽带路
由于面向3G移动电话的电子商务网站看不到用户进行销售服务,因此,对用户身份进行认证是必要。通常,在Internet中进行电子签名的认证过程如下:①文件的发送者将要发送的文件生成(1);②用发送者的(2)对摘要加密后,将其添加到文件中;
在安装RedhatLinux9.0操作系统的过程中,如果没有选择安装Web服务器,Apache服务器则需要手动安装。现从http://httpd.apache.org网站上免费下载了一个apache-2.2.3RPM格式的软件包,请将以下(1)空缺处
随机试题
患者男性,30岁,有明显的尿频、尿急和尿痛症状,用复方新诺明数日无效。现做尿液检验结果为:Pro+,RBC22~27/HP.WBC11~16/HP。医生又安排做尿液抗酸染色,是因为怀疑患者为
泡沫灭火系统主要由()组成。
根据《中华人民共和国证券投资基金法》规定,基金份额持有人享有的权利包括()。Ⅰ.分享基金财产收益Ⅱ.参与分配清算后的剩余基金财产Ⅲ.按照规定要求召开基金份额持有人大会Ⅳ.依法转让或者申请赎回其持有的基金份额
某农机厂2009年2月发生下列业务:(1)购入农机专用零件一批,取得防伪税控增值税专用发票,注明不含税价款100000元;(2)向小规模纳税人购入电吹风200个,取得税务机关代开的增值税发票一张,注明价款4000元,增值税240元;(3)
甲公司2007年12月31日的股本为10000000股,面值为1元,资本公积(股本溢价)30000000元,盈余公积50000000元。经股东大会批准,A公司以现金回购本公司股票5000000股并拄销。假定A公司按每股9元回购股票,不考虑其他因素,则应冲
在胜任特征冰山模型中,自我评估和自我教育属于()
集中裁决方式包括()。
根据现行宪法,下列国家领导人中连续任职不得超过两届的有()。(2012年多选57)
Arabsconsiderit【B1】______extremelybadmannertostarttalking【B2】______businessimmediately.Eventhebusiestgovernmentof
A、Itdoesn’thaveanycooperationwithothercompanies.B、Ithaslimitedkindsofsoftwareproducts.C、Theafter-salesteamisn’
最新回复
(
0
)