1、软件设计师-27 及答案解析(总分：99.97，做题时间：90 分钟)一、试题一(总题数：1，分数：25.00)阅读下列说明和 C 代码，回答下面问题。 说明 用两台处理机 A 和 B 处理 n 个作业。设 A 和 B 处理第 i 个作业的时间分别为 a i 和 b i 。由于各个作业的特点和机器性能的关系，对某些作业，在 A 上处理时间长，而对某些作业在 B 上处理时间长。一台处理机在某个时刻只能处理一个作业，而且作业处理是不可中断的，每个作业只能被处理一次。现要找出一个最优调度方案，使得 n 个作业被这两台处理机处理完毕的时间(所有作业被处理的时间之和)最少。 算法步骤： (1)确定候选解
2、上界为最短的单台处理机处理所有作业的完成时间 m， （分数：24.99）(1).根据以上说明和 C 代码，填充 C 代码中的空。（分数：8.33）_(2).根据以上 C 代码，算法的时间复杂度为_(用 O 符号表示)。（分数：8.33）_(3).考虑 6 个作业的实例，各个作业在两台处理机上的处理时间如下表所示。该实例的最优解为_，最优解的值(即最短处理时间)为_。最优解用(x1,x2,x3,x4,x5,x6)表示，其中若第 i 个作业在 A 上处理，则 x i =1，否则 x i =2。如(1，1，1，1，2，2)表示作业 1，2，3 和 4 在 A 上处理，作业 5 和 6在 B 上处理。
3、 作业 1 作业 2 作业 3 作业 4 作业 5 作业 6 处理机 A 2 5 7 10 5 2 处理机 B 3 8 4 11 3 4 （分数：8.33）_二、试题二(总题数：1，分数：25.00)阅读下列说明和 C 代码，回答下面问题。 说明 设有 n 个货物要装入若干个容重为 C 的集装箱以便运输，这 n 个货物的体积分别为s1,s2,sn，且有siC(1in)。为节省运输成本，用尽可能少的集装箱来装运这 n 个货物。 下面分别采用最先适宜策略和最优适宜策略来求解该问题。 最先适宜策略(firstfit)首先将所有的集装箱初始化为空，对于所有货物，按照所给的次序，每次将一个货物装入第一个
4、能容纳它的集装箱中。 最优适宜策略(bestfit)与最先适宜策略类似，不同的是，总是把货物装到能容纳它且目前剩余容重最小的集装箱，使得该箱子装入货物后闲置空间最小。 C 代码 下面是这两个算法的 C 语言核心代码。 (1)变量说明 n：货物数。 C：集装箱容量。 s：数组，长度为 n，其中每个元素表示货物的体积，下标从 0 开始。 b：数组，长度为 n，bi表示第 n+i 个集装箱当前已经装入货物的体积，下标从 0 开始。 j：循环变量。 k：所需的集装箱数。 min：当前所用的各集装箱装入了第 i 个货物后的最小剩余容量。 m：当前所需的集装箱数。 temp：临时变量。 (2)函数 fir
5、stfit int firstfit() int i,j; k=0; for(i=0;in; i+) bi=0; for(i=0;in;i+) _; while(c-bjsi) j+; _; k=k(j+1)?k:(j+1); return k; (3)函数 bestfit int bestfit() int i,j,min,m, temp; k=0; for(i=0;in;i+) bi=0; for(i=0;in;i+) min=C; m=k+1; for(j=0;jk+1;j+) temp=C-bj-si; if(temp0 m=j; _; k=k(j+1)?k:(j+1); return
6、 k; （分数：24.99）(1).根据说明和C 代码，填充 C 代码中的空。（分数：8.33）_(2).根据说明和C 代码，该问题在最先适宜和最优适宜策略下分别采用了_和_算法设计策略，时间复杂度分别为_和_(用 O 符号表示)。（分数：8.33）_(3).考虑实例 n=10，C=10，各个货物的体积为4,2,7,3,5,4,2,3,6,2。该实例在最先适宜和最优适宜策略下所需的集装箱分别为_和_。考虑一般的情况，这两种求解策略能否确保得到最优解?_(是或否)（分数：8.33）_三、试题三(总题数：1，分数：25.00)1.阅读下列说明和 C 语言代码，将应填入空格处的字句写在下面。 说明
7、设某一机器由 n 个部件组成，每一个部件都可以从 m 个不同的供应商处购得。供应商 j 供应的部件 i 具有重量 W ij 和价格 C ij 。设计一个算法，求解总价格不超过上限 cc 的最小重量的机器组成。 采用回溯法来求解该问题： 首先定义解空间。解空间由长度为 n 的向量组成，其中每个分量取值来自集合1，2，m，将解空间用树形结构表示。 接着从根节点开始，以深度优先的方式搜索整个解空间。从根节点开始，根节点成为活节点，同时也成为当前的扩展节点。向纵深方向考虑第一个部件从第一个供应商处购买，得到一个新节点。判断当前的机器价格(C 11 )是否超过上限(cc)，重量(W 11 )是否比当前已
8、知的解(最小重量)大，若为是，应回溯至最近的一个活节点；若为否，则该新节点成为活节点，同时也成为当前的扩展节点，根节点不再是扩展节点。继续向纵深方向考虑第二个部件从第一个供应商处购买，得到一个新节点。同样判断当前的机器价格(C 11 +C 21 )是否超过上限(cc)，重量(W 11 +W 21 )是否比当前已知的解(最小重量)大。若为是，应回溯至最近的一个活节点；若为否，则该新节点成为活节点，同时也成为当前的扩展节点，原来的节点不再是扩展节点。以这种方式递归地在解空间中搜索，直到找到所要求的解或者解空间中已无活节点为止。 C 语言代码 下面是该算法的 C 语言实现。 (1)变量说明 n：机器
9、的部件数。 m：供应商数。 cc：价格上限。 w：二维数组，wij表示第 j 个供应商供应的第 i 个部件的重量。 c：二维数组，cij表示第 j 个供应商供应的第 i 个部件的价格。 best1W：满足价格上限约束条件的最小机器重量。 bestC：最小重量机器的价格。 bestX：最优解，一维数组，bestXi表示第 i 个部件来自哪个供应商。 cw：搜索过程中机器的重量。 cp：搜索过程中机器的价格。 x：搜索过程中产生的解，xi表示第 i 个部件来自哪个供应商。 i：当前考虑的部件，从 0 到 n-1。 j：循环变量。 (2)函数 backtrack int n=3; int m=3;
10、int cc=4; int w33=1,2,3,3,2,1,2,2,2); int c33=1,2,3,3,2,1,2,2,2; int bestW=8; int bestC=0; int bestX3=0,0,0; int cw=0; int cp=0; int x3=0,0,0; int backtrack(int i) int j=0; int found=0; if(in-1)/*得到问题解*/ bestW=cw; bestC=cp; for(j=0;jn;j+)( _; return 1; if(cp=cc)/*有解*/ found=1; for(j=0;_;j+) /*第 i 个部
11、件从第 j 个供应商购买*/ _; cw=cw+wij; cp=cp+cij; if(cp=cc /*回溯*/ cw=cw-wij; _; return found; （分数：25.00）_四、试题四(总题数：1，分数：25.00)阅读下列说明和 C 代码，回答下面问题。 说明 某应用中需要对 100000 个整数元素进行排序，每个元素的取值在 05 之间。排序算法的基本思想是：对每一个元素 x，确定小于等于 x 的元素个数(记为 m)，将 x 放在输出元素序列的第 m 个位置。对于元素值重复的情况，依次放入第 m-1、m-2个位置。例如，如果元素值小于等于 4 的元素个数有 10 个，其中元
12、素值等于 4 的元素个数有 3 个，则 4 应该在数据元素序列的第 10 个位置、第 9 个位置和第 8 个位置上。算法具体的步骤为： 步骤 1：统计每个元素值的个数。 步骤 2：统计小于等于每个元素值的个数。 步骤 3：将输入元素序列中的每个元素放入有序的输出元素序列。 C 代码 下面是该排序算法的 C 语言实现。 (1)常量和变量说明 R：常量，定义元素取值范围中的取值个数，如上述应用中 R 值应取 6。 i：循环变量。 n：待排序元素个数。 a：输入数组，长度为 n。 b：输出数组，长度为 n。 c：辅助数组，长度为 R，其中每个元素表示小于等于下标所对应的元素值的个数。 (2)函数 s
13、ort void sort(int n,int a ,int b ) int cR, i; for(i=0;i_; i+) ci=0; for(i=0;in;i+) cai=_; for(i=0; iR; i+) ci=_; for(i=0;in; i+) bcai-1=_; cai=cai-1; （分数：24.99）(1).根据说明和 C 代码，填充 C 代码中的空缺。（分数：8.33）_(2).根据 C 代码，函数的时间复杂度和空间复杂度分别为_和_(用 O 符号表示)。（分数：8.33）_(3).根据以上 C 代码，分析该排序算法是否稳定。若稳定，请简要说明(不超过 100 字)；若不稳
14、定，请修改其中代码使其稳定(给出要修改的行号和修改后的代码)。（分数：8.33）_软件设计师-27 答案解析(总分：99.97，做题时间：90 分钟)一、试题一(总题数：1，分数：25.00)阅读下列说明和 C 代码，回答下面问题。 说明 用两台处理机 A 和 B 处理 n 个作业。设 A 和 B 处理第 i 个作业的时间分别为 a i 和 b i 。由于各个作业的特点和机器性能的关系，对某些作业，在 A 上处理时间长，而对某些作业在 B 上处理时间长。一台处理机在某个时刻只能处理一个作业，而且作业处理是不可中断的，每个作业只能被处理一次。现要找出一个最优调度方案，使得 n 个作业被这两台处理
15、机处理完毕的时间(所有作业被处理的时间之和)最少。 算法步骤： (1)确定候选解上界为最短的单台处理机处理所有作业的完成时间 m， （分数：24.99）(1).根据以上说明和 C 代码，填充 C 代码中的空。（分数：8.33）_正确答案：()解析：pxy0=1；pxyk=px-ak-1yk-1；y-bk-1=0 pxyn=1，或 pxyn或 pxyn!=0； (x=y)?x:y 解析 本题考查独立任务最优调度问题，也称双机调度，是一种动态规划算法。 从 schedule()函数的第一个程序段可以看出，该段程序主要进行初始化第一个作业，下标从 0 开始，即pxy0=1，内层循环里的 pxyk=0
16、 用于初始化后面的 n-1 个作业。第二个程序段是对后面的 n-1 个作业，确定 p(x,y,k)的值。x-ak-1=0 的判定条件若成立，则表示第 k 个作业由机器 A 处理，完成 k-1 个作业时机器 A 花费的时间是 x-ak-1，即 pxyk=px-ak-1yk-1。第三处要求填入一判定条件，由其后的执行语句可知，第 k 个作业由机器 B 处理，因此判定条件应为 y-bk-1=0。 write()程序段用于确定最优解并输出结果，即得到最短处理时间 min(max(x,y)。第四处的判定条件是任务 n 完成，因此为 pxyn=1 或其等价形式。(5)处表达式为 max(x,y)或者(x=
17、y)?x:y。(2).根据以上 C 代码，算法的时间复杂度为_(用 O 符号表示)。（分数：8.33）_正确答案：()解析：O(m 2 n) 解析 从程序的循环层数即可看出算法的时间复杂度。程序的最高循环层数为 3 层。最外层循环变量的变化范围是 1n-1，次外层循环变量的变化范围是 0m，内层循环变量的变化范围是0m，所以时间复杂度为 O(m 2 n)。(3).考虑 6 个作业的实例，各个作业在两台处理机上的处理时间如下表所示。该实例的最优解为_，最优解的值(即最短处理时间)为_。最优解用(x1,x2,x3,x4,x5,x6)表示，其中若第 i 个作业在 A 上处理，则 x i =1，否则
18、x i =2。如(1，1，1，1，2，2)表示作业 1，2，3 和 4 在 A 上处理，作业 5 和 6在 B 上处理。 作业 1 作业 2 作业 3 作业 4 作业 5 作业 6 处理机 A 2 5 7 10 5 2 处理机 B 3 8 4 11 3 4 （分数：8.33）_正确答案：()解析：(1,1,2,2,1,1); 15 解析 为了方便考生更好地理解本算法的思想，现做如下分析： 当完成 k 个作业，设机器 A 花费了 x 时间，机器 B 所花费时间的最小值肯定是 x 的一个函数，设 Fkx表示机器 B 所花费时间的最小值，则 Fkx=MinFk-1x+bk，Fk-1x-ak。其中 F
19、k-1x+bk表示第 k 个作业由机器 B 来处理(完成 k-1 个作业时机器 A 花费的时间仍是 x)，Fk-1x-ak表示第 k 个作业由机器 A 处理(完成 k-1 个作业时机器 A 花费的时间是 x-ak)。 那么单个点对较大值 max(x，Fkx)，表示此时(即机器 A 花费 x 时间的情况下)所需要的总时间。而机器 A 花费的时间 x 是变化的，即 x=0,1,2x(max)，由此构成了点对较大值序列。要求整体时间最短，取这些点对较大值序列中最小的即是。现分析前两个作业的情况： 对于第一个作业：下标从 0 开始。 首先，机器 A 所花费时间的所有可能值范围：0=x=a0。 设 x0
20、 时，设 F0x=，则 max(x，)=。记法意义如下。 x=0 时，F00=3，则 max(0,3)=3，机器 A 花费 0 时间，机器 B 花费 3 时间，而此时两个机器所需时间为 3。 x=1 时，F01=3，max(1,3)=3。 x=2 时，F02=0，则 max(2,0)=2。 那么上面的点对序列中，可以看出当 x=2 时，完成第一个作业两台机器花费最少的时间为 2，此时机器 A花费 2 时间，机器 B 花费 0 时间。 再来看第二个作业。 首先，x 的取值范围是：0=x=(a0+a1)。 当 x0 时，记 F1x=。这个记法编程使用，因为数组下标不能小于 0。在这里的实际含义是：
21、x 是代表完成前两个作业机器 A 的时间，a1是机器 A 完成第 2 个作业的时间，若 xa1，则势必第 2 个作业由机器 B 来处理，即在 min()中取前者。 x=0，则 F10=minF00+b2,F00-a1)=min3+8,=11，进而 max(0,11)=11。 x=1，则 F11=minF01+b2,F01-a1=min3+8,=11，进而 max(11)=11。 x=2，则 F12=minF02+b2,F02-a1=min0+8,=8，进而 max(2,8)=8。 x=3，则 F13=minF03+b2,F03-a1=min0+8,=8，进而 max(3,8)=8。 x=4，则
22、 F14=minF04+b2,F04-a1=min0+8,=8，进而 max(4,8)=8。 x=5，则 F15=minF05+b2,F05-a1=min0+8,3=3，进而 max(5,3)=5。 x=6，则 F16=minF06+b2,F06-a1=min0+8,3=3，进而 max(6,3)=6。 x=7，则 F17=minF07+b2,F07-a1=min0+8,0=0，进而 max(7,0)=7。 那么上面的点对序列中，可以看出当 x=5 时，完成两个作业两台机器花费最少的时间为 5，此时机器 A 花费 5 时间，机器 B 花费 3 时间。 接下来依次类推即可，最终该实例的最优解为(
23、1,1,2,2,1,1)，最短处理时间为 15。这里提供当各个作业完成时的最短处理时间，考生可自行推导：2，5，7，12，14，15。二、试题二(总题数：1，分数：25.00)阅读下列说明和 C 代码，回答下面问题。 说明 设有 n 个货物要装入若干个容重为 C 的集装箱以便运输，这 n 个货物的体积分别为s1,s2,sn，且有siC(1in)。为节省运输成本，用尽可能少的集装箱来装运这 n 个货物。 下面分别采用最先适宜策略和最优适宜策略来求解该问题。 最先适宜策略(firstfit)首先将所有的集装箱初始化为空，对于所有货物，按照所给的次序，每次将一个货物装入第一个能容纳它的集装箱中。 最
24、优适宜策略(bestfit)与最先适宜策略类似，不同的是，总是把货物装到能容纳它且目前剩余容重最小的集装箱，使得该箱子装入货物后闲置空间最小。 C 代码 下面是这两个算法的 C 语言核心代码。 (1)变量说明 n：货物数。 C：集装箱容量。 s：数组，长度为 n，其中每个元素表示货物的体积，下标从 0 开始。 b：数组，长度为 n，bi表示第 n+i 个集装箱当前已经装入货物的体积，下标从 0 开始。 j：循环变量。 k：所需的集装箱数。 min：当前所用的各集装箱装入了第 i 个货物后的最小剩余容量。 m：当前所需的集装箱数。 temp：临时变量。 (2)函数 firstfit int fi
25、rstfit() int i,j; k=0; for(i=0;in; i+) bi=0; for(i=0;in;i+) _; while(c-bjsi) j+; _; k=k(j+1)?k:(j+1); return k; (3)函数 bestfit int bestfit() int i,j,min,m, temp; k=0; for(i=0;in;i+) bi=0; for(i=0;in;i+) min=C; m=k+1; for(j=0;jk+1;j+) temp=C-bj-si; if(temp0 m=j; _; k=k(j+1)?k:(j+1); return k; （分数：24.9
26、9）(1).根据说明和C 代码，填充 C 代码中的空。（分数：8.33）_正确答案：()解析：j=0；bj=bj+si；min=temp；bm=bm+si 解析 本题考查算法的 C 语言实现、时间复杂度的计算及应用，试题本身具有一定的难度。 本题描述的算法包括最先适宜算法和最优适宜算法。其中，最先适宜算法要求按顺序给货物找到一个能容纳它的集装箱，找到即可装箱。这里的关键在于找到第一个能容纳它的集装箱，从头到尾遍历各集装箱即可。firstfit 函数用于实现最先适宜算法。定位到第一个空处，其上面的 for 循环用于对所有 n 个货物进行遍历，分别找出满足条件 C-bj=si的集装箱。但条件 C-
27、bjsi中的变量 j 在第一个空前并没有显式的赋值语句，且遍历各集装箱应从第一个开始，因此第一个空应填入 j=0。第二处表示货物已放入集装箱的情况，应更新装入货物后的体积，因此第二处应填入 bj=bj+si。 最优适宜算法不仅要找到能容纳货物的集装箱，而且还要求该集装箱的剩余容量最小。bestfit 函数用于实现最优适宜算法。该函数的 for 循环语句中的 temp 表示剩余的最小容量，若其小于 min，则应更新其值。因此，第三个空应填入 min=temp。和 firstfit 函数中第二空类似的思路，第四空应填入 bm=bm+si。(2).根据说明和C 代码，该问题在最先适宜和最优适宜策略下
28、分别采用了_和_算法设计策略，时间复杂度分别为_和_(用 O 符号表示)。（分数：8.33）_正确答案：()解析：贪心 贪心 O(n 2 ) O(n 2 ) 解析 贪心算法在解决最优化问题上是仅根据当前已有的信息作出选择，即不是从整体最优考虑，它所作出的选择只是力求局部最优。最先适宜策略和最优适宜策略均采用了该算法设计策略。 对于时间复杂度，应根据程序中循环的层数及每层循环的次数来进行计算。可以很容易地判断，这两种算法的时间复杂度均为 O(n 2 )。(3).考虑实例 n=10，C=10，各个货物的体积为4,2,7,3,5,4,2,3,6,2。该实例在最先适宜和最优适宜策略下所需的集装箱分别为
29、_和_。考虑一般的情况，这两种求解策略能否确保得到最优解?_(是或否)（分数：8.33）_正确答案：()解析：5 4 否 解析 本问题考查对程序的具体理解和应用。 对 firstfit 函数进行遍历的结果如下。 1 bj k 0 b0=4 1 1 b0=6 1 2 b1=7 2 3 b1=10 2 4 b2=5 3 5 b2=9 3 6 b3=2 4 7 b3=5 4 8 b4=6 5 9 b4=8 5 因此，该实例在最先适宜策略下所需的集装箱数为 5。同理可对 bestfit 函数进行遍历，可得到该实例在最优适宜策略下所需的集装箱数为 4，遍历过程可由考生自己进行，以增强对整个算法的理解。
30、由于贪心算法在解决最优化问题上是仅根据当前已有的信息作出选择，即不是从整体最优考虑，它所作出的选择只是力求局部最优，因此这两种求解策略不能确保得到最优解。三、试题三(总题数：1，分数：25.00)1.阅读下列说明和 C 语言代码，将应填入空格处的字句写在下面。 说明 设某一机器由 n 个部件组成，每一个部件都可以从 m 个不同的供应商处购得。供应商 j 供应的部件 i 具有重量 W ij 和价格 C ij 。设计一个算法，求解总价格不超过上限 cc 的最小重量的机器组成。 采用回溯法来求解该问题： 首先定义解空间。解空间由长度为 n 的向量组成，其中每个分量取值来自集合1，2，m，将解空间用树
31、形结构表示。 接着从根节点开始，以深度优先的方式搜索整个解空间。从根节点开始，根节点成为活节点，同时也成为当前的扩展节点。向纵深方向考虑第一个部件从第一个供应商处购买，得到一个新节点。判断当前的机器价格(C 11 )是否超过上限(cc)，重量(W 11 )是否比当前已知的解(最小重量)大，若为是，应回溯至最近的一个活节点；若为否，则该新节点成为活节点，同时也成为当前的扩展节点，根节点不再是扩展节点。继续向纵深方向考虑第二个部件从第一个供应商处购买，得到一个新节点。同样判断当前的机器价格(C 11 +C 21 )是否超过上限(cc)，重量(W 11 +W 21 )是否比当前已知的解(最小重量)大
32、。若为是，应回溯至最近的一个活节点；若为否，则该新节点成为活节点，同时也成为当前的扩展节点，原来的节点不再是扩展节点。以这种方式递归地在解空间中搜索，直到找到所要求的解或者解空间中已无活节点为止。 C 语言代码 下面是该算法的 C 语言实现。 (1)变量说明 n：机器的部件数。 m：供应商数。 cc：价格上限。 w：二维数组，wij表示第 j 个供应商供应的第 i 个部件的重量。 c：二维数组，cij表示第 j 个供应商供应的第 i 个部件的价格。 best1W：满足价格上限约束条件的最小机器重量。 bestC：最小重量机器的价格。 bestX：最优解，一维数组，bestXi表示第 i 个部件
33、来自哪个供应商。 cw：搜索过程中机器的重量。 cp：搜索过程中机器的价格。 x：搜索过程中产生的解，xi表示第 i 个部件来自哪个供应商。 i：当前考虑的部件，从 0 到 n-1。 j：循环变量。 (2)函数 backtrack int n=3; int m=3; int cc=4; int w33=1,2,3,3,2,1,2,2,2); int c33=1,2,3,3,2,1,2,2,2; int bestW=8; int bestC=0; int bestX3=0,0,0; int cw=0; int cp=0; int x3=0,0,0; int backtrack(int i) in
34、t j=0; int found=0; if(in-1)/*得到问题解*/ bestW=cw; bestC=cp; for(j=0;jn;j+)( _; return 1; if(cp=cc)/*有解*/ found=1; for(j=0;_;j+) /*第 i 个部件从第 j 个供应商购买*/ _; cw=cw+wij; cp=cp+cij; if(cp=cc /*回溯*/ cw=cw-wij; _; return found; （分数：25.00）_正确答案：()解析：bestXj=xj jm xi=j cwbestW cp=cp-cij 解析 本题中机器需要 3 个部件，共 3 个供应商
35、，每个供应商可提供 3 种部件，供应商0 提供的 3 个部件数量分别为 1、2、3，价格分别为 1、2、3；供应商 1 提供的 3 个部件数量分别为3、2、1，价格分别为 3、2、1；供应商 2 提供的 3 个部件数量分别为 2、2、2，价格分别为 2、2、2。 价格上限为 4；初始时，满足价格上限约束条件的最小机器重量为 8，最小重量机器的价格为 0。 在回溯过程中，先购买第 0 个部件，首选选择第 0 个供应商的部件 0，计算总重量和总价格，如果总价值不大于上限 cc，则扩展当前节点；然后购买第 1 个部件，同样先选择第 0 个供应商的部件 1，计算总重量和总价格，如果总价值不大于上限 c
36、c，则扩展当前节点如果当前总价格大于上限 cc 或者当前总重量比已知的最小重要大，则当前节点成为死节点，返回前一次购买部件所在的节点，同时更新总价值和总重量。因此可将空补充完整，代码如下。 for(j=0; jm; j+) /*第 i 个部件从第 j 个供应商购买*/ xi=j; cw=cw+wij; cp=cp+cij; if(cp=cc /*回溯*/ cw=cw-wij; cp=cp-cij; 如果得到问题解，将部件的总质量和总价值保存在变量 bestW 和 bestC 中，并将部件的来源保存在数组bestX 中。数组 x 中保存搜索过程中产生的解，把 x 中的元素值赋给数组 bestX
37、即可，因此空处应填入bestXj=xj。四、试题四(总题数：1，分数：25.00)阅读下列说明和 C 代码，回答下面问题。 说明 某应用中需要对 100000 个整数元素进行排序，每个元素的取值在 05 之间。排序算法的基本思想是：对每一个元素 x，确定小于等于 x 的元素个数(记为 m)，将 x 放在输出元素序列的第 m 个位置。对于元素值重复的情况，依次放入第 m-1、m-2个位置。例如，如果元素值小于等于 4 的元素个数有 10 个，其中元素值等于 4 的元素个数有 3 个，则 4 应该在数据元素序列的第 10 个位置、第 9 个位置和第 8 个位置上。算法具体的步骤为： 步骤 1：统计
38、每个元素值的个数。 步骤 2：统计小于等于每个元素值的个数。 步骤 3：将输入元素序列中的每个元素放入有序的输出元素序列。 C 代码 下面是该排序算法的 C 语言实现。 (1)常量和变量说明 R：常量，定义元素取值范围中的取值个数，如上述应用中 R 值应取 6。 i：循环变量。 n：待排序元素个数。 a：输入数组，长度为 n。 b：输出数组，长度为 n。 c：辅助数组，长度为 R，其中每个元素表示小于等于下标所对应的元素值的个数。 (2)函数 sort void sort(int n,int a ,int b ) int cR, i; for(i=0;i_; i+) ci=0; for(i=0
39、;in;i+) cai=_; for(i=0; iR; i+) ci=_; for(i=0;in; i+) bcai-1=_; cai=cai-1; （分数：24.99）(1).根据说明和 C 代码，填充 C 代码中的空缺。（分数：8.33）_正确答案：()解析：R； cai+1； ci+ci-1； ai 解析 在函数 sort 中，首先对辅助数组 C 进行初始化，将 R 个元素全部初始化为 0，代码为： for(i=0;iR;i+) ci=0; 然后，统计每个元素值的个数，元素的个数保存数组 c 中，c 的下标表示对应的元素。通过循环读取元素ai，每读取到一个 ai，cai的值变加 1，代码
40、如下： for(i=0; in;i+) cai=cai+1; 接下来统计小于等于每个元素值的个数，用 ci保存。输入数组的每个元素的取值在 05 之间，即有 6种取值，0、1、2、3、4、5，则 c0保存的是值为 0 的元素个数，c1保存的是值为 1 的元素个数，以此类推，c5保存的是值为 5 的元素个数。则小于等于 0 的元素个数有 c0个，小于等于 1 的元素有 c0+c1个，小于等于 2 的元素有 c0+c1+c2个，依次类推，小于等于 5 的元素个数为 c0+c1+c2+c3+c4+c5。代码为： for(i=0; iR; i+) ci=ci+ci-1; 最后，将输入元素序列中的每个元素放入有序的输出元素序列。小于等于 ai的元素有 cai个，由于c 语言中，数组的下标从 0 开始，每读取的一个值为 aj的元素，应保存到 bcai-1，然后将 cai的值减 1
