《2022软件水平考试-中级软件设计师考试题库套卷45（含答案解析）》由会员分享，可在线阅读，更多相关《2022软件水平考试-中级软件设计师考试题库套卷45（含答案解析）（7页珍藏版）》请在金锄头文库上搜索。
1、2022软件水平考试-中级软件设计师考试题库（含答案解析）1. 填空题：在FM方式的数字音乐合成器中，改变数字载波频率可以改变乐音的（），改变它的信号幅度可以改变乐音的（）。问题1选项A.音调B.音色C.音高D.音质问题2选项A.音调B.音域C.音高D.带宽答案：AC 本题解析：暂无解析2. 填空题：已知关系模式：图书（图书编号，图书类型，图书名称，作者，出版社，出版日期，ISBN），图书编号唯一识别一本图书。建立“计算机”类图书的视图Computer-BOOK，并要求进行修改、插入操作时保证该视图只有计算机类的图书。实现上述要求的SQL语句如下：CREATE（）AS SELECT图书编号，图
2、书名称，作者，出版社，出版日期FROM图书WHERE图书类型=计算机（）；问题1选项A.TABLE Computer-BOOKB.VIEWComputer-BOOKC.Computer-BOOK TABLED.Computer-BOOKVIEW问题2选项A.FOR ALLB.PUBLICC.WITH CHECK OPTIOND.WITH GRANT OPTION答案：BC 本题解析：暂无解析3. 填空题：快速排序算法在排序过程中，在待排序数组中确定一个元素为基准元素，根据基准元素把待排序数组划分成两个部分，前面一部分元素值小于等于基准元素，而后面一部分元素值大于基准元素。然后再分别对前后两个部
3、分进一步进行划分。根据上述描述，快速排序算法采用了（）算法设计策略。已知确定基准元素操作的时间复杂度为(n)，则快速排序算法的最好和最坏情况下的时间复杂度为（）。问题1选项A.分治B.动态规划C.贪心D.回溯问题2选项A.(n)和(nlgn)B.(n)和(n2)C.(nlgn)和(nlgn)D.(nlgn)和(n2)答案：AD 本题解析：暂无解析4. 填空题：（）模式将一个复杂对象的构建与其表示分离，使得同样的构建过程可以创建不同的表示。以下（）情况适合选用该模式。抽象复杂对象的构建步骤基于构建过程的具体实现构建复杂对象的不同表示一个类仅有一个实例一个类的实例只能有几个不同状态组合中的一种问题
4、1选项A.生成器（Builder）B.工厂方法（Factory Method）C.原型（Prototype）D.单例（Singleton）问题2选项A.B.C.D.答案：AA 本题解析：暂无解析5. 问答题：模式匹配是指给定主串t和子串s，在主串t中寻找子串s的过程，其中s称为模式。如果匹配成功，返回s在t中的位置，否则返回-1。KMP算法用next数组对匹配过程进行了优化。KMP算法的伪代码描述如下：1在串t和串s中，分别设比较的起始下标i=j=0。2如果串t和串s都还有字符，则循环执行下列操作：（1）如果j=-l或者ti=sj，则将i和j分别加1，继续比较t和s的下一个字符；（2）否则，将
5、j向右滑动到nextj的位置，即j=nextj。3如果s中所有字符均已比较完毕，则返回匹配的起始位置（从1开始）；否则返回-1。其中，next数组根据子串s求解。求解next数组的代码已由get_next函数给出。【C代码】（1）常量和变量说明t，s：长度为lt和Is的字符串next:next数组，长度为ls（2）C程序#includestdio.h#includestdlib.h#includestring.h/*求next的值*/void get_next(int*next,char*s,int ls)int i=0，j=-1;next0=-1;/*初始化next0*/while(ils)
6、/*还有字符*/if(j=-1l lsi=sj)/*匹配*/j+;i+;if(si=sj)nexti=nextj;elseNexti=j;elsej=nextj;int kmp(int*next,char*t,char*s,int lt,int Is)Int i=0,j=0;while(ilt&（1）)if(j=-1|（2）)i+;j+;else（3）;if(j=ls)return（4）;elsereturn-1;【问题1】（8分）根据题干说明，填充C代码中的空（1）（4）.【问题2】（2分）根据题干说明和C代码，分析出kmp算法的时间复杂度为（5）（主串和子串的长度分别为lt和ls，用O符号
7、表示）。【问题3】（5分）根据C代码，字符串“BBABBCAC”的next数组元素值为（6）（直接写素值，之间用逗号隔开）。若主串为“AABBCBBABBCACCD”，子串为“BBABBCAC”，则函数Kmp的返回值是（7）。答案： 本题解析：【问题1】（1）：jls;（2）：ti=sj;（3）：j=nextj;（4）：i-ls+1或其等价形式;【问题2】O(It+Is)【问题3】（6）：-1,-1,1,-1,-1,2,0,0，（7）6。【问题1】本题问题1根据KMP算法的伪代码描述进行推导。根据伪代码中第2步可以推导（1）是判断字符串s是否还有字符，即jls。i表示字符串t的下标，j表示字符
8、串s的下标。根据伪代码第2.1步可以推导（2）是判断字符串t和字符串s当前位置的字符是否相同，即ti=sj。根据伪代码第2.2步可以推导（3）是当第2.1步判断条件不满足时，改变j所指向的字符位置。即j=nextj。根据伪代码第3步可以推导（4）是返回匹配的起始位置。由于当前i所指向字符串中匹配子串的最后一个字符的位置，且已知子串的长度为ls。（4）的代码为i-ls+1或其等价形式。【问题2】本题问题2是计算KMP算法的复杂度。算法的复杂度一般考虑最坏情况，那么在子串读到ls及主串读到It的时候是最坏情况。所以复杂度是O(It+Is)【问题3】本题问题3中已知字符串“BBABBCAC”，则根据
9、get_next()函数可以求得next数组的元素值为-1,-1,1,-1,-1,2,0,0。并计算得到起始位置为6。代入字符串“BBABBCAC”到get_next函数。void get_next(int*next,char*s,int ls)int i=0，j=-1;next0=-1;/*初始化next0*/while(ils)/*还有字符*/if(j=-1l lsi=sj)/*匹配*/j+;i+;if(si=sj)nexti=nextj;elseNexti=j;elsej=nextj;这里涉及的只是代码的代入分析过程，注意循环的处理即可。下面将循环过程依次代入数值并且写作顺序处理过程如下
10、：传参：s=B,B,A,B,B,C,A,C，ls=8，next数组只声明未取值。初始化：i=0,j=-1,next0=-1。while(ils)执行后面的循环体，即当i8时执行循环。（1）当i=0,j=-1时：判断if(j=-1|s0=s-1)，满足条件1执行下一步：i+=1,j+=0。判断if(s1=s0)，满足条件执行下一步next1=next0=-1。【此时i=1,j=0】（2）当i=1,j=0时：判断if(j=-1|s1=s0)，满足条件2执行下一步：i+=2,j+=1。判断if(s2=s1)，不满足条件执行else下一步next2=j=1。【此时i=2,j=1】（3）当i=2,j=1
11、时：判断if(j=-1|s2=s1)，不满足条件1和2执行else下一步：j=next1=-1。【此时i=2,j=-1】（4）当i=2,j=-1时：判断if(j=-1|s2=s-1)，满足条件1执行下一步：i+=3,j+=0。判断if(s3=s0)，满足条件执行下一步next3=next0=-1。【此时i=3,j=0】（5）当i=3,j=0时：判断if(j=-1|s3=s0)，满足条件2执行下一步：i+=4,j+=1。判断if(s4=s1)，满足条件执行下一步next4=next1=-1。【此时i=4,j=1】（6）当i=4,j=1时：判断if(j=-1|s4=s1)，满足条件2执行下一步：i
12、+=5,j+=2。判断if(s5=s2)，不满足条件执行else下一步next5=j=2。【此时i=5,j=2】（7）当i=5,j=2时：判断if(j=-1|s5=s2)，不满足条件1和2执行else下一步：j=next2=1。【此时i=5,j=1】（8）当i=5,j=1时：判断if(j=-1|s5=s1)，不满足条件1和2执行else下一步：j=next1=-1。【此时i=5,j=-1】（9）当i=5,j=-1时：判断if(j=-1|s5=s-1)，满足条件1执行下一步：i+=6,j+=0。判断if(s6=s0)，不满足条件执行else下一步next6=j=0。【此时i=6,j=0】（10）
13、当i=6,j=0时：判断if(j=-1|s6=s0)，不满足条件1和2执行else下一步：j=next0=-1。【此时i=6,j=-1】（11）当i=6,j=-1时：判断if(j=-1|s6=s-1)，满足条件1执行下一步：i+=7,j+=0。判断if(s7=s0)，不满足条件执行else下一步next7=j=0。【此时i=7,j=0】（12）当i=7,j=0时：判断if(j=-1|s7=s0)，不满足条件1和2执行else下一步：j=next0=-1。【此时i=7,j=-1】（13）当i=7,j=-1时：判断if(j=-1|s7=s0)，满足条件1执行下一步：i+=8，i=ls，退出while循环。next数组下标从0到7，结果分别为：-1，-1，1，-1，-1，2，0，06. 填空题：在面向对象技术中，不同的对象在收到同一消息时可以产生完全不同的结果，这一现象称为（），它由（）机制来支持。利用类的层次关系，把具有通用功能的消息存放在高层次，而不同的实现这一功能的行为放在较低层次，在这些低层次上生成的对象能够给通用消息以不同的响应。问题1选项A.绑定B.继承C.消息D.多态问题2选项A.绑定B.继承C.消息D.多态答案：DB 本题解析：暂无解析7. 填空题：某文件系统
