软件水平考试（中级）软件设计师上午（基础知识）历年真题试卷汇编1
(总分70, 做题时间90分钟)
1. 选择题
选择题（）下列各题A、B、C、D四个选项中，只有一个选项是正确的，请将此选项涂写在答题卡相应位置上，答在试卷上不得分。
1.
采用顺序表和单链表存储长度为n的线性序列，根据序号查找元素，其时间复杂度分别为(51)。
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
答案: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
答案: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
解析：对于单向循环链表，可以从表中任意节点出发都能遍历整个链表。但并不能对表中的任意节点进行随机访问，需要从设置的第一个节点开始，沿着指针访问表中的节点。当然访问某一节点的直接后继节点最快，访问其直接前驱节点最慢，因为首先要遍历要表尾，然后从表头遍历到其前驱节点。
10.
设循环队列Q的定义中有rear和len两个域变量，其中rear表示队尾元素的指针，len表示队列的长度，如图8—3所示(队列长度为3，队头元素为e)。设队列的存储空间容量为M，则队头元素的指针为(57)。
A (Q．rear+Q．len—1)
B (Q．rear+Q．len一1+M)％M
C (Q．rear一Q．len+1)
D (Q．rear—Q．len+1+M)％M
分值: 2
答案:D
解析：队列的存储空间容量为M，说明队列中最多可以有M个元素；队列的长度为len，说明当前队列中有len个元素。设队列的队头指针为front，front指向队头元素，则有：Q．rear=(Q．front+Q．1en一1)％M Q．front=(Q．rear一Q．len+1+M)％M
11.
栈是一种按“后进先出”原则进行插入和删除操作的数据结构，因此，(60)必须用栈。
A 实现函数或过程的递归调用及返回处理时
B 将一个元素序列进行逆置
C 链表节点的申请和释放
D 可执行程序的装入和卸载
分值: 2
答案:A
解析：栈是一种后进先出的数据结构。将一个元素序列逆置时，可以使用栈也可以不用。链表节点的申请和释放次序与应用要求相关，不存在“先申请后释放”的操作要求。可执行程序的装入与卸载，也不存在“后进先出”的操作要求。对于函数的递归调用与返回，一定是后被调用执行的先返回。
12.
若对一个链表最常用的操作是在末尾插入节点和删除尾节点，则采用仅设尾指针的单向循环链表(不含头节点)时，(65)。
A 插入和删除操作的时间复杂度都为O(1)
B 插入和删除操作的时间复杂度都为O(n)
C 插入操作的时间复杂度为O(1)，删除操作的时间复杂度为O(n)
D 插入操作的时间复杂度为O(n)，删除操作的时间复杂度为O(1)
分值: 2
答案:C
解析：设尾指针的单项循环链表(不含头节点)如图8—4所示：设节点的指针域为next，新节点的指针为s，则在尾指针所指节点后插入节点的操作为： S一>next=t一>next；t一>next=S；t=S； 也就是插入操作的时间复杂度为O(1)。 要删除尾指针所指节点，必须通过遍历操作找到尾节点的前驱节点，其操作序列如下： if(t一>next==t)free(t)； eiSe{ P=t一>next； whiie(p一>next!=t) p=p一>next； P一>next=t一>next； free(t
13.
对二维数组a[1一N，1一N]中的一个元素a[i,j](1≤i，j≤N)，存储在a嘶]之前的元素个数(21)。
A 与按行存储或按列存储方式无关
B 在i=j时与按行存储或按列存储方式无关
C 在按行存储方式下比按列存储方式下要多
D 在按行存储方式下比按列存储方式下要少
分值: 2
答案:B
解析：存储在a[i,j]之前的元素个数与按行存储或按列存储方式有关。按行存储时，存储在a[i,j]之前的元素个数为(i—1) * N+j一1_iN+j—N—1；按列存储时，存储在a[i,j]之前的元素个数为(j—1) * N+i—1=jN+i—N—1。很显然，i
14.
若二维数组arr[1一M，1一N]的首地址为base，数组元素按列存储且每个元素占用K个存储单元，则元素arr[i，j]在该数组空间的地址为(21)。
A base+((i—1)×M+j—1)×K
B base+((i一1)×N+j—1)×K
C base+((j一1)×M+i一1)×K
D base+((j一1)×N+i一1)×K
分值: 2
答案:C
解析：数据art共M行N列，下标均从1开始。元素arr[i,j]在数据arr的第i行第j列，如果数组元素按列存储，则1~j-1列共有(j—1)×M个元素，a[i,j]之前共(j一1)×M+i一1个元素，元素arr[i，j]在该数组空间的地址为为base+((j一1)×M+i一1)×K。
15.
设下三角矩阵(上三角部分的元素值都为0)A[0...n，0...n]如下所示，将该三角矩阵的所以非零元素(即行下标不小于列下标的元素)按行优先压缩存储在容量足够大的数组M[1...m]中，则元素A[i，j](0≤i≤n，j≤i)存储在数组M的(57)中。
A
B
C
D
分值: 2
答案:A
解析：第0行有1个元素保存在数组M中，第l行有2个元素保存在数组M中，第i一1行中有i个元素保存在数组M中，第i行之前有1+2+3+…+i=i(i+1)／2个元素保存在数组M中，元素A[i，j]是第i行的j+1个元素。由于数组M的下标从1开始，因此A[i,j]的值存储在中。
16.
设有如下所示的下三角矩阵A【0...8，0...8】，将该三角矩阵的非零元素(即行下标不小于列下标的所有元素)按行优先压缩存储在数组M[1...m]中，则元素A嘶】(0≤i≤8,j≤i)存储在数组M的(58)中。
A
B
C
D
分值: 2
答案:A
解析：如图所示，按行方式压缩存储时，A[i，j]之前的元素数目为(1+2+…+i+j)个，数组M的下标从1开始，因此A[i,j]的值存储在中。
17.
一个高度为h的满二叉树的节点总数为2 b 一1，从根结点开始，自上而下、同层次结点从左至右，埘结点按照顺序依次编号，即根节点编号为1，其左、右孩子节点编号分为2和3，再下一层从左到右的编号为4、5、6、7，依次类推。那么，在一颗满二叉树中，对于编号为m和n的两个节点，若n=2m+1，则()结点。
A m是n的左孩子
B m是n的右孩子
C n是m的左孩子
D n是m的右孩子
分值: 2
答案:D
解析：由于该二叉树为满二叉树，且根节点编号从1开始，由满二叉树的性质可知父节点m和右孩子之间的关系为n=2m+1。
18.
以下关于哈夫曼树的叙述，正确的是(60)。
A 哈夫曼树一定是满二叉树，其每层结点数都达到最大值
B 哈夫曼树一定是平衡二叉树，其每个结点左右子树的高度差为一1、0或1
C 哈夫曼树中左孩子结点的权值小于父结点、右孩子结点的权值大于父结点
D 哈夫曼树中叶子结点的权值越小则距离树根越远、叶子结点的权值越大则距离树根越近
分值: 2
答案:D
解析：哈夫曼树即最优二叉树，是一类带权路径长度的最短的树。树的带权路径为书中所有叶子节点的带权路径长度之和，记为： 其中，n为带权叶子节点的数目，w k 为叶子节点的权值，l k 为叶子节点到根的路径长度。哈夫曼树是指权值为w 1 ,w 2 ,…，w n 的n个叶子节点的二叉树中带权路径长度最小的二又树。哈夫曼树与完全二叉树、平衡二叉树之间没有必然的联系。选项A、B中的说法是错误的。在哈夫曼树的构建中，由哈夫曼树的
19.
若某二叉树的后序遍历序列为KBFDCAE，中序遍历序列为BKFEACD，则该二又树为(58)。
A
B
C
D
分值: 2
答案:A
解析：本题考查二叉树的遍历算法，根据中序遍历序列和另一种遍历序列的结果，可以确定该二叉树。后序遍历是按照左子树、右子树、根节点的顺序进行遍历，中序遍历是按照左子树、根节点、右子树的顺序进行遍历。E为根节点，K为B的右子树，因此应选A项描述的二叉树。
20.
若n 2 、n 1 、n 0 分别表示一个二叉树中度为2、度为1和叶子节点的数目(节点的度定义为节点的子树数目)，则对于任何一个非空的二叉树，(59)。
A
n 2 一定大于n 1
B
n 1 一定大于n 0
C
n 2 一定大于n 0
D
n 0 一定大于n 2
分值: 2
答案:D
解析：由二叉树的性质可知，度为0的节点比度为2的节点数多1，即n 0 =n 2 +1，因此n 0 一定大于n 2 。
21.
一棵满二叉树，其每一层节点个数都达到最大值，对其中的节点从1开始顺序编号，即根节点编号为1，其左、右孩子节点编号分别为2和3，再下一层从左到右的编号为4、5、6、7，依此类推，每一层都从左到右依次编号，直到最后的叶子节点层为止，则用(60)可判定编号为m和n的两个节点是否在同一层。
A
log 2 m=log 2 n
B
[log 2 m]=[log 2 n]
C
[log 2 m]+1=[log 2 n]
D
[log 2 m]=[log 2 n]+1
分值: 2
答案:B
解析：由于是满二叉树，只有m个节点的二叉树一定是完全二叉树，只有n个节点的二叉树也一定是完全二叉树，因此，具有m个节点的完全二叉树的深度为[log 2 m]+1，具有n个节点的完全二叉树的深度为[log 2 n]+1。如果编号为m和n的两个节点是在同一层，则有[log 2 m]+1=[log2n]+1，即[log 2 m]=[log 2 ,n]。
22.
(61)是由权值集合{8，5，6，2}构造的哈夫曼树(最优二叉树)。
A
B
C
D
分值: 2
答案:C
解析：哈夫曼树是带权路径最短的树。选项A、B、C、D四棵树的带权路径长度分别如下。选项A：8×2+5×2+6×2+2×2=412选项B：8×3+5×3+6×2+2=53选项C：8+6×2+2×3+5×3=41选项D：2+5×2+6×3+8×3=54
23.
以下编码方法中，(12)属于熵编码。
A 哈夫曼编码
B 小波变换编码
C 线性预测编码
D 行程编码
分值: 2
答案:A
解析：熵编码根据信息熵理论，编码时只压缩冗余而不损伤信息熵，是一种无损压缩。常见的熵编码有哈夫曼编码、游程编码和算术编码。
24.
在(59)中，任意一个节点的左、右子树的高度之差的绝对值不超过1。
A 完全二又树
B 二叉排序树
C 线索二叉树
D 最优二叉树
分值: 2
答案:A
解析：对于完全二叉树，若设二叉树的高度为h，除第h层外，其他各层(1～h一1)的节点数都达到最大个数，第h层所有的节点都连续集中在最左边，这就是完全二又树。在完全二叉树中，任意一个节点的左、右子树的高度之差的绝对值不超过1。二叉排序树(BinarySortTree)又称二叉查找树。它或者是一棵空树，或者是具有下列性质的二叉树：①若左子树不空，则左子树上所有节点的值均小于它的根节点的值；②若右子树不空，则右子树上所有节点的值均大于它的根节点的值；③左、右子树也分别为二叉排序树。对于二叉排序树，由于左子树或右子树可
25.
下面关于哈夫曼树的叙述中，正确的是(58)。
A 哈夫曼树一定是完全二叉树
B 哈夫曼树一定是平衡二叉树
C 哈夫曼树中权值最小的两个节点互为兄弟节点
D 哈夫曼树中左孩子节点小于父节点、右孩子节点大于父节点
分值: 2
答案:C
解析：哈夫曼树即最优二叉树，是一类带权路径长度的最短的树。树的带权路径为书中所有叶子节点的带权路径长度之和，记为： 其中，n为带权叶子节点的数目，w k 为叶子节点的权值，l k 为叶子节点到根的路径长度。则哈夫曼树是指权值为w 1 、w 2 、…、w n 的n个叶子节点的二叉树中带权路径长度最小的二叉树。哈夫曼树与完全二叉树、平衡二叉树之间没有必然的联系。选项A、B中的说法是错误的。在哈夫曼树的构建中，由哈夫曼树
26.
已知一棵度为3的树(一个节点的度是指其子树的数目，树的度是指该树中所有节点的度的最大值)中有5个度为1的节点，4个度为2的节点，2个度为3的节点，那么，该树中的叶子节点数目为(61)。
A 10
B 9
C 8
D 7
分值: 2
答案:B
解析：树的节点总数为：5+4×2+2×3+1=20，叶子节点数为：20—5—4—2=9。
27.
2010年11月真题62某算法的时间复杂度可用递归式表示，若用Θ表示该算法的渐进时间复杂度的紧致界，则正确的是(62)。
A
Θ(nlg 2 n)
B Θ(nlgn)
C
Θ(n 2 )
D
Θ(n 2 )
分值: 2
答案:A
解析：采用主定理来求解递归式。a=2，b=2，f(n)=nlgn，log b a=1，f(n)=O(n logba lg k n)=nlgn，因此k=1，属于主定理的情况(2)，因此有T(n)=Θ(n logba lg k+1 n)=Θ(nlg 2 n)。
28.
若用n个权值构造一棵最优二叉树(哈夫曼树)，则该二叉树的节点总数为(59)。
A 2n
B 2n一1
C 2n+1
D 2n+2
分值: 2
答案:B
解析：二叉树具有以下性质：度为2的几点(双分支节点)数比度为0(叶子节点)数正好少1。而根据最优二叉树(哈夫曼树)的构造过程可知，最优二叉树中只有度为2和0的节点，因此，其节点总数为2n一1。
29.
用关键字序列10、20、30、40、50构造的二叉树排序(二叉查找树)为(63)。
A
B
C
D
分值: 2
答案:C
解析：根据关键字序列构造二叉排序树的基本过程是，若需插入的关键字大于树根，则插入到右子树上，若小于树根，则插入到左子树上，若为空，则作为树根节点。
30.
若某算法在问题规模为n时，其基本操作的重复次数可由下式表示，则该算法的时间复杂度为()。
A O(n)
B
O(n 2 )
C O(logn)
D O(nlogn)
分值: 2
答案:B
解析：根据题中给出的递归定义式进行推导，可得T(n)=n+n—1+…+2+1，因此时间复杂度为O(n 2 )。
31.
在一个有向图G的拓扑序列中，顶点v i 列在v j 之前，说明图G中(59)。
A
一定存在弧 i，vj>
B
一定存在弧 j，vi>
C
可能存在v i 到v j 的路径，而不可能存在v j 到v i 的路径
D
可能存在v j 到 i 的路径，而不可能存在v i 到v j 的路径
分值: 2
答案:C
解析：根据有向图G的拓扑序列定义，顶点v i 排列在v j 之前，可以得知可能存在v i 到v j 的路径，拓扑序列是单向的，所以不可能从v j 到v i 的路径。所以本题答案选C。
32.
拓扑排序是将有向图中所有顶点排成一个线性序列的过程，并且该序列满足：若在AOV网中从顶点V i 到V j 有一条路径，则顶点V i 必然在顶点V j 之前。对于图8—7所示的有向图，(60)是其拓扑序列。
A 1234576
B 1235467
C 2135476
D 2134567
分值: 2
答案:C
解析：对AOV网进行拓扑排序的方法如下：(1)在AOV网中选择一个入度为0(没有前驱)的顶点且输出它；(2)从网中删除该顶点及与该顶点有关的所有边；(3)重复上述两步，直至网中不存在入度为0的顶点为止。本题中只有序列“2135476”是其拓扑序列。
33.
从存储空间的利用率角度来看，以下关于数据结构中图的存储的叙述，正确的是(60)。
A 有向图适合采用邻接矩阵存储，无向图适合采用邻接表存储
B 无向图适合采用邻接矩阵存储，有向图适合采用邻接表存储
C 完全图适合采用邻接矩阵存储
D 完全图适合采用邻接表存储
分值: 2
答案:C
解析：邻接矩阵是用矩阵来指出顶点和顶点之间是否存在着关系。如果图有n个节点，则需要用n 2 个元素来表示顶点间的关系。邻接表是图的一种链式存储结构。在邻接表中，图中的每一个顶点都需要建立一个单链表，第i个单链表中的节点表示依附于顶点v i 的边。对于无向图，若无向图有n个顶点，e条边，则它的邻接表需要n个头节点和2e个表节点。对于有向图，若有n个顶点、e条边，则它的邻接表需要n个头节点和e个表节点。等e<
算术表达式采用逆波兰式表示时不用括号，可以利用(20)进行求值。与逆波兰式ab—cd+ * 对应的中缀表达式是(21)。
34.
(20)
A 数组
B 栈
C 队列
D 散列表
分值: 2
答案:B
35.
(21)
A
a—b+c * d
B
(a—b) * c+d
C
(a—b) * (c+d)
D
a—b * c+d
分值: 2
答案:C
解析：逆波兰式表示方式把运算符写在运算对象的后面，不需要使用括号。由于后缀表示中的各个运算是按顺序执行的，因此，它的计值很容易实现。为此，仅需从左到右依次扫视表达式中的各个符号，每遇到运算对象，就把它压入栈顶暂存起来；每遇到一个二元(或一元)运算符时，就取出栈顶的两个(或一个)运算对象进行相应的运算，并用运算结果去替换栈顶的这两(或一)个运算对象，然后再继续扫视余留的符号，如此等等，直到扫视完整个表达式为止。当上述过程结束时，整个表达式的值将留于栈顶。a－b+c * d对应的逆波兰式为：ab－
窗体顶端
窗体底端下载本文
