>>>>>>>>>> 点击进入2016年软件设计师网络课堂课
  >>>>>>>>>>点击进入软件设计师历年真题题库
>>>>>>>>>>点击进入2016年软件设计师考试指南

2013年上半年软件设计师考试真题

下午卷

试题四

设有m台完全相同的机器运行n个独立的任务，运行任务i所需要的时间为ti，要求确定一个调度方案是的完成所有任务所需要的时间最短。

假设任务已经按照其运行时间从大到小排序，算法基于最长运行时间作业优先的策略；按顺序先把每个1务分配到一台机器上，然后将剩余的任务一次放入最先空闲的机器。

  [C代码]

下面是算法的C语言实现。

  10、常量和变量说明

  m:机器数

  n:任务数。

t[]：输入数组，长度为n，其中每个元素表示任务的运行时间，下标从0开始。

s[][]:二维数组，长度为m*n，下标从0开始，其中元素s<i>[j]表示机器i运行的任务j的编号。

d[]：数组，长度为m其中元素d<i>表示机器i的运行时间，下标从0开始。

count[]:数组，长度为m，下标从0开始，其中元素count<i>表示机器i运行的任务数。i：循环变量。j：循环变量。k：临时变量。

max：完成所有任务的时间。

min：临时变量。

11、函数schedulevoidschedule12{

inti,j,kmax=0;

for(i=0;i＜m;i++){

d<i>=0;

for(j=0;j＜n;j++){

s<i>[j]=0;

}

}

for(i=0;i＜m;i++){//分配前m个任务

s<i>[0]=i;

______;

count<i>=1;

}

for(______;i＜n;i++){//分配后n-m个任务

intmin=d[0];

k=0;

for(j=1;j＜n;j++){//确定空闲机器

if(rain＞d[j]){

min=d[j];

k=j;//机器k空闲

}

}

______;

count[k]=count[k]+1;

d[k]=d[k]+t<i>;

for(i=0;

i＜m;i++){//确定完成所有任务所需要的时间

if(______){

max=d<i>;

}

}

}

}

  参考答案：

10、d<i>=d<i>+t<i>

i=m

srk][0]=i(4)Max＜d<i>

11、贪心0(2m*n+2m)

12、0

1、52、3、4、617

[解析]根据题中算法的思想将任务将前三个任务分给三个机器，再将接下来的任务分给最先空闲的机器，故可知机器0运行任务，机器1运行任务1、5，机器3运行任务2、3、4、6；且运行的最长时间为17。

>>>>>>>>>>点击继续答题

>>>>>>>>>>点击返回目录 

  相关链接：

软件设计师考前ppt串讲

软件设计师考试下午知识点精讲与考前必练

      软件设计师考试试题分类精解（第3版）