2022软件水平考试-中级软件设计师考试题库套卷27（含答案解析）

《2022软件水平考试-中级软件设计师考试题库套卷27（含答案解析）》由会员分享，可在线阅读，更多相关《2022软件水平考试-中级软件设计师考试题库套卷27（含答案解析）（8页珍藏版）》请在装配图网上搜索。

1、2022软件水平考试-中级软件设计师考试题库（含答案解析）1. 问答题：快速排序是一种典型的分治算法。采用快速排序对数组Ap.r排序的三个步骤如下: 分解：选择一个枢轴（pivot）元素划分数组。将数组Ap.r划分为两个子数组（可能为空） Ap.q-1和Aq+1.r，使得Aq大于等于Ap.q-1中的每个元素，小于Aq+1.r中的每个元素。q的值在划分过程中计算。 递归求解：通过递归的调用快速排序，对子数组Ap.q-1和Aq+1.r分别排序。 合并：快速排序在原地排序，故不需合并操作。 【问题1】 下面是快速排序的伪代码，请填补其中的空缺。伪代码中的主要变量说明如下： A：待排序数组 p, r：

2、数组元素下标，从p到r q：划分的位置 x：枢轴元素 i：整型变量，用于描述数组下标。下标小于或等于i的元素的值小于或等于枢轴元素的值 j：循环控制变量，表示数组元素下标 QUICKSORT( A, p, r )if ( p 大于 r )q = PARTITION( A,p,r ) ;QUICKSORT( A, p, q-1 );QUICKSORT( A, q+1, r );PARTITION( A, p, r )x= Ar; i = p - 1;for( j = p ; j 大于= r - 1; j+ )if ( Aj 大于= x )i = i + 1 ;交换Ai 和 Aj;交换 （1） 和

3、 （2） /注：空（1）和空（2）答案可互换，但两空全部答对方可得分return （3） 【问题2】（1） 假设要排序包含n个元素的数组，请给出在各种不同的划分情况下，快速排序的时间复杂度，用O记号。最佳情况为 （4）平均情况为 （5）最坏情况为 （6） （2） 假设要排序的n个元素都具有相同值时，快速排序的运行时间复杂度属于哪种情况? （7）（最佳、平均、最坏） 【问题3】（1） 待排序数组是否能被较均匀地划分对快速排序的性能有重要影响，因此枢轴元素的选取非常重要。有人提出从待排序的数组元素中随机地取出一个元素作为枢轴元素，下面是随机化快速排序划分的伪代码-利用原有的快速排序的划分操作，请填

4、充其中的空缺处。其中，RANDOM( i,j )表示随机取i到j之间的一个数，包括i和j。 RANDOMIZED-PARTITION( A,p,r )i = RANDOM( p,r );交换（8）和（9）; /注：空（8）和空（9）答案可互换，但两空全部答对方可得分return PARTITION( A,p,r ); （2） 随机化快速排序是否能够消除最坏情况的发生? （10）（是或否）答案： 本题解析：【问题1】（1）Ai+1 或 Ar （2）Ar 或 Ai+1 （3）i+1 【问题2】（4）O(nlgn) 或 O(nlog2n) （5）O(nlgn) 或 O(nlog2n) （6）O(n2

5、 ) （7）最坏 【问题3】（8）Ai （9）Ar （10）否该题主要考查考生对分治算法的快速排序的理解，对伪代码、快速排序的复杂度的掌握，做题的关键是要读懂题干，理解题干中对算法的描述。 问题1考查的是算法的伪代码表示。分治法的设计思想是将一个难以直接解决的问题，分解成一些规模较小的相同问题，各个击破。其快速排序算法的核心处理是进行划分，根据枢轴元素的值，把一个较大的数组分成两个较小的子数组。一个子数据组的所有元素的值小于等于枢轴元素的值，一个子数组的所有元素的值大于枢轴元素的值，而子数组内的元素不排序。以最后一个元素为枢轴元素进行划分，从左到右依次访问数组的每一个元素，与枢轴元素比较大小，

6、并进行元素的交换。在问题1给出的伪代码中，当循环结束后，Ap.i中的值小于等于枢轴元素值x，而Ai+1.r-1中的值应大于x。此时Ai+1是第一个比Ar大的元素，于是Ar与Ai+1交换，得到划分后的两个子数组。由于划分操作（即PARTITION操作）返回枢轴元素的值，因此返回值为i+1。 问题2考查的是算法的时间复杂度分析。当每次都能做均匀划分时，是算法的最佳情况，其时间复杂度为T( N )=2T( n/2 )+O( N )，即时间复杂度为O( nlgn )；算法的最坏情况是每次为极不均匀划分，即长度为n的数组划分后一个子数组为n-1，一个为0，其时间复杂度为T( N )=T( n-1 )+O

7、( N )，即时间复杂度为O( n2 )；算法的平均情况分析起来比较复杂，假设数组每次划分为9/10:1/10，此时时间复杂度可以通过计算得到为O(nlgn)；也就是说在平均情况下快速排序仍然有较好的性能。问题2中假设要排序的n个元素都具有相同值时，快速排序的运行时间复杂度，属于最坏情况，因为每次都划分为长度为n-1和0的两个子数组。 问题3中，由于随机化的快速排序的划分调用了PARTITION操作，而传统划分每次以数组的最后一个元素作为枢轴元素。随机化的快速排序消除了输入数据的不同排列对算法性能的影响，降低了极端不均匀划分的概率，但不能保证不会导致最坏情况的发生。2. 填空题：Creatin

8、g a clear map of where the project is going is an important first step.It lets you identify risks,clarify objectives,and determine if the project even makes sense.The only thing more important than the Release Plan is not to take it too seriously.Release planning is creating a game plan for your Web

9、 project（1）what you think you want your Web site to be.The plan is a guide for the content,design elements,and functionality of a Web site to be released to the public,to partners,or internally.It also（2）how long the project will take and how much it will cost.What the plan is not is a functional（3）

10、that defines the project in detail or that produces a budget you can take to the bank.Basically you use a Release Plan to do an initial sanity check of the projects（4）and worthiness.Release Plans are useful road maps,but dont think of them as guides to the interstate road system.Instead,think of the

11、m as the（5）used by early explorershalf rumor and guess and half hope and expectation.Its always a good idea to have a map of where a project is headed.问题1选项A.constructingB.designingC.implementingD.outlining问题2选项A.definesB.calculatesC.estimatesD.knows问题3选项A.specificationB.structureC.requirementD.impl

12、ementation问题4选项A.correctnessB.modifiabilityC.feasibilityD.traceability问题5选项A.navigatorsB.mapsC.guidancesD.goals答案：DCACB 本题解析：暂无解析3. 问答题：希尔排序算法又称最小增量排序算法，其基本思想是:步骤1 :构造一个步长序列delta1、delta2.、deltak ，其中delta1=n/2 ，后面的每个delta是前一个的1/2 ， deltak=1；步骤2 :根据步长序列、进行k趟排序；步骤3 :对第i趟排序，根据对应的步长delta，将等步长位置元素分组，对同一组内

13、元素在原位置上进行直接插入排序。【C代码】下面是算法的C语言实现。（1）常量和变量说明data：待排序数组data，长度为n，待排序数据记录在data0、data1、.、datan-1中。n：数组a中的元素个数。delta：步长数组。（2）C程序#include stdio.hvoid shellsort(int data , int n) int *delta,k,i,t,dk,j; k=n; delta=(int *)nalloc(sizeof(int)*(n/2); if(i=0) do ( 1 ) ; deltai+=k; while ( 2 ) ; i=0; while(dk=del

14、tai)0) for(k=deltai;kn;+k) if( ( 3 ) ) t=datak; for(j=k-dk;j=0&tdataj;j-=dk) dataj+dk=dataj; /*for*/ ( 4 ) ;/dataj+dk=t; /*if*/ +i; /*while*/ 【问题1】（8分）根据说明和c代码，填充c代码中的空(1) (4)。【问题2】（4分）根据说明和c代码，该算法的时间复杂度(5)O(n2) (小于、等于或大于)。该算法是否稳定(6) ( 是或否)。【问题3】（3分）对数组(15、9、7、8、20、-1、 4)用希尔排序方法进行排序，经过di-趟排后得到的数组为(7

15、)。答案： 本题解析：【问题1】（8分）（1）k=k/2（2）k1（3）datakdatak-dt（4）dataj+dk=t【问题2】（4分）（5）小于（6）否【问题3】（3分）（7）(4，9，-1，8，20，7，15)4. 填空题：在地址），welcome.htm表示（）。问题1选项A.协议类型B.主机C.网页文件名D.路径问题2选项A.协议类型B.主机域名C.网页文件名D.路径答案：BC 本题解析：暂无解析5. 填空题：分配给某公司网络的地址块是220.17.192.0/20，该网络被划分为（）个C类子网，不属于该公司网络的子网地址是（）。问题1选项A.4B.8C.16D.32问题2选项A

16、.220.17.203.0B.220.17.205.0C.220.17.207.0D.220.17.213.0答案：CD 本题解析：暂无解析6. 填空题：给定关系R（A，B，C，D）和关系S（A，C，E，F），对其进行自然连接运算R S后的属性列为（）个；与R.BS.E（R S）等价的关系代数表达式为（）。问题1选项A.4B.5C.6D.8问题2选项A.27（RS）B.1,2,3,4,7,8（1=5273=6（RS）C.27（RS）D.1,2,3,4,7,8（1=5273=6（RS）答案：CB 本题解析：暂无解析7. 填空题：The beauty of software is in its f

17、unction,in its internal structure,and in the way in which it is created by a team.To a user,a program with just the right features presented through an intuitive and（1）interface is beautiful.To a software designer,an internal structure that is partitioned in a simple and intuitive manner,and that mi

18、nimizes internal coupling is beautiful.To developers and managers,a motivated team of developers making significant progress every week,and producing defect-free code,is beautiful.There is beauty on all these levels.Our world needs softwarelots of software.Fifty years ago software was something that

19、 ran in a few big and expensive machines.Thirty years ago it was something that ran in most companies and industrial settings.Now there is software running in our cell phones,watches,appliances,automobiles,toys,and tools.And need for new and better software never（2）.As our civilization grows and exp

20、ands,as developing nations build their infrastructures,as developed nations strive to achieve ever greater efficiencies,the need for more and more Software（3）to increase.It would be a great shame if,in all that software,there was no beauty.We know that software can be ugly.We know that it can be har

21、d to use,unreliable,and carelessly structured.We know that there are software systems whose tangled and careless internal structures make them expensive and difficult to change.We know that there are software systems that present their features through an awkward and cumbersome interface.We know tha

22、t there are software systems that crash and misbehave.These are（4）systems.Unfortunately,as a profession,software developers tend to create more ugly systems than beautiful ones.There is a secret that the best software developers know.Beauty is cheaper than ugliness.Beauty is faster than ugliness.A b

23、eautiful software system can be built and maintained in less time,and for less money,than an ugly one.Novice software developers dont understand this.They think that they have to do everything fast and quick.They think that beauty is（5）.No!By doing things fast and quick,they make messes that make th

24、e software stiff,and hard to understand,beautiful systems are flexible and easy to understand.Building them and maintaining them is a joy.It is ugliness that is impractical.Ugliness will slow you down and make your software expensive and brittle.Beautiful systems cost the least build and maintain,an

25、d are delivered soonest.问题1选项A.SimpleB.HardC.ComplexD.duplicated问题2选项A.happensB.existsC.stopsD.starts问题3选项A.startsB.continuesC.appearsD.stops问题4选项A.practicalB.usefulC.beautifulD.ugly问题5选项A.impracticalB.perfectC.time-wastingD.practical答案：ACBDA 本题解析：暂无解析8. 填空题：与HTTP相比，HTTPS协议对传输的内容进行加密，更加安全。HTTPS基于（）安

26、全协议，其默认端口是（）。问题1选项A.RSAB.DESC.SSLD.SSH问题2选项A.1023B.443C.80D.8080答案：CB 本题解析：暂无解析9. 填空题：Cloud computing is a phrase used to describe a variety of computing concepts that involve a large number of computers（1）through a real-time communication network such as the Internet.In science,cloud computing is a

27、（2）for distributed computing over a network,and means the（3）to run a program or application on many connected computers at the same time.The architecture of a cloud is developed at three layers:infrastructure,platform,and application,The infrastructure layer is built with virtualized computer,storag

28、e,and network resources.The platform layer is for general-purpose and repeated usage of the collection of software resources.The application layer is formed with a collection of all needed software modules for SaaS applications.The infrastructure layer serves as the（4）for building the platform layer

29、 of the cloud.In turn,the platform layer is a foundation for implementing the（5）layer for SaaS applications.问题1选项A.connectedB.imlementedC.optimizedD.Virtualized问题2选项A.replacementB.switchC.substituteD.synonym(同义词)问题3选项A.abilityB.applroachC.functionD.method问题4选项A.networkB.foundationC.softwareD.hardwar

30、e问题5选项A.resoruceB.serviceC.applicationD.software答案：ADABC 本题解析：暂无解析10. 填空题：假设学生Students和教师Teachers关系模式如下所示：Students（学号，姓名，性别，类别，身份证号）Teachers（教师号，姓名，性别，身份证号，工资）其中，学生关系中的类别分为“本科生“和”研究生“两类：a.查询在读研究生的教师的平均工资、最高与最低工资之间差值的SQL语句如下：SELECT（）FROM Students,TeachersWHERE（）;b.查询既是女教师，又是研究生且工资大于等于3500元的身份证号和姓名的SQ

31、L语名如下：SELECT身份证号，姓名FROM StudentsWHERE（）INTERSECT(SELECT身份证号，姓名FROM TeachersWHERE（）)问题1选项A.AVG(工资)AS平均工资，MAX（工资）-MIN(工资)AS差值B.平均工资AS AVG（工资），差值AS MAX(工资)-MIN(工资)C.AVG(工资)ANY平均工资，MAX（工资）-MIN(工资)ANY差值D.平均工资ANY AVG（工资），差值ANY MAX(工资)-MIN（工资）问题2选项A.Students.身份证号=Teachers.身份证号B.Students.类别=研究生C.Students.身份证号=Teachers.身份证号AND Students.类别=研究生D.Students.身份证号=Teachers.身份证号OR Students.类别=研究生问题3选项A.工资=3500B.工资=3500C.性别=女AND类别=研究生D.性别=女AND类别=研究生问题4选项A.工资=3500B.工资=3500C.性别=女AND类别=研究生D.性别=女AND类别=研究生答案：ACDA 本题解析：暂无解析