1、软件设计师-17 及答案解析(总分：100.00，做题时间：90 分钟)一、单项选择题(总题数：45，分数：100.00)1.对于线性表，相对于顺序存储，采用链表存储的缺点是_。（分数：2.00）A.数据元素之间的关系需要占用存储空间，导致存储密度不高B.表中结点必须占用地址连续的存储单元，存储密度不高C.插入新元素时需要遍历整个链表，运算的时间效率不高D.删除元素时需要遍历整个链表，运算的时间效率不高2.在字符串的 KMP 模式匹配算法中，需要先求解模式串中的 next 函数值，其定义如下式所示，j 表示模式串中字符的序号(从 1 开始)。若模式串 p 为“abaac“，则其。next 函数
2、值为_。 （分数：2.00）A.01234B.01122C.01211D.011113.若对线性表的最常用操作是访问任意指定序号的元素，并在表尾加入和删除元素，则适宜采用_存储。（分数：2.00）A.顺序表B.单链表C.双向链表D.哈希表4.某双端队列如下图所示，要求元素进出队列时必须在同一端口，即从 A 端进入的元素必须从 A 端出，从B 端进入的元素必须从 B 端出，则对于 4 个元素的序列 e1、e2、e3、e4，若要求前 2 个元素(e1，e2)从 A端口按次序全部进入队列，后两个元素(e3，e4)从 B 端口按次序全部进入队列，则可能得到的出队序列是_。 （分数：2.00）A.e1、
3、e2、e3、e4B.e2、e3、e4、e1C.e3、e4、e1、e2D.e4、e3、e2、e15.采用顺序表和单链表存储长度为 n 的线性序列，根据序号查找元素，其时间复杂度分别为_。（分数：2.00）A.O(1)、O(1)B.O(1)、O(n)C.O(n)、O(1)D.O(n)、O(n)6.设元素序列 a、b、c、d、e、f 经过初始为空的栈 S 后，得到出栈序列 c e d f b a，则栈 S 的最小容量为_。（分数：2.00）A.3B.4C.5D.67.输出受限的双端队列是指元素可以从队列的两端输入、但只能从队列的一端输出，如下图所示。若有e1、e2、e3、e4 依次进入输出受限的双端
4、队列，则得不到输出队列_。 （分数：2.00）A.e4、e3、e2、e1B.e4、e2、e1、e3C.e4、e3、e1、e2D.e4、e2、e3、e18.以下关于线性表存储结构的叙述，正确的是_。（分数：2.00）A.线性表采用顺序存储结构时，访问表中任意一个指定序号元素的时间复杂度为常量级B.线性表采用顺序存储结构时，在表中任意位置插入新元素的运算时间复杂度为常量级C.线性表采用链式存储结构时，访问表中任意一个指定序号元素的时间复杂度为常量级D.线性表采用链式存储结构时，在表中任意位置插入新元素的运算时间复杂度为常量级9.设循环队列 Q 的定义中有 front 和 size 两个域变量，其中
5、 front 表示队头元素的指针，size 表示队列的长度，如下图所示(队列长度为 3，队头元素为 X、队尾元素为 Z)。设队列的存储空间容量为 M，则队尾元素的指针为_。 （分数：2.00）A.(Q.front+Q.size-1)B.(Q.front+Q.size-1+M)%MC.(Q.front-Q.size)D.(Q.front-Q.size+M)%M10.在字符串的模式匹配过程中，如果模式串的每个字符依次和主串中的一个连续的字符序列相等，则成为匹配成功。如果不能在主串中找到与模式串相同的子串，则称为匹配失败。在布鲁特福斯模式匹配算法(朴素的或基本的模式匹配)中，若主串和模式串的长度分别
6、为 n 和 m(且 n 远大于 m)，且恰好在主串末尾的 n 个字符处匹配成功，则在上述的模式匹配过程中，字符的比较次数最多为_。 A.n*m B.(n-m+1)*m C.(n-m-1)*m D.(n-m)*n（分数：2.00）A.B.C.D.11.对于一个长度大于 1 且不存在重复元素的序列，令其所有元素依次通过一个初始为空的队列后，再通过一个初始为空的栈。设队列和栈的容量都足够大，一个序列通过队列(栈)的含义是序列的每个元素都入队列(栈)且出队列(栈)一次且仅一次。对于该序列在上述队列和栈上的操作，正确的是_。（分数：2.00）A.出队序列和出栈序列一定相同B.出队序列和出栈序列一定互为逆
7、序C.入队序列和出队序列一定相同，入栈序列和出栈序列不一定相同D.入栈序列和出栈序列一定互为逆序，入队序列和出队序列不一定互为逆序12.在字符串的 KMP 模式匹配算法中，需要求解模式串 p 的 next 函数值，其定义如下所示。若模式串 p 为“aaabaaa”，则其 next 函数值为_。 （分数：2.00）A.0123123B.0123210C.0123432D.012345613.对于线性表(由 n 个同类元素构成的线性序列)，采用单向循环链表存储的特定之一是_。（分数：2.00）A.从表中任意节点出发都能遍历整个链表B.对表中的任意节点可以进行随机访问C.对于表中的任意一个节点，访问
8、其直接前驱和直接后继节点所有时间相同D.第一个节点必须是头节点14.对二维数组 a1N,1N中的一个元素 ai,j(1i，jN)，存储在 ai,j之前的元素个数_。（分数：2.00）A.与按行存储或按列存储方式无关B.在 i=j 时与按行存储或按列存储方式无关C.在按行存储方式下比按列存储方式下要多D.在按行存储方式下比按列存储方式下要少15.若二维数组 arr1M,1N的首地址为 base，数组元素按列存储且每个元素占用 K 个存储单元，则元素 arri,j在该数组空间的地址为_。（分数：2.00）A.base+(i-1)M+j-1)KB.base+(i-1)N+j-1)KC.base+(j
9、-1)M+i-1)KD.base+(j-1)N+i-1)K16.在某棵二叉查找树(即二叉排序树)中进行查找时，效率最差的情形是该二叉查找树是_。（分数：2.00）A.完全二叉树B.平衡二叉树C.单枝树D.满二叉树某二叉树如图 1 所示，若进行顺序存储(即用一维数组元素存储该二叉树中的结点且通过下标反映结点间的关系，例如，对于下标为 i 的结点，其左孩子的下标为 2i、右孩子的下标为 2i+1)，则该数组的大小至少为_；若采用三叉链表存储该二叉树(各个结点包括结点的数据、父结点指针、左孩子指针、右孩子指针)，则该链表的所有结点中空指针的数目为_。 （分数：4.00）A.6B.10C.12D.15
10、A.6B.8C.12D.1417.一个高度为 h 的满二叉树的节点总数为 2 h -1，从根结点开始，自上而下、同层次结点从左至右，对结点按照顺序依次编号，即根节点编号为 1，其左、右孩子节点编号分为 2 和 3，再下一层从左到右的编号为 4、5、6、7，依次类推。那么，在一颗满二叉树中，对于编号为 m 和 n 的两个节点，若 n=2m+1，则_结点。（分数：2.00）A.m 是 n 的左孩子B.m 是 n 的右孩子C.n 是 m 的左孩子D.n 是 m 的右孩子18.以下关于哈夫曼树的叙述，正确的是_。（分数：2.00）A.哈夫曼树一定是满二叉树，其每层结点数都达到最大值B.哈夫曼树一定是平
11、衡二叉树，其每个结点左右子树的高度差为-1、0 或 1C.哈夫曼树中左孩子结点的权值小于父结点、右孩子结点的权值大于父结点D.哈夫曼树中叶子结点的权值越小则距离树根越远、叶子结点的权值越大则距离树根越近19.若某二叉树的后序遍历序列为 KBFDCAE，中序遍历序列为 BKFEACD，则该二叉树为_。 A B C D （分数：2.00）A.B.C.D.20.若 n 2 、n 1 、n 0 分别表示一个二叉树中度为 2、度为 1 和叶子节点的数目(节点的度定义为节点的子树数目)，则对于任何一个非空的二叉树，_。（分数：2.00）A.n2 一定大于 n1B.n1 一定大于 n0C.n2 一定大于 n
12、0D.n0 一定大于 n221.一棵满二叉树，其每一层节点个数都达到最大值，对其中的节点从 1 开始顺序编号，即根节点编号为1，其左、右孩子节点编号分别为 2 和 3，再下一层从左到右的编号为 4、5、6、7，依此类推，每一层都从左到右依次编号，直到最后的叶子节点层为止，则用_可判定编号为 m 和 n 的两个节点是否在同一层。 Alog 2 m=log 2 n B C D （分数：2.00）A.B.C.D.22._是由权值集合8,5,6,2构造的哈夫曼树(最优二叉树)。 A B C D （分数：2.00）A.B.C.D.23.以下编码方法中，_属于熵编码。（分数：2.00）A.哈夫曼编码B.小
13、波变换编码C.线性预测编码D.行程编码算术表达式采用逆波兰式表示时不用括号，可以利用_进行求值。与逆波兰式 ab-cd+ * 对应的表达式是_。（分数：4.00）A.数组B栈C.队列D.散列表(2). A.a-b+c*d B.(a-b)*c+d C.(a-b)*(c+d) D.a-b*c+d（分数：2.00）A.B.C.D.24.在_中，任意一个节点的左、右子树的高度之差的绝对值不超过 1。（分数：2.00）A.完全二叉树B.二叉排序树C.线索二叉树D.最优二叉树25.在一个有向图 G 的拓扑序列中，顶点 排列在 之前，说明图 G 中_。 A一定存在弧 B一定存在弧 C可能存在 到 的路径，而
14、不可能存在 到 的路径 D可能存在 到 的路径，而不可能存在 到 （分数：2.00）A.B.C.D.26.拓扑排序是将有向图中所有顶点排成一个线性序列的过程，并且该序列满足：若在 AOV 网中从顶点 Vi到 Vj 有一条路径，则顶点 Vi 必然在顶点 Vj 之前。对于如下图所示的有向图，_是其拓扑序列。 （分数：2.00）A.1234576B.1235467C.2135476D.213456727.从存储空间的利用率角度来看，以下关于数据结构中图的存储的叙述，正确的是_。（分数：2.00）A.有向图适合采用邻接矩阵存储，无向图适合采用邻接表存储B.无向图适合采用邻接矩阵存储，有向图适合采用邻接
15、表存储C.完全图适合采用邻接矩阵存储D.完全图适合采用邻接表存储28.无向图中一个顶点的度是指图中与该顶点相邻接的顶点数。若无向图 G 中的顶点数为 n，边数为 e，则所有顶点的度数之和为_。（分数：2.00）A.neB.n+eC.2nD.2e29.设一个包含 N 个顶点、E 条边的简单无向图采用邻接矩阵存储结构(矩阵元素 Aij等于 1/0 分别表示顶点 i 与顶点 j 之间有/无边)，则该矩阵中的非零元素数据为_。（分数：2.00）ANBEC.2ED.N+E30.实现二分查找(折半查找)时，要求查找表_。（分数：2.00）A.顺序存储，关键码无序排列B.顺序存储，关键码有序排列C.双向链表
16、存储，关键码无序排列D.双向链表存储，关键码有序排列31.以下关于哈希(Hash，散列)查找的叙述中，正确的是_。（分数：2.00）A.哈希函数应尽可能复杂些，以消除冲突B.构造哈希函数时应尽量使关键字的所有组成部分都能起作用C.进行哈希查找时，不再需要与查找表中的元素进行比较D.在哈希表中只能添加元素不能删除元素32.某哈希表(散列表)的长度为 n，设散列函数为 H(Key)=Key mod p，采用线性探测法解决冲突。以下关于 p 值的叙述中，正确的是_。（分数：2.00）A.p 的值一般为不大于 n 且最接近 n 的质数B.p 的值一般为大于 n 的任意整数C.p 的值必须为小于 n 的
17、合数D.p 的值必须等于 n33.在 13 个元素构成的有序表 M113中进行折半查找(向下取整)，若找到的元素为 M4，则被比较的元素依次为_。（分数：2.00）A.M7、M3、M5、M4B.M7、M5、M4C.M7、M6、M4D.M7、M434.下图所示为一棵 N 阶 B-树，N 最有可能的值为_。 （分数：2.00）A.1B.2C.3D.435.对 n 个元素的有序表 A1n进行顺序查找，其成功查找的平均查找长度(即在查找表中找到指定关键码的元素时，所进行比较的表中元素个数的期望值)为_。 A.n B.(n+1)/2 C.log2n D.n2（分数：2.00）A.B.C.D.36.对于关
18、键字序列(26，25，72，38，8，18，59)，采用散列函数 H(Key)=Key mod 13 构造散列表(哈希表)。若采用线性探测的开放定址法解决冲突(顺序地探查可用存储单元)，则关键字 59 所在散列表中的地址为_。（分数：2.00）A.6B.7C.8D.9快速排序算法在排序过程中，在待排序数组中确定一个元素为基准元素，根据基准元素把待排序数组划分成两个部分，前面一部分元素值小于基准元素，而后面一部分元素值大于基准元素，然后再分别对前后两个部分进一步进行划分。根据上述描述，快速排序算法采用了_算法设计策略。已知基准元素操作的时间复杂度为 O(n)，则快速排序算法的最好和最坏情况下的时
19、间复杂度为_。（分数：4.00）A.分治B.动态规划C.贪心D.回溯(2). A.O(n)和 O(nlgn) B.O(n)和 O(n2) C.O(nlgn)和 O(nlgn) D.O(nlgn)和 O(n2)（分数：2.00）A.B.C.D.37.对一待排序序列分别进行直接插入排序和简单选择排序，若待排序序列中有两个元素的值相同，则_保证这两个元素在排序前后的相对位置不变。（分数：2.00）A.直接插入排序和简单选择排序都可以B.直接插入排序和简单选择排序都不能C.只有直接插入排序可以D.只有简单选择排序可以对 n 个基本有序的整数进行排序，若采用插入排序算法，则时间和空间复杂度分别为_；若采
20、用快速排序算法，则时间和空间复杂度分别为_。（分数：4.00）(1). A.O(n2)和 O(n) B.O(n)和 O(n) C.O(n2)和 O(1) D.O(n)和 O(1)（分数：2.00）A.B.C.D.(2). A.O(n2)和 O(n) B.O(nlgn)和 O(n) C.O(n2)和 O(1) D.O(nlgn)和 O(1)（分数：2.00）A.B.C.D.将数组1,1,2,4,7,5从小到大排序，若采用_排序算法，则元素之间需要进行的比较次数最少，共需要进行_次元素之间的比较。（分数：4.00）A.直接插入B.归并C堆D.快速A.5B.6C.7D.838.递增序列 A(a 1
21、,a 2 ,a n )和 B(b 1 ，b 2 ，b n )的元素互不相同，若需将它们合并为一个长度为 2n 的递增序列，则当最终的排列结果为_时，归并过程中元素的比较次数最多。（分数：2.00）A.a1,a2,an,b1,b2,bnB.b1,b2,bn,a1,a2,anC.a1,b1,b2,b2,ai,bi,an,bnD.a1,a2,ai/2,b1,b2,bi/2,ai/2+1,ai/2+2,an,bi/2+1,bi/2+2,bn39.用插入排序和归并排序算法对数组3,1,4,1,5,9,6,5进行从大到小排序，则分别需要进行_次数组元素之间的比较。（分数：2.00）A.12,14B.10,
22、14C.12,16D.10,16已知一个文件中出现的各个字符及其对应的频率如下表所示。若采用定长编码，则该文件中字符的码长应为_上。若采用 Huffman 编码，则字符序列“face”的编码应为_。 字符 a b c d e f 频率(%) 45 13 12 16 9 5 （分数：2.00）A.2B.3C.4D.5A.110001001101B.001110110011C.101000010100D.010111101011软件设计师-17 答案解析(总分：100.00，做题时间：90 分钟)一、单项选择题(总题数：45，分数：100.00)1.对于线性表，相对于顺序存储，采用链表存储的缺点是
23、_。（分数：2.00）A.数据元素之间的关系需要占用存储空间，导致存储密度不高 B.表中结点必须占用地址连续的存储单元，存储密度不高C.插入新元素时需要遍历整个链表，运算的时间效率不高D.删除元素时需要遍历整个链表，运算的时间效率不高解析：解析 链接需要额外的空间存储结点之间的连接关系，因此存储密度不高，但其优点是插入和删除单个元素的时间复杂度为 0(1)。2.在字符串的 KMP 模式匹配算法中，需要先求解模式串中的 next 函数值，其定义如下式所示，j 表示模式串中字符的序号(从 1 开始)。若模式串 p 为“abaac“，则其。next 函数值为_。 （分数：2.00）A.01234B.
24、01122 C.01211D.01111解析：解析 根据公式依次推导即可。3.若对线性表的最常用操作是访问任意指定序号的元素，并在表尾加入和删除元素，则适宜采用_存储。（分数：2.00）A.顺序表 B.单链表C.双向链表D.哈希表解析：解析 采用顺序表(即数组)，可以任意访问指定序号的元素，便于在表尾加入和删除元素，但不便于在表头插入和删除元素，在表头操作时需要移动大量元素。需要注意的是，题目中要求在表尾加入和删除元素，而不是在表头进行操作，因此适宜采用顺序表。采用链表插入、删除元素时较为方便，但是访问指定序号的元素较为麻烦，需要从头指针开始遍历。4.某双端队列如下图所示，要求元素进出队列时必
25、须在同一端口，即从 A 端进入的元素必须从 A 端出，从B 端进入的元素必须从 B 端出，则对于 4 个元素的序列 e1、e2、e3、e4，若要求前 2 个元素(e1，e2)从 A端口按次序全部进入队列，后两个元素(e3，e4)从 B 端口按次序全部进入队列，则可能得到的出队序列是_。 （分数：2.00）A.e1、e2、e3、e4B.e2、e3、e4、e1C.e3、e4、e1、e2D.e4、e3、e2、e1 解析：解析 e1、e2 从 A 端口按次序进入队列，由于从 A 端进入的元素必须从 A 端出，则 e2 要先于 e1出队；e3、e4 从 B 端口按次序进入队列，而从 B 端进入的元素必须
26、从 B 端出，则 e4 要先于 e3 出队，只有选项 D 满足要求。5.采用顺序表和单链表存储长度为 n 的线性序列，根据序号查找元素，其时间复杂度分别为_。（分数：2.00）A.O(1)、O(1)B.O(1)、O(n) C.O(n)、O(1)D.O(n)、O(n)解析：解析 顺序表存储位置是相邻连续的，可以随即访问的一种数据结构，一个顺序表在使用前必须指定其长度，一旦分配内存，则在使用中不可以动态的更改。他的优点是访问数据是比较方便，可以随即的访问表中的任何一个数据。链表是通过指针来描述元素关系的一种数据结构，他可以是物理地址不连续的物理空间。不能随即访问链表元素，必须从表头开始，一步一步搜
27、索元素。它的优点是：对于数组，可以动态的改变数据的长度，分配物理空间。因此两者的查找复杂度就显而易见了。6.设元素序列 a、b、c、d、e、f 经过初始为空的栈 S 后，得到出栈序列 c e d f b a，则栈 S 的最小容量为_。（分数：2.00）A.3B.4 C.5D.6解析：解析 此题考查栈的用法，根据题中出栈的顺序，当元素 c 出栈后，栈中有元素 a、b，当元素 e出栈之前，栈中有元素 a、b、d、e，此时栈中的元素达到最多。因此栈 S 最小容量为 4。7.输出受限的双端队列是指元素可以从队列的两端输入、但只能从队列的一端输出，如下图所示。若有e1、e2、e3、e4 依次进入输出受限
28、的双端队列，则得不到输出队列_。 （分数：2.00）A.e4、e3、e2、e1B.e4、e2、e1、e3C.e4、e3、e1、e2D.e4、e2、e3、e1 解析：解析 此题考查队列的性质，队列为先进先出的线性结构，题中给出的受限的双端队列，两端都可以进，而一端可出，假设分为 a 和 b 端，b 端可以进出，由 D 选项的出序列，可以看出 e1、e2、e3 按顺序从 a 端进入，而 e4 从 b 端进入，当 e4 从 b 端出来之后，无法将后面的 e2 出队列，故 D 选项有误。8.以下关于线性表存储结构的叙述，正确的是_。（分数：2.00）A.线性表采用顺序存储结构时，访问表中任意一个指定序
29、号元素的时间复杂度为常量级 B.线性表采用顺序存储结构时，在表中任意位置插入新元素的运算时间复杂度为常量级C.线性表采用链式存储结构时，访问表中任意一个指定序号元素的时间复杂度为常量级D.线性表采用链式存储结构时，在表中任意位置插入新元素的运算时间复杂度为常量级解析：解析 顺序存储结构可以随机存取，时间复杂度最低为常量级的，答案选 A。9.设循环队列 Q 的定义中有 front 和 size 两个域变量，其中 front 表示队头元素的指针，size 表示队列的长度，如下图所示(队列长度为 3，队头元素为 X、队尾元素为 Z)。设队列的存储空间容量为 M，则队尾元素的指针为_。 （分数：2.0
30、0）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解析：解析 考虑到循环，会对 M 进行求模，元素的指针从 0 开始到 M-1，所以队尾元素指针为答案 B。10.在字符串的模式匹配过程中，如果模式串的每个字符依次和主串中的一个连续的字符序列相等，则成为匹配成功。如果不能在主串中找到与模式串相同的子串，则称为匹配失败。在布鲁特福斯模式匹配算法(朴素的或基本的模式匹配)中，若主串和模式串的长度分别为 n 和 m(且 n 远大于 m)，且恰好在主串末尾的 n 个字符处匹配成功，
31、则在上述的模式匹配过程中，字符的比较次数最多为_。 A.n*m B.(n-m+1)*m C.(n-m-1)*m D.(n-m)*n（分数：2.00）A.B. C.D.解析：解析 在最坏的情况下，每一趟不成功的匹配都是模式串的最后一个字符与主串中相应的字符不相等，则主串中新一趟的起始位置为 i-m+2。若从主串的第 i 个字符开始匹配时成功，则前 i 趟不成功的匹配中，每趟都比较了 m 次，总共比较了 i * m 次，第 i+1 趟的成功匹配也比较了 m 次。因此，在本题所述的匹配模式中，字符的比较次数最多为(n-m+1) * m 次。11.对于一个长度大于 1 且不存在重复元素的序列，令其所有
32、元素依次通过一个初始为空的队列后，再通过一个初始为空的栈。设队列和栈的容量都足够大，一个序列通过队列(栈)的含义是序列的每个元素都入队列(栈)且出队列(栈)一次且仅一次。对于该序列在上述队列和栈上的操作，正确的是_。（分数：2.00）A.出队序列和出栈序列一定相同B.出队序列和出栈序列一定互为逆序C.入队序列和出队序列一定相同，入栈序列和出栈序列不一定相同 D.入栈序列和出栈序列一定互为逆序，入队序列和出队序列不一定互为逆序解析：解析 队列具有先进先出的特点，也就是说最先入队的元素最先出队，所以入队序列和出队序列一定相同。栈则具有先进后出的特点，如果所有元素进栈后再依次出栈，则入栈序列和出栈序
33、列互为逆序，否则不一定。12.在字符串的 KMP 模式匹配算法中，需要求解模式串 p 的 next 函数值，其定义如下所示。若模式串 p 为“aaabaaa”，则其 next 函数值为_。 （分数：2.00）A.0123123 B.0123210C.0123432D.0123456解析：解析 j=1 时，next1=0。j=2 时，不存在 k，满足 1kj，则 next2=1。j=3 时，k 只能取2，等式的左边为 p 1 ，等式的右边为 p 2 ，p 1 =p =a，next3=2。j=4 时，k 可以取 2 和 3，k 取 2 的时候，左边为 p 1 ，右边为 p 3 ，p 1 =p 3
34、=a；k 取 3 时，左边为 p 1 p 2 ，右边为 p 2 p 3 ，p 1 p 2 =p 2 p 3 =aa；k 取较大值 3，因此 next4=3。j=5 时，k 可以取 2、3、2，k 取 2 的时候，左边为 p 1 =a，右边为 p 4 =b，左右两边不等；k 取 3 的时候，左边为 p 1 p 2 =aa，右边为 p 3 p 4 =ab，左右两边不等；k 取 4 的时候，左边为 p 1 p 2 p 3 =aaa，右边为 p 2 p 3 p 4 =aaba，左右两边不等，因此 next5=1。至此，可以判断正确的答案为 A。13.对于线性表(由 n 个同类元素构成的线性序列)，采用
35、单向循环链表存储的特定之一是_。（分数：2.00）A.从表中任意节点出发都能遍历整个链表 B.对表中的任意节点可以进行随机访问C.对于表中的任意一个节点，访问其直接前驱和直接后继节点所有时间相同D.第一个节点必须是头节点解析：解析 对于单向循环链表，可以从表中任意节点出发都能遍历整个链表。但并不能对表中的任意节点进行随机访问，需要从设置的第一个节点开始，沿着指针访问表中的节点。当然访问某一节点的直接后继节点最快，访问其直接前驱节点最慢，因为首先要遍历要表尾，然后从表头遍历到其前驱节点。14.对二维数组 a1N,1N中的一个元素 ai,j(1i，jN)，存储在 ai,j之前的元素个数_。（分数：
36、2.00）A.与按行存储或按列存储方式无关B.在 i=j 时与按行存储或按列存储方式无关 C.在按行存储方式下比按列存储方式下要多D.在按行存储方式下比按列存储方式下要少解析：解析 存储在 ai,j之前的元素个数与按行存储或按列存储方式有关。按行存储时，存储在ai,j之前的元素个数为(i-1) * N+j-1=iN+j-N-1；按列存储时，存储在 ai,j之前的元素个数为(j-1) * N+i-1=jN+i-N-1。很显然，ij 时，在按行存储方式下比按列存储方式下要多；ij 时，在按行存储方式下比按列存储方式下要少。15.若二维数组 arr1M,1N的首地址为 base，数组元素按列存储且每
37、个元素占用 K 个存储单元，则元素 arri,j在该数组空间的地址为_。（分数：2.00）A.base+(i-1)M+j-1)KB.base+(i-1)N+j-1)KC.base+(j-1)M+i-1)K D.base+(j-1)N+i-1)K解析：解析 数据 arr 共 M 行 N 列，下标均从 1 开始。元素 arri,j在数据 arr 的第 i 行第 j 列，如果数组元素按列存储，则 1-j-1 列共有(j-1)M 个元素，ai,j之前共(k-1)M+i-1 个元素，元素arri,j在该数组空间的地址为为 base+(j-1)M+i-1)K。16.在某棵二叉查找树(即二叉排序树)中进行查
38、找时，效率最差的情形是该二叉查找树是_。（分数：2.00）A.完全二叉树B.平衡二叉树C.单枝树 D.满二叉树解析：解析 单枝树极度不平衡，查找的平均时间复杂度为 O(N)。某二叉树如图 1 所示，若进行顺序存储(即用一维数组元素存储该二叉树中的结点且通过下标反映结点间的关系，例如，对于下标为 i 的结点，其左孩子的下标为 2i、右孩子的下标为 2i+1)，则该数组的大小至少为_；若采用三叉链表存储该二叉树(各个结点包括结点的数据、父结点指针、左孩子指针、右孩子指针)，则该链表的所有结点中空指针的数目为_。 （分数：4.00）A.6B.10C.12D.15 解析：A.6B.8 C.12D.14
39、解析：解析 采用顺序存储结构存储二叉树时，一般的二叉树也必须按照完全二叉树的形式存储，需要填上一些不存在的“虚结点”。题中二叉树的高度为 4，需要的存储空间为 2 4 -1=15，示意图如图 2 所示。 图 2采用三叉链表存储二叉树时，示意图如图 3 所示。 17.一个高度为 h 的满二叉树的节点总数为 2 h -1，从根结点开始，自上而下、同层次结点从左至右，对结点按照顺序依次编号，即根节点编号为 1，其左、右孩子节点编号分为 2 和 3，再下一层从左到右的编号为 4、5、6、7，依次类推。那么，在一颗满二叉树中，对于编号为 m 和 n 的两个节点，若 n=2m+1，则_结点。（分数：2.0
40、0）A.m 是 n 的左孩子B.m 是 n 的右孩子C.n 是 m 的左孩子D.n 是 m 的右孩子 解析：解析 由于该二叉树为满二叉树，且根节点编号从 1 开始，由满二叉树的性质可知父节点 m 和右孩子之间的关系为 n=2m+1。18.以下关于哈夫曼树的叙述，正确的是_。（分数：2.00）A.哈夫曼树一定是满二叉树，其每层结点数都达到最大值B.哈夫曼树一定是平衡二叉树，其每个结点左右子树的高度差为-1、0 或 1C.哈夫曼树中左孩子结点的权值小于父结点、右孩子结点的权值大于父结点D.哈夫曼树中叶子结点的权值越小则距离树根越远、叶子结点的权值越大则距离树根越近 解析：解析 哈夫曼树，即最优二叉
41、树，是一类带权路径长度的最短的树。树的带权路径为书中所有叶子节点的带权路径长度之和，记为： 19.若某二叉树的后序遍历序列为 KBFDCAE，中序遍历序列为 BKFEACD，则该二叉树为_。 A B C D （分数：2.00）A. B.C.D.解析：解析 本题考查二叉树的遍历算法，根据中序遍历序列和另一种遍历序列的结果，可以确定该二叉树。后序遍历是按照左子树、右子树、根节点的顺序进行遍历，中序遍历是按照左子树、根节点、右子树的顺序进行遍历。E 为根节点，K 为 B 的右子树，因此应选 A 项描述的二叉树。20.若 n 2 、n 1 、n 0 分别表示一个二叉树中度为 2、度为 1 和叶子节点的
42、数目(节点的度定义为节点的子树数目)，则对于任何一个非空的二叉树，_。（分数：2.00）A.n2 一定大于 n1B.n1 一定大于 n0C.n2 一定大于 n0D.n0 一定大于 n2 解析：解析 由二叉树的性质可知，度为 0 的节点比度为 2 的节点数多 1，即 n 0 =n 2 +1，因此 n 0 一定大于 n 2 。21.一棵满二叉树，其每一层节点个数都达到最大值，对其中的节点从 1 开始顺序编号，即根节点编号为1，其左、右孩子节点编号分别为 2 和 3，再下一层从左到右的编号为 4、5、6、7，依此类推，每一层都从左到右依次编号，直到最后的叶子节点层为止，则用_可判定编号为 m 和 n
43、 的两个节点是否在同一层。 Alog 2 m=log 2 n B C D （分数：2.00）A.B. C.D.解析：解析 由于是满二叉树，只有 m 个节点的二叉树一定是完全二叉树，只有 n 个节点的二叉树也一定是完全二叉树，因此，具有 m 个节点的完全二叉树的深度为 ，具有 n 个节点的完全二叉树的深度为 。如果编号为 m 和 n 的两个节点是在同一层，则有 ，即22._是由权值集合8,5,6,2构造的哈夫曼树(最优二叉树)。 A B C D （分数：2.00）A.B.C. D.解析：解析 哈夫曼树是带权路径最短的树。选项 A、B、C、D 四棵树的带权路径长度分别如下。 选项 A：82+52+
44、62+22=42 选项 B：83+53+62+2=53 选项 C：8+62+23+53=41 选项 D：2+52+63+83=5423.以下编码方法中，_属于熵编码。（分数：2.00）A.哈夫曼编码 B.小波变换编码C.线性预测编码D.行程编码解析：解析 熵编码根据信息熵理论，编码时只压缩冗余而不损伤信息熵，是一种无损压缩。常见的熵编码有哈夫曼编码、游程编码和算术编码。算术表达式采用逆波兰式表示时不用括号，可以利用_进行求值。与逆波兰式 ab-cd+ * 对应的表达式是_。（分数：4.00）A.数组B栈 C.队列D.散列表解析：(2). A.a-b+c*d B.(a-b)*c+d C.(a-b
45、)*(c+d) D.a-b*c+d（分数：2.00）A.B.C. D.解析：解析 逆波兰式表示方式把运算符写在运算对象的后面，不需要使用括号。由于后缀表示中的各个运算是按顺序执行的，因此，它的计值很容易实现。为此，仅需从左到右依次扫视表达式中的各个符号，每遇到运算对象，就把它压入栈顶暂存起来；每遇到一个二元(或一元)运算符时，就取出栈顶的两个(或一个)运算对象进行相应的运算，并用运算结果去替换栈顶的这两(或一)个运算对象，然后再继续扫视余留的符号，如此等等，直到扫视完整个表达式为止。当上述过程结束时，整个表达式的值将留于栈顶。 a-b+c * d 对应的逆波兰式为：ab-cd * + (a-b
46、) * c+d 对应的逆波兰式为：ab-c * d+ (a-b) * (c+d)对应的逆波兰式为：ab-cd+ * a-b * c+d 对应的逆波兰式为：abc * -d+24.在_中，任意一个节点的左、右子树的高度之差的绝对值不超过 1。（分数：2.00）A.完全二叉树 B.二叉排序树C.线索二叉树D.最优二叉树解析：解析 对于完全二叉树，若设二叉树的高度为 h，除第 h 层外，其他各层(1h-1)的节点数都达到最大个数，第 h 层所有的节点都连续集中在最左边，这就是完全二叉树。在完全二叉树中，任意一个节点的左、右子树的高度之差的绝对值不超过 1。 二叉排序树(Binary Sort Tre
47、e)又称二叉查找树。它或者是一棵空树，或者是具有下列性质的二叉树：若左子树不空，则左子树上所有节点的值均小于它的根节点的值；若右子树不空，则右子树上所有节点的值均大于它的根节点的值；左、右子树也分别为二叉排序树。对于二叉排序树，由于左子树或右子树可能为空，不能保证每一个节点的左、右子树的高度之差的绝对值不超过 1。 按照某种遍历方式对二叉树进行遍历，可以把二叉树中所有节点排序为一个线性序列。在该序列中，除第一个节点外每个节点有且仅有一个直接前驱节点；除最后一个节点外每一个节点有且仅有一个直接后继节点。这些指向直接前驱节点和指向直接后续节点的指针被称为线索，加了线索的二叉树称为线索二叉树。线索二叉树只是加了线索的二叉树，对节点的排列没有要求，不能保证每一个节点的左、右子树的高度之差的绝对值不超过 1。 给定 n 个权值作为 n 个叶子节点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树，不能保证每一个节点的左、右子树的高度之差的绝对值不超过 1。25.在一个有向图 G 的拓扑序列中，顶点 排列在 之前，说明图 G 中_。 A一定存在弧
