[计算机类试卷]软件水平考试(中级)软件设计师下午(应用技术)历年真题试卷汇编4及答案与解析.doc
《[计算机类试卷]软件水平考试(中级)软件设计师下午(应用技术)历年真题试卷汇编4及答案与解析.doc》由会员分享,可在线阅读,更多相关《[计算机类试卷]软件水平考试(中级)软件设计师下午(应用技术)历年真题试卷汇编4及答案与解析.doc(23页珍藏版)》请在麦多课文档分享上搜索。
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,将解答写在答题纸的对应栏
- 1.请仔细阅读文档,确保文档完整性,对于不预览、不比对内容而直接下载带来的问题本站不予受理。
- 2.下载的文档,不会出现我们的网址水印。
- 3、该文档所得收入(下载+内容+预览)归上传者、原创作者;如果您是本文档原作者,请点此认领!既往收益都归您。
下载文档到电脑,查找使用更方便
2000 积分 0人已下载
下载 | 加入VIP,交流精品资源 |
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机 试卷 软件 水平 考试 中级 设计师 下午 应用技术 历年 汇编 答案 解析 DOC
