首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】 设有m台完全相同的机器运行n个独立的任务,运行任务i所需要的时间为ti,要求确定一个调度方案,使的完成所有任务所需要的时间最短。假设任务已经按照其运行时间从大到小排序,算法基
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】 设有m台完全相同的机器运行n个独立的任务,运行任务i所需要的时间为ti,要求确定一个调度方案,使的完成所有任务所需要的时间最短。假设任务已经按照其运行时间从大到小排序,算法基
admin
2014-11-13
42
问题
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。
【说明】
设有m台完全相同的机器运行n个独立的任务,运行任务i所需要的时间为t
i
,要求确定一个调度方案,使的完成所有任务所需要的时间最短。假设任务已经按照其运行时间从大到小排序,算法基于最长运行时间作业优先的策略;按顺序先把每个任务分配到一台机器上,然后将剩余的任务一次放入最先空闲的机器。
【C代码】
下面是算法的C语言实现。
(1)常量和变量说明
m:机器数
n:任务数
t[]:输入数组,长度为n,其中每个元素表示任务的运行时间,下标从0开始
s[][]:二维数组,长度为m*n,下标从oF始,其中元素s
表示机器i运行的任j的编号
d[]:数组,长度为m其中元素d
表示机器i的运行时间,下标从0开始
count[]:数组,长度为m,下标从0开始,其中元素count[i一]表示机器i运行的任务数
i:循环变量
i:循环变量
k:临时变量
max:完成所有任务的时间
min:临时变量
(2)函数schedule
void schedule(){
int i,j,k max=0;
for(i=0;i
d
=0;
for(j=0;j
s
[j]=0;
}
}
for(i:0;i
S
[0]=i;
(1);
count
=1;
for((2) ;i
int min:d[0];
k=0:
for(J=1;J
i f(min>d[j])(
min:d[j];
k=j; //机器k空闲
}
}
(3) ;
count[k]=count[k]+1;
d[k]=d[k]+t
;
for(i=0;i
i f( (4) )(
max:d
;
}
}
}
}
考虑实例m=3(编号0~2),n=7(编号0~6),各任务的运行时间为{16,14,6,5,4,3,2}。则在机器0、1和2上运行的任务分别为(7)、(8)和(9)(给出任务编号)。从任务开始运行到完成所需要的时间为(10)。
选项
答案
(7)0(8)1、5(9)2、3、4、6(10)17
解析
本题考查算法的设计和分析技术中的贪心算法。贪心法是一种不追求最优解,只希望得到较为满意解的方法。贪心法一般可以快速得到满意的解,因为省去了为找到最优解要穷尽所有可能而必须耗费的大量时间。贪心法常以当前情况为基础做出最优选择,而不考虑各种可能的整体情况,所以贪心法不要回溯。问题1:根据上述思想和题中的说明,首先将s[1[]和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
。问题2:根据以上分析,(5)处采用了贪心算法的策略,而时间复杂度由算法中的两个嵌套for循环和两个非嵌套for循环确定,即为O(2m*n+2m),问题3:根据题中算法的思想将前三个任务分给三个机器,再将接下来的任务分给最先空闲的机器,故可知机器O运行任务0,机器1运行任务1、5,机器2运行任务2、3、4、6;且运行的最长时间为17。
转载请注明原文地址:https://kaotiyun.com/show/9pDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
阅读以下说明,回答问题1至问题8。[说明]Linux系统开机引导时首先启动内核,由内核检查和初始化硬件设备,载入设备的驱动程序模块,安装root文件系统,然后内核将启动一个名为init的进程。在init运行完成并启动其他必要的后续进程后,
销售部的网络号是(1),广播地址是(2):技术部的网络号是(3),广播地址是(4);每个子网可用的IP地址有(5)个。在网关计算机/etc/sysconfig/network-scripts/目录中有以下文件,运行某命令可以启动网络,该命令是(9),其
阅读以下关于Linux网关安装和配置过程的说明,回答问题1至问题5。【说明】当局域网中存在大量计算机时,根据业务的不同,可以将网络分成几个相对独立的子网。图12-2是某公司子网划分的示意图,整个网络被均分为销售部和技术部两个子网,子网之间通过一台
请阅读下列SwitchA的配置信息,并在(1)~(5)处解释该语句的作用。Switch>enable(进入特权模式)Switch#configterminal(进入配置模式)Switch(config)#hostnameSwi
DHCP允许服务器向客户端动态分配Ⅲ地址和配置信息。客户端可以从DHCP服务器获得(1)。(1)A.DHCP服务器的地址B.Web服务器的地址C.DNS服务器的地址邮件服务器的网络配置信息如图3-5所示。请在图3-6中为邮件服务器
DHCP允许服务器向客户端动态分配Ⅲ地址和配置信息。客户端可以从DHCP服务器获得(1)。(1)A.DHCP服务器的地址B.Web服务器的地址C.DNS服务器的地址通常采用IP地址与MAC地址绑定的策略为某些设备保留固定的IP地址
从网络拓扑图中可以看出该校园网采用了分层设计结构,回答以下问题:1.交换机按照所处的层次和完成的功能分为三种类型:核心交换机、汇聚交换机和接入交换机。下表是学校采购的三种交换机,请根据交换机的技术指标确定交换机的类型。在答题纸对应的解答栏内
阅读以下说明,回答问题1至问题3。【说明】如图5-1所示,某单位通过2M的DDN专线接入广域网,该单位内网共分为三个子网。服务器放置在子网192.168.5.0/24中,财务部工作站放置在子网192.168.10.0/24,销售部工作站放置在子网
阅读以下说明,回答问题1至问题3。【说明】某校园网物理地点分布如图1-1所示,拓扑结构如图1-2所示:
根据你的网络工程经验,请用250字以内的文字简要描述该21层教学综合大楼网络层次结构设计的要点。(不要求画图)该21层教学综合大楼的部分网络拓扑结构如图1-22所示,其中L3_switch1、L3_switch2为该教学综合大楼的两台核心交换机;Swi
随机试题
女性,30岁,颈前肿块多年,近1个月来,肿块生长迅速,并出现声音嘶哑,颈前可触及2cm×3cm肿块,质地较硬,表面欠光滑。诊断首先考虑
患者,男,30岁,从二楼跌下致前胸外伤。胸壁无伤口,左前胸壁大片淤斑,压痛明显,压之凹陷,有明显捻发音。患者呼吸困难。紫绀。体检:R30次/分,血压78/30mmHg,气管向右侧移位。左肺呼吸音消失,叩诊鼓音。本例患者的最佳急救方案是
中年女性患者,尿频、尿痛、尿急3个月余,伴尿液混浊。一般抗菌药物治疗无效,下一步应先做哪项检查
一肿瘤患者,医生决定对他进行主动免疫治疗,应选下述哪种方法
属于糖皮质激素的平喘药的是()。
下列各项不通过“在建工程—待摊支出”科目核算的是()。
我国国家最高监督权的行使机构是()。
《义务教育英语课程标准》(2011年版)将英语学习策略分为认知策略、调控策略、交际策略及______。
根据学习的定义,属于学习现象的是()。
如果A为“Boolean”型数据,则下列赋值语句正确的是()。
最新回复
(
0
)