阅读下列算法说明和流程图，根据要求回答问题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)空缺处的内容填写完整。
阅读下列算法说明和流程图，根据要求回答问题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函数，回答问题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)。
假设有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，将解答填入对应栏内。【说明】某机器上需要处理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代码，回答问题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) 。
阅读下列说明，回答问题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至问题3，将解答写在答题纸的对应栏内。【说明】n-皇后问题是在n行n列的棋盘上放置n个皇后，使得皇后彼此之间不受攻击，其规则是任意两个皇后不在同一行、同一列和相同的对角线上。拟采用以下思路解决n-皇后问题：第i个皇后放在第i行。从第一个皇后开始，对每个皇后，从其对应行（第i个皇后对应第i行）的第一列开始尝试放置，若可以放置，确定该位置，考虑下一个皇后；若与之前的皇后冲突，则考虑下一列；若超出最后一列，则重新确定上一个皇后的位置。重复该过程，直到找到所有的放置方案。【C代码】下面是算法的C语言实现。(1)常量和变量说明pos：一维数组，pos[i]表示第i个皇后放置在第i行的具体位置count：统计放置方案数i，j，k：变量N：皇后数【问题1】（10分）根据以上说明和C代码，填充C代码中的空（1）～（5）。【问题2】（2分）根据以上说明和C代码，算法采用了（6）设计策略。【问题3】（3分）上述C代码的输出为：（7）。
阅读下列说明和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字）；若不稳定，请修改其中代码使其稳定（给出要修改的行号和修改后的代码）。