《2022年软考-软件设计师考前模拟强化练习题52（附答案详解）》由会员分享，可在线阅读，更多相关《2022年软考-软件设计师考前模拟强化练习题52（附答案详解）（23页珍藏版）》请在金锄头文库上搜索。
1、2022年软考-软件设计师考前模拟强化练习题（附答案详解）1. 单选题在求解某问题时，经过分析发现该问题具有最优子结构和重叠子问题性质。则适用（ ）算法设计策略得到最优解。若了解问题的解空间，并以广度优先的方式搜索解空间,则采用的是（ ）算法策略。问题1选项A.分治B.贪心C.动态规则D.回溯问题2选项A.动态规则B.贪心C.回溯D.分支限界【答案】第1题:C第2题:D【解析】要想直接解决一个较大的问题，有时是相当困难的，分治法的设计思想是将一个难以解决的大问题分解成一些规模较小的相同问题，以便各个击破，分而治之。动态规划法与分治法类似，其基本思想也是将带求解问题分解为若干个子问题，先求解子问
2、题再从这些子问题的解得到原问题的解。与分治法不同的是，适合用动态规划法求解的问题，经分解得到的子问题往往不是独立的。若用分治法来解这类问题，则相同的子问题会被求解多次，以至于最后解决原问题需要耗费指数级时间。此时用一个中间表记录重复子问题的解，可以避免大量的重复计算。这就是动态规划法的基本思路。动态规划法的应用场景一般会出现“最优子结构”的描述，并且针对重复子问题的计算通过记录-查表，可以提高效率。本题第一空描述的是C选项动态规划法。贪心法也经常用于解决最优化问题，与之不同的是，贪心法在解决问题的策略上是仅根据当前已有的信息做出选择，而且一旦做出选择，无论未来如何都不会改变。也就是只考虑当前最
3、优，不考虑全局最优。一般不涉及划分和求解重复子问题。回溯法可以系统地搜索一个问题的所有解或任意解。它在包含问题的解空间树中，按照深度优先的策略的策略，从根结点出发搜索解空间树。分支限界法类似于回溯法，也是一种在问题的解空间树T上搜索问题解的算法，但在一般情况下，分支限界法与回溯法的求解目标不同。分支限界法的求解目标是找出满足约束条件的一个解即可。由于求解目标不同，其探索方式与回溯法也不同，分支限界法以广度优先或以最小耗费优先的方式搜索解空间树。本题第二空描述的是D选项分支限界法。2. 案例题生物学上通常采用编辑距离来定义两个物种DNA序列的相似性,从而刻画物种之间的进化关系。具体来说，编辑距离
4、是指将一个字符串变换为另一个字符串所需要的最小操作次数。操作有三种,分别为:插入一个字符、删除一个字符以及将一个字符修改为另一个字符。用字符数组str1和str2分别表示长度分别为len1和len2的字符串，定义二维数组d记录求解编辑距离的子问题最优解，则该二维数组可以递归定义为:【C代码】下面是算法的C语言实现。（1）常量和变量说明A，B：两个字符数组d：二维数组i，j：循环变量temp：临时变量（2）C程序#include#define N 100char AN=CTGA;char BN=ACGCTA;int dNN;int min(int a, int b)return a （1） ；f
5、or(i=1;i （2） )dij=di-1j-1; else temp=min(di-1j+1, dij-1+1);dij=min(temp, （3） ); return （4） ;【问题1】(8分)根据说明和C代码，填充C代码中的空(1)(4)。【问题2】(4分)根据说明和C代码，算法采用了(5)设计策略，时间复杂度为(6)(用O符号表示，两个字符串的长度分别用m和n表示)。【问题3】(3分)已知两个字符串A=CTGA和B=ACGCTA，根据说明和C代码，可得出这两个字符串的编辑距离为(7)。【答案】问题1：（1） d0j=j (2)str1i-1=str2j-1 (3)di-1j-1 +
6、1 (4) dlen1len2问题2：（5）动态规划法 （6）O(mn)问题3：（7）43. 单选题下面是一个软件项目活动图，其中顶点表示项目里程碑，连接顶点的边表示包含的活动，边上的权重表示活动的持续时间（天），则关键路径长度为（ ），在该活动图中，活动（ ）晚16天开始不会影响上班。问题1选项A.20B.25C.27D.48问题2选项A.ACB.BEC.FID.HJ【答案】第1题:D第2题:B【解析】本题是对进度网络图分析的考查。将各个活动的最早开始和完成时间、最晚开始和完成时间、持续时间和总时差分别进行标注，结果如下：4. 单选题关于螺旋模型，下列陈述中不正确的是（ ），（ ）。问题1选
7、项A.将风险分析加入到瀑布模型中B.将开发过程划分为几个螺旋周期，每个螺旋周期大致和瀑布模型相符C.适合于大规模、复杂且具有高风险的项目D.可以快速的提供一个初始版本让用户测试问题2选项A.支持用户需求的动态变化B.要求开发人员具有风险分析能力C.基于该模型进行软件开发，开发成本低D.过多的迭代次数可能会增加开发成本，进而延迟提交时间【答案】第1题:D第2题:C【解析】第一空选项中，可以快速提供一个初始版本给用户的是增量模型而不是瀑布模型。D选项描述错误。其他描述都是正确的。第二空选项中，在螺旋模型中过多的迭代次数会增加开发成本，C选项开发成本低的描述是错误的。其他描述都是正确的。5. 单选题
8、最大尺寸和问题描述为，在n个整数（包含负数）的数组A中，求之和最大的非空连续子数组,如数组A= (-2, 11, -4，13, -5，-2) ，其中子数组B= (11, -4, 13)具有最大子段和20 (11-4+13=20) 。求解该问题时,可以将数组分为两个n/2个整数的子数组最大子段或或者在前半段，或者在后半段，或者跨越中间元素，通过该方法继续划分问题，直至最后求出最大子段和，该算法的时间复杂度为（ ）。问题1选项A.O(nlgn)B.O(n2)C.O(n2lgn)D.O(n3)【答案】A【解析】本题中将数组不断进行二分，这个过程的时间复杂度为O(log2n)，划分后求解问题需要2个并
9、列的for循环对划分后的数组进行求和比较，此时时间复杂度为O(n)，划分和求和过程应该是嵌套的，所以时间复杂度综合为O(nlgn)，本题应该选择A选项。其算法过程可以设计如下：int MaxSubSum(int *Array,int left ,int right)int sum=0;int i ;if(left=right)/*分解到单个整数，不可继续分解*/if(Arrayleft0)sum=Arrayleft;elsesum=0; /和小于等于0时，最大和记作0/*if*/else/*从left和right的中间分解数组*/int center=(left+right)/2; /*划分位
10、置*/int leftsum=MaxSubSum(Array,left,center);int rightsum=MaxSubSum(Array,center+1,right);/*计算包含center的最大值，判断是情形1（前半段）-Array1.n的最大子段和与Array1.n/2的最大子段和相同、情形2（后半段）-Array1.n的最大子段和与Arrayn/2+1.n的最大子段和、还是情形3（跨越中间元素）-Array1.n的最大子段和为Arrayi.j的最大子段和，且1in/2,n/2+1jn。*/int s1=0;int lefts=0;for(i=center;i=left;i-)
11、lefts+=Arrayi;if(leftss1=lefts;/*for*/int s2=0;int rights=0;for(i=center+1;irights+=Arrayi;if(rightss2)s2=rights;/*for*/sum=s1+s2;/*情形1*/if(sumsuml=leftsum;/*情形2*/if(sumsuml=rightsum;/*else*/return sum;6. 单选题提高程序执行效率的方法一般不包括（ ）。问题1选项A.设计更好的算法B.采用不同的数据结构C.采用不同的程序设计语言D.改写代码使其更紧凑【答案】D【解析】本题考查软件工程的设计原则。
12、改写代码仅使其结构上更紧凑，并不能提高执行效率问题。其他三项都能够提高执行效率。故正确答案选择D选项。7. 单选题函数foo、hoo的含义如下所示，函数调用hoo(a,x)的两个参数分别采用引用调用（call by reference）和值调用（call by value）方式传递，则函数调用foo(5)的输出结果为（ ）。问题1选项A.2，5B.2，15C.13，5D.13，15【答案】C【解析】根据题干给出的信息，foo(5)，在该函数中，初始情况x=5，a=2。调用hoo(a,x)函数，此时a=2传给hoo函数中的x，并且由于是引用方式，此时x在hoo函数内的修改会影响原a的值（注意区别
13、，hoo函数的x与foo函数的x是不用的局部变量）。同时x=5传给hoo函数中的y，并且是值调用方式，此时y在hoo函数内的修改是不会影响原x的值。接着分析hoo()函数，x的初始值为2，y初始值为5。执行y=y+10=15，执行x=y-x=15-2=13，此时x的值会传回原foo函数的a，即a=x=13。返回foo函数进行分析，输出的a和x，取值分别为修改后的13和原数值5。本题选择C选项。8. 单选题对于一个初始无序的关键字序列，在下面的排序方法中，（ ）第一趟排序结束后，一定能将序列中的某个元素在最终有序序列中的位置确定下来。直接插入排序冒泡排序简单选择排序堆排序快速排序归并排序问题1选项A.B.C.D.【答案】C【解析】选择类排序，每一轮会选择最值（最大值或最小值）与第一个位置进行交换，此时确定第一个元素位置。都满足要求。冒泡排序，每一轮会让最值相邻交换直至放到最终的位置，满足要求。快速排序，每一轮会根据基准元素划分左右数组，此时基准元素的位置可以确定，因此也满足要求。其他排序方式每一轮只能确定元素的当前位置，不能确定该元素的最终位置。本题选择C选项。9. 单选题下列算法中属于非对称加密算法的是（ ）。问题1选项A.DESB.RSAC.AESD.MD5【答案】B【解析】典型的对称加密算法：DES，3DES，AES等。典型的非对称加密算法：RSA，
