1、软件水平考试（中级）软件设计师上午（基础知识）历年真题试卷汇编 12及答案与解析 1 采用顺序表和单链表存储长度为 n的线性序列，根据序号查找元素，其时间复杂度分别为 (51)。 （ A） 0(1)、 0(1) （ B） 0(1)、 0(n) （ C） 0(n)、 0(1) （ D） 0(n)、 0(n) 2 设元素序列 a、 b、 c、 d、 e、 f经过初始为空的栈 S后，得到出栈序列 cedfba，则栈 S的最小容量为 (52)。 （ A） 3 （ B） 4 （ C） 5 （ D） 6 3 输出受限的双端队列是指元素可以从队列的两端输入、 但只能从队列的一端输出，如图81所示。若有 e1
2、、 e2、 e3、 e4 依次进入输出受限的双端队列，则得不到输出队列 (53)。 （ A） e4、 e3、 e2、 e1 （ B） e4、 e2、 e1、 e3 （ C） e4、 e3、 e1、 e2 （ D） e4、 e2、 e3、 e1 4 以下关于线性表存储结构的叙述，正确的是 (57)。 （ A）线性表采用顺序存储结构时，访问表中任意一个指定序号元素的时间复杂度为常量级 （ B）线性表采用顺序存储结构时，在表中任意位置插入新元素的运算时间复杂度为常量级 （ C）线性表采用链式存储结构时，访 问表中任意一个指定序号元素的时间复杂度为常量级 （ D）线性表采用链式存储结构时，在表中任意位
3、置插入新元素的运算时间复杂度为常量级 5 设循环队列 Q的定义中有 front和 size两个域变量，其中 front表示队头元素的指针， size表示队列的长度，如图 8 2所示 (队列长度为 3，队头元素为 X、队尾元素为 z)。设队列的存储空间容量为 M，则队尾元素的指针为 (58)。 （ A） (Q front+Q size一 1) （ B） (Q front+Q size1+M) M （ C） (Q frontQ size) （ D） (Q frontQ size+M) M 6 在字符串的模式匹配过程中，如果模式串的每个字符依次和主串中的一个连续的字符序列相等，则成为匹配成功。如果不
4、能在主串中找到与模式串相同的子串，则称为匹配失败。在布鲁特一福斯模式匹配算法 (朴素的或基本的模式匹配 )中，若主串和模式串的长度分别为n和 m(且 n远大于 m)，且恰好在主串末尾的 n个字符处匹配成功，则在上述的模式匹配过程中，字符的比较次数最多为 (57)。 （ A） n*m （ B） (nm+1)*m （ C） (nm一 1)*m （ D） (nm)*n 7 对于一个长度大于 1且不存在重复元素的序列，令其所有元素依次通过一个初始为空的队列后，再通过一个初始为空的栈。设队列和栈的容量都足够大，一个序列通过队列 (栈 )的含义是序列的每个元素都入队列 (栈 )且出队列 (栈 )一次且仅一
5、次。对于该序列在上述队列和栈上的操作，正确的是 (57)。 （ A）出队序列和出栈序列一定相同 （ B）出队序列和出栈序列一定互为逆序 （ C）入队序列和出队序列一定相同，入栈序列和出栈序列不一定相同 （ D）入栈序列和出栈序列一定互为逆序，入队序列和出队序列不一定互为逆序 8 在字符串的 KMP模式匹配算法中，需要求解模式串 p的 next函数值，其定义如下所示。若模式串 p为 “aaabaaa”，则其 next函数值为 (58)。（ A） 123123 （ B） 123210 （ C） 123432 （ D） 123456 9 对于线性表 (由 n个同类元素构成的线性序列 )，采用单向循环
6、链表存储的特定之一是 (58)。 （ A）从表中任意节点出发都能遍历整个链表 （ B）对表中的任意节点可以进行随机访问 （ C）对于表中的任意一个节点，访问其直接前驱和直接后继节点所有时间相同 （ D）第一个节点必须是头节点 10 设循环队列 Q的定义中有 rear和 len两个域变量，其中 rear表示队尾元素的指针， len表示队列的长度，如图 83所示 (队列长度为 3，队头元素为 e)。设队列的存储空间容量为M，则队头元素的指针为 (57)。 （ A） (Q rear+Q len1) （ B） (Q rear+Q len一 1+M) M （ C） (Q rear一 Q len+1) （
7、 D） (Q rearQ len+1+M) M 11 栈是一种按 “后进先出 ”原则进行插入和删除操作的数据结构，因此， (60)必须用栈。 （ A）实现函数或 过程的递归调用及返回处理时 （ B）将一个元素序列进行逆置 （ C）链表节点的申请和释放 （ D）可执行程序的装入和卸载 12 若对一个链表最常用的操作是在末尾插入节点和删除尾节点，则采用仅设尾指针的单向循环链表 (不含头节点 )时， (65)。 （ A）插入和删除操作的时间复杂度都为 O(1) （ B）插入和删除操作的时间复杂度都为 O(n) （ C）插入操作的时间复杂度为 O(1)，删除操作的时间复杂度为 O(n) （ D）插入操
8、作的时间复杂度为 O(n)，删除操作的时间复杂度为 O(1) 13 对二维数组 a1一 N， 1一 N中的一个元素 ai,j(1i， jN)，存储在 a嘶 之前的元素个数 (21)。 （ A）与按行存储或按列存储方式无关 （ B）在 i=j时与按行存储或按列存储方式无关 （ C）在按行存储方式下比按列存储方式下要多 （ D）在按行存储方式下比按列存储方式下要少 14 若二维数组 arr1一 M， 1一 N的首地址为 base，数组元素按列存储且每个元素占用 K个存储单元，则元素 arri， j在该数组空间的地址为 (21)。 （ A） base+(i1)M+j1)K （ B） base+(i一
9、 1)N+j1)K （ C） base+(j一 1)M+i一 1)K （ D） base+(j一 1)N+i一 1)K 15 设下三角矩阵 (上三角部分的元素值都为 0)A0.n， 0.n如下所示，将该三角矩阵的所以非零元素 (即行下标不小于列下标的元素 )按行优先压缩存储在容量足够大的数组 M1.m中，则元素 Ai， j(0in， ji)存储在数组 M的 (57)中。（ A） （ B） （ C） （ D） 16 设有如下所示的下三角矩阵 A【 0.8， 0.8】，将该三角矩阵的非零元素 (即行下标不小于列下标的所有元素 )按行优先压缩存储在数组 M1.m中，则元素 A嘶】 (0i8,ji)存
10、储在数组 M的 (58)中。 （ A） （ B） （ C） （ D） 17 一个高度为 h的满二叉树的节点总数为 2b一 1，从根结点开始，自上而下、同层次结点从左至右，埘结点按照顺序依次编号，即根节点编号为 1，其左、右孩子节点编号分为 2和3，再下一层从左到右的编号为 4、 5、 6、 7，依次类推。那么，在一颗满二叉树中 ，对于编号为 m和 n的两个节点，若 n=2m+1，则 (64)结点。 （ A） m是 n的左孩子 （ B） m是 n的右孩子 （ C） n是 m的左孩子 （ D） n是 m的右孩子 18 以下关于哈夫曼树的叙述，正确的是 (60)。 （ A）哈夫曼树一定是满二叉树，其
11、每层结点数都达到最大值 （ B）哈夫曼树一定是平衡二叉树，其每个结点左右子树的高度差为一 1、 0或 1 （ C）哈夫曼树中左孩子结点的权值小于父结点、右孩子结点的权值大于父结点 （ D）哈夫曼树中叶子结点的权值越小则距离树根越远、叶子结点的权值越大则距离树根越近 19 若某二叉树的后序遍历序列为 KBFDCAE，中序遍历序列为 BKFEACD，则该二又树为 (58)。 （ A） （ B） （ C） （ D） 20 若 n2、 n1、 n0分别表示一个二叉树中度为 2、度为 1和叶子节点的数目 (节点的度定义为节点的子树数目 )，则对于任何一个非空的二叉树， (59)。 （ A） n2一定大于
12、 n1 （ B） n1一定大于 n0 （ C） n2一定大于 n0 （ D） n0一定大于 n2 21 一棵满二叉树，其每一层节点个数都达到最大值，对其中的节点从 1开始顺序编号，即根节点编号为 1，其左、 右孩子节点编号分别为 2和 3，再下一层从左到右的编号为 4、 5、6、 7，依此类推，每一层都从左到右依次编号，直到最后的叶子节点层为止，则用 (60)可判定编号为 m和 n的两个节点是否在同一层。 （ A） log2m=log2n （ B） log2m=log2n （ C） log2m+1=log2n （ D） log2m=log2n+1 22 (61)是由权值集合 8， 5， 6，
13、2构造的哈夫曼树 (最优二叉树 )。 （ A） （ B） （ C） （ D） 23 以下编码方法中， (12)属于 熵编码。 （ A）哈夫曼编码 （ B）小波变换编码 （ C）线性预测编码 （ D）行程编码 24 在 (59)中，任意一个节点的左、右子树的高度之差的绝对值不超过 1。 （ A）完全二又树 （ B）二叉排序树 （ C）线索二叉树 （ D）最优二叉树 25 下面关于哈夫曼树的叙述中，正确的是 (58)。 （ A）哈夫曼树一定是完全二叉树 （ B）哈夫曼树一定是平衡二叉树 （ C）哈夫曼树中权值最小的两个节点互为兄弟节点 （ D）哈夫曼树中左孩子节点小于父节点、右孩子节点大于父节点
14、26 已知一棵度为 3的 树 (一个节点的度是指其子树的数目，树的度是指该树中所有节点的度的最大值 )中有 5个度为 1的节点， 4个度为 2的节点， 2个度为 3的节点，那么，该树中的叶子节点数目为 (61)。 （ A） 10 （ B） 9 （ C） 8 （ D） 7 27 2010年 11 月真题 62 某算法的时间复杂度可用递归式表示，若用 表示该算法的渐进时间复杂度的紧致界，则正确的是 (62)。 （ A） (nlg2n) （ B） (nlgn) （ C） (n2) （ D） (n2) 28 若用 n个权值构造一棵最优二叉树 (哈夫曼树 )，则该二叉树的节点 总数为 (59)。 （ A
15、） 2n （ B） 2n一 1 （ C） 2n+1 （ D） 2n+2 29 用关键字序列 10、 20、 30、 40、 50 构造的二叉树排序 (二叉查找树 )为 (63)。 （ A） （ B） （ C） （ D） 30 若某算法在问题规模为 n时，其基本操作的重复次数可由下式表示，则该算法的时间复杂度为 (64)。 （ A） O(n) （ B） O(n2) （ C） O(logn) （ D） O(nlogn) 31 在一个有向图 G的拓扑序列中，顶点 vi列在 vj之前，说明图 G中 (59)。 （ A）一定 存在弧 i， vj （ B）一定存在弧 j， vi （ C）可能存在 vi到
16、vj的路径，而不可能存在 vj到 vi的路径 （ D）可能存在 vj到 i的路径，而不可能存在 vi到 vj的路径 32 拓扑排序是将有向图中所有顶点排成一个线性序列的过程，并且该序列满足：若在 AOV网中从顶点 Vi到 Vj有一条路径，则顶点 Vi必然在顶点 Vj之前。对于图 87所示的有向图，(60)是其拓扑序列。 （ A） 1234576 （ B） 1235467 （ C） 2135476 （ D） 2134567 33 从存储空间的利用率角度来看，以下 关于数据结构中图的存储的叙述，正确的是 (60)。 （ A）有向图适合采用邻接矩阵存储，无向图适合采用邻接表存储 （ B）无向图适合采用邻接矩阵存储，有向图适合采用邻接表存储 （ C）完全图适合采用邻接矩阵存储 （ D）完全图适合采用邻接表存储 33 算术表达式采用逆波兰式表示时不用括号，可以利用 (20)进行求值。与逆波兰式 abcd+*对应的中缀表达式是 (21)。 34 (20) （ A）数组 （ B）栈 （ C）队列 （ D）散列表 35 (21) （ A） ab+c*d （ B） (ab)*c+d （ C） (ab)*(c+d) （ D） ab*c+d 软件水平考试（中级）软件设计师上午（基础知识）历年真题试卷汇编 12答案与解析
