1、软件水平考试中级软件设计师下午应用技术（算法设计和分析）历年真题试卷汇编 1及答案与解析 一、必答题（共 4道大题，每道大题 15分） 0 (2013年下半年下午试题四 )阅读下列说明和 C代码，回答问题 1至问题 3，将解答写在答题纸的对应栏内。 【说明】 某工程计算中要完成多个矩阵相乘 (链乘 )的计算任务。 两个矩阵相乘要求第一个矩阵的列数等于第二个矩阵的行数，计算量主要由进行乘法运算的次数决定。采用标准的矩阵相乘算法，计算 Amn*Bnp，需要 m*n*p次乘法运算。 矩阵相乘满足结合律，多个矩阵相乘，不同的计算 顺序会产生不同的计算量。以矩阵 A110100， A21005， A35
2、50三个矩阵相乘为例，若按(A1*A2)*A3计算，则需要进行 10*100*5+10*5*50=7500次乘法运算；若按A1*(A2*A3)计算，则需要进行 100*5*50+10*100*50=75000次乘法运算。可见不同的计算顺序对计算量有很大的影响。 矩阵链乘问题可描述为：给定 n个矩阵A1， A2， ， An，矩阵 Ai的维数为 pi-1p i，其中 i=1， 2， ， n。确定一种乘法顺序，使得这 n个矩阵相乘时进行乘法的运算次数最少。 由 于可能的计算顺序数量非常庞大，对较大的 n，用蛮力法确定计算顺序是不实际的。经过对问题进行分析，发现矩阵链乘问题具有最优子结构，即若 A1*
3、A2*An 的一个最优计算顺序从第 k个矩阵处断开，即分为 A1*A2*Ak 和 Ak+1*Ak+2*An 两个子问题，则该最优解应该包含 A1*A2*Ak 的一个最优计算顺序和 Ak+1*Ak+2*An 的一个最优计算顺序。据此构造递归式式中，costij表示 Ai+1*Ai+2*Aj+1 的最优计算的计算代价。最终需要求解 cost0n-1。 【 C代码】 算法实现采用自底向上的计算过程。首先计算两个矩阵相乘的计算量，然后依次计算 3个矩阵、 4个矩阵、 、 n个矩阵相乘的最小计算量及最优计算顺序。下面是该算法的 C语言实现。 (1)主要变量说明 n：矩阵数 seq：矩阵维数序列 cost
4、：二维数组，长度为 n*n，其中元素 costij表示Ai+1*Ai+2*Aj+1 的最优计算的计算代价 trace：二维数组，长度为 n*n，其中元素 traceij表示 Ai+1*Ai+2*Aj+1 的最优计算对应的划分位置，即 k (2)函数 cmm#define N 100int costNN； int traceNN； int cmm(int n， int seq) int tempCost； int tempTrace； int i， j， k， p； int temp； for(i=0； i n；i+) costii=0； for(p=1； p n； p+) for(i=0； _
5、(1)； i+) _(2)； tempCost=-1； for(k=i； k j； k+) temp=_(3)； if(tempCost=-1 tempCost temp) tempCost=temp； _(4)； costij=tempCost； traceij=tempTrace； return cost0n-1； 1 根据以上说明和 C代码，填充 C代码中的空 (1) (4)。 2 根据以上说明和 C代码，该问题采用了 _(5)算法设计策略，时间复杂度为_(6)(用 O符号表示 )。 3 考虑实例 n=6，各个矩阵的维数： A1为 5*10， A2为 10*3， A3为 3*12， A4
6、为12*5， A5为 5*50， A6为 50*6，即维数序列为 5， 10， 3， 12， 5， 50， 6。则根据上述 C代码得到的一个最优计算顺序为 _(7)(用加括号方式表示计算顺序 )，所需要的乘法运算次数为 _(8)。 3 (2013年上半年下午试题四 )阅读下列说明和 C代码，回答问题 1至问题 3，将解答写在答题纸的对应栏内。 【说明】 设有 m台完全相同的机器运行 n个独立的任务，运行任务 i所需要的时间为 tI，要求确定一个调度方案，使得完成所有任务所需要的时间最短。 假 设任务已经按照其运行时间从大到小排序，算法基于最长运行时间作业优先的策略；按顺序先把每个任务分配到一台
7、机器上，然后将剩余的任务一次放入最先空闲的机器。 【 C代码】 下面是算法的 C语言实现。 (1)常量和变量说明 m：机器数 n：任务数 t：输入数组，长度为 n，其中每个元素表示任务的运行时间，下标从 0开始 S：二维数组，长度为 mn，下标从 0开始，其中元素 siD表示机器 i运行的任务 j的编号 d：数组，长度为 m，其中元素 di表示机器 i的运行时间，下标从 0开始 count：数组，长 度为 m，下标从 0开始，其中元素 counti表示机器 i运行的任务数 i：循环变量 j：循环变量 k：临时变量 max：完成所有任务的时间 min：临时变量 (2)函数 schedule vo
8、id Schedule() int i,j， k，max=0； for(i=0;i m;i+) di=0； for(j=0； j n； j+) sij=0； for(i=0； im;i+) 分配前 m个任务 si0=i； _(1) counti=1; for(_(2)； in； i+) 分配后 n-m个任务 int min=d0； k=0； for(j=1； j m； j+) 确定空闲机器 if(min dj) min=dj； k=j； 机器 k空闲 _(3); countk=countk+1； dk=dk+ti; for(i=0； i m； i+) 确定完成所有任务所需要的时间 if(_(4
9、) max=di; 4 根据说明和 C代码，填充 C代码中的空 (1) (4)。 5 根据说明和 C代码，该问题采用了 _(5)算法设计策略，时间复杂度为_()(用 O符号表示 )。 6 考虑实例 m=3(编号 0 2)， n=7(编号 0 6)，各任务的运行时间为 16， 14， 6，5， 4， 3， 2。则在机器 0、 1和 2上运行的任务分别为 _(7)、 _(8)和_(9)(给出任务编号 )。从任务开始运行到完成所需要的时间为 _(10)。 6 (2021年下半年下午试题四 )阅读下列说明和 C代码，回答问题 1至问题 3，将解答写在答题纸的对应栏 内。 【说明】 设有 n个货物要装入
10、若干个容重为 C的集装箱以便运输，这 n个货物的体积分别为 s1， s2， ， sn，且有 siC(1in)。为节省运输成本，用尽可能少的集装箱来装运这 n个货物。 下面分别采用最先适宜策略和最优适宜策略来求解该问题。 最先适宜策略 (firstfit)首先将所有的集装箱初始化为空，对于所有货物，按照所给的次序，每次将一个货物装入第一个能容纳它的集装箱中。 最优适宜策略 (bestfit)与最先适宜策略类似，不同的是，总是把货物装到能容纳它且 目前剩余容重最小的集装箱，使得该箱子装入货物后闲置空间最小。 【 C代码】 下面是这两个算法的 C语言核心代码。 (1)变量说明 n：货物数 C：集装箱
11、容量 s：数组，长度为 n，其中每个元素表示货物的体积，下标从 0开始 b：数组，长度为 n， bi表示第 n+i个集装箱当前已经装入货物的体积，下标从 0开始 i， j：循环变量 k：所需的集装箱数 min：当前所用的各集装箱装入了第 i个货物后的最小剩余容量 m：当前所需的集装箱数 temp：临时变量 (2)函数 firstfit int firstfit() int i， j； k=0； for(i=0； i n； i+) bi=0; for(i=0； i n； i+) _(1); while(C-bj si) j+； _(2)； k=k (j+1)?k： (j+1)； return k
12、； (3)函数 bestfit int bestfit() int i， j， min， m， temp; k=0； for(i=0； i n； i+) bi=0； for(i=0； i n； i+) min=C； m=k+1； for(j=0； j k+1;j+) temp=C-bj-si； if(temp 0 temp min) _(3); m=j; _(4)； k=k (j+1)?k： (j+1); return k； 7 根据【说明】和【 C代码】，填充 C代码中的空 (1) (4)。 8 根据【说明】和【 C代码】，该问题在最先适宜和最优适宜策略下分别采用了_(5)和 _(6)算法设
13、计策略，时间复杂度分别为 _(7)和盟 (用 O符号表示 )。 9 考虑实例 n=10， C=10，各个货物的体积为 4， 2， 7， 3， 5， 4， 2， 3， 6， 2。该实例在最先适宜和最优适宜策略下所需的集装箱分别为 _(9)和 _(10)。考虑一般的情况，这两种求解策略能否确保得到最优解 ?_(11)(能或 否 ) 9 (2012年上半年下午试题四 )阅读下列说明和 C代码，回答问题 1至问题 3，将解答写在答题纸的对应栏内。 【说明】 用两台处理机 A和 B处理 n个作业。设 A和B处理第 i个作业的时间分别为 ai和 bi。由于各个作业的特点和机器性能的关系，对某些作业，在 A
14、上处理时间长，而对某些作业，在 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，
15、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代码 #include stdio h int n， m;int a60，b60， p10010060;void read() *输入 n、 a、 b，求出 m，代码略 * void schedule() *求解过程 * int x， y，
16、 k； for(x=0； x =m； x+) for(y=0； y m；y+) _(1) for(k=1;k n； k+) pxyk=0； for(k=1； kn;k+) for(x=0； x =m； x+) for(y=0;y =m;y+) if(x-ak-1 =0)_(2)； if(_(3)pxyk=(pxyk pxy-bk-1k-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 10 根据以上说明和 C代码
17、，填充 C代码中的空 (1) (5)。 11 根据以上 C代码，算法的时间复杂度为 _(6)(用 O符号表示 )。 12 考虑 6个作业的实例，各个作业在两台处理机上的处理时间如表 9 5所示。该实例的最优解为 _(7)，最优解的值 (即最短处理时间 )为 _(8)。最优解用(x1， x2， x3， x4， x5， x6)表示，其中若第 i个作业在 A上处理，则 xi=1，否则i=2。如 (1， 1， 1， 1， 2， 2)表示作业 1， 2， 3和 4在 A上处理，作业 5和 6在 B上处理。软件水平考试中级软件设计师下午应用技术（算法设计和分析）历年真题试卷汇编 1答案与解析 一、必答题（
18、共 4道大题，每道大题 15分） 【知识模块】 算法设计和分析 1 【正确答案】 (1)i n-p (2)j=i+p (3)costik+costk+1j+seqi*seq1(+1*seq+1(4)tempTrace=k； 【试题解析】 上述算法中，第一个循环是给 n个 costii赋初值 0；第二个循环是个外循环，其循环变量 p是矩阵连乘的规模， (p=1时 )先计算出所有规模为 2的costi， i+1， (p=2)再计算出所有规模为 3的 costi， i+2， ，最后计算出来的即为我们所求的 cost1， n-1，所以空 (1)处应填入 i n-p；第三个循环是内循环，其循环变量 i表
19、示矩阵连乘的起始位置，即从 l， 1+1， ， i， 1+i， ，一直算到n-1， n，所以空 (2)处应填入 j=i+p；第四个循环用于计算 mincosti， j(ik j)，所以空 (3)处应填入 costik+costk+1j+seqi*seqk+1*seqi+1；空 (4)处用于追踪取得最小花费代价的 k值，应填入 tempTrace=k。 【知识模块】 算法设计和分析 2 【正确答案】 (5)动态规划 (6)O(n3) 【试题解析】 求 min(costik+costk+1j+Pi*Pk-1*Pj)要做 p次比较 (k=i，i+1， ， j，而 j=i+p)；而第 3层的循环 (f
20、or(k=i； k j； k+)要做 n-p次，故该循环执行完毕要做 p+n-p=n次比 较。第 2层的循环 for(i=0； i n p； i+)从 1做到 n-1，第 1层的循环 for(i=0； i n;+)从 1做到 n-1。故循环执行完毕要做 O(n3)比较，此即该算法的时间复杂度。 【知识模块】 算法设计和分析 3 【正确答案】 (7)(A1*A2)*(A3*A4)*(A5*A6) (8)2010 【试题解析】 根据以上分析可知，最优子序列为 (A1*A2)*(A3*A4)*(A5*A6)，所需要的乘法运算次数为 2010。 【知识模块】 算法设计和分析 【知识模块】 算法设计和分
21、析 4 【正确答案】 (1)di=di+ti(2)i=m(k)sk0=i(4)max di 【试题解析】 本题考查算法的设计和分析技术中的贪心算法。 贪心算法是一种不追求最优解，只希望得到较为满意解的方法。贪心算法一般可以快速得到满意的解，因为它省去了为找到最优解要穷尽所有可能而必须耗费的大量时间。贪心算法常以当前情况为基础做出最优选择，而不考虑各种可能的整体情况，所以贪心算法不要回溯。 根据上述思想和题中的说明，首先将 s和 d数组初始 化为 0，然后将前 m个运行时间最长的任务分给 m个机器，空 (1)处需要表示此时每个机器运行的时间，即当前已经运行的时间加上此时所运行任务的时间，可以推断
22、空 (1)处应填入di=di+ti。此后需将剩下的 n-m个任务按顺序分配给空闲的机器，故空 (2)处将i初始化为以 m为起始的仟务，即应填入 i=m。空 (3)处根据空闲的机器分配任务，所以需记录第 k个空闲机器所运行任务的编号，即应填入 sk0=i。空 (4)处已经完成了任务的运行，此处需要统计所有机器所运行任务的最长时间，机器 i的运行时间为 di，若有 di大于当前的最大时间 max，就将当前机器的运行时间di赋给 max，即应填入 max di。 【知识模块】 算法设计和分析 5 【正确答案】 (5)贪心 (6)O(2mn+2m) 【试题解析】 根据以上分析，该问题采用了贪心算法的策
23、略，而时间复杂度由算法中的两个嵌套 for循环和两个非嵌套 for循环确定，即为 O(2mn+2m)。 【知识模块】 算法设计和分析 6 【正确答案】 (7)0 (8)1、 5 (9)2、 3、 4、 6 (10)17 【试题解 析】 根据题中算法的思想，将前 i个任务分给三个机器，再将接下来的任务分给最先空闲的机器，故可知机器 0运行任务 0，机器 1运行任务 1、 5，机器 3运行任务 2、 3、 4、 6，且运行的最长时间为 17。 【知识模块】 算法设计和分析 【知识模块】 算法设计和分析 7 【正确答案】 (1)j=0 (2)bj=bj+si (3)min=temp (4)bm=bm
24、+si 【试题解析】 本题描述的算法包括最先适宜算法和最优适宜算法。其中，最先适宜算法要求按顺序给货物 找到一个能容纳它的集装箱，找到即可装箱。这里的关键在于找到第一个能容纳它的集装箱，从头到尾遍历各集装箱即可。 firstfit函数用于实现最先适宜算法。定位到空 (1)处，其上面的 for循环用于对所有 n个货物进行遍历，分别找出满足条件 C-bj =si的集装箱。但条件 C-bj si中的变量 j在空 (1)前并没有显式的赋值语句，且遍历各集装箱应从第一个开始，因此空 (1)处应填入 j=0。空 (2)处表示货物已放入集装箱的情况，应更新装入货物后的体积，因此空 (2)处应填入 bj=bj
25、+si。 最优适宜算法不仅要找到能容纳货物的集装箱，而且还要求该集装箱的剩余容量最小。 bestfit函数用于实现最优适宜算法。该函数的 for循环语句中的 temp表示剩余的最小容量，若其小于 min，则应更新其值。因此，空 (3)处应填入min=temp。和 firstfit函数中空 (2)处类似的思路，空 (4)处应填入 bm=bm+si。 【知识模块】 算法设计和分析 8 【正确答案】 (5)贪心 (6)贪心 (7)O(n2) (8)O(n2) 【试题解析】 贪心算法在解决最优化问题上是仅根据当前已有 的信息做出选择，即不是从整体最优考虑，它所做出的选择只是力求局部最优。最先适宜策略和
26、最优适宜策略均采用了该算法设计策略。 对于时间复杂度，应根据程序中循环的层数及每层循环的次数来进行计算。可以很容易地判断，这两种算法的时间复杂度均为 O(n2)。 【知识模块】 算法设计和分析 9 【正确答案】 (9)5 (10)4 (11)否 【试题解析】 本问题考查对程序的具体理解和应用。 对 firstfit函数进行遍历的结果如表 9 4所示。因此，该实例在最先适宜策略下所需的集装箱数为 5。同理可 对 bestfit函数进行遍历，可得到该实例在最优适宜策略下所需的集装箱数为 4，遍历过程可由考生自己进行，以增强对整个算法的理解。 由于贪心算法在解决最优化问题上是仅根据当前已有的信息做出
27、选择，即不是从整体最优考虑，它所做出的选择只是力求局部最优，因此这两种求解策略都不能确保得到最优解。 【知识模块】 算法设计和分析 【知识模块】 算法设计和分析 10 【正确答案】 (1)pxy0=1 (2)pxyk=px-ak-1yk-1 (3)y-bk-1 =0 (4)pxyn=1或 pxyn或 pxyn!=0 (5)(x =y)?x： y 【试题解析】 从 schedule()函数的第一个程序段可以看出，该段程序主要进行初始化第一个作业，下标以 0开始，即空 (1)处应填入 pxy0=1，内层循环里的pxyk=0用于初始化后面的 n-1个作业。第二个程序段是对后面的 n-1个作业，确定
28、p(x， y， k)的值。 x-ak-1 =0的判定条件若成立，则表示第 k个作业由机器 A处理，完成 k一 1个作业时机器 A花 费的时间是 x-ak-1，即空 (2)处应填入 pxyk=px-ak-1yk-1。空 (3)处要求填入一判定条件，由其后的执行语句可知，第 k个作业由机器 B处理，因此空 (3)处应填入 y-bk-1 =0。 write()程序段用于确定最优解并输出结果，即得到最短处理时间 min(max(x，y)。空 (4)处的判定条件是任务 n完成，因此应填入 pxyn=1或其等价形式。空 (5)处表达 max(x， y)，应填入 (x =y)?x： y。 【知识模块】 算法
29、设计和分析 11 【正确答案】 O(m2n) 【试题解析】 从程序的循环层数即可看出算法的时间复杂度。程序的最高循环层数为 3层。最外层循环变量的变化范围是 1 n-1，次外层循环变量的变化范围是0 m，内层循环变量的变化范围是 0 m，所以时间复杂度为 O(m2n)。 【知识模块】 算法设计和分析 12 【正确答案】 (7)(1， 1， 2， 2， 1， 1) (8)15 【试题解析】 为了方便考生更好地理解本算法的思想，现做如下分析。 当完成 k个作业，设机器 A花费了 x时间，机器 B所花费时间的最小值肯 定是x的一个函数，设 Fkx表示机器 B所花费时间的最小值，则 Fkx=MinFk
30、-1x+bk， Fk-1x-ak。其中， Fk-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， 2， ，x(max)，由此构成了点对较大值序列。要求整体时间最短，取这些点对较大值序列中最小的即可。现分析前两个作业的情况。 对于第一个作业：下标以 0开始。 首先，机器 A所花费时间的所有
31、可能值范围为 0 =x =a0。 x 0时，设 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)。 x 0时，记 F1x=；这个记法编程使用，因为数组下标不能
32、小于 0。在这里的实际含义是： x是代表完成前两个作业机器 A的时间， a1是机器 A完成第二个作业的时间，若 x a1，则势必第二个作业由机器 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(1， 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， =
33、8，进而 max(3，8)8。 x=4，则 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时间。 接下来依次类推即可，最终该实例的最优解为 (1， 1， 2， 2， 1， 1)，最短处理时间为 15。这里提供当各个作业完成时的最短处理时间，考生可自行推导： 2， 5，7， 12， 14， 15 【知 识模块】 算法设计和分析
