1、软件设计师-26 及答案解析(总分：99.96，做题时间：90 分钟)一、试题一(总题数：1，分数：25.00)阅读下列说明和 C 代码，回答下面问题。 说明 计算一个整数数组 a 的最长递增子序列长度，对其方法描述如下。 假设数组 a 的长度为 n，用数组 b 的元素 bi记录以 ai(0in)为结尾元素的最长递增子序列的长度为 max(0in)bi，其中 bi满足最优子结构，可递归定义为： （分数：24.99）(1).根据说明和 C 代码，填充 C 代码中的空。（分数：8.33）_(2).根据说明和 C 代码，算法采用了_设计策略，时间复杂度为_(用 O 符号表示)。（分数：8.33）_(
2、3).已知数组 a=3,10,5,15,6,8，据说明和 C 代码，给出数组 b 的元素值。（分数：8.33）_二、试题二(总题数：1，分数：25.00)阅读下列说明和 C 代码，回答下面问题。 说明 采用归并排序对 n 个元素进行递增排序时，首先将 n 个元素的数组分成各含 n/2 个元素的两个子数组，然后用归并排序对两个子数组进行递归排序，最后合并两个已经排序的子数组得到排序结果。 下面的 C 代码是对上述归并算法的实现，其中的常量和变量说明如下。 art：待排序数组。 p，q，r：一个子数组的位置从 p 到 q，另一个子数组的位置从 q+1 到 r。 begin，end：待排序数组的起止
3、位置。 left，right：临时存放待合并的两个子数组。 n1，n2：两个子数组的长度。 i，j，k：循环变量。 mid：临时变量。 C 代码 #inciudestdio.h #inciudestdlib.h Define MAX 65536 void merge(int art(,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
4、=(int*)malloc(n2+1)*sizeof(int)=NULL) Perror(“malloc error“); exit(1); for(i=0;in1;i+) lefti=artp+i; lefti=MAX; for(i=0;in2;i+) righti=arrq+i+1 righti=MAX; i=0;j=0; For(k=p;(1);k+) If(leftirightj _ j+; else arrk1=lefti; i+; Void merge Sort(int art(),int begin,int end) int mid; if(_) mid=(begin+end)/
5、2; merge Sort(art,begin,mid); _; Merge(arr,begin,mid,end); （分数：24.99）(1).根据以上说明和 C 代码，填充各个空。（分数：8.33）_(2).根据题干说明和以上 C 代码，算法采用了_算法设计策略，分析时间复杂度时，列出其递归式为_， 接触渐进时间复杂度_(用 O 符号表示)，空间复杂度为_(用 O 符号表示)。（分数：8.33）_(3).两个长度分别为 n1 和 n2 的已经排好序的子数组进行归并，根据上述 C 代码，则元素之间的比较次数为_。（分数：8.33）_三、试题三(总题数：1，分数：25.00)阅读下列说明和 C
6、 代码，回答下面问题。 说明 设有 m 台完全相同的机器运行 n 个独立的任务，运行任务 i 所需要的时间为 t i ，要求确定一个调度方案，使的完成所有任务所需要的时间最短。 假设任务已经按照其运行时间从大到小排序，算法基于最长运行时间作业优先的策略；按顺序先把每个任务分配到一台机器上，然后将剩余的任务一次放入最先空闲的机器。 C 代码 下面是算法的 C 语言实现。 (1)常量和变量说明 m：机器数。 n：任务数。 t：输入数组，长度为 n，其中每个元素表示任务的运行时间，下标从 0 开始。 s：二维数组，长度为 m*n，下标从 0 开始，其中元素 sij表示机器 i 运行的任务 j 的编号
7、。 d：数组，长度为 m 其中元素 di表示机器 i 的运行时间，下标从 0 开始。 count：数组，长度为 m，下标从 0 开始，其中元素 counti表示机器 i 运行的任务数。 i：循环变量。 i：循环变量。 k：临时变量。 max：完成所有任务的时间。 min：临时变量。 (2)函数 schedule void schedule() int i,j,k max=0; for(i=0; im;i+) di=0; for(j=0;jn;j+) sij=0; for(i=0;im;i+) /分配前 m 个任务 si0=i; _; counti=1; for(_;in;i+) /分配后 n-
8、m 个任务 int min=d0; k=0; for(j=1;jm;j+) /确定空闲机器 if(mindj) min=dj; k=j; /机器 k 空闲 _; countk=countk+1; dk=dk+ti; for(i=0;im;i+) /确定完成所有任务所需要的时间 if(_) max=di; （分数：24.99）(1).根据说明和 C 代码，填充 C 代码中的空。（分数：8.33）_(2).根据说明和 C 代码，该问题采用了_算法设计策略，时间复杂度为_(用 O 符号表示)（分数：8.33）_(3).考虑实例 m=3(编号 02)，n=7(编号 06)，各任务的运行时间为16,14
9、,6,5,4,3,2，则在机器0、1 和 2 上运行的任务分别为_、_和_(给出任务编号)。从任务开始运行到完成所需要的时间为_。（分数：8.33）_四、试题四(总题数：1，分数：25.00)阅读以下说明和 C 代码，根据要求回答问题。 说明 某工程计算中要完成多个矩阵相乘(链乘)的计算任务。 两个矩阵相乘要求第一个矩阵的列数等于第二个矩阵的行数，计算量主要由进行乘法运算的次数决定。采用标准的矩阵相乘算法，计算 A mn *B np ，需要 m*n*p 次乘法运算。 矩阵相乘满足结合律，多个矩阵相乘，不同的计算顺序会产生不同的计算量。以矩阵 A1 10100 ，A2 1005 ，A3 550
10、三个矩阵相乘为例，若按(A1*A2)*A3 计算，则需要进行 10*100*5+10*5*50=7500 次乘法运算；若按 A1*(A2*A3)计算，则需要进行 100*5*50+10*100*50=75000 次乘法运算。可见不同的计算顺序对计算量有很大的影响。 矩阵链乘问题可描述为：给定 n 个矩阵A1,A2,A n ，矩阵 4 的维数为 p i-1 p i ，其中i=1，2，n。确定一种乘法顺序，使得这 n 个矩阵相乘时进行乘法的运算次数最少。 由于可能的计算顺序数量非常庞大，对较大的 n，用蛮力法确定计算顺序是不实际的。经过对问题进行分析，发现矩阵链乘问题具有最优子结构，即若 A1*A
11、2*An 的一个最优计算顺序从第 k 个矩阵处断开，即分为 A1*A2*Ak 和 Ak+1*Ak+2*An 两个子问题，则该最优解应该包含 A1*A2*Ak 的一个最优计算顺序和 Ak+1*Ak+2*An 的一个最优计算顺序。据此构造递归式： （分数：24.99）(1).根据以上说明和 C 代码，填充 C 代码中的空。（分数：8.33）_(2).根据以上说明和 C 代码，该问题采用了_算法设计策略，时间复杂度为_(用 O 符号表示)。（分数：8.33）_(3).考虑实例 n=6，各个矩阵的维数：A1 为 5*10，A2 为 10*3，A3 为 3*12，A4 为 12*5，A5 为 5*50，
12、A6为 50*6，即维数序列为 5,10,3,12,5,50,6。则根据上述 C 代码得到的一个最优计算顺序为_(用加括号方式表示计算顺序)，所需要的乘法运算次数为_。（分数：8.33）_软件设计师-26 答案解析(总分：99.96，做题时间：90 分钟)一、试题一(总题数：1，分数：25.00)阅读下列说明和 C 代码，回答下面问题。 说明 计算一个整数数组 a 的最长递增子序列长度，对其方法描述如下。 假设数组 a 的长度为 n，用数组 b 的元素 bi记录以 ai(0in)为结尾元素的最长递增子序列的长度为 max(0in)bi，其中 bi满足最优子结构，可递归定义为： （分数：24.9
13、9）(1).根据说明和 C 代码，填充 C 代码中的空。（分数：8.33）_正确答案：()解析：本题考查最长递增序列问题，是一种动态规划法，也考查时间复杂度的计算。 b0=1 j=i aj=ai bi=len+1 解析 本题考查算法设计、分析技术以及算法的 C 语言实现，是比较传统的题目，要求考生细心分析题目中所描述的内容。 根据题中说明，b 数组记录最长递增子序列的长，故应初始化 b0=1，这是第一问的答案，初始 Len=0，接下来 a 中某个元素的值大于前面某个元素，则 Len+1 放进 b，故第二问为 j=i，第四问为 bi=Len+1。(2).根据说明和 C 代码，算法采用了_设计策略
14、，时间复杂度为_(用 O 符号表示)。（分数：8.33）_正确答案：()解析：动态规划法 O(n 2 ) 解析 算法将待求解问题分解成若干个子问题，先求子问题，然后从这些子问题的解中得到原问题的解，使用的是动态规划的思想，时间复杂度计算最坏情况下的运算次数，最坏情况时 i 和 j 都从 1跑到 n，故运算 n 的平方次，算法的时间复杂度为 O(n 2 )。(3).已知数组 a=3,10,5,15,6,8，据说明和 C 代码，给出数组 b 的元素值。（分数：8.33）_正确答案：()解析：=1,2,2,3,3,4解析 初始化 b0=1，a0=3，a1=10，进入时 b1=2，a2=5 进入时有3
15、,5 的序列，故 b2=2，a3=15，进入时有 3,10,15，故子序列为 3，a4=6 时，有子序列 3,5,6，故为3，当最后一个元素 8 进入时有 3,5,6,8，故 b5=4，所以 b=1,2,2,3,3,4。二、试题二(总题数：1，分数：25.00)阅读下列说明和 C 代码，回答下面问题。 说明 采用归并排序对 n 个元素进行递增排序时，首先将 n 个元素的数组分成各含 n/2 个元素的两个子数组，然后用归并排序对两个子数组进行递归排序，最后合并两个已经排序的子数组得到排序结果。 下面的 C 代码是对上述归并算法的实现，其中的常量和变量说明如下。 art：待排序数组。 p，q，r：
16、一个子数组的位置从 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 art(,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)*sizeo
17、f(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+) lefti=artp+i; lefti=MAX; for(i=0;in2;i+) righti=arrq+i+1 righti=MAX; i=0;j=0; For(k=p;(1);k+) If(leftirightj _ j+; else arrk1=lefti; i+; Void merge Sort(int ar
18、t(),int begin,int end) int mid; if(_) mid=(begin+end)/2; merge Sort(art,begin,mid); _; Merge(arr,begin,mid,end); （分数：24.99）(1).根据以上说明和 C 代码，填充各个空。（分数：8.33）_正确答案：()解析：k=r arrk=rightj beginend mergeSort(arr,mid+1,end) 解析 首先，函数 voidmerge(int arr,int p,int q,int r)的意思是：对子数组 arrpq和子数组 arrq+Lr进行合并，因此第一个空为
19、 k=q;由于是采用归并排序对 n 个元素进行递增排序，所以第二个空是将 lefti和 rightj的较小者存放到 arrk中去，即 arrk=rightj：当数组长度为 1 时，停止递归，因为此时该数组有序，则第三个空为 beginend，即数组至少有两个元素才进行递归，合并了 begin 到 mid 之间的元素，继续合并 mid+1 到 end 之间的元素，则第四个空为 mergeSort(arr,mid+1,end)。(2).根据题干说明和以上 C 代码，算法采用了_算法设计策略，分析时间复杂度时，列出其递归式为_， 接触渐进时间复杂度_(用 O 符号表示)，空间复杂度为_(用 O 符号
20、表示)。（分数：8.33）_正确答案：()解析：分治 T(n)=2T(n/2)+O(n) O(nlogn) O(n) 解析 归并算法实际上就是将数组一直往下分割，直到分割到由一个元素组成的 n 个子数组，再往上两两归并。 将数组进行分割需要 logn 步，因为每次都是将数组分割成两半(2 x =n，x=logn)。 合并 n 个元素，需要进行 n 步，也就是 O(n)，则总的时间复杂度为 O(nlogn)。 在合并过程中，使用了 n 个中间变量存储，left=(int*)malloc(n1+1)*sizeof(int)，所以空间复杂度为 O(n)。 推导递归式：假设 n 个元素进行归并排序需要
21、 T(n)，可以将其分割成两个分别包括 n/2 个元素的数组分别进行归并，也就是 2T(n/2)，在将这两个数组合并，需要 O(n)的时间复杂度，则推导公式为 T(n)=2T(n/2)+O(n)。(3).两个长度分别为 n1 和 n2 的已经排好序的子数组进行归并，根据上述 C 代码，则元素之间的比较次数为_。（分数：8.33）_正确答案：()解析：n1+n2 解析 假定有这样两个有序数组 L1:a1,a2,an和 L2:b1,b2,bn，简单归并，就是逐个比对，没有跳跃优化(skip)的。 在最好的情况下，归并后的结果为a1,a2,an,b1,b2,bn或者b1,b2,bn,a1,a2,an
22、，比较的次数显然为 n 次(n/2+n/2)，出现前者或者后者的概率均为 1/2 在最坏的情况下，归并后的结果为a1,b1,a2,b2,an,bn或者b1,a1,b2,a2,bn,an，不妨考察前者，L1 或 L2 中任意一个(除 bn 以外)要想确定自己的位置，必须进行一次比较，因此总的比较次数为 2n-1。 再考察平均情况：假定归并后的结果为b1,bra1,an-1|anbr+1,bn-1bn，这表示任意的b1br 共计 r 个来自 L2 的 b 序列，a1an-1 共计 n-1 个来自 L1 的 a 序列的数字组合成的一个串。 该串共计有 C(r+n-1，r)种可能性，这 r+n-1 个
23、数每个数要想确定自己的位置都需要进行一次比较，因此比较次数是 n+r 次，而 an 和 bn-r 相比，确定自己更小，还需要 1 次，因此总计的比较次数是 n+r，根据上述解释，若题目中有长度为 n1 和 n2 的两个有序数组进行归并，则总计的比较次数为 n1+n2。三、试题三(总题数：1，分数：25.00)阅读下列说明和 C 代码，回答下面问题。 说明 设有 m 台完全相同的机器运行 n 个独立的任务，运行任务 i 所需要的时间为 t i ，要求确定一个调度方案，使的完成所有任务所需要的时间最短。 假设任务已经按照其运行时间从大到小排序，算法基于最长运行时间作业优先的策略；按顺序先把每个任务
24、分配到一台机器上，然后将剩余的任务一次放入最先空闲的机器。 C 代码 下面是算法的 C 语言实现。 (1)常量和变量说明 m：机器数。 n：任务数。 t：输入数组，长度为 n，其中每个元素表示任务的运行时间，下标从 0 开始。 s：二维数组，长度为 m*n，下标从 0 开始，其中元素 sij表示机器 i 运行的任务 j 的编号。 d：数组，长度为 m 其中元素 di表示机器 i 的运行时间，下标从 0 开始。 count：数组，长度为 m，下标从 0 开始，其中元素 counti表示机器 i 运行的任务数。 i：循环变量。 i：循环变量。 k：临时变量。 max：完成所有任务的时间。 min：
25、临时变量。 (2)函数 schedule void schedule() int i,j,k max=0; for(i=0; im;i+) di=0; for(j=0;jn;j+) sij=0; for(i=0;im;i+) /分配前 m 个任务 si0=i; _; counti=1; for(_;in;i+) /分配后 n-m 个任务 int min=d0; k=0; for(j=1;jm;j+) /确定空闲机器 if(mindj) min=dj; k=j; /机器 k 空闲 _; countk=countk+1; dk=dk+ti; for(i=0;im;i+) /确定完成所有任务所需要的
26、时间 if(_) max=di; （分数：24.99）(1).根据说明和 C 代码，填充 C 代码中的空。（分数：8.33）_正确答案：()解析：di=di+ti;i=m;sk0=i;Maxdi 解析 本题考查算法的设计和分析技术中的贪心算法。贪心法是一种不追求最优解，只希望得到较为满意解的方法。贪心法一般可以快速得到满意的解，因为省去了为找到最优解要穷尽所有可能而必须耗费的大量时间。贪心法常以当前情况为基础做出最优选择，而不考虑各种可能的整体情况，所以贪心法不要回溯。 根据上述思想和题中的说明，首先将 s和 d数组初始化为 0，然后将前 m 个运行时间最长的任务分给 m 个机器，第一处中需要
27、表示此时每个机器运行的时间，即当前已经运行的时间加上此时所运行任务的时间，可以推断第一处为 di=di+ti，此后需将剩下的 n-m 个任务按顺序分配给空闲的机器，故第二处将 i 初始化为以 m 为起始的任务，即 i=m，第三处根据空闲的机器分配任务，所以需记录第 k 个空闲机器所运行任务的编号，即 sk0=i，第四处已经完成了任务的运行，此处需要统计所有机器所运行任务的最长时间，对于每个机器 i 的运行时间为 di，存在 di大于当前的最大时间 Max，就将当前机器的运行时间 di赋给 Max，即：Maxdi。(2).根据说明和 C 代码，该问题采用了_算法设计策略，时间复杂度为_(用 O
28、符号表示)（分数：8.33）_正确答案：()解析：贪心；O(2m*n+2m)解析 根据以上分析，第一处采用了贪心算法的策略，而时间复杂度由算法中的两个嵌套 for 循环和两个非嵌套 for 循环确定，即为 O(2m*n+2m)。(3).考虑实例 m=3(编号 02)，n=7(编号 06)，各任务的运行时间为16,14,6,5,4,3,2，则在机器0、1 和 2 上运行的任务分别为_、_和_(给出任务编号)。从任务开始运行到完成所需要的时间为_。（分数：8.33）_正确答案：()解析：0；1、5；2、3、4、6；17解析 根据题中算法的思想将前三个任务分给三个机器，再将接下来的任务分给最先空闲的
29、机器，故可知机器 0 运行任务 0，机器 1 运行任务 1、5，机器 2 运行任务2、3、4、6，且运行的最长时间为 17。四、试题四(总题数：1，分数：25.00)阅读以下说明和 C 代码，根据要求回答问题。 说明 某工程计算中要完成多个矩阵相乘(链乘)的计算任务。 两个矩阵相乘要求第一个矩阵的列数等于第二个矩阵的行数，计算量主要由进行乘法运算的次数决定。采用标准的矩阵相乘算法，计算 A mn *B np ，需要 m*n*p 次乘法运算。 矩阵相乘满足结合律，多个矩阵相乘，不同的计算顺序会产生不同的计算量。以矩阵 A1 10100 ，A2 1005 ，A3 550 三个矩阵相乘为例，若按(A
30、1*A2)*A3 计算，则需要进行 10*100*5+10*5*50=7500 次乘法运算；若按 A1*(A2*A3)计算，则需要进行 100*5*50+10*100*50=75000 次乘法运算。可见不同的计算顺序对计算量有很大的影响。 矩阵链乘问题可描述为：给定 n 个矩阵A1,A2,A n ，矩阵 4 的维数为 p i-1 p i ，其中i=1，2，n。确定一种乘法顺序，使得这 n 个矩阵相乘时进行乘法的运算次数最少。 由于可能的计算顺序数量非常庞大，对较大的 n，用蛮力法确定计算顺序是不实际的。经过对问题进行分析，发现矩阵链乘问题具有最优子结构，即若 A1*A2*An 的一个最优计算顺
31、序从第 k 个矩阵处断开，即分为 A1*A2*Ak 和 Ak+1*Ak+2*An 两个子问题，则该最优解应该包含 A1*A2*Ak 的一个最优计算顺序和 Ak+1*Ak+2*An 的一个最优计算顺序。据此构造递归式： （分数：24.99）(1).根据以上说明和 C 代码，填充 C 代码中的空。（分数：8.33）_正确答案：()解析：in-p；j=i+p；costik+costk+1j+seqi*seqk+1*seqj+1；tempTrace=k； 解析 本题考查矩阵连乘最优调度问题，是一种动态规划算法。 上述算法中，第一个循环是给 n 个 costii赋初值 0；第 2 个循环是个外循环，其循
32、环变量 p 是矩阵连乘的规模，p=1 时先计算出所有规模为 2 的 costi,i+1，p=2 时再计算出所有规模为 3 的costi,i+2最后计算出来的即为我们所求的 cost1，n-1，所以第一个处填 in-p；第 3 个循环是内循环，其循环变量 i 表示矩阵连乘的起始位置，即从 1，1+1，i，1+i一直算到 n-1，n，所以第二个处填 j=i+p；第 4 个循环用于计算 mincosti,j(ikj)，所以第三处填“costik+costk+1j+seqi*seqk+1*seqj+1;”，而第四个处用于追踪取得最小花费代价的 k 值，即tempTrace=k，而每一项的计算可在 O(
33、1)时间里完成。(2).根据以上说明和 C 代码，该问题采用了_算法设计策略，时间复杂度为_(用 O 符号表示)。（分数：8.33）_正确答案：()解析：动态规划；O(n3) 解析 求 min(ikj)要做 1 次比较(k=i，i+1i 而 j=i+1)，而第 3 行的循环要做 n-1 次，故该循环执行完毕要做 n-1 次比较，第 2 行的循环 i 从 1 做到 n-1，故该外循环执行完毕要做 O(n 3 )比较，此即该算法的时间复杂度。(3).考虑实例 n=6，各个矩阵的维数：A1 为 5*10，A2 为 10*3，A3 为 3*12，A4 为 12*5，A5 为 5*50，A6为 50*6
34、，即维数序列为 5,10,3,12,5,50,6。则根据上述 C 代码得到的一个最优计算顺序为_(用加括号方式表示计算顺序)，所需要的乘法运算次数为_。（分数：8.33）_正确答案：()解析：(A1*A2)*(A3*A4)*(A5*A6)；2010解析 启发式的思路是先把维度最大的消掉，如 A5*A6 相乘之后，维度 30 就没有了，所以考虑这两个矩阵先相乘；然后是 A3*A4 相乘之后，维度 12 就没有了，所以考虑这两个矩阵相乘；接着，A1*A2 相乘之后，维度 10 就没有了，所以考虑这两个矩阵相乘从而确定相乘的顺序(A1*A2)*(A3*A4)*(A5*A6)，需要的计算开销分别是5*50*6=1500，3*12*5=180，5*10*3=150，3*5*6=90，5*3*6=90，把上述值相加，即1500+180+150+90+90=2010。
