1、软件水平考试（中级）软件设计师上午（基础知识）历年真题试卷汇编 1 及答案解析(总分：70.00，做题时间：90 分钟)一、选择题(总题数：35，分数：70.00)1.选择题（）下列各题 A、B、C、D 四个选项中，只有一个选项是正确的，请将此选项涂写在答题卡相应位置上，答在试卷上不得分。_2.采用顺序表和单链表存储长度为 n 的线性序列，根据序号查找元素，其时间复杂度分别为(51)。（分数：2.00）A.0(1)、0(1)B.0(1)、0(n)C.0(n)、0(1)D.0(n)、0(n)3.设元素序列 a、b、c、d、e、f 经过初始为空的栈 S 后，得到出栈序列 cedfba，则栈 S 的
2、最小容量为(52)。（分数：2.00）A.3B.4C.5D.64.输出受限的双端队列是指元素可以从队列的两端输入、但只能从队列的一端输出，如图 81 所示。若有 e1、e2、e3、e4 依次进入输出受限的双端队列，则得不到输出队列(53)。（分数：2.00）A.e4、e3、e2、e1B.e4、e2、e1、e3C.e4、e3、e1、e2D.e4、e2、e3、e15.以下关于线性表存储结构的叙述，正确的是(57)。（分数：2.00）A.线性表采用顺序存储结构时，访问表中任意一个指定序号元素的时间复杂度为常量级B.线性表采用顺序存储结构时，在表中任意位置插入新元素的运算时间复杂度为常量级C.线性表采
3、用链式存储结构时，访问表中任意一个指定序号元素的时间复杂度为常量级D.线性表采用链式存储结构时，在表中任意位置插入新元素的运算时间复杂度为常量级6.设循环队列 Q 的定义中有 front 和 size 两个域变量，其中 front 表示队头元素的指针，size 表示队列的长度，如图 82 所示(队列长度为 3，队头元素为 X、队尾元素为 z)。设队列的存储空间容量为 M，则队尾元素的指针为(58)。 （分数：2.00）A.(Qfront+Qsize 一 1)B.(Qfront+Qsize1+M)MC.(QfrontQsize)D.(QfrontQsize+M)M7.在字符串的模式匹配过程中，如
4、果模式串的每个字符依次和主串中的一个连续的字符序列相等，则成为匹配成功。如果不能在主串中找到与模式串相同的子串，则称为匹配失败。在布鲁特一福斯模式匹配算法(朴素的或基本的模式匹配)中，若主串和模式串的长度分别为 n 和 m(且 n 远大于 m)，且恰好在主串末尾的 n 个字符处匹配成功，则在上述的模式匹配过程中，字符的比较次数最多为(57)。（分数：2.00）A.n * mB.(nm+1) * mC.(nm 一 1) * mD.(nm) * n8.对于一个长度大于 1 且不存在重复元素的序列，令其所有元素依次通过一个初始为空的队列后，再通过一个初始为空的栈。设队列和栈的容量都足够大，一个序列通
5、过队列(栈)的含义是序列的每个元素都入队列(栈)且出队列(栈)一次且仅一次。对于该序列在上述队列和栈上的操作，正确的是(57)。（分数：2.00）A.出队序列和出栈序列一定相同B.出队序列和出栈序列一定互为逆序C.入队序列和出队序列一定相同，入栈序列和出栈序列不一定相同D.入栈序列和出栈序列一定互为逆序，入队序列和出队序列不一定互为逆序9.在字符串的 KMP 模式匹配算法中，需要求解模式串 p 的 next 函数值，其定义如下所示。若模式串 p 为“aaabaaa”，则其 next 函数值为(58)。 （分数：2.00）A.123123B.123210C.123432D.12345610.对于
6、线性表(由 n 个同类元素构成的线性序列)，采用单向循环链表存储的特定之一是(58)。（分数：2.00）A.从表中任意节点出发都能遍历整个链表B.对表中的任意节点可以进行随机访问C.对于表中的任意一个节点，访问其直接前驱和直接后继节点所有时间相同D.第一个节点必须是头节点11.设循环队列 Q 的定义中有 rear 和 len 两个域变量，其中 rear 表示队尾元素的指针，len 表示队列的长度，如图 83 所示(队列长度为 3，队头元素为 e)。设队列的存储空间容量为 M，则队头元素的指针为(57)。 （分数：2.00）A.(Qrear+Qlen1)B.(Qrear+Qlen 一 1+M)M
7、C.(Qrear 一 Qlen+1)D.(QrearQlen+1+M)M12.栈是一种按“后进先出”原则进行插入和删除操作的数据结构，因此，(60)必须用栈。（分数：2.00）A.实现函数或过程的递归调用及返回处理时B.将一个元素序列进行逆置C.链表节点的申请和释放D.可执行程序的装入和卸载13.若对一个链表最常用的操作是在末尾插入节点和删除尾节点，则采用仅设尾指针的单向循环链表(不含头节点)时，(65)。（分数：2.00）A.插入和删除操作的时间复杂度都为 O(1)B.插入和删除操作的时间复杂度都为 O(n)C.插入操作的时间复杂度为 O(1)，删除操作的时间复杂度为 O(n)D.插入操作的
8、时间复杂度为 O(n)，删除操作的时间复杂度为 O(1)14.对二维数组 a1 一 N，1 一 N中的一个元素 ai,j(1i，jN)，存储在 a 嘶之前的元素个数(21)。（分数：2.00）A.与按行存储或按列存储方式无关B.在 i=j 时与按行存储或按列存储方式无关C.在按行存储方式下比按列存储方式下要多D.在按行存储方式下比按列存储方式下要少15.若二维数组 arr1 一 M，1 一 N的首地址为 base，数组元素按列存储且每个元素占用 K 个存储单元，则元素 arri，j在该数组空间的地址为(21)。（分数：2.00）A.base+(i1)M+j1)KB.base+(i 一 1)N+
9、j1)KC.base+(j 一 1)M+i 一 1)KD.base+(j 一 1)N+i 一 1)K16.设下三角矩阵(上三角部分的元素值都为 0)A0.n，0.n如下所示，将该三角矩阵的所以非零元素(即行下标不小于列下标的元素)按行优先压缩存储在容量足够大的数组 M1.m中，则元素 Ai，j(0in，ji)存储在数组 M 的(57)中。 （分数：2.00）A.B.C.D.17.设有如下所示的下三角矩阵 A【0.8，0.8】，将该三角矩阵的非零元素(即行下标不小于列下标的所有元素)按行优先压缩存储在数组 M1.m中，则元素 A 嘶】(0i8,ji)存储在数组 M 的(58)中。（分数：2.00
10、）A.B.C.D.18.一个高度为 h 的满二叉树的节点总数为 2 b 一 1，从根结点开始，自上而下、同层次结点从左至右，埘结点按照顺序依次编号，即根节点编号为 1，其左、右孩子节点编号分为 2 和 3，再下一层从左到右的编号为 4、5、6、7，依次类推。那么，在一颗满二叉树中，对于编号为 m 和 n 的两个节点，若 n=2m+1，则(64)结点。（分数：2.00）A.m 是 n 的左孩子B.m 是 n 的右孩子C.n 是 m 的左孩子D.n 是 m 的右孩子19.以下关于哈夫曼树的叙述，正确的是(60)。（分数：2.00）A.哈夫曼树一定是满二叉树，其每层结点数都达到最大值B.哈夫曼树一定
11、是平衡二叉树，其每个结点左右子树的高度差为一 1、0 或 1C.哈夫曼树中左孩子结点的权值小于父结点、右孩子结点的权值大于父结点D.哈夫曼树中叶子结点的权值越小则距离树根越远、叶子结点的权值越大则距离树根越近20.若某二叉树的后序遍历序列为 KBFDCAE，中序遍历序列为 BKFEACD，则该二又树为(58)。（分数：2.00）A.B.C.D.21.若 n 2 、n 1 、n 0 分别表示一个二叉树中度为 2、度为 1 和叶子节点的数目(节点的度定义为节点的子树数目)，则对于任何一个非空的二叉树，(59)。（分数：2.00）A.n 2 一定大于 n 1B.n 1 一定大于 n 0C.n 2 一
12、定大于 n 0D.n 0 一定大于 n 222.一棵满二叉树，其每一层节点个数都达到最大值，对其中的节点从 1 开始顺序编号，即根节点编号为1，其左、右孩子节点编号分别为 2 和 3，再下一层从左到右的编号为 4、5、6、7，依此类推，每一层都从左到右依次编号，直到最后的叶子节点层为止，则用(60)可判定编号为 m 和 n 的两个节点是否在同一层。（分数：2.00）A.log 2 m=log 2 nB.log 2 m=log 2 nC.log 2 m+1=log 2 nD.log 2 m=log 2 n+123.(61)是由权值集合8，5，6，2构造的哈夫曼树(最优二叉树)。（分数：2.00）
13、A.B.C.D.24.以下编码方法中，(12)属于熵编码。（分数：2.00）A.哈夫曼编码B.小波变换编码C.线性预测编码D.行程编码25.在(59)中，任意一个节点的左、右子树的高度之差的绝对值不超过 1。（分数：2.00）A.完全二又树B.二叉排序树C.线索二叉树D.最优二叉树26.下面关于哈夫曼树的叙述中，正确的是(58)。（分数：2.00）A.哈夫曼树一定是完全二叉树B.哈夫曼树一定是平衡二叉树C.哈夫曼树中权值最小的两个节点互为兄弟节点D.哈夫曼树中左孩子节点小于父节点、右孩子节点大于父节点27.已知一棵度为 3 的树(一个节点的度是指其子树的数目，树的度是指该树中所有节点的度的最大
14、值)中有 5 个度为 1 的节点，4 个度为 2 的节点，2 个度为 3 的节点，那么，该树中的叶子节点数目为(61)。（分数：2.00）A.10B.9C.8D.728.2010 年 11 月真题 62 某算法的时间复杂度可用递归式 （分数：2.00）A.(nlg 2 n)B.(nlgn)C.(n 2 )D.(n 2 )29.若用 n 个权值构造一棵最优二叉树(哈夫曼树)，则该二叉树的节点总数为(59)。（分数：2.00）A.2nB.2n 一 1C.2n+1D.2n+230.用关键字序列 10、20、30、40、50 构造的二叉树排序(二叉查找树)为(63)。（分数：2.00）A.B.C.D.
15、31.若某算法在问题规模为 n 时，其基本操作的重复次数可由下式表示，则该算法的时间复杂度为(64)。（分数：2.00）A.O(n)B.O(n 2 )C.O(logn)D.O(nlogn)32.在一个有向图 G 的拓扑序列中，顶点 v i 列在 v j 之前，说明图 G 中(59)。（分数：2.00）A.一定存在弧 i，v jB.一定存在弧 j，v iC.可能存在 v i 到 v j 的路径，而不可能存在 v j 到 v i 的路径D.可能存在 v j 到 i 的路径，而不可能存在 v i 到 v j 的路径33.拓扑排序是将有向图中所有顶点排成一个线性序列的过程，并且该序列满足：若在 AOV
16、 网中从顶点 V i 到 V j 有一条路径，则顶点 V i 必然在顶点 V j 之前。对于图 87 所示的有向图，(60)是其拓扑序列。 （分数：2.00）A.1234576B.1235467C.2135476D.213456734.从存储空间的利用率角度来看，以下关于数据结构中图的存储的叙述，正确的是(60)。（分数：2.00）A.有向图适合采用邻接矩阵存储，无向图适合采用邻接表存储B.无向图适合采用邻接矩阵存储，有向图适合采用邻接表存储C.完全图适合采用邻接矩阵存储D.完全图适合采用邻接表存储算术表达式采用逆波兰式表示时不用括号，可以利用(20)进行求值。与逆波兰式 abcd+ * 对应
17、的中缀表达式是(21)。（分数：4.00）(1).(20)（分数：2.00）A.数组B.栈C.队列D.散列表(2).(21)（分数：2.00）A.ab+c * dB.(ab) * c+dC.(ab) * (c+d)D.ab * c+d软件水平考试（中级）软件设计师上午（基础知识）历年真题试卷汇编 1 答案解析(总分：70.00，做题时间：90 分钟)一、选择题(总题数：35，分数：70.00)1.选择题（）下列各题 A、B、C、D 四个选项中，只有一个选项是正确的，请将此选项涂写在答题卡相应位置上，答在试卷上不得分。_解析：2.采用顺序表和单链表存储长度为 n 的线性序列，根据序号查找元素，其
18、时间复杂度分别为(51)。（分数：2.00）A.0(1)、0(1)B.0(1)、0(n) C.0(n)、0(1)D.0(n)、0(n)解析：解析：顺序表存储位置是相邻连续的，可以随即访问的一种数据结构，一个顺序表在使用前必须指定起长度，一旦分配内存，则在使用中不可以动态的更改。他的优点是访问数据是比较方便，可以随即的访问表中的任何一个数据。链表是通过指针来描述元素关系的一种数据结构，他可以是物理地址不连续的物理空间。不能随即访问链表元素，必须从表头开始，一步一步搜索元素。它的优点是：对于数组，可以动态的改变数据的长度，分配物理空间。因此两者的查找复杂度就显而易见了。3.设元素序列 a、b、c、
19、d、e、f 经过初始为空的栈 S 后，得到出栈序列 cedfba，则栈 S 的最小容量为(52)。（分数：2.00）A.3B.4 C.5D.6解析：解析：此题考查栈的用法，根据题中出栈的顺序，当元素 c 出栈后，栈中有元素 a、b，当元素 e出栈之前，栈中有元素 a、b、d、e，此时栈中的元素达到最多。因此栈 S 最小容量为 4。4.输出受限的双端队列是指元素可以从队列的两端输入、但只能从队列的一端输出，如图 81 所示。若有 e1、e2、e3、e4 依次进入输出受限的双端队列，则得不到输出队列(53)。（分数：2.00）A.e4、e3、e2、e1B.e4、e2、e1、e3C.e4、e3、e1
20、、e2D.e4、e2、e3、e1 解析：解析：此题考查队列的性质，队列为先进先出的线性结构，题中给出的受限的双端队列，两端都可以进，而一端可出，假设分 a 和 b 端，b 端可以进出，由 D 选项的出序列，可以看出 e1、e2、e3 按顺序从 a 端进入，而 e4 从 b 端进入，当 e4 从 b 端出来之后，无法将后面的 e2 出队列，故 D 选项有误。5.以下关于线性表存储结构的叙述，正确的是(57)。（分数：2.00）A.线性表采用顺序存储结构时，访问表中任意一个指定序号元素的时间复杂度为常量级 B.线性表采用顺序存储结构时，在表中任意位置插入新元素的运算时间复杂度为常量级C.线性表采用
21、链式存储结构时，访问表中任意一个指定序号元素的时间复杂度为常量级D.线性表采用链式存储结构时，在表中任意位置插入新元素的运算时间复杂度为常量级解析：解析：顺序存储结构可以随机存取，时间复杂度最低为常量级的，答案选 A。6.设循环队列 Q 的定义中有 front 和 size 两个域变量，其中 front 表示队头元素的指针，size 表示队列的长度，如图 82 所示(队列长度为 3，队头元素为 X、队尾元素为 z)。设队列的存储空间容量为 M，则队尾元素的指针为(58)。 （分数：2.00）A.(Qfront+Qsize 一 1)B.(Qfront+Qsize1+M)M C.(QfrontQs
22、ize)D.(QfrontQsize+M)M解析：解析：考虑到循环，会对 M 进行求模，元素的指针从 0 开始到 M 一 1，所以队尾元素指针为答案B。7.在字符串的模式匹配过程中，如果模式串的每个字符依次和主串中的一个连续的字符序列相等，则成为匹配成功。如果不能在主串中找到与模式串相同的子串，则称为匹配失败。在布鲁特一福斯模式匹配算法(朴素的或基本的模式匹配)中，若主串和模式串的长度分别为 n 和 m(且 n 远大于 m)，且恰好在主串末尾的 n 个字符处匹配成功，则在上述的模式匹配过程中，字符的比较次数最多为(57)。（分数：2.00）A.n * mB.(nm+1) * m C.(nm 一
23、 1) * mD.(nm) * n解析：解析：在最坏的情况下，每一趟不成功的匹配都是模式串的最后一个字符与主串中相应的字符不相等，则主串中新一趟的起始位置为 im+2。若从主串的第 i 个字符开始匹配时成功，则前 i 趟不成功的匹配中，每趟都比较了 m 次，总共比较了 i * m 次，第 i+1 趟的成功匹配也比较了 m 次。因此，在本题所述的匹配模式中，字符的比较次数最多为(nm+1) * m 次。8.对于一个长度大于 1 且不存在重复元素的序列，令其所有元素依次通过一个初始为空的队列后，再通过一个初始为空的栈。设队列和栈的容量都足够大，一个序列通过队列(栈)的含义是序列的每个元素都入队列(
24、栈)且出队列(栈)一次且仅一次。对于该序列在上述队列和栈上的操作，正确的是(57)。（分数：2.00）A.出队序列和出栈序列一定相同B.出队序列和出栈序列一定互为逆序C.入队序列和出队序列一定相同，入栈序列和出栈序列不一定相同 D.入栈序列和出栈序列一定互为逆序，入队序列和出队序列不一定互为逆序解析：解析：队列具有先进先出的特点，也就是说最先入队的元素最先出队，所以入队序列和出队序列一定相同。栈则具有先进后出的特点，如果所有元素进栈后再依次出栈，则入栈序列和出栈序列互为逆序，否则不一定。9.在字符串的 KMP 模式匹配算法中，需要求解模式串 p 的 next 函数值，其定义如下所示。若模式串
25、p 为“aaabaaa”，则其 next 函数值为(58)。 （分数：2.00）A.123123 B.123210C.123432D.123456解析：解析：j=1 时，next1=0。j=2 时，不存在 k，满足 1kj，则 next2=1。j=3 时，k 只能取2，等式的左边为 p1，等式的右边为 p 2 ，p 1 =p 2 =a，next3=2。j=4 时，k 可以取 2 和 3，k 取 2 的时候，左边为 p 1 ，右边为 p 3 ，p 1 =p 3 =a；k 取 3 时，左边为 p 1 p 2 ，右边为 P 210.对于线性表(由 n 个同类元素构成的线性序列)，采用单向循环链表存储
26、的特定之一是(58)。（分数：2.00）A.从表中任意节点出发都能遍历整个链表 B.对表中的任意节点可以进行随机访问C.对于表中的任意一个节点，访问其直接前驱和直接后继节点所有时间相同D.第一个节点必须是头节点解析：解析：对于单向循环链表，可以从表中任意节点出发都能遍历整个链表。但并不能对表中的任意节点进行随机访问，需要从设置的第一个节点开始，沿着指针访问表中的节点。当然访问某一节点的直接后继节点最快，访问其直接前驱节点最慢，因为首先要遍历要表尾，然后从表头遍历到其前驱节点。11.设循环队列 Q 的定义中有 rear 和 len 两个域变量，其中 rear 表示队尾元素的指针，len 表示队列
27、的长度，如图 83 所示(队列长度为 3，队头元素为 e)。设队列的存储空间容量为 M，则队头元素的指针为(57)。 （分数：2.00）A.(Qrear+Qlen1)B.(Qrear+Qlen 一 1+M)MC.(Qrear 一 Qlen+1)D.(QrearQlen+1+M)M 解析：解析：队列的存储空间容量为 M，说明队列中最多可以有 M 个元素；队列的长度为 len，说明当前队列中有 len 个元素。设队列的队头指针为 front，front 指向队头元素，则有：Qrear=(Qfront+Q1en 一 1)M Qfront=(Qrear 一 Qlen+1+M)M12.栈是一种按“后进先
28、出”原则进行插入和删除操作的数据结构，因此，(60)必须用栈。（分数：2.00）A.实现函数或过程的递归调用及返回处理时 B.将一个元素序列进行逆置C.链表节点的申请和释放D.可执行程序的装入和卸载解析：解析：栈是一种后进先出的数据结构。将一个元素序列逆置时，可以使用栈也可以不用。链表节点的申请和释放次序与应用要求相关，不存在“先申请后释放”的操作要求。可执行程序的装入与卸载，也不存在“后进先出”的操作要求。对于函数的递归调用与返回，一定是后被调用执行的先返回。13.若对一个链表最常用的操作是在末尾插入节点和删除尾节点，则采用仅设尾指针的单向循环链表(不含头节点)时，(65)。（分数：2.00
29、）A.插入和删除操作的时间复杂度都为 O(1)B.插入和删除操作的时间复杂度都为 O(n)C.插入操作的时间复杂度为 O(1)，删除操作的时间复杂度为 O(n) D.插入操作的时间复杂度为 O(n)，删除操作的时间复杂度为 O(1)解析：解析：设尾指针的单项循环链表(不含头节点)如图 84 所示：14.对二维数组 a1 一 N，1 一 N中的一个元素 ai,j(1i，jN)，存储在 a 嘶之前的元素个数(21)。（分数：2.00）A.与按行存储或按列存储方式无关B.在 i=j 时与按行存储或按列存储方式无关 C.在按行存储方式下比按列存储方式下要多D.在按行存储方式下比按列存储方式下要少解析：
30、解析：存储在 ai,j之前的元素个数与按行存储或按列存储方式有关。按行存储时，存储在 ai,j之前的元素个数为(i1) * N+j 一 1_iN+jN1；按列存储时，存储在 ai,j之前的元素个数为(j1) * N+i1=jN+iN1。很显然，i 15.若二维数组 arr1 一 M，1 一 N的首地址为 base，数组元素按列存储且每个元素占用 K 个存储单元，则元素 arri，j在该数组空间的地址为(21)。（分数：2.00）A.base+(i1)M+j1)KB.base+(i 一 1)N+j1)KC.base+(j 一 1)M+i 一 1)K D.base+(j 一 1)N+i 一 1)K
31、解析：解析：数据 art 共 M 行 N 列，下标均从 1 开始。元素 arri,j在数据 arr 的第 i 行第 j 列，如果数组元素按列存储，则 1j-1 列共有(j1)M 个元素，ai,j之前共(j 一 1)M+i 一 1 个元素，元素arri，j在该数组空间的地址为为 base+(j 一 1)M+i 一 1)K。16.设下三角矩阵(上三角部分的元素值都为 0)A0.n，0.n如下所示，将该三角矩阵的所以非零元素(即行下标不小于列下标的元素)按行优先压缩存储在容量足够大的数组 M1.m中，则元素 Ai，j(0in，ji)存储在数组 M 的(57)中。 （分数：2.00）A. B.C.D.
32、解析：解析：第 0 行有 1 个元素保存在数组 M 中，第 l 行有 2 个元素保存在数组 M 中，第 i 一 1 行中有 i个元素保存在数组 M 中，第 i 行之前有 1+2+3+i=i(i+1)2 个元素保存在数组 M 中，元素 Ai，j是第 i 行的 j+1 个元素。由于数组 M 的下标从 1 开始，因此 Ai,j的值存储在17.设有如下所示的下三角矩阵 A【0.8，0.8】，将该三角矩阵的非零元素(即行下标不小于列下标的所有元素)按行优先压缩存储在数组 M1.m中，则元素 A 嘶】(0i8,ji)存储在数组 M 的(58)中。（分数：2.00）A. B.C.D.解析：解析：如图所示，按
33、行方式压缩存储时，Ai，j之前的元素数目为(1+2+i+j)个，数组 M 的下标从 1 开始，因此 Ai,j的值存储在18.一个高度为 h 的满二叉树的节点总数为 2 b 一 1，从根结点开始，自上而下、同层次结点从左至右，埘结点按照顺序依次编号，即根节点编号为 1，其左、右孩子节点编号分为 2 和 3，再下一层从左到右的编号为 4、5、6、7，依次类推。那么，在一颗满二叉树中，对于编号为 m 和 n 的两个节点，若 n=2m+1，则(64)结点。（分数：2.00）A.m 是 n 的左孩子B.m 是 n 的右孩子C.n 是 m 的左孩子D.n 是 m 的右孩子 解析：解析：由于该二叉树为满二叉
34、树，且根节点编号从 1 开始，由满二叉树的性质可知父节点 m 和右孩子之间的关系为 n=2m+1。19.以下关于哈夫曼树的叙述，正确的是(60)。（分数：2.00）A.哈夫曼树一定是满二叉树，其每层结点数都达到最大值B.哈夫曼树一定是平衡二叉树，其每个结点左右子树的高度差为一 1、0 或 1C.哈夫曼树中左孩子结点的权值小于父结点、右孩子结点的权值大于父结点D.哈夫曼树中叶子结点的权值越小则距离树根越远、叶子结点的权值越大则距离树根越近 解析：解析：哈夫曼树即最优二叉树，是一类带权路径长度的最短的树。树的带权路径为书中所有叶子节点的带权路径长度之和，记为： 20.若某二叉树的后序遍历序列为 K
35、BFDCAE，中序遍历序列为 BKFEACD，则该二又树为(58)。（分数：2.00）A. B.C.D.解析：解析：本题考查二叉树的遍历算法，根据中序遍历序列和另一种遍历序列的结果，可以确定该二叉树。后序遍历是按照左子树、右子树、根节点的顺序进行遍历，中序遍历是按照左子树、根节点、右子树的顺序进行遍历。E 为根节点，K 为 B 的右子树，因此应选 A 项描述的二叉树。21.若 n 2 、n 1 、n 0 分别表示一个二叉树中度为 2、度为 1 和叶子节点的数目(节点的度定义为节点的子树数目)，则对于任何一个非空的二叉树，(59)。（分数：2.00）A.n 2 一定大于 n 1B.n 1 一定大
36、于 n 0C.n 2 一定大于 n 0D.n 0 一定大于 n 2 解析：解析：由二叉树的性质可知，度为 0 的节点比度为 2 的节点数多 1，即 n 0 =n 2 +1，因此 n 0 一定大于 n 2 。22.一棵满二叉树，其每一层节点个数都达到最大值，对其中的节点从 1 开始顺序编号，即根节点编号为1，其左、右孩子节点编号分别为 2 和 3，再下一层从左到右的编号为 4、5、6、7，依此类推，每一层都从左到右依次编号，直到最后的叶子节点层为止，则用(60)可判定编号为 m 和 n 的两个节点是否在同一层。（分数：2.00）A.log 2 m=log 2 nB.log 2 m=log 2 n
37、 C.log 2 m+1=log 2 nD.log 2 m=log 2 n+1解析：解析：由于是满二叉树，只有 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。23.(61)是由权值集合8，5，6，2构造的哈夫曼树(最优二叉树)。（分数：2.00）A.B.C. D.解析：解析：哈夫曼树是带权路径最短的树。选项 A、B、C、D
38、四棵树的带权路径长度分别如下。选项A：82+52+62+22=412 选项 B：83+53+62+2=53 选项 C：8+62+23+53=41 选项D：2+52+63+83=5424.以下编码方法中，(12)属于熵编码。（分数：2.00）A.哈夫曼编码 B.小波变换编码C.线性预测编码D.行程编码解析：解析：熵编码根据信息熵理论，编码时只压缩冗余而不损伤信息熵，是一种无损压缩。常见的熵编码有哈夫曼编码、游程编码和算术编码。25.在(59)中，任意一个节点的左、右子树的高度之差的绝对值不超过 1。（分数：2.00）A.完全二又树 B.二叉排序树C.线索二叉树D.最优二叉树解析：解析：对于完全二
39、叉树，若设二叉树的高度为 h，除第 h 层外，其他各层(1h 一 1)的节点数都达到最大个数，第 h 层所有的节点都连续集中在最左边，这就是完全二又树。在完全二叉树中，任意一个节点的左、右子树的高度之差的绝对值不超过 1。二叉排序树(BinarySortTree)又称二叉查找树。它或者是一棵空树，或者是具有下列性质的二叉树：若左子树不空，则左子树上所有节点的值均小于它的根节点的值；若右子树不空，则右子树上所有节点的值均大于它的根节点的值；左、右子树也分别为二叉排序树。对于二叉排序树，由于左子树或右子树可26.下面关于哈夫曼树的叙述中，正确的是(58)。（分数：2.00）A.哈夫曼树一定是完全二
40、叉树B.哈夫曼树一定是平衡二叉树C.哈夫曼树中权值最小的两个节点互为兄弟节点 D.哈夫曼树中左孩子节点小于父节点、右孩子节点大于父节点解析：解析：哈夫曼树即最优二叉树，是一类带权路径长度的最短的树。树的带权路径为书中所有叶子节点的带权路径长度之和，记为： 27.已知一棵度为 3 的树(一个节点的度是指其子树的数目，树的度是指该树中所有节点的度的最大值)中有 5 个度为 1 的节点，4 个度为 2 的节点，2 个度为 3 的节点，那么，该树中的叶子节点数目为(61)。（分数：2.00）A.10B.9 C.8D.7解析：解析：树的节点总数为：5+42+23+1=20，叶子节点数为：20542=9。
41、28.2010 年 11 月真题 62 某算法的时间复杂度可用递归式 （分数：2.00）A.(nlg 2 n) B.(nlgn)C.(n 2 )D.(n 2 )解析：解析：采用主定理来求解递归式。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)。29.若用 n 个权值构造一棵最优二叉树(哈夫曼树)，则该二叉树的节点总数为(59)。（分数：2.00）A.2nB.2n 一 1 C.2n+1D.2n+2解析：解析：二叉树具有以
42、下性质：度为 2 的几点(双分支节点)数比度为 0(叶子节点)数正好少 1。而根据最优二叉树(哈夫曼树)的构造过程可知，最优二叉树中只有度为 2 和 0 的节点，因此，其节点总数为2n 一 1。30.用关键字序列 10、20、30、40、50 构造的二叉树排序(二叉查找树)为(63)。（分数：2.00）A.B.C. D.解析：解析：根据关键字序列构造二叉排序树的基本过程是，若需插入的关键字大于树根，则插入到右子树上，若小于树根，则插入到左子树上，若为空，则作为树根节点。31.若某算法在问题规模为 n 时，其基本操作的重复次数可由下式表示，则该算法的时间复杂度为(64)。（分数：2.00）A.O
43、(n)B.O(n 2 ) C.O(logn)D.O(nlogn)解析：解析：根据题中给出的递归定义式进行推导，可得 T(n)=n+n1+2+1，因此时间复杂度为 O(n 2 )。32.在一个有向图 G 的拓扑序列中，顶点 v i 列在 v j 之前，说明图 G 中(59)。（分数：2.00）A.一定存在弧 i，v jB.一定存在弧 j，v iC.可能存在 v i 到 v j 的路径，而不可能存在 v j 到 v i 的路径 D.可能存在 v j 到 i 的路径，而不可能存在 v i 到 v j 的路径解析：解析：根据有向图 G 的拓扑序列定义，顶点 v i 排列在 v j 之前，可以得知可能存
44、在 v i 到 v j 的路径，拓扑序列是单向的，所以不可能从 v j 到 v i 的路径。所以本题答案选 C。33.拓扑排序是将有向图中所有顶点排成一个线性序列的过程，并且该序列满足：若在 AOV 网中从顶点 V i 到 V j 有一条路径，则顶点 V i 必然在顶点 V j 之前。对于图 87 所示的有向图，(60)是其拓扑序列。 （分数：2.00）A.1234576B.1235467C.2135476 D.2134567解析：解析：对 AOV 网进行拓扑排序的方法如下：(1)在 AOV 网中选择一个入度为 0(没有前驱)的顶点且输出它；(2)从网中删除该顶点及与该顶点有关的所有边；(3)
45、重复上述两步，直至网中不存在入度为 0 的顶点为止。本题中只有序列“2135476”是其拓扑序列。34.从存储空间的利用率角度来看，以下关于数据结构中图的存储的叙述，正确的是(60)。（分数：2.00）A.有向图适合采用邻接矩阵存储，无向图适合采用邻接表存储B.无向图适合采用邻接矩阵存储，有向图适合采用邻接表存储C.完全图适合采用邻接矩阵存储 D.完全图适合采用邻接表存储解析：解析：邻接矩阵是用矩阵来指出顶点和顶点之间是否存在着关系。如果图有 n 个节点，则需要用 n 2 个元素来表示顶点间的关系。邻接表是图的一种链式存储结构。在邻接表中，图中的每一个顶点都需要建立一个单链表，第 i 个单链表
46、中的节点表示依附于顶点 v i 的边。对于无向图，若无向图有 n 个顶点，e 条边，则它的邻接表需要 n 个头节点和 2e 个表节点。对于有向图，若有 n 个顶点、e 条边，则它的邻接表需要 n 个头节点和 e 个表节点。等 e 算术表达式采用逆波兰式表示时不用括号，可以利用(20)进行求值。与逆波兰式 abcd+ * 对应的中缀表达式是(21)。（分数：4.00）(1).(20)（分数：2.00）A.数组B.栈 C.队列D.散列表解析：(2).(21)（分数：2.00）A.ab+c * dB.(ab) * c+dC.(ab) * (c+d) D.ab * c+d解析：解析：逆波兰式表示方式把运算符写在运算对象的后面，不需要使用括号。由于后缀表示中的各个运算是按顺序执行的，因此，它的计值很容易实现。为此，仅需从左到右依次扫视表达式中的各个符号，每遇到运算对象，就把它压入栈顶暂存起来；每遇到一个二元(或一元)运算符时，就取出栈顶的两个(或一个)运算对象进行相应的运算，并用运算结果去替换栈顶的这两(或一)个运算对象，然后再继续扫视余留的符号，如此等等，直到扫视完整个表达式为止。当上述过程结束时，整个表达式的值将留于栈顶。ab+c * d 对应的逆波兰式为：ab
