阅读下列说明和图，回答问题1至问题3，将解答填入对应栏内。【说明】某机器上需要处理n个作业．job1，job2，…，jobn，其中：(1)每个作jobi(1≤i≤n)的编号为i，jobi有一个收益值p[i]和最后期限值d[i]小(2)机器在一个时刻只能处理一个作业，而且每个作业需要一个单位时间进行处理，一旦作业开始就不可中断，每个作业的最后期限值为单位时间的正整数倍；(3)job1～jobn的收益值呈非递增顺序排列，即p[1)≥P[2]≥…[n)：(4)如果作业jobi在其期限之内完成，则获得收益9[i]；如果在其期限之后完成，则没有收益。为获得较高的收益，采用贪心策略求解在期限之内完成的作业序列。图4*1是基于贪心策略求解该问题的流程图。(1)整型数组J[]有n个存储单元，变量k众表示在期限之内完成的作业J[1..k]存储所有能够在期限内完成的作业编号，数组J[1..k]里的作业按其最后期限非递减排序，即d[J[1]]≤…≤d[J[k]]。(2)为了便于在数组J中加入作业，增加一个虚拟作业Job0，并令d[0]=0，j[0]=0。(3)算法大致思想：先将作业．job1的编号1放入J[1]，然后，依次对每个作业．jobi (2≤i≤n)进行判定，看其能否插入到数组J中。若能，则将其编号插入到数组J的适当位置，并保证J中作业按其最后期限非递减排列；否则不插入。jobi能插入数组J的充要条件是：jobi和数组J中已有作业均能在其期限之内完成。(4)流程图中的主要变量院明如下。i：循环控制变量，表示作业的编号；k：表示在期限内完成的作业数：r：若．jobi能插入数组J，则其在数组了中的位置为r+1：q：循环控制变量，用于移动数组J中的元素。请填充图4-1中的空缺(1)、(2)和(3)处。
阅读下列说明和图，回答问题1至问题3，将解答填入对应栏内。
【说明】
某机器上需要处理n个作业．job1，job2，…，jobn，其中：
(1)每个作jobi(1≤i≤n)的编号为i，jobi有一个收益值p[i]和最后期限值d[i]小
(2)机器在一个时刻只能处理一个作业，而且每个作业需要一个单位时间进行处理，一旦作业开始就不可中断，每个作业的最后期限值为单位时间的正整数倍；
(3)job1～jobn的收益值呈非递增顺序排列，即p[1)≥P[2]≥…[n)：
(4)如果作业jobi在其期限之内完成，则获得收益9[i]；如果在其期限之后完成，则没有收益。
为获得较高的收益，采用贪心策略求解在期限之内完成的作业序列。图4*1是基于贪心策略求解该问题的流程图。
(1)整型数组J[]有n个存储单元，变量k众表示在期限之内完成的作业J[1..k]存储所有能够在期限内完成的作业编号，数组J[1..k]里的作业按其最后期限非递减排序，即d[J[1]]≤…≤d[J[k]]。
(2)为了便于在数组J中加入作业，增加一个虚拟作业Job0，并令d[0]=0，j[0]=0。
(3)算法大致思想：先将作业．job1的编号1放入J[1]，然后，依次对每个作业．jobi (2≤i≤n)进行判定，看其能否插入到数组J中。若能，则将其编号插入到数组J的适当位置，并保证J中作业按其最后期限非递减排列；否则不插入。
jobi能插入数组J的充要条件是：jobi和数组J中已有作业均能在其期限之内完成。
(4)流程图中的主要变量院明如下。
i：循环控制变量，表示作业的编号；
k：表示在期限内完成的作业数：
r：若．jobi能插入数组J，则其在数组了中的位置为r+1：
q：循环控制变量，用于移动数组J中的元素。
请填充图4-1中的空缺(1)、(2)和(3)处。
相关考题：
阅读以下函数说明和C语言函数，将应填入(n)的字句写在答题纸的对应栏内。[说明1]函数int fun1(int m, int n)的功能是：计算并返回正整数m和n的最大公约数。[函数1]int fun1(int m, int n){while ((1)) {if (m＞n) m=m-n;else n=n-m;}(2);}[说明2]函数long fun2(char*str)的功能是：自左至右顺序取出非空字符串str中的数字字符形成一个十进制整数(最多8位)。例如，若字符串str的值为“f3g8d5.ji2e3p12fkp”，则函数返回值为3852312。[函数2]long fun2(char *str){int i=0;long k=0;char *p=str;while (*p!='＼0' (3)) {if (*p＞='0' *p＜='9') {k=(4)+ *p - '0';++i;}(5);}return k;}
阅读以下说明，回答问题，将解答填入对应的解答栏内。[说明] 将一个正整数分解质因数。例如：输入90，打印出90=2*3*3*5。main ( ){int n, i;printf ( "\n please input a number: \n");scanf ( "% d" ,u);printf ( "%d =" ,n);for((1)){while((2)){if((3)){ printf ("%d*",i);(4)}elsebreak;}}printf (“%d”，n)；}
阅读下列函数说明和C函数，回答问题1～2，将解答填入栏内。[说明]若矩阵Am×n中存在某个元素aij满足：aij…是第i行中最小值且是第j列中的最大值，则称该元素为矩阵A的一个鞍点。下面程序的功能是输出A中所有鞍点，其中参数A使用二维数组表示，m和n分别是矩阵A的行列数。[程序]void saddle (int A[ ] [ ], int m, int n){ int i,j,min;for (i=0;i ＜m;i + + ){ min: (1);for (j=1; j＜n; j+ +)if(A[i][j]＜min) (2);for (j=0; j＜n; j+ +)if ((3)){ p=0;while (p＜m(4))p+ +;if (p ＞ = m)printf ("%d,%d,%d\n",i,j,min);}}}[问题1] 将函数代码中的(1)～(4)处补充完整[问题2]在上述代码的执行过程中，若A为矩阵，则调用saddle(A，3，3)后输出是(5)。
阅读以下函数说明和C语言函数，将应填入(n)处的字句写在对应栏内。【说明】设有n个人围坐一圈并按顺时针方向从1到n编号，从第s个人开始进行1到m的报数，报数到第m个人，则此人出圈，再从他的下一个人重新开始1到m的报数，如此进行下去，直到所有的人都出圈为止。现要求按出圈次序，每10人一组，给出这n个人的顺序表。设n=100，s=1，m=10。(1)将1到n个人的序号存入一维数组p中；(2)若第i个人报数后出圈，则将p置于数组的倒数第i个位置上，而原来第i+1个至倒数第i个元素依次向前移动一个位置：(3)重复第(2)步，直至圈中只剩下p[1]为止。include＜stdio.h＞define N 100define S 1define M 10void main(){int p[100],n,s,m;m=M;n=N;s=S;int i,j,s1,w;s1=s;for(i=1;(1);i++)(2)=i;for(i=n;i＞=2;i--){s1=(3);if(s1==0)s1=i;w=(4);for(j=s1;j＜i;j++)p[j-1]=p[j];p[i-1]=(5);printf("%4d",p[i])}}
阅读下列算法说明和流程图，根据要求回答问题1～问题3。[说明]某机器上需要处理n个作业job1，job2，…，jobn，其中：(1)每个作业jobi(1≤i≤n)的编号为i，jobi有一个收益值P[i]和最后期限值d[i]；(2)机器在一个时刻只能处理一个作业，而且每个作业需要一个单位时间进行处理，一旦作业开始就不可中断，每个作业的最后期限值为单位时间的正整数倍；(3)job1～jobn的收益值呈非递增顺序排列，即p[1]≥p[2]≥…≥p[n]；(4)如果作业jobi在其期限之内完成，则获得收益p[i]；如果在其期限之后完成，则没有收益。为获得较高的收益，采用贪心策略求解在期限之内完成的作业序列。图3-25是基于贪心策略求解该问题的流程图。(1)整型数组J[]有n个存储单元，变量k表示在期限之内完成的作业数，J[1..k]存储所有能够在期限内完成的作业编号，数组J[1..k)里的作业按其最后期限非递减排序，即d[J[1]]≤…≤d[J[k]]。(2)为了便于在数组J中加入作业，增加一个虚拟作业job0，并令d[0]=0，J[0]=0。(3)算法大致思想是：先将作业job1的编号1放入J[1]，然后，依次对每个作业jobi(2≤i≤n)进行判定，看其能否插入到数组J中。若能，则将其编号插入到数组J的适当位置，并保证J中作业按其最后期限非递减排列；否则不插入。jobi能插入数组J的充要条件是：jobi和数组J中已有作业均能在其期限之内完成。(4)流程图中的主要变量说明如下。i：循环控制变量，表示作业的编号；k：表示在期限内完成的作业数；r：若jobi能插入数组J，则其在数组J中的位置为r+1；q：循环控制变量，用于移动数组J中的元素。请将图3-25中的(1)～(3)空缺处的内容填写完整。
阅读以下函数说明和C语言函数，将应填入(n)处的字句写在对应栏内。【说明】有n个整数，使其前面各数顺序向后移m个位置，最后m个数变成最前面的m个数。【函数】main(){int number[20],n,m,i;printf("the total numbers is:");scanf("%d",n);printf("back m:");scanf("%d",m);for(i=0;i＜=n-1;i)scanf("%d,",number[i]);(1);for(i=0;i＜=n-1;i)printf("%d,",number[i]);}move(array,n,m)int n,m,array[20];{int *p,array_end;array_end=(2);for(p=array[n-1];(3);p--)*p=(4);*array=array_end;m--;if(m＞0) (5);}
假设有6个作业job1，job2，…，job6；完成作业的收益数组p=(p[1],p[2],p[3],p[4],p[5],p[6])=(90,80,50,30,20,10)；每个作业的处理期限数组d=(d[1],d[2],d[3],d[4],d[5],d[6])=(1,2,1,3,4,3)。请应用试题中描述的贪心策略算法，给出在期限之内处理的作业编号序列(4) (按作业处理的顺序给出)，得到的总收益为(5)。
阅读以下关于中断的叙述，回答问题1至问题3，将答案填入对应栏内。【说明】某计算机中断系统有4级中断I1，I2，I3和I4，中断响应的优先次序为I1→I2→I3→I4，即先响应I1，冉响应I2，……，最后响应I4。每级中断对应一个屏蔽码，屏蔽码中某位为“1”表示禁止中断(关中断)，若为“0”则表示允许中断(开中断)。各级中断处理程序与屏蔽码的关系如表3-1所示。若ti时刻I1、I2和I4级同时产生中断，在各中断处理完成后，tj(ti＜tj)时刻发出I3级中断申请，CPU为I3服务时，I1级发出请求，在CPU为I1服务时，I2级发出请求。请参照图3-1所示的格式，画出CPU的运行轨迹。
试题四（共15 分）阅读下列说明和C代码，回答问题 1 至问题3，将解答写在答题纸的对应栏内。【说明】某应用中需要对100000 个整数元素进行排序，每个元素的取值在 0～5 之间。排序算法的基本思想是：对每一个元素 x，确定小于等于 x的元素个数(记为m)，将 x放在输出元素序列的第m 个位置。对于元素值重复的情况，依次放入第 m-l、m-2、…个位置。例如，如果元素值小于等于4 的元素个数有 10 个，其中元素值等于 4 的元素个数有3个，则 4 应该在输出元素序列的第10 个位置、第 9 个位置和第8 个位置上。算法具体的步骤为：步骤1：统计每个元素值的个数。步骤2：统计小于等于每个元素值的个数。步骤3：将输入元素序列中的每个元素放入有序的输出元素序列。【C代码】下面是该排序算法的C语言实现。(1)常量和变量说明R:常量，定义元素取值范围中的取值个数，如上述应用中 R值应取6i：循环变量n：待排序元素个数a：输入数组，长度为nb：输出数组，长度为nc：辅助数组，长度为R，其中每个元素表示小于等于下标所对应的元素值的个数。(2)函数sort1 void sort(int n,int a[ ]，intb[ ]){2 int c[R]，i；3 for (i=0；i (1) ；i++){4 c[i]=0；5 }6 for(i=0；in；i++）{7 c[a[i]] = (2) ；8 }9 for(i=1；iR；i++）{10 c[i]= （3） ；11 }12 for(i=0；in；i++）{13 b[c[a[i]]-1]= (4) ；14 c[a[i]]=c[a[i] ]-1；15 }16 }【问题1】（8 分）根据说明和C代码，填充 C代码中的空缺(1)～(4)。【问题2】（4 分）根据C代码，函数的时间复杂度和空间复杂度分别为 (5) 和 (6) （用 O符号表示）。【问题3】（3 分）根据以上C代码，分析该排序算法是否稳定。若稳定，请简要说明（不超过 100 字）；若不稳定，请修改其中代码使其稳定（给出要修改的行号和修改后的代码）。从下列的2 道试题（试题五和试题六）中任选 1 道解答。如果解答的试题数超过 道，则题号小的 道解答有效。
【程序说明】程序功能是若输入的N值为5，则输出结果如下：11 11 2 11 3 3 11 4 6 4 1【程序】SET TALK OFFCLEARINPUT“N＝”TO NDIME A(N，N)P=NDO WHILE N＞0A(N，N)=1(5)N＝N-1ENDDOFOR I＝3 TO (6)FOR J＝2 TO I-1A(I，J)= (7)ENDFORENDFORFOR I＝1 TO P? SPACE(3*(P-I+1))FOR J＝1 TO I?? STR(A(I，J)，3)(8)?ENDFORSET TALK ON(5)A．A(1，N)=1B．A(1，N-1)＝1C．A(N，1)=1D．A(N-1，1)＝1
某单道批处理系统中有四个作业JOB1、JOB2、JOB3和JOB4，它们到达“输入井”的时刻和需要的运行时间如下表假设9：30开始进行作业调度，按照最高响应比作业优先算法，首先被调度的作业是A．JOB1B．JOB2C．JOB3D．JOB4
阅读以下说明和C语言函数，将应填入(n)处的字句写在对应栏内。【说明】输入数组，最大的与第一个元素交换，最小的与最后一个元素交换，输出数组。【函数】main ( ){int number[10];input (number);max min (number);output (number);}input (number)int number[10];{int i;for ( i=0;i＜9;i++ )scanf ( "%d,",number[i] );scanf ( "%d",number[9] );}max_min ( array )int array[10];{int *max,*min,k,1;int *p,*arr_end;arr end=(1);max=min=array;for ( p=(2);p＜arr_end;p++ )if((3)) max=p;else if ( *p＜*min ) min=p;(4);l=*min;(5);array[0]=1;1=*p;*p=array[9];array[9]=k;k=*p;return;}output ( array )int array[10];{ int *p;for ( p=array;p＜array+9;p++ )printf ( "%d,",*p );printf ( "%d\n",array[9] );}
已知N个数已存入数组A[1..M)的前N个元素中(N＜M)，为在A[i](1≤i≤N)之前插入一个新数，应先(37)，以挪出一个空闲位置插入该数。A．从A[i]开始直到A[1]，每个数向后移动一个位置B．从A[1]开始直到A[i]小每个数向后移动一个位置C．从A[i]开始直到A[N]，每个数向前移动一个位置D．从A[N]开始直到A[i]小每个数向后移动一个位置
阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。 【说明】 采用归并排序对n个元素进行递增排序时，首先将n个元素的数组分成各含n/2个元素的两个子数组，然后用归并排序对两个子数组进行递归排序，最后合并两个已经排好序的子数组得到排序结果。 下面的C代码是对上述归并算法的实现，其中的常量和变量说明如下： arr：待排序数组 p,q,r：一个子数组的位置从p到q，另一个子数组的位置从q+1到r begin,end：待排序数组的起止位置 left,right：临时存放待合并的两个子数组 n1,n2：两个子数组的长度 i,j,k：循环变量 mid：临时变量 【C代码】inciudestdio.h inciudestdlib.h define MAX 65536 void merge(int arr[],int p,int q,int r) { int *left, *right; int n1,n2,i,j,k; n1=q-p+1; n2=r-q; if((left=(int*)malloc((n1+1)*sizeof(int)))=NULL) { perror(malloc error); exit(1); } if((right=(int*)malloc((n2+1)*sizeof(int)))=NULL) { perror(malloc error); exit(1); } for(i=0;in1;i++){ left[i]=arr[p+i]； } left[i]=MAX； for(i=0; in2; i++){ right[i]=arr[q+i+1] } right[i]=MAX; i=0; j=0; for(k=p; （1） ; k++) { if(left[i] right[j]) { （2） ; j++; }else { arr[k]=left[i]； i++； } } } void mergeSort(int arr[],int begin,int end){ int mid; if( （3） ){ mid=(begin+end)/2; mergeSort(arr,begin,mid); （4） ; merge(arr,begin,mid,end); } }【问题1】 根据以上说明和C代码，填充1-4。 【问题2】 根据题干说明和以上C代码，算法采用了（5）算法设计策略。 分析时间复杂度时，列出其递归式位（6），解出渐进时间复杂度为（7）（用O符号表示）。空间复杂度为（8）（用O符号表示）。 【问题3】 两个长度分别为n1和n2的已经排好序的子数组进行归并，根据上述C代码，则元素之间比较次数为（9）。
试题四(共15 分)阅读下列说明和图，回答问题 1 至问题 3，将解答填入答题纸的对应栏内。【说明】某机器上需要处理 n 个作业 job1, job2, …, jobn，其中：(1) 每个作业jobi(1≤i≤n)的编号为 i， jobi有一个收益值 p[i]和最后期限值 d[i]；(2) 机器在一个时刻只能处理一个作业，而且每个作业需要一个单位时间进行处理，一旦作业开始就不可中断，每个作业的最后期限值为单位时间的正整数倍；(3) job1～jobn 的收益值呈非递增顺序排列，即p[1]≥p[2]≥…≥p[n]；(4) 如果作业jobi在其期限之内完成，则获得收益 p[i]；如果在其期限之后完成，则没有收益。为获得较高的收益，采用贪心策略求解在期限之内完成的作业序列。图 4-1 是基于贪心策略求解该问题的流程图。(1) 整型数组 J[]有 n 个存储单元，变量 k 表示在期限之内完成的作业数，J[1..k]存储所有能够在期限内完成的作业编号， 数组 J[1..k]里的作业按其最后期限非递减排序，即d[J[1]]≤ … ≤d[J[k]]。(2) 为了方便于在数组 J 中加入作业，增加一个虚拟作业 job0，并令d[0] = 0， J[0] = 0。(3) 算法大致思想：先将作业 job1 的编号 1 放入 J[1]，然后，依次对每个作业 jobi (2≤i≤n)进行判定，看其能否插入到数组 J 中，若能，则将其编号插入到数组 J 的适当位置，并保证 J 中作业按其最后期限非递减排列，否则不插入。 jobi能插入数组 J 的充要条件是：jobi 和数组 J 中已有作业均能在其期限之内完成。(4) 流程图中的主要变量说明如下：i：循环控制变量，表示作业的编号；k：表示在期限内完成的作业数；r：若jobi能插入数组 J，则其在数组 J 中的位置为 r+1；q：循环控制变量，用于移动数组 J 中的元素。【问题 1】 （9 分）请填充图4-1 中的空缺(1)、(2)和(3)处。【问题 2】(4 分)假设有 6 个作业 job1, job2, …, job6；完成作业的收益数组 p=(p[1],p[2],p[3],p[4],p[5],p[6]) = (90,80,50,30,20,10)；每个作业的处理期限数组 d=(d[1],d[2],d[3],d[4],d[5],d[6]) = (1,2,1,3,4,3)。请应用试题中描述的贪心策略算法，给出在期限之内处理的作业编号序列 (4)（按作业处理的顺序给出） ，得到的总收益为 (5) 。【问题 3】(2 分)对于本题的作业处理问题， 用图 4-1的贪心算法策略， 能否求得最高收益？ (6) 。用贪心算法求解任意给定问题时，是否一定能得到最优解？ (7) 。
试题三（共 20 分）阅读以下关于中断的叙述，回答问题 1 至问题 3，将答案填入答题纸的对应栏内。【说明】某计算机中断系统有 4级中断 I1，I2，I3 和I4，中断响应的优先次序为 I1→I2→I3→I4，即先响应 I1，再响应 I2，……，最后响应 I4。每级中断对应一个屏蔽码，屏蔽码中某位为“1”表示禁止中断（关中断） ，若为“0”则表示允许中断（开中断） 。各级中断处理程序与屏蔽码的关系如表 3-1 所示。【问题 1】 （6 分）若ti 时刻I1、I2 和 I4 级同时产生中断，在各中断处理完成后，tj（titj）时刻发出 I3 级中断申请，CPU 为 I3 服务时，I1 级发出请求，在 CPU 为 I1 服务时，I2 级发出请求。请参照图 3-1 所示的格式，画出CPU的运行轨迹。【问题 2】 （8 分）若将中断优先次序设置为 I1→I4→I3→I2，即先响应 I1，再响应 I4，……，最后响应 I2。请重新设置各级的屏蔽码，填写表 3-2。【问题 3】 （6 分）设中断优先次序为 I1→I4→I3→I2。若 ti 时刻 I1、I2 和 I4 级同时产生中断，在各中断处理完成后，tj（titj）时刻发出 I3 级中断申请，CPU为 I3服务时，I1级发出请求，在 CPU为 I1 服务时，I2 级发出请求。请画出这种情况下 CPU的运行轨迹。
试题四（共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代码includestdio.hint 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；ym；y++）{（1）for（k=1；kn；k++）p[x][y][k]=0；}}for（k=1；kn；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上处理。
阅读下列说明，回答问题1至问题3，将解答填入对应栏内。【说明】某餐厅供应各种标准的营养套餐。假设菜单上共有n项食物m1，m2，…，mn，每项食物mi的营养价值为vi，价格为pi其中i＝1，2，…，n，套餐中每项食物至多出现一次。客人常需要一个算法来求解总价格不超过M的营养价值最大的套餐。1. 【问题1】下面是用动态规划策略求解该问题的伪代码，请填充其中的空缺(1)、(2)和(3)处。伪代码中的主要变量说明如下。n：总的食物项数；v：营养价值数组，下标从1到n，对应第1到第n项食物的营养价值；p：价格数组，下标从1到n，对应第1到第n项食物的价格；M：总价格标准，即套餐的价格不超过M；x：解向量(数组)，下标从1到n，其元素值为0或1，其中元素值为0表示对应的食物不出现在套餐中，元素值为1表示对应的食物出现在套餐中；nv：n+1行M+1列的二维数组，其中行和列的下标均从0开始，nv[i][j]表示由前i项食物组合且价格不超过j的套餐的最大营养价值。问题最终要求的套餐的最大营养价值为nv[n][M]。伪代码如下：MaxNutrientValue(n，v，p，M，x)1 for i＝0 to n2 nv[i][0] ＝ 03 for j＝1 to M4 nv[0][j]＝05 for i＝1 to n6 for j＝1 to M7 if j＜p[i] //若食物mi不能加入到套餐中8 nv[i][j] ＝ nv[i-1][j]9 else if (1)10 nv[i][j]＝ nv[i-1][j]11 else12 nv[i][j]＝ nv[i-1][j-p[i]] + v[i]13 j ＝ M14 for i＝n downto 115 if (2)16 x[i] ＝ 017 else18 x[i] ＝ 119 (3)20 return x and nv[n][M](1)nv[i-1][j]≥nv[i-1][j-p[i]]+v[i] (2)nv[i][j]＝nv[i-1][j] (3)j＝j-p[i]
阅读下列说明和C代码，回答问题，将解答填入答题纸的对应栏内。【说明】计算一个整数数组a的最长递增子序列长度的方法描述如下：假设数组a的长度为n，用数组b的元素b[i]记录以a[i](0≤i＜n)为结尾元素的最长递增子序列的长度为 ；其中b[i]满足最优子结构，可递归定义为：【C代码】下面是算法的C语言实现。（1）常量和变量说明a：长度为n的整数数组，待求其最长递增子序列b：长度为n的数组，b[i]记录以a[i](0≤ilen：最长递增子序列的长度i, j：循环变量temp：临时变量（2）C程序#include int maxL(int*b, int n) {int i, temp=0;for(i=0; itemp) temp=b[i]; } return temp;}int main() { int n,a[100], b[100], i, j, len; scanf("%d", for(i=0;i【问题1】（8分）根据说明和C代码，填充C代码中的空（1）～（4）。【问题2】（4分） 根据说明和C代码，算法采用了 （5） 设计策略，时间复杂度为 （6） （用O符号表示）。【问题3】（5分） 已知数组a={3，10，5，15，6，8}，据说明和C代码，给出数组b的元素值。
阅读下列说明和 C 代码，回答问题 1 和问题 2，将解答填入答题纸的对应栏内。【说明】某公司购买长钢条，将其切割后进行出售。切割钢条的成本可以忽略不计，钢条的长度为整英寸。已知价格表 P，其中中 Pi（i＝1，2，...，m）表示长度为 i 英寸的钢条的价格。现要求解使销售收益最大的切割方案。求解此切割方案的算法基本思想如下：假设长钢条的长度为 n 英寸，最佳切割方案的最左边切割段长度为 i 英寸，则继续求解剩余长度为 n－i 英寸钢条的最佳切割方案。考虑所有可能的 i，得到的最大收益 rn对应的切割方案即为最佳切割方案。rn的递归定义如下：rn =max1≤ i ≤n(pi +rn-i)对此递归式，给出自顶向下和自底向上两种实现方式【C 代码】/*常量和变量说明n：长钢条的长度P[]：价格数组*/#define LEN 100int Top_Down_Cut_Rod(int P[], int n){/*自顶向下*/ int r = 0; int i; if (n == 0){ return 0; } for (i = 1; （1）; i++){ int tmp = P[i] + Top_Down_Cut_Rod(p, n - i); r = (r >= tmp) ? r : tmp; } return r;}int Bottom_Up_Cut_Rod(int p[], int n){ /*自底向上*/ int r[LEN] = { 0 }; int temp = 0; int i, j; for (j = 1; j 【问题 2】（7 分）根据说明和 C 代码，算法采用的设计策略为（5）。求解 rn时，自顶向下方法的时间复杂度为（6）；自底向上方法的时间复杂度为（7）（用 O 表示）。
阅读下列说明和C代码，回答问题1至问题3【说明】??? 某应用中需要对100000个整数元素进行排序，每个元素的取值在0～5之间。排序算法的基本思想是：对每一个元素x，确定小于等于x的元素个数(记为m)，将x放在输出元素序列的第m个位置。对于元素值重复的情况，依次放入第m-l、m-2、…个位置。例如，如果元素值小于等于4的元素个数有10个，其中元素值等于4的元素个数有3个，则4应该在输出元素序列的第10个位置、第9个位置和第8个位置上。算法具体的步骤为：步骤1：统计每个元素值的个数。步骤2：统计小于等于每个元素值的个数。步骤3：将输入元素序列中的每个元素放入有序的输出元素序列。【C代码】下面是该排序算法的C语言实现。(1)常量和变量说明R: 常量，定义元素取值范围中的取值个数，如上述应用中R值应取6i：循环变量n：待排序元素个数a：输入数组，长度为nb：输出数组，长度为nc：辅助数组，长度为R，其中每个元素表示小于等于下标所对应的元素值的个数。(2)函数sort1??? void sort(int n，int a[]，int b[]){2??? ???int c[R]，i；3?? for (i=0；i4?? ??c[i]=0；5??? ???}6??? ???for(i=0；i7??? ?c[a[i]] = ??(2)? ；8??? ???}9 ??for(i=1；i10??? c[i]= ?（3）11??? ??}12 ?for(i=0；i13??? b[c[a[i]]-1]=? (4)?? ；14??? c[a[i]]=c[a[i]]-1；15??? ??}16??? }【问题1】? 根据说明和C代码，填充C代码中的空缺(1)～(4)。【问题2】根据C代码，函数的时间复杂度和空间复杂度分别为 (5) 和 (6) （用O符号表示）。【问题3】?? 根据以上C代码，分析该排序算法是否稳定。若稳定，请简要说明（不超过100字）；若不稳定，请修改其中代码使其稳定（给出要修改的行号和修改后的代码）。
某操作系统采用斯普林操作技术。现有两个作业，每个作业都是先占用CPU，用时均为P；然后用打印机输出结果，打印需时均为PR；打印完成后，作业结束。作业进入输入井的时间均为I；把作业从输入井取出送入主存的时间和把作业的运行结果送入输出井的时间均为t。这里PR（I+t），I（P+t）。则完成这两个作业总共用时为（）A、I+3t+P+2PRB、1+2t+P+2PRC、I+3t+2P+2PRD、1+2t+2P+2PR
有n个独立的作业{1，2，..，n}，由m台相同的机器进行加工处理。作业i所需的处理时间为ti。现约定，任何作业可以在任何一台机器上加工处理，但未完工前不允许中断处理。任何作业不能拆分成更小的作业。多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成（nm）。对于多级调度问题，使用以下哪种贪心策略比较合适（）A、作业从小到大依次分配给空闲的机器B、作业从大到小依次分配给空闲的机器C、每个机器分配一样的作业数D、使用以上几种贪心策略都能找到最优解，所以都合适
下列关于时间价值系数的关系式，表达不正确的是（）。A、（F/A，i，n）=（F/P，i，n）×（P/A，i，n）B、（F/P，i，n）=（F/P，i，n1）×（F/P，i，n2），其中：n1+n2=nC、（F/P，i，n）=（F/P，i，n1）+（F/P，i，n2），其中：n1+n2=nD、（P/A，i，n）=（P/F，i，n）／（A／F，i，n）
单选题某操作系统采用斯普林操作技术。现有两个作业，每个作业都是先占用CPU，用时均为P；然后用打印机输出结果，打印需时均为PR；打印完成后，作业结束。作业进入输入井的时间均为I；把作业从输入井取出送入主存的时间和把作业的运行结果送入输出井的时间均为t。这里PR（I+t），I（P+t）。则完成这两个作业总共用时为（）AI+3t+P+2PRB1+2t+P+2PRCI+3t+2P+2PRD1+2t+2P+2PR
单选题下列关于时间价值系数的关系式，表达不正确的是（）。A（F/A，i，n）=（F/P，i，n）×（P/A，i，n）B（F/P，i，n）=（F/P，i，n1）×（F/P，i，n2），其中：n1+n2=nC（F/P，i，n）=（F/P，i，n1）+（F/P，i，n2），其中：n1+n2=nD（P/A，i，n）=（P/F，i，n）／（A／F，i，n）