1、软件水平考试（中级）软件设计师下午（应用技术）历年真题试卷汇编 4及答案与解析 一、必答题（共 4道大题，每道大题 15分） 0 阅读下列说明和 C代码，回答问题 1至问题 3，将解答写在答题纸的对应栏内。 【说明】 设有 m台完全相同的机器运行 n个独立的任务，运行任务 i所需要的时间为 ti，要求确定一个调度方案，使的完成所有任务所需要的时间最短。假设任务已经按照其运行时间从大到小排序，算法基于最长运行时间作业优先的策略；按顺序先把每个任务分配到一台机器上，然后将剩余的任务一次放入最先空闲的机器。 【 C代码】 下面是算 法的 C语言实现。 (1)常量和变量说明 m：机器数 n：任务数 t
2、：输入数组，长度为 n，其中每个元素表示任务的运行时间，下标从 0开始 s：二维数组，长度为 m*n，下标从 oF始，其中元素 sii表示机器 i运行的任j的编号 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； idj)( min：dj； k=j； 机器 k空闲 (3)
3、 ； countk=countk+1； dk=dk+ti； for(i=0； i 1 根据说明和 C代码，填充 C代码中的空 (1) (4)。 2 根据说明和 C代码，该问题采用了 (5)算法设计策略，时间复杂度为 (6)(用 O符号表示 ) 3 考虑实例 m=3(编号 0 2)， n=7(编号 0 6)，各任务的运行时间为 16， 14， 6，5， 4， 3， 2。则在机器 0、 1和 2上运行的任务分别为 (7)、 (8)和 (9)(给出任务编号 )。从任务开始运行到完成所需要的时间为 (10)。 3 阅读以下说明和 C代码，根据要求回答问题 1问题 3。【说明】某工程计算中要完成多个矩阵
4、相乘 (链乘 )的计算任务。两个矩阵相乘要求第一个矩阵的列数等于第二个矩阵的行数，计算量主要由进行乘法运算的次数决定。采用标准的矩阵相乘算法，计算 Amn*Bnp，需要 m*n*p次乘法运算。矩阵相乘满足结合律，多个矩阵相乘，不同的计算顺序会产生不同的计算量。以矩阵 A110100， A21005， A3550三个矩阵相乘为例，若按 (A1*A2)*A3计算，则需要进行 10*100*5+10*5*50=7500次乘法运算；若按 A1*(A2*A3)计算，则需要进行 100*5*50+10*100*50=75000次乘法运算。可见不同的计算顺序对计算量有很大的影响。矩阵链乘问题可描述为：给定
5、n个矩阵 n，矩阵 Ai的维数为 Pi-1P i，其中 i=1， 2， ， n。确定一种乘法顺序，使得这 n个矩阵相乘时进行乘法的运算次数最少。由于可能的计算顺序数量非常庞大，对较大的 n，用蛮力法确定计算顺序是 不实际的。经过对问题进行分析，发现矩阵链乘问题具有最优子结构，即若 AI*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 的最优计算的计算
6、代价。最终需要求解cost0n1。【 C代码】算法实现采用自底向上的计算过程。首先计算两个矩阵相乘的计算量，然 后依次计算 3个矩阵、 4个矩阵 n 个矩阵相乘的最小计算量及最优计算顺序。下面是该算法的 C语言实现。 (1)主要变量说明 n：矩阵数seq：矩阵维数序列 cost：二维数组，长度为 n*n，其中元素 costij表示Ai+1*Ai+2*Aj+l 的最优计算的计算代价 trace：二维数组，长度为 n*n，其中元素 traceij表示 Ai+1*Ai+2： i： *Aj+1 的最优计算对应的划分位置，即 k (2)函数 cmm #define N 100 int cost NIN；
7、 int trace NN； int cmm(int n， int seq) int tempCost； int tempTrace； int i,j,k , P； int temp； for(i=0；itemp) tempCost=temp； (4) costij=tempCost； traceij=tempTrace： return cost0n1； 4 根据以上说和 C代码，填充 C代码中的空 (1) (4)。 5 根据以上说明和 C代码，该问题采用了 （ 5）算法设计策略，时间复杂度为(6)(用 0符号表示 )。 6 考虑实例 n=6，各个矩阵的维数： A1为 5*10， A2为 10
8、*3， A3为 3*12， A4为12*5， A5为 5*50， A6为 50*6，即维数序列为 5， 10， 3， 12， 5， 50， 6。则根据上述 C代码得到的一个最优计算顺序为 (7)(用加括号方式表示计算顺序 )，所需要的乘法运算次数为 (8)。 6 阅读下列说明 C代码，回答问题 1至问题 3，将解答写在答题纸的对应栏内。【说明】用两台处理机 A和 B处理 n个作业。设 A和 B处理第 i个作业的时间分别为 ai和 bi。由于 各个作业的特点和机器性能的关系，对某些作业，在 A上处理时间长，而对某些作业在 B上处理时间长。一台处理机在某个时刻只能处理一个作业，而且作业处理是不可中
9、断的，每个作业只能被处理一次。现要找出一个最优调度方案，使得 n个作业被这两台处理机处理完毕的时间 (所有作业被处理的时间之和 )最少。算法步骤： (1)确定候选解上界为最短的单台处理机处理所有作业的完成时间 m， (2)用 p(x， y， k)=1表示前 k个作业可以在 A用时不超过 x且在 B用时不超过 y时间内处理完成，则 p(x， y， k)=p(xak，Y， k一 1) p(x， y bk， k一 1)(11表示逻辑或操作 )。 (3)得到最短处理时间为min(max(x， y)。【 C代码】下面是该算法的 C语言实现。 (1)常量和变量说明 n：作业数 m：候选解上界 a：数组，长
10、度为 n，记录 n个作业在 A上的处理时间，下标从 0开始 b：数组，长度为 n，记录 n个作业在 B上的处理时间，下标从 0开始k：循环变量 p：三维数组，长度为 (m+1)*(m+1)*(n+1)temp：临时变量 max：最短处理时间 (2)C代码 #includeintn， m； inta60， b60， P10010060；voidread()( *输入 rl、 a、 b，求出 m，代码略 * )voidschedule()( (求解过程 *intX， Y， k； for(x=0； x=0)(2)； if(3)pxyk=(pIxyklIPXybk一 1k一1)； voidwrite(
11、) *确定最优解并输出 * intXY， temp,max： m； for(x=0； x 7 根据以上说明和 C代码，填允 C代码中的空 (1) (5)。 8 根据以上 C代码，算法的时间复杂度为 (6)(用 O符号表示 )。 9 考虑 6个作 业的实例，各个作业在两台处理机上的处理时间如表 15一 1所示。该实例的最优解为 (7)，最优解的值 (即最短处理时间 )为 (8)。最优解用 (x1， x2， x3，x4， x5， x6)表示，其中若第 i个作业在 A上处理，则 xi=1，否则 xi=2。如 (1， 1，1， 1， 2， 2)表示作业 1， 2， 3和 4在 A上处理，作业 5和 6
12、在 B上处理。9 阅读下列说明和 C代码，回答问题 1至问题 3，将解答写在答题纸的对应栏内。 【说明】设有 n个货物要装入若干个容重为 C的集装箱以便运输，这 n个货物的体积分别为 s1， s2， ， sn，且有 siC(1in)。为节省运输成本，用尽可能少的集装箱来装运这 n个货物。下面分别采用最先适宜策略和最优适宜策略来求解该问题。最先适宜策略 (firstfit)首先将所有的集装箱初始化为空，对于所有货物，按照所给的次序，每次将一个货物装入第一个能容纳它的集装箱中。最优适宜策略(bestfit)与最先适宜策略类似，不同的是，总是把货物装到能容纳它且目前剩余容重最小的集装箱，使得该箱子装
13、入货物后闲置空间最小。 【 C代码】 下面是这两个算法的 C语言核心代码。 (1)变量说明 n：货物数 C：集装箱容量 s：数组，长度为 n，其中每个元素表示货物的体积，下标从 0开始。 b：数组，长度为 n， bi表示第 n+i个集装箱当前已经装入货物的体积，下标从 0开始 i， j：循环变量 k：所需的集装箱数 min：当前所用的各集装箱装入了第 i个货物后的最小剩余容量 m：当前所需的集装箱数 temp：临时变量 (2)函数 firstfit intfirs七 fit()( inti， j； k=0; for(i=0;i(j+1)?k： (j+1)； returnk； (3)函数 bes
14、tfit intbestfit() inti， j， min， m， temp； k=0； for(i=0； iO intc33=(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； j 13 阅读下列说明和 C代码，回答问题 1至问题
15、 3，将解答写在答题纸的对应栏内。 【说明】 某应用中需要对 100000个整数元素进行排序，每个元素的取值在 0 5之间。排序算法的基本思想是：对每一个元素 x，确定小于等于 x的元素个数 (记为 m)，将 x放在输出元素序列的第 m个位置。对于元素值重复的情况，依次放入第 m1、 m一 2、 个位置。例如，如果元素值小于等于 4的元素个数有 10个，其中元素值等于 4的元素个数有 3个，则 4应该在数据元素序列的第 10个位置、第 9个位置和第 8个位置上。算法具体的步骤为： 步骤 1：统计每个元素值的个数。 步骤 2：统计小于等于每个元素值的个数。 步骤 3：将输入元素序列中的每个元素放
16、入有序的输出元素序列。 【 C代码】 下面是该排序算法的 C语言实现。 (1)常量和变量说明 R常量，定义元素取值范围中的取值个数，如上述应用中 R值应取 6 i：循环变量 n：待排序元素个数 a：输入数组，长度为 n b：输出数组，长度为 n c：辅助数组，长度为 R，其中每个元素表示小于等于下标所对应的元素值的个数。 (2)函数 sort voidsort(intn， inta， intb) intcR， i； for(i=0； iintarray0；(2)； A一 array_size-一； Heapify(A， A一 arraysize， 0)；将剩余元素调整成大顶堆 returnma
17、x； (3)函数 maxHeaplnsertintmaxHeaplnsert(ARRAY*A，intkey)inti， *P； if(A一 array一 size=A一 capacity)存储空间的容量不够时扩充空间 p=(int*)realloc(A一 intarray， A一 capacity*2*sizeof(int)； if(!P)return一1； A一 int_array=P； A一 capacity=2*A一 capacity； A一 array_size+：i=(3)； while(i0&(4)A一 int_arrayi=A一 int_arrayPARENT(i)；i=PARE
18、NT(i)； (5)； return0； 17 根据以上说明和 C代码，填充 C代码中的空 (1) (5)。 18 根据以上 c代码，函数 heapMaximum， heapExtractMax和 maxHeaplnsert的时间复杂度的上界分别为 (6)、 (7)和 (8)(用 O符号表示 )。 19 若将元素 10插入到堆 A=(15， 13， 9， 5， 12， 8， 7， 4， 0， 6， 2， 1)中，调用maxHeaplnsert函数进行操作，则新插入的元素在堆 A中第 (9)个位置 (从 1开始 )。 19 阅读下列说明和 C代码，回答问题 1至问题 3，将解答写在答题纸的对应栏
19、内。【说明】对有向图进行拓扑排序的方法是： (1)初始时拓扑序列为空： (2)任意选择一个入度为 0的顶点，将其放入拓扑序列中，同时从图中删除该顶点以及从该顶点出发的弧； (3)重复 (2)，直到不存在入度为 0的顶点为止 (若所有顶点都进入拓扑序列则完成拓扑排序，否则由于有向图中存在回路无法完成拓扑排序 )。函数int*TopSoa(LinkedDigraphG)的功能是对有向图 G中的顶点进行拓扑排序，返回拓扑序列中的顶点编号序列，若不能完成拓扑排序，则返 回空指针。其中，图 G中的顶点从 1开始依次编号，顶点序列为 v1， v2， ， vn，图 G采用邻接表示，其数据类型定义如下： #d
20、ef ine NAXVNUM 50 *最大顶点数 * typedef structArcNode( *表节点类型 * int adjvex； *邻接顶点编号 * struct ArcNode*nextarc； *指示下一个邻接顶点 * ArcNode： typedef struct Adj List( *头节点类型 * char vdata； *顶点的数据信息 * ArcNode*firstarc； *指向邻接表的第一个表节点 * Adj List； typedef struct LinkedDigraph( *图的类型 * int n； *图中顶点个数 * AdjLiSt VheadMAXV
21、NUM； *所有顶点的头节点数组 * LinkedDigraph；例如，某有向图 G如图 15 3所示，其邻接表如图15-4所示。函数T0pSon中用到了队列结构 (Queue的定义省略 )，实现队列基本操作的函数原型如表152所示：【 C代码】 int *TopSort(LinkedDigraph G) ArcNode*P； *临时指针，指示表节点* Queue Q； *临时队列，保存入度为 0的顶点编号 * int k=0； *临时变量，用作数组元素的下标 * int j=0， W=0； *临时变量，用作顶点编号 *int*toporder， *inDegree； toporder=(in
22、t*)malloc(G n+1)*Si zeof(int)； *存储拓扑序列中的顶点编号 * inDegree=(int*)malloc(G n+1)*sizeof(int)； *存储图 G中各顶点的入度 * if(!inDegree I I!toporder)return NULL； (1)； *构造一个空队列* for(j=1； Jnextarc)inDegreep一 adjvex+=1； for(j=1； Jnextarc)(3)一 =1；if(0=(4)EnQueue( Q， P一 adjvex)； *for* *while* free(inDegree)；if( (5) )retur
23、n NULL； return topOrder； *TopSort* 20 根据以上说明和 C代码，填充 C代码中的 空 (1) (5)。 21 对于图 153所示的有向图 G，写出函数 TopSoa执行后得到的拓扑序列。若将函数 T0pSort中的队列改为栈，写出函数 TopSon执行后得到的拓扑序列。 22 设某有向无环图的顶点个数为 n、弧数为 e，那么用邻接表存储该图时，实现上述拓扑排序算法的函数 TopSo的时间复杂度是 (6)。若有向图采用邻接矩阵表示 (例如，图 153所示有向图的邻接矩阵如图 155所示 )，且将函数 TopSort中有关邻接表的操作修改为针对邻接矩阵的操作，那
24、么对于有 n个顶点、 e条弧的有向无环图，实现上述 拓扑排序算法的时间复杂度是 (7)。软件水平考试（中级）软件设计师下午（应用技术）历年真题试卷汇编 4答案与解析 一、必答题（共 4道大题，每道大题 15分） 【知识模块】 数据结构及算法设计 1 【正确答案】 (1)di=di+ti(2)i=m(3)sk0=i(4)Max=0 (4)pxyn=1，或 pxyn或 pxyn!=0(5)(x=y)?x： y 【试题解析】 从 schedule()函数的第一个程序段可以看出，该段程序主要进行初始化第一个作业，下标以 0开始，即 pxy0=1，内层循环里的 pxyk=0用于初始化后面的 n-1个作业
25、。第二个程序段是对后面的 n1个作业，确定。 p(x，y， k)的值。 x ak 1=0的判定条件若成立，则表示第 k个作业由机器 A处理，完成 k一 1个作业时机器 A花费的时间 是 xak1，即 pxyk=pxak1yk1。 (3)空要求填入一判定条件，由其后的执行语句可知，第 k个作业由机器 B 【知识模块】 数据结构及算法设计 8 【正确答案】 (6)O(m2n) 【试题解析】 从程序的循环层数即可看出算法的时间复杂度。程序的最高循环层数为 3层。最外层循环变量的变化范围是 1一 n一 1，次外层循环变量的变化范围是 0 m，内层循环变量的变化范围是 0m，所以时间复杂度为 O(m2n
26、)。 【知识模块】 数据结构及算法设计 9 【正确答案】 (7)(1， 1， 2， 2， 1， 1)(8)15 【试题解析】 为了方便考生更好地理解本算法的思想，现做如下分析：当完成 k个作业，设机器 A花费了 x时间，机器 B所花费时间的最小值肯定是 x的一个函数，设 Fkx表示机器 B所花费时间的最小值，则 Fkx=MinFk1x+bk， Fk 1xak。其中 Fk1x+bk表示第 k个作业由机器 B来处理 (完成 k-1个作业时机器 A花费的时间仍是 x)， Fk1x ak表示第 k个作业由机器 A处理 (完成 k1个作业时 机器 A花费的时间是 x-ak)。那么单个点对较大值 max(
27、x， Fkx)，表示此时 (即机器 A花费 X时间的情况下 )所需要的总时间。而机器 A花费的时间 x是变化的，即 x=0， 1， 2x(max) ，由此构成了点对较大值序列。要求整体时间最短，取这些点对较大值序列中最小的即是。现分析前两个作业的情况：对于第一个作业：下标以 0开始。首先，机器 A所花费时间的所有可能值范围： 0=si的集装箱。但条件 c-bj： 0； i-)即可。 【试题解析】 假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中， ri=rj，且 ri在 rj之前，而在排序后的序列中， ri仍在 rj之前，则称这种排
28、序算法是稳定的；否则称为不稳定的。题目中，从下标 0开始读取 a(i元素，第一个读取的值为 ai的元素保存在 bcai一 1，第二个读取的 ai的元素保存在 bcai 2，也就是说后读取的值为 ai的元素保存在前面，因此该算法是不 稳定的，只需讲最后一个 for循环改为如下代码即可变为稳定的。 for(i=n一 1； i=0； i一一 )( bcai一1=ai； cai=cai一 1； 【知识模块】 数据结构及算法设计 【知识模块】 数据结构及算法设计 17 【正确答案】 (1)A-int_array0 (2)A-int_array0=A-int_arrayA-array_size一 1 (3
29、)A-array_size-1 (4)keyA-int_arrayPARENT(i) (5)A-int_arrayi=key 【试题解析】 heapMaximum(A)函数返回大顶堆 A中的最大元素。大顶堆 A的优先队列采用顺序存储方式，指 int_array指向优先队列的存储空间首地址，其内容为大项堆 A中的最大元素，因此空 (1)处应填入 A一 inLarray0。heapExtractMax(A)功能是去掉并返回大顶堆 A的最大元素，将最后一个元素 “提前 ”到堆顶位置，并将剩余元素调整成大顶堆。可知空 (2)处所填的语句应该是将最后一个元素的值存储在原最大元素所在的位置，即 存储空间的
30、首地址。maxHeaplnsert(A,key)的功能是把元素 key插入到大顶堆 A的最后位置，再将 A调整成大顶堆。在将 A调整成大堆的过程中需要用到上滤策略。maxHeaplnsert(A， key)函数中，首先用 i指示元素 key的位置，则i=array_size_1；然后将 int_arrayi-其父节点进行比较，如果大于其父节点的值，也两者的位置进行交换， key的位置 i=PARENT(i)；往上比较，直至 key的值不大于其父节点的值。 【知识模块】 数据结构及算法设计 18 【正确答 案】 (6)O(1) (7)O(1gn) (8)O(1gn) 【试题解析】 heapMax
31、imum函数不需要进行比较，直接输出存储空间首地址中的内容。时间复杂度的上界 O(1)。 heapExtractMax函数将最后一个元素 “提前 ”到堆顶位置，并将剩余元素调整成大顶堆，在最坏的情况下，需要从根节点下滤比较到最底层，时间复杂度的上界 O(lgn)。 maxHeaplnsert(A， key)函数把元素 key插入到大顶堆 A的最后位置，再将 A调整成大顶堆。在最坏的情况下，需要从最底层上滤比较到根节点，时间复杂度的上 界 O(lgn)。 【知识模块】 数据结构及算法设计 19 【正确答案】 3 【试题解析】 调用 maxtteaplnsert函数进行排序的过程如下。可见，元素
32、10在堆 A的第 3个位置。 【知识模块】 数据结构及算法设计 【知识模块】 数据结构及算法设计 20 【正确答案】 (1)InitQueue(&Q)(2)DeQueue(&Q， w)(3)inDegreep adjvex 或其等价形式 (4)inDegreep一 adjvex或其等价形式 (5)kadjvex表示 vi的一个邻接顶点，删除 Vi至顶点 p一 adjvex的弧的操作实现为顶点 p一 adjvex的入度减 1，因此 ，空 (3)处应填入 inDegree p一 adIjvex，当顶点 p一 adjvex的入度为 0时，需要将其加入队列，因此空 (4)处也应填入 inDegreep
33、adjvex。空 (5)处判断是否所有顶点都加入拓扑序列，算法中变量 k用于对加入序列的项点计数，因此，空 (5)处应填入 “kG n”或 “k!=G n”。 【知识模块】 数据结构及算法设计 21 【正确答案】 队列方式： v1 v2 v5 v4 v3 v7 v6 或者 1 2 5 4 3 7 6栈方式： v1 v2 v5 v4 v7 v3 v6 或者 1 2 5 4 7 3 6 【试题解析】 使用栈和队列的差别在于拓扑序列中顶点的排列次序可能不同。对于本题中的有向图，在使用队列的方式下： (1)开始时仅顶点 v1的入度为 0，因此顶点 v1入队； (2)对头顶点 v1出队，并进入拓扑序列，
34、然后删除从顶点 v1出发的弧后，仅使顶点 v2的入度为 0，因此顶点 v2入队； (3)队头顶点 v1出队，并进入拓扑序列，然后删除从顶点 v2出发的弧后，仅使顶点 v5的入度为 i，因此顶点 v5入队； (4)队头顶点 v5出队，并进入拓扑序列，然后删除从顶点 v5出发的弧 后，仅使顶点 v4的入度为 0，因此顶点 v4入队； (5)队头顶点 v4出队，并进入拓扑序列，然后删除从顶点 v4出发的弧后，仅使顶点 v3和 v的入度为 0，因此顶点 v3和 v7依次入队； (6)队头顶点 v3出队，并进入拓扑序列，然后删除从顶点 v3出发的弧后，没有产生新的入度为 0的顶点； (7)队头顶点 v7
35、出队，并进入拓扑序列，然后删除从顶点 v7出发的弧后，使顶点v6的入度为 0，因此顶点 v6入队； (8)队头顶点 v6出队，并进入拓扑序列，然后删除从顶点 v6出发的弧后，没有产生新的入度为 0的顶点，队列已空，因此结束拓扑排序 过程，得到的拓扑序列为v1 v2 v5 v4 v3 v7 v6。使用栈保存入度为 0的顶点时，前 4步都是一样的，因为每次仅有一个元素进栈，因此出栈序列与入栈序列一致。到第 5步时， v3和 v7依次入栈后，出栈时的次序为 v7和 v3，因此得到的拓扑序列为 v1 v2 v5 v4 v7 v3 v6。 【知识模块】 数据结构及算法设计 22 【正确答案】 (6)0(
36、n+e)(7)O(n2) 【试题解析】 以邻接表为存储结构时，计算各项点入度的时间复杂度为 O(e)，建立零入度顶点队列的时间复杂度为 O(n)。在拓扑排 序过程中， (图中无环情况下 )每个顶点进出队列各 1次，入度减 1的操作在 while循环中共执行 e次，所以总的时间复杂度为 O(n+e)。以邻接矩阵为存储结构时，计算各顶点入度时需要遍历整个矩阵，因此时间复杂度为 O(n2)，建立零入度顶点队列的时间复杂度为 O(n)。在拓扑排序过程中， (图中无环情况下 )每个顶点进出队列各 1次，实现入度减 1操作时需遍历每个顶点的行向量 1遍 (时间复杂度为 O(n)，所以总的时间复杂度为O(n2)。 【知识模块】 数据结构及算法设计
