阅读下列说明和 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 和问题 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 <= n; j++){ temp = 0; for (i = 1; （2）; i++){ temp = （3）; } （4）; } return r[n];}【问题 1】（8 分）根据说明，填充 C 代码中的空（1）～（4）。
【问题 2】（7 分）根据说明和 C 代码，算法采用的设计策略为（5）。求解 rn时，自顶向下方法的时间复杂度为（6）；自底向上方法的时间复杂度为（7）（用 O 表示）。
【问题 2】（7 分）根据说明和 C 代码，算法采用的设计策略为（5）。求解 rn时，自顶向下方法的时间复杂度为（6）；自底向上方法的时间复杂度为（7）（用 O 表示）。
参考解析
解析：【问题 1】（8 分） (1)i<=n(2)i<=j(3)temp=（temp>=r[i]+r[j-1]）?temp:（r[i]+r[j-1]）(4)r[j]=temp【问题 2】（7 分） (5)动态规划（6）O（2n）(7)O（n2）
相关考题：
阅读下列函数说明和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)。
试题四（共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 极时，N 极远离钢条，根据这一现象[]A．可以确定钢条原来一定有磁性，且钢条与磁针接近一端是N 极。B．可以确定钢条原来一定有磁性，且钢条与磁针接近一端是S 极。C．不能确定原来有没有磁性。D．可以确定钢条原来一定无磁性。
判断两根钢条甲和乙是否有磁性时，可将它们．当钢条甲靠近时，小磁针自动远离；当钢条乙靠近时，小磁针自动接近，由此可知[]A．两根钢条均有磁性B．两根钢条均无磁性C．钢条甲一定有磁性，钢条乙一定无磁性D．钢条甲一定有磁性，钢条乙可能有磁性
阅读下列说明和C代码，回答问题l至问题3．将解答写在答题纸的对应栏内。【说明】计算一个整数数组a的最长递增子序列长度的方法描述如下：假设数组a的长度为n，用数组b的元素b[i]记录以a[i](0≤in)为结尾元素的最长递增子序列的长度，则数组a的最长递增子序列的长度为器；其中b[i]满足最优子结构，可递归定义为：【c代码】下面是算法的c语言实现。(1)常量和变量说明a：长度为n的整数数组，待求其最长递增子序列b：长度为n的数组，b[i]记录以a[i](0≤in)为结尾元素的最长递增子序列的长度，其中0≤inlen:最长递增子序列的长度i.j:循环变量temp,临时变量(2)C程序include stdio . hint maxL （int *b. int n） {int i. temp =0;For（i = 0; i n; i++）{if （b[i] temp ）Temp= b[i];}Return temp;【问题l】（8分）根据说明和C代码,填充C代码中的空(1)～(4)。【问题2】（4分）根据说明和C代码，算法采用了(5)设计策略，时间复杂度为(6)（用O符号表示）。【问题3】（3分）已知数组a={3，10，5，15，6，8}，根据说明和C代码，给出数组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至问题3，将解答写在答题纸的对应栏内。【说明】模式匹配是指给定主串t和子串s，在主串t中寻找子串s的过程，其中s称为模式。如果匹配成功，返回s在t中的位置，否则返回-1。KMP算法用next数组对匹配过程进行了优化。KMP算法的伪代码描述如下：1．在串t和串s中，分别设比较的起始下标i=j=0。2．如果串t和串s都还有字符，则循环执行下列操作：（1）如果j=-l或者t[i]=s[j]，则将i和j分别加1，继续比较t和s的下一个字符；（2）否则，将j向右滑动到next[j]的位置，即j =next[j]。3．如果s中所有字符均已比较完毕，则返回匹配的起始位置（从1开始）；否则返回-1。其中，next数组根据子串s求解。求解next数组的代码已由get_next函数给出。【C代码】（1）常量和变量说明t，s：长度为lt和ls的字符串next:next数组，长度为ls（2）C程序#include #include#include/*求next[]的值*/void get_next( int*next, char *s, int ls) { inti=0，j=-1; next[0]=-1;/*初始化next[0]*/ while(i= ls)return （4） ;else return-1;}【问题1】（8分）根据题干说明，填充C代码中的空（1）～（4）.【问题2】（2分）根据题干说明和C代码，分析出kmp算法的时间复杂度为（5）（主串和子串的长度分别为It和Is，用O符号表示）。【问题3】（5分）根据C代码，字符串"BBABBCAC"的next数组元素值为（6）（直接写素值，之间用逗号隔开）。若主串为"AABBCBBABBCACCD"，子串为"BBABBCAC"，则函数Kmp的返回值是（7）。
阅读以下说明和C函数，填补代码中的空缺，将解答填入答题纸的对应栏内。[说明]函数removeDuplicates(chai *str)的功能是移除给定字符串中的重复字符，使每种字符仅保留一个，其方法是：对原字符串逐个字符进行扫描，遇到重复出现的字符时，设置标志，并将其后的非重复字符前移。例如，若str指向的字符串为"aaabbbbscbsss"，则函数运行后该字符串为"absc"。[C代码] voidremoveDuplicates(char *str) { inti,len=strlen(str); /*求字符串长度*/ if(______)return; /*空串或长度为1的字符串无需处理*/ for(i=0;i＜len;i++){ int flag=0; /*字符是否重复标志*/ int m; for(m=______; m＜len;m++){ if(Str[i]==str[m]){ ______; break; } } if (flag) { int n,idx=m; /*将字符串第idx字符之后、与str[i]不同的字符向前移*/ for(n=idx+1; n＜len; n++) if(Str[n]!=str[i]){ str[idx]=str[n];______; } str[______]='\0'; /*设置字符串结束标志*/ } } }
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。【说明】0-1背包问题定义为:给定1个物品的价值v[1....i]、重量w[1....i]和背包容量T,每个物品装到背包里或者不装到背包里,求最优的装包方案,使得所得到的价值最大。0-1背创问题具有最优子结构性质,定义c为最优装包方案所获得的最大价值则可得到如下所示的递归式。【C代码】下面是算法的C语言实现(1)常量和变量说明T:背包容量V[]:价值数组W[]:重量数组C[][]:c[i][j]表示前i个物品在背包容量为j的情况下最优装包方案所能获得的最大价值(2)C程序【问题1】(8分)根据说明和C代码,填充C代码中的空(1)~(4)【问题2】(4分)根据说明和C代码,算法采用了(5)设计策略。在求解过程中,采用了(6)(自底向上或者自顶向下)的方式。【问题3】(3分)若5项物品的价值数组和重量数组分别为v[]={0,1,6,18,22,28}和w[]={0,1,2,5,6,7},背包容量为T=11,则获得的最大价值为(7)。
阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。【说明】 计算两个字符串x和y的最长公共子串（Longest Common Substring）。 假设字符串x和字符串y的长度分别为m和n，用数组c的元素c[i][j]记录x中前i个字符和y中前j个字符的最长公共子串的长度。c[i][j]满足最优子结构，其递归定义为： 计算所有c[i][j](0 ≤i ≤ m，0 ≤j ≤ n)的值，值最大的c[i][j]即为字符串x和y的最长公共子串的长度。根据该长度即i和j，确定一个最长公共子串。【C代码】(1)常量和变量说明 x，y：长度分别为m和n的字符串 c[i][j]：记录x中前i个字符和y中前j个字符的最长公共子串的长度 max：x和y的最长公共子串的长度 maxi, maXj：分别表示x和y的某个最长公共子串的最后一个字符在x和y中的位置（序号） (2)C程序#include #include int c[50][50];int maxi;int maxj;int lcs(char*x, int m, char *y, int n) { int i, j; int max= 0; maxi= 0; maxj = 0;for ( i=0;i i i (1) ) {c[i][j] = c[i-1][j -1] + 1;if(max { (2) ; maxi = i; maxj =j; }}else (3) ; } } return max;}voidprintLCS(int max, char *x) { int i= 0; if (max == 0) return; for ( (4) ; i 【问题1】（8分） 根据以上说明和C代码，填充C代码中的空（1）～（4）。【问题2】（4分） 根据题干说明和以上C代码，算法采用了 （5） 设计策略。 分析时间复杂度为 （6） （用O符号表示）。【问题3】（3分） 根据题干说明和以上C代码，输入字符串x= "ABCADAB’，'y="BDCABA",则输出为 （7） 。
阅读下列说明和C代码，回答下列问题。[说明] 计算一个整数数组a的最长递增子序列长度的方法描述如下： 假设数组a的长度为n，用数组b的元素b[i]记录以a[i](0≤i＜n”)为结尾元素的最长递增子序列的长度为其中b[i]满足最优子结构，可递归定义为： [C代码] 下面是算法的C语言实现。 10常量和变量说明 a:长度为n的整数数组，待求其最长递增子序列 b:长度为n的数组，b[i]记录以a[i](0≤i＜n”)为结尾元素的最长递增子序列的长度，其中0≤i＜n len:最长递增子序列的长度 i,j:循环变量 temp:临时变量 11C程序 # jnclude＜stdio,h＞ mtmaxL(int*b,mt n) { mt I, temp=0 for(i=0; i＜n; i++) { (b[i]＞temp) temp=b[i] return temp; int main12 { int n,a[100],b[100],i,j,len; scanf(" % d", for(i=0;i＜n;i++) { scanf("% d", ___1___: for(i=1;i＜n;i++) { for(j=0,len=0;___2___;j++){ if( ___3___ } Printf("len:% d\n",maxL(b,n)) Primtf("\n") }1~4、 根据说明和C代码，填充C代码中的空______～______。5、 根据说明和C代码，算法采用了______设计策略，时间复杂度为______(用O符号表示)6、 已知数组a={3，10，5，15，6，8}，据说明和C代码，给出数组b的元素值。
阅读下列说明和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字）；若不稳定，请修改其中代码使其稳定（给出要修改的行号和修改后的代码）。
客车2型参考试块是一个不需外部磁场感应的自磁化体。它包括（）和（）磁体。显示长度给出测量性能。显示从端部开始向中间逐步减弱。长度增加表示性能更好，以左右侧显示的累积长度作为结果。A、1块钢条、1块永久磁体B、2块钢条、2块永久磁体C、1块钢条、2块永久磁体D、2块钢条、1块永久磁体
单选题客车2型参考试块是一个不需外部磁场感应的自磁化体。它包括（）和（）磁体。显示长度给出测量性能。显示从端部开始向中间逐步减弱。长度增加表示性能更好，以左右侧显示的累积长度作为结果。A1块钢条、1块永久磁体B2块钢条、2块永久磁体C1块钢条、2块永久磁体D2块钢条、1块永久磁体
单选题宏达钢铁公司有钢条、钢圈和钢板3条生产线，目前钢条有4个产品项目，钢圈有8个产品项目，钢板有6个产品项目，此企业产品组合的长度是A3B6C8D18