试题四（共15分） 阅读下列说明和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 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 （1） for（k=1；k p[x][y][k]=0； } } for（k=1；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< max）max = temp; } } } printf('/n%d/n'，max）, } void main(){read();schedule();write();} 【问题1】 （9分） 根据以上说明和C代码，填充C代码中的空（1）～（5）。 【问题2】（2分） 根据以上C代码，算法的时间复杂度为（6）（用O符号表示）。 【问题3】（4分） 考虑6个作业的实例，各个作业在两台处理机上的处理时间如表4-1所示。该实例的最优（7），最优解的值（即最短处理时间）为（8）。最优（x1,x2,x3,x4,x5,x6）表示，其中若第i个作业在A上赴理，则xi=l，否则xi=2。如（1，1，1，1，2，2）表示作业1，2，3和4在A上处理，作业5和6在B上处理。