首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和C代码,回答以下问题,将解答写在答题纸的对应栏内。 【说明】 设有m台完全相同的机器运行n个独立的任务,运行任务i所需要的时间为ti,要求确定一个调度方案,是的完成所有任务所需要的时间最短。 假设任务已经按照其运行时间
阅读下列说明和C代码,回答以下问题,将解答写在答题纸的对应栏内。 【说明】 设有m台完全相同的机器运行n个独立的任务,运行任务i所需要的时间为ti,要求确定一个调度方案,是的完成所有任务所需要的时间最短。 假设任务已经按照其运行时间
admin
2013-07-09
26
问题
阅读下列说明和C代码,回答以下问题,将解答写在答题纸的对应栏内。
【说明】
设有m台完全相同的机器运行n个独立的任务,运行任务i所需要的时间为t
i
,要求确定一个调度方案,是的完成所有任务所需要的时间最短。
假设任务已经按照其运行时间从大到小排序,算法基于最长运行时间作业优先的策略;按顺序先把每个任务分配到一台机器上,然后将剩余的任务一次放入最先空闲的机器。
【C代码】
下面是算法的C语言实现。
(1)常量和变量说明
m:机器数。
n:任务数。
t[]:输入数组,长度为n,其中每个元素表示任务的运行时间,下标从0开始。
s[][]:二维数组,长度为m*n,下标从0开始,其中元素s
[j]表示机器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)
算法设计策略,时间复杂度为
(6)
(用O符号表示)
选项
答案
(5)贪心 (6)O(2m*n+2m)
解析
根据以上分析,(5)处采用了贪心算法的策略,而时间复杂度由算法中的两个嵌套for循环和两个非嵌套for循环确定,即为O(2m*n+2m),
转载请注明原文地址:https://kaotiyun.com/show/ziDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
下图是①设计模式的类图,该设计模式的目的是②,图中,Abstraction和RefinedAbstraction之间是③关系,Abstraction和Implementor之间是④关系。②处应填入?
缺陷探测率DDP是衡量一个公司测试工作效率的软件质量成本的指标。在某公司开发一个软件产品的过程中,开发人员自行发现并修正的缺陷数量为80个,测试人员A发现的缺陷数量为50个,测试人员B发现的缺陷数为50个,测试人员A和测试人员B发现的缺陷不重复,客户反馈缺
序言性注释是指在每个程序或模块开头的一段说明,起辅助理解程序的作用,一般包括:程序的表示、名称和版本号;程序功能描述;接口与界面描述;输入输出数据说明:开发历史;与运行环境有关的信息等。下列叙述中不属于序言性注释的是(23)。
某银行系统要求报表功能容易扩展,以便在需要的时候可以处理新的文件格式,.则该需求是()的。
下图是________________设计模式的类图,该设计模式的目的是________________,图中,Decorator和Component之间是________________关系,ConcreteDecorator和Decorator之间是_
以下关于建立良好的程序设计风格的叙述中,正确的是()。
软件需求规格说明书的内容不包括_______。
通常VLAN有静态和动态2种实现方式,这2种方式分别是如何实现的?各有什么特点?Switch1采用的是哪种实现方式?填充VLAN信息表如表9-3所示,将答案填写在答题纸相应位置。
阅读下面的说明,回答问题1至问题5。[说明]利用VLAN技术可以把物理上连接的网络从逻辑上划分为多个虚拟子网,可以对各个子网实施不同的管理策略。下图表示两个交换机相连,把6台计算机配置成两个VLAN。
认真阅读下列说明信息,回答问题1至问题5。[说明]在一个基于TCP/IP协议的网络中,每台主机都有一个IP地址,根据获得IP地址的方式不同,可以分为静态IP和动态IP。例如:用宽带入网,会有一个固定的IP地址,每次连入Internet,你的IP地
随机试题
对疑有胆结石所致梗阻性黄疸较深者,应选择哪种检查法较合适
下列有机化合物中极性最强的是()。
社会公德是指人们在社会交往和公共生活中应该遵守的行为准则,是维护公共利益、公共秩序、社会和谐稳定的起码道德要求。社会公德最基本的要求是()
下列关于蜂窝织炎的叙述,正确的是
GU与溃疡型胃癌的X线表现最主要区别是
甲和乙因合同纠纷诉至人民法院,甲不服一审判决提起上诉,二审人民法院的下列哪些做法是错误的?()
E公司的2005年度财务报表主要数据如下(单位:万元): 要求:请分别回答下列问题:(1)计算该公司的可持续增长率;(2)假设该公司2006年度计划销售增长率是5%,公司拟通过提高销售净利率来解决资金不足问题。请计算销售净利率达到多少
对从业人员来说,“尊老爱幼”这一民族传统美德包括()。
劳动合同法规定的用人单位设立的分支机构,依法取得营业执照或者登记证书的,可以作为用人单位与劳动者订立劳动合同;未依法取得营业执照或者登记证书的,受用人单位委托可以与劳动者订立劳动合同。()
适合进行牛市套利的商品是()。
最新回复
(
0
)