2. 计算机
  3. (2012年上半年下午试题四)阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。 【说明】 用两台处理机A和B处理n个作业。设A和B处理第i个作业的时间分别为ai和bi。由于各个作业的特点和机器性能的关系，对某些作业，在

(2012年上半年下午试题四)阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。 【说明】 用两台处理机A和B处理n个作业。设A和B处理第i个作业的时间分别为ai和bi。由于各个作业的特点和机器性能的关系，对某些作业，在

admin2018-07-27  41
问题 (2012年上半年下午试题四)阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。
    【说明】
    用两台处理机A和B处理n个作业。设A和B处理第i个作业的时间分别为ai和bi。由于各个作业的特点和机器性能的关系，对某些作业，在A上处理时间长，而对某些作业，在B上处理时间长。一台处理机在某个时刻只能处理一个作业，而且作业处理是不可中断的，每个作业只能被处理一次。现要找出一个最优调度方案，使得n个作业被这两台处理机处理完毕的时间(所有作业被处理的时间之和)最少。
    算法步骤：
    (1)确定候选解上界为R短的单台处理机处理所有作业的完成时间m，有

    (2)用p(x，y，k)=1表示前k个作业可以在A用时不超过x且在B用时不超过y时间内处理完成，则p(x，y，k)=p(x-ak，y，k-1)｜｜p(x，y-bk，k-1)(｜｜表示逻辑或操作)。
    (3)得到最短处理时间为min(max(x，y))。
【C代码】
下面是该算法的C语言实现。
(1)常量和变量说明
n：作业数
m：候选解上界
a：数组，长度为n，记录n个作业在A上的处理时间，下标从0开始
b：数组，长度为n，记录n个作业在B上的处理时间，下标从0开始
k：循环变量
p：三维数组，长度为(m+1)×(m+1)×(n+1)
temp：临时变量
max：最短处理时间
(2)C代码
#include＜stdio．h＞
int n，m;
int a[60]，b[60]，p[100][100][60];
void read(){／*输入n、a、b，求出m，代码略*／}
void schedule(){／*求解过程*／
    int  x，y，k；
    for(x=0；x＜=m；x++){
    for(y=0；y＜m；y++){
    _____(1)
    for(k=1;k＜n；k++)
    p[x][y][k]=0；
    }
  }
  for(k=1；k＜n;k++){
    for(x=0；x＜=m；x++){
    for(y=0;y＜=m;y++){
    if(x-a[k-1]＞=0)______(2)；
    if(______(3))p[x][y][k]=(p[x][y][k]｜｜p[x][y-b[k-1]][k-1])；
      }
      }
    }
}
void write(){／*确定最优解并输出*／
  int X，Y，temp，max=m；
  for(x=0；x＜=m；x++){
    for(y=0；y＜=m；y++){
    if(_____(4)){
    temp=______(5)；
    if(temp      }
      }
    }
    printf(’’＼n％d＼n’’，max)；
}
void main(){read()；schedule()；write()；}
根据以上说明和C代码，填充C代码中的空(1)～(5)。
选项
答案(1)p[x][y][0]=1 (2)p[x][y][k]=p[x-a[k-1]][y][k-1] (3)y-b[k-1]＞=0 (4)p[x][y][n]==1或p[x][y][n]或p[x][y][n]!=0 (5)(x＞=y)?x：y
解析 从schedule()函数的第一个程序段可以看出，该段程序主要进行初始化第一个作业，下标以0开始，即空(1)处应填入p[x][y][0]=1，内层循环里的p[x][y][k]=0用于初始化后面的n-1个作业。第二个程序段是对后面的n-1个作业，确定p(x，y，k)的值。x-a[k-1]＞=0的判定条件若成立，则表示第k个作业由机器A处理，完成k一1个作业时机器A花费的时间是x-a[k-1]，即空(2)处应填入p[x][y][k]=p[x-a[k-1]][y][k-1]。空(3)处要求填入一判定条件，由其后的执行语句可知，第k个作业由机器B处理，因此空(3)处应填入y-b[k-1]＞=0。
    write()程序段用于确定最优解并输出结果，即得到最短处理时间min(max(x，y))。空(4)处的判定条件是任务n完成，因此应填入p[x][y][n]==1或其等价形式。空(5)处表达max(x，y)，应填入(x＞=y)?x：y。
转载请注明原文地址:https://jikaoti.com/ti/9Fi7FFFM
本试题收录于： 软件设计师下午应用技术考试题库软考中级分类
0

软件设计师下午应用技术考试

软考中级

相关试题推荐
随机试题
最新回复(0)