软件水平考试（中级）软件设计师上午（基础知识）历年真题试卷汇编1
(总分70, 做题时间90分钟)
1. 选择题
选择题（）下列各题A、B、C、D四个选项中，只有一个选项是正确的，请将此选项涂写在答题卡相应位置上，答在试卷上不得分。
1.
A 0(1)、0(1)
B 0(1)、0(n)
C 0(n)、0(1)
D 0(n)、0(n)
分值: 2
答案:B
解析：顺序表存储位置是相邻连续的，可以随即访问的一种数据结构，一个顺序表在使用前必须指定起长度，一旦分配内存，则在使用中不可以动态的更改。他的优点是访问数据是比较方便，可以随即的访问表中的任何一个数据。链表是通过指针来描述元素关系的一种数据结构，他可以是物理地址不连续的物理空间。不能随即访问链表元素，必须从表头开始，一步一步搜索元素。它的优点是：对于数组，可以动态的改变数据的长度，分配物理空间。因此两者的查复杂度就显而易见了。
2.
设元素序列a、b、c、d、e、f经过初始为空的栈S后，得到出栈序列cedfba，则栈S的最小容量为(52)。
A 3
B 4
C 5
D 6
分值: 2
2022年中考分数怎么查答案:B
解析：此题考查栈的用法，根据题中出栈的顺序，当元素c出栈后，栈中有元素a、b，当元素e出栈之前，栈中有元素a、b、d、e，此时栈中的元素达到最多。因此栈S最小容量为4。
3.
山西省人社厅登录查询输出受限的双端队列是指元素可以从队列的两端输入、但只能从队列的一端输出，如图8—1所示。若有e1、e2、e3、e4依次进入输出受限的双端队列，则得不到输出队列(53)。
A e4、e3、e2、e1
B e4、e2、e1、e3
C e4、e3、e1、e2
D e4、e2、e3、e1
分值: 2
答案:22年省考成绩查询D
解析：此题考查队列的性质，队列为先进先出的线性结构，题中给出的受限的双端队列，
两端都可以进，而一端可出，假设分a和b端，b端可以进出，由D选项的出序列，可以看出e1、e2、e3按顺序从a端进入，而e4从b端进入，当e4从b端出来之后，无法将后面的e2出队列，故D选项有误。
4.
以下关于线性表存储结构的叙述，正确的是(57)。
A 线性表采用顺序存储结构时，访问表中任意一个指定序号元素的时间复杂度为常量级
B 线性表采用顺序存储结构时，在表中任意位置插入新元素的运算时间复杂度为常量级
C 线性表采用链式存储结构时，访问表中任意一个指定序号元素的时间复杂度为常量级
D 线性表采用链式存储结构时，在表中任意位置插入新元素的运算时间复杂度为常量级
分值: 2
答案:A
解析：顺序存储结构可以随机存取，时间复杂度最低为常量级的，答案选A。
5.
设循环队列Q的定义中有front和size两个域变量，其中front表示队头元素的指针，size表示队列的长度，如图8．2所示(队列长度为3，队头元素为X、队尾元素为z)。设队列的存储空间容量为M，则队尾元素的指针为(58)。
A (Q．front+Q．size一1)
B (Q．front+Q．size—1+M)％M
C (Q．front—Q．size)
D (Q．front—Q．size+M)％M
分值: 2
答案:B
解析：考虑到循环，会对M进行求模，元素的指针从0开始到M一1，所以队尾元素指针为答案B。
6.
在字符串的模式匹配过程中，如果模式串的每个字符依次和主串中的一个连续的字符序列相等，则成为匹配成功。如果不能在主串中到与模式串相同的子串，则称为匹配失败。在布鲁特一福斯模式匹配算法(朴素的或基本的模式匹配)中，若主串和模式串的长度分别为n和m(且n远大于m)，且恰好在主串末尾的n个字符处匹配成功，则在上述的模式匹配过程中，字符的比较次数最多为(57)。
A
n * m
贵州人才招聘网B
(n—m+1) * m
C
(n—m一1) * m
D
(n—m) * n
分值: 2
答案:B
解析：在最坏的情况下，每一趟不成功的匹配都是模式串的最后一个字符与主串中相应的字符不相等，则主串中新一趟的起始位置为i—m+2。若从主串的第i个字符开始匹配时成功，则前i趟不成功的匹配中，每趟都比较了m次，总共比较了i * m次，第i+1趟的成功匹配也比较了m次。因此，在本题所述的匹配模式中，字符的比较次数最多为(n．m+1) * m次。
7.
对于一个长度大于1且不存在重复元素的序列，令其所有元素依次通过一个初始为空的队列后，再通过一个初始为空的栈。设队列和栈的容量都足够大，一个序列通过队列(栈)的含义是序列的每个元素都入队列(栈)且出队列(栈)一次且仅一次。对于该序列在上述队列和栈上的操作，正确的是(57)。
A 出队序列和出栈序列一定相同
B 出队序列和出栈序列一定互为逆序
C 入队序列和出队序列一定相同，入栈序列和出栈序列不一定相同
D 入栈序列和出栈序列一定互为逆序，入队序列和出队序列不一定互为逆序
分值: 2
答案:C
解析：队列具有先进先出的特点，也就是说最先入队的元素最先出队，所以入队序列和出队序列一定相同。栈则具有先进后出的特点，如果所有元素进栈后再依次出栈，则入栈序列和出栈序列互为逆序，否则不一定。
8.
在字符串的KMP模式匹配算法中，需要求解模式串p的next函数值，其定义如下所示。若模式串p为“aaabaaa”，则其next函数值为(58)。
A 123123
B 123210
C 123432
D 123456
证券从业成绩查询 分值: 2
答案:A
解析：j=1时，next[1]=0。j=2时，不存在k，满足1＜k＜j，则next[2]=1。j=3时，k只能取2，等式的左边为p1，等式的右边为p 2 ，p 1 =p 2 =a，next[3]=2。j=4时，k可以取2和3，k取2的时候，左边为p 1 ，右边为p 3 ，p 1 =p 3 =a；k取3时，左边为p 1 p 2 ，右边为P 2
9.
对于线性表(由n个同类元素构成的线性序列)，采用单向循环链表存储的特定之一是(58)。
A 从表中任意节点出发都能遍历整个链表
B 对表中的任意节点可以进行随机访问
C 对于表中的任意一个节点，访问其直接前驱和直接后继节点所有时间相同
D 第一个节点必须是头节点
分值: 2
初级会计报名费用多少答案:A
解析：对于单向循环链表，可以从表中任意节点出发都能遍历整个链表。但并不能对表中的任意节点进行随机访问，需要从设置的第一个节点开始，沿着指针访问表中的节点。当然访问某一节点的直接后继节点最快，访问其直接前驱节点最慢，因为首先要遍历要表尾，然后从表头遍历到其前驱节点。
发布评论