1、二级 MS+Office 高级应用-67 及答案解析(总分：100.00，做题时间：90 分钟)一、选择题(总题数：50，分数：100.00)1.下列叙述中错误的是（分数：2.00）A.对于各种特定的输入，算法的时间复杂度是固定不变的B.算法的时间复杂度与使用的计算机系统无关C.算法的时间复杂度与使用的程序设计语言无关D.算法的时间复杂度与实现算法过程中的具体细节无关2.在长度为 n 的顺序表中查找一个元素，假设需要查找的元素一定在表中，并且元素出现在表中每个位置上的可能性是相同的，则在平均情况下需要比较的次数为（分数：2.00）A.(n+1)/2BnC.3n/4D.n/43.设非空二叉树的所
2、有子树中，其左子树上的结点值均小于根结点值，而右子树上的结点值均不小于根结点值，则称该二叉树为排序二叉树。对排序二叉树的遍历结果为有序序列的是（分数：2.00）A.中序序列B.前序序列C.后序序列D.前序序列或后序序列4.循环队列的存储空间为 Q(1:50)，初始状态为 front=rear=50。经过一系列正常的入队与退队操作后，front=rear=25，此后又插入一个元素，则循环队列中的元素个数为（分数：2.00）A.1，或 50 且产生上溢错误B.51C.26D.25.下列算法中均以比较作为基本运算，则平均情况与最坏情况下的时间复杂度相同的是（分数：2.00）A.在顺序存储的线性表中寻
3、找最大项B.在顺序存储的线性表中进行顺序查找C.在顺序存储的有序表中进行对分查找D.在链式存储的有序表中进行查找6.在具有 2n 个结点的完全二叉树中，叶子结点个数为（分数：2.00）AnB.n+1C.n-1D.n/27.下列叙述中正确的是（分数：2.00）A.在栈中，栈顶指针的动态变化决定栈中元素的个数B.在循环队列中，队尾指针的动态变化决定队列的长度C.在循环链表中，头指针和链尾指针的动态变化决定链表的长度D.在线性链表中，头指针和链尾指针的动态变化决定链表的长度8.循环队列的存储空间为 Q(1:40)，初始状态为 front=rear=40。经过一系列正常的入队与退队操作后，front=
4、rear=15，此后又退出一个元素，则循环队列中的元素个数为（分数：2.00）A.39，或 0 且产生下溢错误B.14C.40D.159.某二叉树的中序遍历序列为 CBADE，后序遍历序列为 CBADE，则前序遍历序列为（分数：2.00）A.EDABCB.CBEDAC.CBADED.EDCBA10.下列叙述中正确的是（分数：2.00）A.在循环队列中，队头指针和队尾指针的动态变化决定队列的长度B.在循环队列中，队尾指针的动态变化决定队列的长度C.在带链的队列中，队头指针与队尾指针的动态变化决定队列的长度D.在带链的栈中，栈顶指针的动态变化决定栈中元素的个数11.设栈的存储空间为 S(1:60)
5、，初始状态为 top=61。现经过一系列正常的入栈与退栈操作后，top=1，则栈中的元素个数为（分数：2.00）A.60B.59C.0D.112.设顺序表的长度为 n。下列排序方法中，最坏情况下比较次数小于 n(n-1)/2 的是（分数：2.00）A.堆排序B.快速排序C.简单插入排序D.冒泡排序13.在长度为 n 的顺序表中查找一个元素，假设需要查找的元素有一半的机会在表中，并且如果元素在表中，则出现在表中每个位置上的可能性是相同的。则在平均情况下需要比较的次数大约为（分数：2.00）A.(3+n)/4BnC.n/2D.n/414.设一棵树的度为 3，其中度为 3，2，1 的结点个数分别为
6、4，1，3。则该棵树中的叶子结点数为（分数：2.00）A.10B.11C.12D.不可能有这样的树15.设栈的存储空间为 S(1:50)，初始状态为 top=0。现经过一系列正常的入栈与退栈操作后，top=51，则栈中的元素个数为（分数：2.00）A.不可能B.50C.0D.116.设顺序表的长度为 n。下列算法中，最坏情况下比较次数等于 n(n-1)/2 的是（分数：2.00）A.快速排序B.堆排序C.顺序查找D.寻找最大项17.设表的长度为 n。下列算法中，最坏情况下比较次数小于 n 的是（分数：2.00）A.二分查找法B.堆排序C.快速排序D.顺序查找法18.下列叙述中错误的是（分数：2
7、.00）A.循环链表是循环队列的存储结构B.二叉链表是二叉树的存储结构C.栈是线性结构D.循环队列是队列的存储结构19.设一棵树的度为 4，其中度为 4，3，2，1 的结点个数分别为 2，3，3，0。则该棵树中的叶子结点数为（分数：2.00）A.16B.15C.17D.不可能有这样的树20.循环队列的存储空间为 Q(1:100)，初始状态为 front=rear=100。经过一系列正常的入队与退队操作后，front=rear=99，则循环队列中的元素个数为（分数：2.00）A.0 或 100B.1C.2D.9921.设顺序表的长度为 n。下列算法中，最坏情况下比较次数小于 n 的是（分数：2.
8、00）A.寻找最大项B.堆排序C.快速排序D.顺序查找法22.设栈的顺序存储空间为 S(1:m)，初始状态为 top=m+1。现经过一系列正常的入栈与退栈操作后，top=0，则栈中的元素个数为（分数：2.00）A.不可能B.m+1C.1Dm23.某二叉树的后序遍历序列与中序遍历序列相同，均为 ABCDEF，则按层次输出(同一层从左到右)的序列为（分数：2.00）A.FEDCBAB.CBAFEDC.DEFCBAD.ABCDEF24.循环队列的存储空间为 Q(1:200)，初始状态为 front=rear=200。经过一系列正常的入队与退队操作后，front=rear=1，则循环队列中的元素个数为
9、（分数：2.00）A.0 或 200B.1C.2D.19925.设栈的顺序存储空间为 S(1:m)，初始状态为 top=0。现经过一系列正常的入栈与退栈操作后，top=m+1，则栈中的元素个数为（分数：2.00）A.不可能B.m+1C.0Dm26.下列排序法中，最坏情况下时间复杂度最小的是（分数：2.00）A.堆排序B.快速排序C.希尔排序D.冒泡排序27.某二叉树的前序遍历序列与中序遍历序列相同，均为 ABCDEF，则按层次输出(同一层从左到右)的序列为（分数：2.00）A.ABCDEFB.BCDEFAC.FEDCBAD.DEFABC28.下列叙述中正确的是（分数：2.00）A.对数据进行压
10、缩存储会降低算法的空间复杂度B.算法的优化主要通过程序的编制技巧来实现C.算法的复杂度与问题的规模无关D.数值型算法只需考虑计算结果的可靠性29.设数据结构 B=(D，R)，其中 D=a，b，c，d，e，f R=(a，b)，(b，c)，(c，d)，(d，e)，(e，f)，(f，a) 该数据结构为（分数：2.00）A.非线性结构B.循环队列C.循环链表D.线性结构30.下列排序法中，每经过一次元素的交换会产生新的逆序的是（分数：2.00）A.快速排序B.冒泡排序C.简单插入排序D.简单选择排序31.某带链的队列初始状态为 front=rear=NULL。经过一系列正常的入队与退队操作后，fron
11、t=rear=10。该队列中的元素个数为（分数：2.00）A.1B.0C.1 或 0D.不确定32.某完全二叉树按层次输出(同一层从左到右)的序列为 ABCDEFGH。该完全二叉树的前序序列为（分数：2.00）A.ABDHECFGB.ABCDEFGHC.HDBEAFCGD.HDEBFGCA33.下列叙述中正确的是（分数：2.00）A.有的二叉树也能用顺序存储结构表示B.有两个指针域的链表就是二叉链表C.多重链表一定是非线性结构D.顺序存储结构一定是线性结构34.下列各排序法中，最坏情况下时间复杂度最小的是（分数：2.00）A.堆排序B.快速排序C.希尔排序D.冒泡排序35.某带链队列初始状态为
12、 front=rear=NULL。经过一系列正常入队与退队操作后，front=10，rear=5。该队列中的元素个数为（分数：2.00）A.不确定B.5C.4D.636.某二叉树的前序序列为 ABDFHCEG，中序序列为 HFDBACEG。该二叉树按层次输出(同一层从左到右)的序列为（分数：2.00）A.ABCDEFGHB.HFDBGECAC.HGFEDCBAD.ACEGBDFH37.某带链栈初始状态为 top=bottom=NULL，经过一系列正常的入栈与退栈操作后，top=10，bottom=20。该栈中的元素个数为（分数：2.00）A.不确定B.10C.1D.038.设表的长度为 15。
13、则在最坏情况下，快速排序所需要的比较次数为（分数：2.00）A.105B.55C.15D.7539.设循环队列的存储空间为 Q(1:100)，初始状态为空。现经过一系列正常操作后，front=49，则循环队列中的元素个数为（分数：2.00）A.不确定B.49C.51D.5040.某完全二叉树按层次输出(同一层从左到右)的序列为 ABCDEFGH。该完全二叉树的中序序列为（分数：2.00）A.HDBEAFCGB.HDEBFGCAC.ABDHECFGD.ABCDEFGH41.下列叙述中正确的是（分数：2.00）A.解决一个问题可以有不同的算法，且它们的时间复杂度可以是不同的B.解决一个问题可以有不
14、同的算法，但它们的时间复杂度必定是相同的C.解决一个问题的算法是唯一的D.算法的时间复杂度与计算机系统有关42.设表的长度为 n。下列查找算法中，在最坏情况下，比较次数最少的是（分数：2.00）A.有序表的二分查找B.顺序查找C.寻找最大项D.寻找最小项43.某带链栈的初始状态为 top=bottom=NULL，经过一系列正常的入栈与退栈操作后，top=bottom=20。该栈中的元素个数为（分数：2.00）A.1B.0C.20D.不确定44.某二叉树的前序序列为 ABDFHCEG，中序序列为 HFDBACEG。该二叉树的后序序列为（分数：2.00）A.HFDBGECAB.ABCDEFGHC.
15、HGFEDCBAD.ACEGBDFH45.下列叙述中错误的是（分数：2.00）A.算法的时间复杂度与问题规模无关B.算法的时间复杂度与计算机系统无关C.算法的时间复杂度与空间复杂度没有必然的联系D.算法的空间复杂度与算法运行输出结果的数据量无关46.设表的长度为 20。则在最坏情况下，冒泡排序的比较次数为（分数：2.00）A.90B.20C.19D.19047.在带链栈中，经过一系列正常的操作后，如果 top=bottom，则栈中的元素个数为（分数：2.00）A.1B.0C.0 或 1D.栈满48.设一棵树的度为 3，共有 27 个结点，其中度为 3，2，0 的结点数分别为 4，1，10。该树
16、中度为 1 的结点数为（分数：2.00）A.11B.12C.13D.不可能有这样的树49.设数据结构 B=(D，R)，其中 D=a，b，c，d，e，f R=(f，a)，(d，b)，(e，d)，(c，e)，(a，c) 该数据结构为（分数：2.00）A.线性结构B.循环队列C.循环链表D.非线性结构50.下列叙述中错误的是（分数：2.00）A.循环队列空的条件是队头指针与队尾指针相同B.若二叉树没有叶子结点，则为空二叉树C.带链栈的栈底指针是随栈的操作而动态变化的D.若带链队列中只有一个元素，则队头指针与队尾指针必定相同二级 MS+Office 高级应用-67 答案解析(总分：100.00，做题时
17、间：90 分钟)一、选择题(总题数：50，分数：100.00)1.下列叙述中错误的是（分数：2.00）A.对于各种特定的输入，算法的时间复杂度是固定不变的 B.算法的时间复杂度与使用的计算机系统无关C.算法的时间复杂度与使用的程序设计语言无关D.算法的时间复杂度与实现算法过程中的具体细节无关解析：解析 一般情况下，算法的基本操作重复执行的次数，是模块 n 的某一个函数 f(n)。因此，算法的时间复杂度记做 T(n)=O(f(n)。随着模块 n 的增大，算法执行的时间的增长率和 f(n)的增长率成正比，所以 f(n)越小，算法的时间复杂度越低，算法的效率越高。因此算法会随着输入数据的不同而有执行
18、效率的不同，有时候会快点儿，有时候会慢点儿。因此选项 A 正确。2.在长度为 n 的顺序表中查找一个元素，假设需要查找的元素一定在表中，并且元素出现在表中每个位置上的可能性是相同的，则在平均情况下需要比较的次数为（分数：2.00）A.(n+1)/2 BnC.3n/4D.n/4解析：解析 在一个长度为 n 的线性表中顺序查找值为 x 的元素时，在等概率情况下查找成功时平均查找长度为(n+1)/2，所以选项 A 正确。3.设非空二叉树的所有子树中，其左子树上的结点值均小于根结点值，而右子树上的结点值均不小于根结点值，则称该二叉树为排序二叉树。对排序二叉树的遍历结果为有序序列的是（分数：2.00）A
19、.中序序列 B.前序序列C.后序序列D.前序序列或后序序列解析：解析 中序遍历的次序是先遍历左子树，再遍历根节点，最后遍历右子树。而左子树结点值根节点节点值4.循环队列的存储空间为 Q(1:50)，初始状态为 front=rear=50。经过一系列正常的入队与退队操作后，front=rear=25，此后又插入一个元素，则循环队列中的元素个数为（分数：2.00）A.1，或 50 且产生上溢错误 B.51C.26D.2解析：解析 循环队列初始状态 front=rear=50，经过一系列入队和出队操作后，结束状态还是front=rear25，这说明入队元素个数和出队元素个数一样多。这样一来最后的元素
20、个数就和原来的元素个数一样多，明显不是 O 就是 50，即要么队空(0 个元素)，要么队满(50 个元素)。这时进行入队操作，如果是队空(0 个元素)的情况，此时元素个数为 1；如果是队满(50 个元素)的情况，就会产生上溢错误。5.下列算法中均以比较作为基本运算，则平均情况与最坏情况下的时间复杂度相同的是（分数：2.00）A.在顺序存储的线性表中寻找最大项 B.在顺序存储的线性表中进行顺序查找C.在顺序存储的有序表中进行对分查找D.在链式存储的有序表中进行查找解析：解析 最坏情况下的时间复杂度称为最坏时间复杂度。一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度。最坏情况下的时间复杂
21、度是算法在任何输入实例上运行时间的上界，这就保证了算法的运行时间不会比任何情况更长。平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间。在输入不同的情况下算法的运行时间复杂度可能会发生变化。平均时间复杂度给出了算法的期望运行时间，有助于算法好坏的评价以及在不同算法之间比较时有一个统一标准。 在顺序存储的线性表中寻找最大项，其平均情况与最坏情况下的时间复杂度都是 n/2。6.在具有 2n 个结点的完全二叉树中，叶子结点个数为（分数：2.00）An B.n+1C.n-1D.n/2解析：解析 在具有 2n 个结点的完全二叉树中，叶子结点个数为：(2n+1)/2 取整，其值
22、等于 n。所以选项 A 正确。7.下列叙述中正确的是（分数：2.00）A.在栈中，栈顶指针的动态变化决定栈中元素的个数 B.在循环队列中，队尾指针的动态变化决定队列的长度C.在循环链表中，头指针和链尾指针的动态变化决定链表的长度D.在线性链表中，头指针和链尾指针的动态变化决定链表的长度解析：解析 栈是一种特殊的线性表，是一种只允许在表的一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶；表的另一端称为栈底。栈顶的当前位置是动态的，对栈顶当前位置的标记称为栈顶指针。在栈中，栈顶指针动态反映了栈中元素的变化情况。所以选项 A 正确。8.循环队列的存储空间为 Q(1:40)，初
23、始状态为 front=rear=40。经过一系列正常的入队与退队操作后，front=rear=15，此后又退出一个元素，则循环队列中的元素个数为（分数：2.00）A.39，或 0 且产生下溢错误 B.14C.40D.15解析：解析 循环队列初始状态 front=rear=40，经过一系列入队和出队操作后，结束状态还是front=rear=15，这说明入队元素个数和出队元素个数一样多。这样一来最后的元素个数就和原来的元素个数一样多，明显不是 0 就是 40，即要么队列为空(0 个元素)，要么队列为满队列(40 个元素)。这时进行出队操作，如果是队列满(40 个元素)的情况，此时队列中的元素个数为
24、 39，如果是队列空(0 个元素)的情况，此时就会产生下溢错误。因此选项 A 正确。9.某二叉树的中序遍历序列为 CBADE，后序遍历序列为 CBADE，则前序遍历序列为（分数：2.00）A.EDABC B.CBEDAC.CBADED.EDCBA解析：解析 后序遍历次序是“左右根”，中序遍历次序是“左根右”。由定义可知：后序遍历中最后一个就是树根结点，即 E 结点；在中序遍历中，根结点左边的是左子树集，右边的是右子树集，即CBAD 是根结点 E 的左子树集合。问题就会转化为：求后序遍历是 CBAD，中序遍历是 CBAD 的子树，方法同上。因为中序遍历中，D 结点右边没有结点了，所以 D 结点不
25、包含右子树，否则就会被分为 2 个子问题。以下是这道题的详细推理过程： 步骤 1 ：由 CBADE 得出根结点为 E，由中序遍历可知CBADE，右子树为空； 步骤 2 ：由 CBAD 得出左子树集合的根节点为 D，由中序可知CBAD，右子树为空； 步骤 3 ：同理，二叉树更新后如下图所示。 10.下列叙述中正确的是（分数：2.00）A.在循环队列中，队头指针和队尾指针的动态变化决定队列的长度 B.在循环队列中，队尾指针的动态变化决定队列的长度C.在带链的队列中，队头指针与队尾指针的动态变化决定队列的长度D.在带链的栈中，栈顶指针的动态变化决定栈中元素的个数解析：解析 循环队列是将顺序队列首尾相
26、连形成的，随着插入元素或删除元素的进行，其队头指针及队尾指针是在不断变化的，有时可能会出现队头指针大于队尾指针的情况，也可能是队尾指针大于队头指针。循环队列中计算元素的个数公式为：(rear-front+queue_size)%queue_size。所以选项 A 正确。11.设栈的存储空间为 S(1:60)，初始状态为 top=61。现经过一系列正常的入栈与退栈操作后，top=1，则栈中的元素个数为（分数：2.00）A.60 B.59C.0D.1解析：解析 栈是向上增长的，每次压入一个元素，栈的 TOP 指针向上移动一位，即 top-1。当压入第一个元素时，TOP 指针指向 60+1-1=60
27、；当压入第二个元素时，TOP 指针指向 60+1-2=59；以此类推，当压入第 N 个元素时，TOP 指针指向 60+1-N=1，则 N=60。所以选项 A 正确。12.设顺序表的长度为 n。下列排序方法中，最坏情况下比较次数小于 n(n-1)/2 的是（分数：2.00）A.堆排序 B.快速排序C.简单插入排序D.冒泡排序解析：解析 假设线性表的长度为 n，则在最坏情况下，冒泡排序需要经过 n/2 遍的从前往后扫描和 n/2遍的从后往前扫描，需要比较次数为 n(n-1)/2。快速排序法的最坏情况比较次数也是 n(n-1)/2。简单插入排序，无论是否最坏都需要 n(n-1)/2 比较。堆排序，无
28、论是否最坏都需要比较 O(nlog 2 n)次。所以选项 A 正确。13.在长度为 n 的顺序表中查找一个元素，假设需要查找的元素有一半的机会在表中，并且如果元素在表中，则出现在表中每个位置上的可能性是相同的。则在平均情况下需要比较的次数大约为（分数：2.00）A.(3+n)/4 BnC.n/2D.n/4解析：解析 在长度为 n 的顺序表中查找一个元素，最好的情况是目标在第一个，一次找到；最坏的情况是目标在最后一个，n 次找到。那么平均长度为：(1+2+n)/n=(n(n+1)/2)/n=(n+1)/2 本题需要查找的元素有一半的机会在表中，则在平均情况下需要比较的次数大约为(1+n)/2+1
29、)/2=(3+n)/4。所以选项 A 正确。14.设一棵树的度为 3，其中度为 3，2，1 的结点个数分别为 4，1，3。则该棵树中的叶子结点数为（分数：2.00）A.10 B.11C.12D.不可能有这样的树解析：解析 因为任一棵树中，结点总数=总分支数目+1，所以：n 0 +4+1+3=(n 0 *0+3*4+2*1+1*3)+1。计算结果 n 0 =10。其中，n 0 表示叶子结点。所以选项 A 正确。15.设栈的存储空间为 S(1:50)，初始状态为 top=0。现经过一系列正常的入栈与退栈操作后，top=51，则栈中的元素个数为（分数：2.00）A.不可能 B.50C.0D.1解析：
30、解析 栈是向上增长的，每次压入一个元素，栈的 TOP 指针向上移动一位，即 top-1。对于这个题目，由于 top 初始值等于 0，此时入栈一个元素，top 值减 1，即 0-1=-1，发生下溢错误，所以选项 A正确。16.设顺序表的长度为 n。下列算法中，最坏情况下比较次数等于 n(n-1)/2 的是（分数：2.00）A.快速排序 B.堆排序C.顺序查找D.寻找最大项解析：解析 假设线性表的长度为 n，则在最坏情况下，快速排序法的最坏情况比较次数也是 n(n-1)/2；堆排序，无论是否最坏都是比较 O(nlog 2 n)次，所以选项 A 正确。17.设表的长度为 n。下列算法中，最坏情况下比
31、较次数小于 n 的是（分数：2.00）A.二分查找法 B.堆排序C.快速排序D.顺序查找法解析：解析 二分法查找只适用于顺序存储的有序表。二分查找的基本方法是：将被查元素 x 与线性表的中间项进行比较，若中间项的值等于 x，则说明查到；若小于中间项的值则在线性表的前半部分；以相同的方法进行查找；若大于中间项的值，则在线性表的后半部分以相同的方法进行查找。在最坏情况下，二分查找需要比较 log 2 n 次。所以选项 A 正确。18.下列叙述中错误的是（分数：2.00）A.循环链表是循环队列的存储结构 B.二叉链表是二叉树的存储结构C.栈是线性结构D.循环队列是队列的存储结构解析：解析 循环队列属
32、于逻辑结构，其实质还是顺序存储，只是使用指针进行首尾的联结，其实现的存储方式可分为：分散的链表和连续的线性表，与其逻辑结构实现功能无关。所以选项 A 正确。19.设一棵树的度为 4，其中度为 4，3，2，1 的结点个数分别为 2，3，3，0。则该棵树中的叶子结点数为（分数：2.00）A.16 B.15C.17D.不可能有这样的树解析：解析 因为任一棵树中，结点总数=总分支数目+1，所以：n 0 +2+3+3+0=(n 0 *0+4*2+3*3+2*3+1*0)+1。计算得出 n 0 =16。其中，n 0 表示叶子结点，所以选项 A 正确。20.循环队列的存储空间为 Q(1:100)，初始状态为
33、 front=rear=100。经过一系列正常的入队与退队操作后，front=rear=99，则循环队列中的元素个数为（分数：2.00）A.0 或 100 B.1C.2D.99解析：解析 循环队列中，由于入队时尾指针 rear 向前追赶头指针 front；出队时头指针 front 向前追赶尾指针 rear，造成队空和队满时头尾指针均相等。因此，无法通过条件 front=rear 来判别队列是“空”还是“满”。对于这个题目来说，经过一系列正常的入队与退队操作后，front=rear=99，此时，要么队列为空(元素个数为 0)，要么队列为满(元素个数为 100)，因此选项 A 正确。21.设顺序表
34、的长度为 n。下列算法中，最坏情况下比较次数小于 n 的是（分数：2.00）A.寻找最大项 B.堆排序C.快速排序D.顺序查找法解析：解析 如果顺序表是线性存储的(不包括线性的链式表)，那么元素要不就是从大到小，要不就是小到大的顺序，假设第一个数就是最大值，那么需要比较 1 次，n-1 应该是最坏情况下要比较的次数，所以选项 A 正确。22.设栈的顺序存储空间为 S(1:m)，初始状态为 top=m+1。现经过一系列正常的入栈与退栈操作后，top=0，则栈中的元素个数为（分数：2.00）A.不可能 B.m+1C.1Dm解析：解析 栈是向上增长的，每次压入一个元素，栈的 TOP 指针向上移动一位
35、，即 top-1。对于这个题目，由于 top 初始值等于 m+1，此时入栈一个元素，top 值减 1，即 m+1-1=m，依次类推，当栈满时，top 的值等于 1，不会出现 top 的值等于 0。所以选项 A 正确。23.某二叉树的后序遍历序列与中序遍历序列相同，均为 ABCDEF，则按层次输出(同一层从左到右)的序列为（分数：2.00）A.FEDCBA B.CBAFEDC.DEFCBAD.ABCDEF解析：解析 后序遍历次序：左右根；中序遍历次序：左根右。 由定义可知：后序遍历中最后一个是树的根结点，即 F 结点；在中序遍历中，根结点左边的是左子树集，右边的是右子树集，即 ABCDE 是根结
36、点 F 的左子树集合。 问题就会转化为：求后序遍历是 ABCDE，中序遍历是 ABCDE 的子树。方法同上，因为中序遍历中，E 结点右边没有结点了，所以 E 结点不包含右子树，否则就会被分为 2 个子问题。以下是这道题的详细推理过程：步骤 1 ：由 ABCDEF 得出根结点为 F，由中序遍历可知：ABCDEF，右子树为空； 步骤 2 ：由 ABCDE 得出左子树集合的根节点为 E，由中序可知：ABCDE，右子树为空； 步骤 3 ：同理，二叉树更新后如下。 24.循环队列的存储空间为 Q(1:200)，初始状态为 front=rear=200。经过一系列正常的入队与退队操作后，front=rea
37、r=1，则循环队列中的元素个数为（分数：2.00）A.0 或 200 B.1C.2D.199解析：解析 循环队列中，由于入队时尾指针 rear 向前追赶头指针 front；出队时头指针 front 向前追赶尾指针 rear，造成队空和队满时头尾指针均相等。因此，无法通过条件 front=rear 来判别队列是“空”还是“满”。对于这个题目来说，经过一系列正常的入队与退队操作后，front=rear=1，此时，要么队列为空(元素个数为 0)，要么队列为满(元素个数为 200)。所以选项 A 正确。25.设栈的顺序存储空间为 S(1:m)，初始状态为 top=0。现经过一系列正常的入栈与退栈操作后
38、，top=m+1，则栈中的元素个数为（分数：2.00）A.不可能 B.m+1C.0Dm解析：解析 栈是向上增长的，每次压入一个元素，栈的 TOP 指针向上移动一位，即 top-1。对于这个题目，由于 top 初始值等于 0，此时入栈一个元素，top 值减 1，即 0-1=-1，出现下溢错误，所以选项 A正确。26.下列排序法中，最坏情况下时间复杂度最小的是（分数：2.00）A.堆排序 B.快速排序C.希尔排序D.冒泡排序解析：解析 假设线性表的长度为 n，则在最坏情况下，冒泡排序需要经过 n/2 遍的从前往后扫描和 n/2遍的从后往前扫描，需要比较次数为 n(n-1)/2。快速排序法的最坏情况
39、比较次数也是 n(n-1)/2。简单插入排序，无论是否最坏都需要 n(n-1)/2 比较。堆排序，无论是否最坏情况都是比较 O(nlog 2 n)次。所以选项 A 正确。27.某二叉树的前序遍历序列与中序遍历序列相同，均为 ABCDEF，则按层次输出(同一层从左到右)的序列为（分数：2.00）A.ABCDEF B.BCDEFAC.FEDCBAD.DEFABC解析：解析 前序遍历次序：根左右；中序遍历次序：左根右。 由定义可以知道：前序遍历中第一个就是树根结点，即 A 结点；在中序遍历中，根结点左边的是左子树集，右边的是右子树集，即 BCDEF 是根结点 A 的右子树集合。问题就会转化为：求前序
40、遍历是 BCDEF，中序遍历是 BCDEF 的子树，方法同上。详细推理过程： 步骤 1 ：由 ABCDEF 得出根结点为 A，由中序遍历可知：左子树为空，ABCDEF； 步骤 2 ：由 BCDEF 得出右子树集合的根节点为 B，由中序可知：左子树为空，BCDEF； 步骤 3 ：同理，二叉树更新后如下。 28.下列叙述中正确的是（分数：2.00）A.对数据进行压缩存储会降低算法的空间复杂度 B.算法的优化主要通过程序的编制技巧来实现C.算法的复杂度与问题的规模无关D.数值型算法只需考虑计算结果的可靠性解析：解析 算法的空间复杂度是指执行这个算法所需要的内存空间，包括 3 个部分：输入数据所占的存
41、储空间：程序本身所占的存储空间：算法执行过程中所需要的额外空间。为了降低算法的空间复杂度，主要应减少输入数据所占的存储空间以及额外空间，通常采用压缩存储技术，A 选项正确。29.设数据结构 B=(D，R)，其中 D=a，b，c，d，e，f R=(a，b)，(b，c)，(c，d)，(d，e)，(e，f)，(f，a) 该数据结构为（分数：2.00）A.非线性结构 B.循环队列C.循环链表D.线性结构解析：解析 该逻辑结构为非线性结构，在 R=(a，b)，(b，c)，(c，d)，(d，e)，(e，f)，(f，a)中，结构中的各结点之间形成一个循环链。30.下列排序法中，每经过一次元素的交换会产生新的
42、逆序的是（分数：2.00）A.快速排序 B.冒泡排序C.简单插入排序D.简单选择排序解析：解析 冒泡排序只交换相邻元素，但不是每次移动都产生新的逆序。简单插入排序的元素移动不会产生新的逆序。快速排序每一次交换移动都会产生新的逆序，因为当不会有新的逆序产生时，本轮比较结束。故选项 A 正确。31.某带链的队列初始状态为 front=rear=NULL。经过一系列正常的入队与退队操作后，front=rear=10。该队列中的元素个数为（分数：2.00）A.1 B.0C.1 或 0D.不确定解析：解析 循环队列用数组 A0；m-1存放其元素值，已知其头尾指针分别是 front 和 rear，则当前队
43、列的元素个数是(rear-front+m)%m=1，所以选项 A 正确。32.某完全二叉树按层次输出(同一层从左到右)的序列为 ABCDEFGH。该完全二叉树的前序序列为（分数：2.00）A.ABDHECFG B.ABCDEFGHC.HDBEAFCGD.HDEBFGCA解析：解析 完全二叉树的特点是除最后一层外，每一层上的节点数均达到最大值；在最后一层上只缺少右边的若干结点。根据上述的特点，完全二叉树按层次输出(同一层从左到右)的序列为 ABCDEFGH，可以得到其结构如下： 33.下列叙述中正确的是（分数：2.00）A.有的二叉树也能用顺序存储结构表示 B.有两个指针域的链表就是二叉链表C.
44、多重链表一定是非线性结构D.顺序存储结构一定是线性结构解析：解析 完全二叉树如果“根”从 1 开始编号，则第 i 结点的左孩子编号为 2i，右孩子为 2i+1，双亲编号为(i/2)下取整，空间紧密，适合顺序存储结构。所以选项 A 正确。 小提示：取整是指取不超过实数 x 的最大整数，称为 x 的整数部分。上取整就是对实数取大于当前实数的第一个整数；下取整就是对当前实数去掉小数取整。34.下列各排序法中，最坏情况下时间复杂度最小的是（分数：2.00）A.堆排序 B.快速排序C.希尔排序D.冒泡排序解析：解析 快速排序、冒泡排序最坏情况下时间复杂度是 O(n 2 )；希尔排序最坏情况下时间复杂度是
45、O(n 1.2 )。堆排序最坏情况下时间复杂度是 O(nlog 2 n)，所以选项 A 正确。35.某带链队列初始状态为 front=rear=NULL。经过一系列正常入队与退队操作后，front=10，rear=5。该队列中的元素个数为（分数：2.00）A.不确定 B.5C.4D.6解析：解析 循环队列用数组 A0:m-1存放其元素值，已知其头尾指针分别是 front 和 rear，则当前队列的元素个数是(rear-front+m)%m=(5-10+m)%m=(m-5)%m。因为本题中的 m 值不确定，所以(m-5)%m 的值不能确定。所以选项 A 正确。36.某二叉树的前序序列为 ABDF
46、HCEG，中序序列为 HFDBACEG。该二叉树按层次输出(同一层从左到右)的序列为（分数：2.00）A.ABCDEFGH B.HFDBGECAC.HGFEDCBAD.ACEGBDFH解析：解析 由于二叉树的前序序列 ABDFHCEG，可以确定这个二叉树的根结点是 A。再由中序序列HFDBACEG，可以得到，HFDB 为 A 的左子树，CEG 为 A 的右子树。同理依次对左子树 HFDB 和右子树 CEG 进行同样的推理，得到这个二叉树的结构如下： 37.某带链栈初始状态为 top=bottom=NULL，经过一系列正常的入栈与退栈操作后，top=10，bottom=20。该栈中的元素个数为（
47、分数：2.00）A.不确定 B.10C.1D.0解析：解析 对于链栈而言，使用了链表来实现栈，链表中的元素存储在不连续的地址。所以当top=10，bottom=20 时，不能确定栈中的元素个数，所以选项 A 正确。38.设表的长度为 15。则在最坏情况下，快速排序所需要的比较次数为（分数：2.00）A.105 B.55C.15D.75解析：解析 假设线性表的长度为 n，在最坏情况下，快速排序法的比较次数是 n(n-1)/2。题中 n=15，所以 15*14/2=105。所以选项 A 正确。39.设循环队列的存储空间为 Q(1:100)，初始状态为空。现经过一系列正常操作后，front=49，则
48、循环队列中的元素个数为（分数：2.00）A.不确定 B.49C.51D.50解析：解析 循环队列用数组 Q1:100存放其元素值，已知其头尾指针分别是 front 和 rear，则当前队列的元素个数是(rear-front+100)%100，题目中首指针 rear 的值未知，所以循环队列中的元素个数不能确定。所以选项 A 正确。40.某完全二叉树按层次输出(同一层从左到右)的序列为 ABCDEFGH。该完全二叉树的中序序列为（分数：2.00）A.HDBEAFCG B.HDEBFGCAC.ABDHECFGD.ABCDEFGH解析：解析 完全二叉树的特点是除最后一层外，每一层上的节点数均达到最大值
49、；在最后一层上只缺少右边的若干结点。根据上述特点，完全二叉树按层次输出(同一层从左到右)的序列为 ABCDEFGH。可以得到其结构如下： 41.下列叙述中正确的是（分数：2.00）A.解决一个问题可以有不同的算法，且它们的时间复杂度可以是不同的 B.解决一个问题可以有不同的算法，但它们的时间复杂度必定是相同的C.解决一个问题的算法是唯一的D.算法的时间复杂度与计算机系统有关解析：解析 算法的时间复杂度和问题有关系，因为一个问题很有可能有许多类算法，但是它们的时间复杂度不同，如排序问题就有 10 种左右算法，它们复杂度显然是不一样的。所以选项 A 正确。42.设表的长度为 n。下列查找算法中，在最坏情况下，比较次数最少的是（分数：2.00）A.有序表的二分查找 B.顺序查找C.寻找最大项D.寻找最小项解析：解析 有序表的二分法查找只适用于顺序存储的有序表。二分查找的基本方法是：将被查元素 x与线性表的中间项进行比较，若中间项的值等于 x，则说明
