1、国家二级 ACCESS 机试选择题（数据结构与算法）模拟试卷 16 及答案解析(总分：64.00，做题时间：90 分钟)一、选择题(总题数：32，分数：64.00)1.下列叙述中正确的是（分数：2.00）A.算法的时间复杂度与运行算法时特定的输入有关B.算法的时间复杂度与计算机的运行速度有关C.算法的时间复杂度与算法程序中的语句条数成正比D.算法的时间复杂度与算法程序编制者的水平有关2.下列各排序法中，最坏情况下的时间复杂度最低的是（分数：2.00）A.堆排序B.快速排序C.希尔排序D.冒泡排序3.设栈的存储空间为 S(1：50)，初始状态为 top=51。现经过一系列正常的入栈与退栈操作后，
2、top=50，则栈中的元素个数为（分数：2.00）A.1B.OC.50D.494.某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（分数：2.00）A.不存在这样的二叉树B.200C.198D.1995.下列叙述中错误的是（分数：2.00）A.对于各种特定的输入，算法的时间复杂度是固定不变的B.算法的时间复杂度与使用的计算机系统无关C.算法的时间复杂度与使用的程序设计语言无关D.算法的时间复杂度与实现算法过程中的具体细节无关6.在长度为 n 的顺序表中查找一个元素，假设需要查找的元素一定在表中，并且元素出现在表中每个位置上的可能性是相同的，则在平均情
3、况下需要比较的次数为（分数：2.00）A.(n+1)2B.nC.3n4D.n47.设非空二叉树的所有子树中，其左子树上的结点值均小于根结点值，而右子树上的结点值均不小于根结点值，则称该二叉树为排序二叉树。对排序二叉树的遍历结果为有序序列的是（分数：2.00）A.中序序列B.前序序列C.后序序列D.前序序列或后序序列8.循环队列的存储空间为 Q(1：50)，初始状态为 front=rear=50。经过一系列正常的入队与退队操作后，front=rear=25，此后又插入一个元素，则循环队列中的元素个数为（分数：2.00）A.1，或 50 且产生上溢错误B.5 1C.26D.29.下列算法中均以比较
4、作为基本运算，则平均情况与最坏情况下的时间复杂度相同的是（分数：2.00）A.在顺序存储的线性表中寻找最大项B.在顺序存储的线性表中进行顺序查找C.在顺序存储的有序表中进行对分查找D.在链式存储的有序表中进行查找10.在只有 2n 个结点的完全二叉树中，叶子结点个数为（分数：2.00）A.nB.n+1C.n-1D.n211.下列叙述中正确的是（分数：2.00）A.在栈中，栈顶指针的动态变化决定栈中元素的个数B.在循环队列中，队尾指针的动态变化决定队列的长度C.在循环链表中，头指针和链尾指针的动态变化决定链表的长度D.在线性链表中，头指针和链尾指针的动态变化决定链表的长度12.循环队列的存储空间
5、为 O(1：40)，初始状态为。front=rear=40。经过一系列正常的入队与退队操作后，front=rear=15，此后又退出一个元素，则循环队列中的元素个数为（分数：2.00）A.39，或 0 且产生下溢错误B.14C.40D.1513.某二又树的中序遍历序列为 CBADE，后序遍历序列为 CBADE，则前序遍历序列为（分数：2.00）A.EDABCB.CBEDAC.CBADED.EDCBA14.下列叙述中正确的是（分数：2.00）A.在循环队列中，队头指针和队尾指针的动态变化决定队列的长度B.在循环队列中，队尾指针的动态变化决定队列的长度C.在带链的队列中，队头指针与队尾指针的动态变
6、化决定队列的长度D.在带链的栈中，栈顶指针的动态变化决定栈中元素的个数15.设栈的存储空间为 S(1：60)，初始状态为 top=61。现经过一系列正常的入栈与退栈操作后，top 则栈中的元素个数为（分数：2.00）A.60B.59C.0D.116.设顺序表的长度为 n。下列排序方法中，最坏情况下比较次数小于 n(n1)2 的是（分数：2.00）A.堆排序B.快速排序C.简单插入排序D.冒泡排序17.在长度为 n 的顺序表中查找一个元素，假设需要查找的元素有一半的机会在表中，并且如果后表中，则出现在表中每个位置上的可能性是相同的。则在平均情况下需要比较的次数大约为（分数：2.00）A.(3+n
7、)4B.nC.n2D.n418.设一棵树的度为 3，其中度为 3，2，1 的结点个数分别为 4，1，3。则该棵树中的叶子结点数为（分数：2.00）A.10B.11C.12D.不可能有这样的树19.设栈的存储空间为 S(1：50)，初始状态为 top=0。现经过一系列正常的入栈与退栈操作后，top 则栈中的元素个数为（分数：2.00）A.不可能B.50C.0D.120.设顺序表的长度为 n。下列算法中，最坏情况下比较次数等于 n(n-1)2 的是（分数：2.00）A.快速排序B.堆排序C.顺序查找D.寻找最大项21.设表的长度为 n。下列算法中，最坏情况下比较次数小于 n 的是（分数：2.00）
8、A.二分查找法B.堆排序C.快速排序D.顺序查找法22.下列叙述中错误的是（分数：2.00）A.循环链表是循环队列的存储结构B.二叉链表是二叉树的存储结构C.栈是线性结构D.循环队列是队列的存储结构23.设一棵树的度为 4，其中度为 4，3，2，1 的结点个数分别为 2，3，3，0。则该棵树中的叶子结数为（分数：2.00）A.16B.15C.17D.不可能有这样的树24.循环队列的存储空间为 Q(1：100)，初始状态为 front=rear=100。经过一系列正常的入队与退队操作后，front=rear=99，则循环队列中的元素个数为（分数：2.00）A.0 或 100B.1C.2D.992
9、5.设顺序表的长度为 n。下列算法中，最坏情况下比较次数小于 n 的是（分数：2.00）A.寻找最大项B.堆排序C.快速排序D.顺序查找法26.设栈的顺序存储空间为 S(1：m)，初始状态为 top=m+1。现经过一系列正常的入栈与退栈操作后，top=0，则栈中的元素个数为（分数：2.00）A.不可能B.m+1C.1D.m27.某二叉树的后序遍历序列与中序遍历序列相同，均为 ABCDEF，则按层次输出(同一层从左到右)的序列为（分数：2.00）A.FEDCBAB.CBAFEDC.DEFCBAD.ABCDEF28.循环队列的存储空间为 Q(1：200)，初始状态为 front=rear=200。
10、经过一系列正常的入队与退队操作后，front=rear=1，则循环队列中的元素个数为（分数：2.00）A.0 或 200B.1C.2D.19929.设栈的顺序存储空间为 S(1：m)，初始状态为 top=0。觋经过一系列正常的入栈与退栈操作后，top=m+1，则栈中的元素个数为（分数：2.00）A.不可能B.m+1C.0D.m30.下列排序法中，最坏情况下时间复杂度最小的是（分数：2.00）A.堆排序B.快速排序C.希尔排序D.冒泡排序31.某二叉树的前序遍历序列与中序遍历序列相同，均为 ABCDEF，则按层次输出(同一层从左到右)的序列为（分数：2.00）A.ABCDEFB.BCDEFAC.
11、FEDCBAD.DEFABC32.下列叙述中正确的是（分数：2.00）A.对数据进行压缩存储会降低算法的空间复杂度B.算法的优化主要通过程序的编制技巧来实现C.算法的复杂度与问题的规模无关D.数值型算法只需考虑计算结果的可靠性国家二级 ACCESS 机试选择题（数据结构与算法）模拟试卷 16 答案解析(总分：64.00，做题时间：90 分钟)一、选择题(总题数：32，分数：64.00)1.下列叙述中正确的是（分数：2.00）A.算法的时间复杂度与运行算法时特定的输入有关 B.算法的时间复杂度与计算机的运行速度有关C.算法的时间复杂度与算法程序中的语句条数成正比D.算法的时间复杂度与算法程序编制
12、者的水平有关解析：解析：算法的时间复杂度，是指执行算法所需要的计算工作量，算法的工作量用算法所执行的基本运行次数来度量，所以与运行算法时特定的输入有关，选项 A 正确。2.下列各排序法中，最坏情况下的时间复杂度最低的是（分数：2.00）A.堆排序 B.快速排序C.希尔排序D.冒泡排序解析：解析：堆排序法，最坏情况需要 O(nlog 2 n)次比较。相比以上几种“除希尔排序法外”，堆排序法的时间复杂度最小，故选项 A 正确。3.设栈的存储空间为 S(1：50)，初始状态为 top=51。现经过一系列正常的入栈与退栈操作后，top=50，则栈中的元素个数为（分数：2.00）A.1 B.OC.50D
13、.49解析：解析：栈的存储空间为 S(1：50)，初始状态为 top=51。现经过一系列正常的入栈与退栈操作后，top=50，则栈中有 51-50=1 个元素，因此选项 A 正确。4.某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（分数：2.00）A.不存在这样的二叉树B.200 C.198D.199解析：解析：在二叉树中，设叶子结点个数为 n 0 ，度为 2 的结点个数为 n 2 ，叶子结点的个数计算方法 n 0 =n 2 +1=199+1=200，所以选项 B 正确。5.下列叙述中错误的是（分数：2.00）A.对于各种特定的输入，算法的时间复杂
14、度是固定不变的 B.算法的时间复杂度与使用的计算机系统无关C.算法的时间复杂度与使用的程序设计语言无关D.算法的时间复杂度与实现算法过程中的具体细节无关解析：解析：一般情况下，算法的基本操作重复执行的次数，是模块 n 的某一个函数 f(n)。因此，算法的时间复杂度记做 T(n)=O(f(n)。随着模块 n 的增大，算法执行的时间的增长率和 f(n)的增长率成正比，所以 f(n)越小，算法的时间复杂度越低，算法的效率越高。因此算法会随着输入数据的不同而有执行效率的不同，有时候会快点儿，有时候会慢点儿。因此选项 A 正确。6.在长度为 n 的顺序表中查找一个元素，假设需要查找的元素一定在表中，并且
15、元素出现在表中每个位置上的可能性是相同的，则在平均情况下需要比较的次数为（分数：2.00）A.(n+1)2 B.nC.3n4D.n4解析：解析：在一个长度为 n 的线性表中顺序查找值为 x 的元素时，在等概率情况下查找成功时平均查找长度为(1+1)2，所以选项 A 正确。7.设非空二叉树的所有子树中，其左子树上的结点值均小于根结点值，而右子树上的结点值均不小于根结点值，则称该二叉树为排序二叉树。对排序二叉树的遍历结果为有序序列的是（分数：2.00）A.中序序列 B.前序序列C.后序序列D.前序序列或后序序列解析：解析：中序遍历的次序是先遍历左子树，再遍历根节点，最后遍历右子树。而左子树结点值根
16、节点节点值右子树节点值，是有序序列，因此选项 A 正确。8.循环队列的存储空间为 Q(1：50)，初始状态为 front=rear=50。经过一系列正常的入队与退队操作后，front=rear=25，此后又插入一个元素，则循环队列中的元素个数为（分数：2.00）A.1，或 50 且产生上溢错误 B.5 1C.26D.2解析：解析：循环队列初始状态 front=rear=50，经过一系列入队和出队操作后，结束状态还是front=rear=25，这说明入队元素个数和出队元素个数一样多。这样一来最后的元素个数就和原来的元素个数一样多，明显不是 0 就是 50，即要么队空(0 个元素)，要么队满(50
17、 个元素)。这时进行入队操作，如果是队空(0 个元素)的情况，此时元素个数为 1；如果是队满(50 个元素)的情况，就会产生上溢错误。9.下列算法中均以比较作为基本运算，则平均情况与最坏情况下的时间复杂度相同的是（分数：2.00）A.在顺序存储的线性表中寻找最大项 B.在顺序存储的线性表中进行顺序查找C.在顺序存储的有序表中进行对分查找D.在链式存储的有序表中进行查找解析：解析：最坏情况下的时间复杂度称为最坏时间复杂度。一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度。最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，这就保证了算法的运行时间不会比任何情况更长。 平均时间复
18、杂度是指所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间。在输入不同的情况下算法的运行时间复杂度可能会发生变化。平均时间复杂度给出了算法的期望运行时间，有助于算法好坏的评价以及在不同算法之间比较时有一个统一标准。 在顺序存储的线性表中寻找最大项，其平均情况与最坏情况下的时间复杂度都是 n2。10.在只有 2n 个结点的完全二叉树中，叶子结点个数为（分数：2.00）A.n B.n+1C.n-1D.n2解析：解析：在具有 2n 个结点的完全二叉树中，叶子结点个数为：(2n+1)2 取整，其值等于 n。所以选项 A 正确。11.下列叙述中正确的是（分数：2.00）A.在栈中，栈顶指针的动
19、态变化决定栈中元素的个数 B.在循环队列中，队尾指针的动态变化决定队列的长度C.在循环链表中，头指针和链尾指针的动态变化决定链表的长度D.在线性链表中，头指针和链尾指针的动态变化决定链表的长度解析：解析：栈是一种特殊的线性表，是一种只允许在表的一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶；表的另一端称为栈底。栈顶的当前位置是动态的，对栈顶当前位置的标记称为栈顶指针。在栈中，栈顶指针动态反映了栈中元素的变化情况。所以选项 A 正确。12.循环队列的存储空间为 O(1：40)，初始状态为。front=rear=40。经过一系列正常的入队与退队操作后，front=rear
20、=15，此后又退出一个元素，则循环队列中的元素个数为（分数：2.00）A.39，或 0 且产生下溢错误 B.14C.40D.15解析：解析：循环队列初始状态 front=rear=40，经过一系列入队和出队操作后，结束状态还是front=rear=15，这说明入队元素个数和出队元素个数一样多。这样一来最后的元素个数就和原来的元素个数一样多，明显不是 0 就是 40，即要么队列为空(0 个元素)，要么队列为满队列(40 个元素)。这时进行出队操作，如果是队列满(40 个元素)的情况，此时队列中的元素个数为 39，如果是队列空(0 个元素)的情况，此时就会产生下溢错误。因此选项 A 正确。13.某
21、二又树的中序遍历序列为 CBADE，后序遍历序列为 CBADE，则前序遍历序列为（分数：2.00）A.EDABC B.CBEDAC.CBADED.EDCBA解析：解析：后序遍历次序是“左右根”，中序遍历次序是“左根右”。 由定义可知：后序遍历中最后一个就是树根结点，即 E 结点：在中序遍历中，根结点左边的是左子树集，右边的是右子树集，即CBAD 是根结点 E 的左子树集合。问题就会转化为：求后序遍历是 CBAD，中序遍历是 CBAD 的子树，方法同上。因为中序遍历中，D 结点右边没有结点了，所以 D 结点不包含右子树，否则就会被分为 2 个子问题 以下是这道题的详细推理过程：步骤 1：由 CB
22、ADE 得出根结点为 E，由中序遍历可知CBADE，右子树为空；步骤 2：由 CBAD 得出左子树集合的根节点为 D，由中序可知CBAD，右子树为空；步骤 3：同理，二叉树更新后如下图所示。14.下列叙述中正确的是（分数：2.00）A.在循环队列中，队头指针和队尾指针的动态变化决定队列的长度 B.在循环队列中，队尾指针的动态变化决定队列的长度C.在带链的队列中，队头指针与队尾指针的动态变化决定队列的长度D.在带链的栈中，栈顶指针的动态变化决定栈中元素的个数解析：解析：循环队列是将顺序队列首尾相连形成的，随着插入元素或删除元素的进行，其队头指针及队尾指针是在不断变化的，有时可能会出现队头指针大于
23、队尾指针的情况，也可能是队尾指针大于队头指针。循环队列中计算元素的个数公式为：(rear-front+queue_size)queue_size。所以选项 A 正确。15.设栈的存储空间为 S(1：60)，初始状态为 top=61。现经过一系列正常的入栈与退栈操作后，top 则栈中的元素个数为（分数：2.00）A.60 B.59C.0D.1解析：解析：栈是向上增长的，每次压入一个元素，栈的 TOP 指针向上移动一位，即 top-1。当压入第一个元素时，TOP 指针指向 60+1-1=60；当压入第二个元素时，TOP 指针指向 60+1-2=59；以此类推，当压入第 N 个元素时，TOP 指针指
24、向 60+1-N=1，则 N=60。所以选项 A 正确。16.设顺序表的长度为 n。下列排序方法中，最坏情况下比较次数小于 n(n1)2 的是（分数：2.00）A.堆排序 B.快速排序C.简单插入排序D.冒泡排序解析：解析：假设线性表的长度为 n，则在最坏情况下，冒泡排序需要经过 n2 遍的从前往后扫描和n2 遍的从后往前扫描，需要比较次数为 n(n-1)2。快速排序法的最坏情况比较次数也是 n(n-1)2。简单插入排序，无论是否最坏都需要 n(n-1)2 比较。堆排序，无论是否最坏都需要比较 O(nlog 2 n)次。17.在长度为 n 的顺序表中查找一个元素，假设需要查找的元素有一半的机会
25、在表中，并且如果后表中，则出现在表中每个位置上的可能性是相同的。则在平均情况下需要比较的次数大约为（分数：2.00）A.(3+n)4 B.nC.n2D.n4解析：解析：在长度为 n 的顺序表中查找一个元素，最好的情况是目标在第一个，一次找到；最坏的情况是目标在最后一个，n 次找到。那么平均长度为：(1+2+n)n=(n(n+1)2)n=(n+1)2。本题需要查找的元素有一半的机会在表中，则在平均情况下需要比较的次数大约为(1+n)2+1)2=(3+n)4。18.设一棵树的度为 3，其中度为 3，2，1 的结点个数分别为 4，1，3。则该棵树中的叶子结点数为（分数：2.00）A.10 B.11C
26、.12D.不可能有这样的树解析：解析：因为任一棵树中，结点总数：总分支数目+1，所以：n 0 +4+1+3=(n 0 *0+3*4+2*1+1*3)+1，计算结果 n 0 =10。其中，n 0 表示叶子结点。所以选项 A 正确。19.设栈的存储空间为 S(1：50)，初始状态为 top=0。现经过一系列正常的入栈与退栈操作后，top 则栈中的元素个数为（分数：2.00）A.不可能 B.50C.0D.1解析：解析：栈是向上增长的，每次压入一个元素，栈的 TOP 指针向上移动一位，即 top-1。对于这个题目，由于 top 初始值等于 0，此时入栈一个元素，top 值减 1，即 0-1=-1，发生
27、下溢错误。20.设顺序表的长度为 n。下列算法中，最坏情况下比较次数等于 n(n-1)2 的是（分数：2.00）A.快速排序 B.堆排序C.顺序查找D.寻找最大项解析：解析：假设线性表的长度为 n，则在最坏情况下，快速排序法的最坏情况比较次数也是 n(n-1)2；堆排序，无论是否最坏都是比较 O(nlog 2 n)次，所以选项 A 正确。21.设表的长度为 n。下列算法中，最坏情况下比较次数小于 n 的是（分数：2.00）A.二分查找法 B.堆排序C.快速排序D.顺序查找法解析：解析：二分法查找只适用于顺序存储的有序表。二分查找的基本方法是：将被查元素 x 与线性表的中间项进行比较，若中间项的
28、值等于 x，则说明查到；若小于中间项的值则在线性表的前半部分；以相同的方法进行查找；若大于中间项的值，则在线性表的后半部分以相同的方法进行查找。在最坏情况下，二分查找需要比较 log 2 n 次。所以选项 A 正确。22.下列叙述中错误的是（分数：2.00）A.循环链表是循环队列的存储结构 B.二叉链表是二叉树的存储结构C.栈是线性结构D.循环队列是队列的存储结构解析：解析：循环队列属于逻辑结构，其实质还是顺序存储，只是使用指针进行首尾的联结，其实现的存储方式可分为：分散的链表和连续的线性表，与其逻辑结构实现功能无关。所以选项 A 正确。23.设一棵树的度为 4，其中度为 4，3，2，1 的结
29、点个数分别为 2，3，3，0。则该棵树中的叶子结数为（分数：2.00）A.16 B.15C.17D.不可能有这样的树解析：解析：因为任一棵树中，结点总数=总分支数目+1，所以：n 0 +2+3+3+0=(n 0 *1+4*2+3*3+2*3+1*0)+1。计算得出 n 0 =16。其中，n 0 表示叶子结点，所以选项 A 正确。24.循环队列的存储空间为 Q(1：100)，初始状态为 front=rear=100。经过一系列正常的入队与退队操作后，front=rear=99，则循环队列中的元素个数为（分数：2.00）A.0 或 100 B.1C.2D.99解析：解析：循环队列中，由于入队时尾指
30、针 rear 向前追赶头指针 front；出队时头指针 front 向前追赶尾指针 rear，造成队空和队满时头尾指针均相等。因此，无法通过条件 front=rear 来判别队列是“空”还是“满”。对于这个题目来说，经过一系列正常的入队与退队操作后，front=rear=99，此时，要么队列为空(元素个数为 0)，要么队列为满(元素个数为 100)，因此选项 A 正确。25.设顺序表的长度为 n。下列算法中，最坏情况下比较次数小于 n 的是（分数：2.00）A.寻找最大项 B.堆排序C.快速排序D.顺序查找法解析：解析：如果顺序表是线性存储的(不包括线性的链式表)，那么元素要不就是从大到小，要
31、不就是小到大的顺序，假设第一个数就是最大值，那么需要比较 1 次，n-1 应该是最坏情况下要比较的次数，所以选项 A 正确。26.设栈的顺序存储空间为 S(1：m)，初始状态为 top=m+1。现经过一系列正常的入栈与退栈操作后，top=0，则栈中的元素个数为（分数：2.00）A.不可能 B.m+1C.1D.m解析：解析：栈是向上增长的，每次压入一个元素，栈的 TOP 指针向上移动一位，即 top-1。对于这个题目，由于 top 初始值等于 m+1，此时入栈一个元素，top 值减 1，即 m+1-1=m，依次类推，当栈满时，top的值等于 1，不会出现 top 的值等于 0。所以选项 A 正确
32、。27.某二叉树的后序遍历序列与中序遍历序列相同，均为 ABCDEF，则按层次输出(同一层从左到右)的序列为（分数：2.00）A.FEDCBA B.CBAFEDC.DEFCBAD.ABCDEF解析：解析：后序遍历次序：左右根；中序遍历次序：左根右。 由定义可知：后序遍历中最后一个是树的根结点，即 F 结点；在中序遍历中，根结点左边的是左子树集，右边的是右子树集，即 ABCDE 是根结点 F 的左子树集合。问题就会转化为：求后序遍历是 ABCDE，中序遍历是 ABCDE 的子树。方法同上，因为中序遍历中，E 结点右边没有结点了，所以 E 结点不包含右子树，否则就会被分为 2 个子问题。以下是这道
33、题的详细推理过程：步骤 l：由 ABCDEF 得出根结点为 F，由中序遍历可知：ABCDEF，右子树为空；步骤 2：由 ABCDE 得出左子树集合的根节点为 E，由中序可知：ABCDE，右子树为空；步骤 3：同理，二叉树更新后如下。28.循环队列的存储空间为 Q(1：200)，初始状态为 front=rear=200。经过一系列正常的入队与退队操作后，front=rear=1，则循环队列中的元素个数为（分数：2.00）A.0 或 200 B.1C.2D.199解析：解析：循环队列中，由于入队时尾指针 rear 向前追赶头指针 front；出队时头指针 front 向前追赶尾指针 rear，造成
34、队空和队满时头尾指针均相等。因此，无法通过条件 front=rear 来判别队列是“空”还是“满”。对于这个题目来说，经过一系列正常的入队与退队操作后，front=rear=1，此时，要么队列为空(元素个数为 0)，要么队列为满(元素个数为 200)。所以选项 A 正确。29.设栈的顺序存储空间为 S(1：m)，初始状态为 top=0。觋经过一系列正常的入栈与退栈操作后，top=m+1，则栈中的元素个数为（分数：2.00）A.不可能 B.m+1C.0D.m解析：解析：栈是向上增长的，每次压入一个元素，栈的 TOP 指针向上移动一位，即 top-1。对于这个题目，由于 top 初始值等于 0，此
35、时入栈一个元素，top 值减 1，即 0-1=-1，出现下溢错误，所以选项 A 正确。30.下列排序法中，最坏情况下时间复杂度最小的是（分数：2.00）A.堆排序 B.快速排序C.希尔排序D.冒泡排序解析：解析：假设线性表的长度为 n，则在最坏情况下，冒泡排序需要经过 n2 遍的从前往后扫描和n2 遍的从后往前扫描，需要比较次数为 n(n-1)2。快速排序法的最坏情况比较次数也是 n(n-1)2。简单插入排序，无论是否最坏都需要 n(n-1)2 比较。堆排序，无论是否最坏情况都是比较 O(nlog 2 n)次。所以选项 A 正确。31.某二叉树的前序遍历序列与中序遍历序列相同，均为 ABCDE
36、F，则按层次输出(同一层从左到右)的序列为（分数：2.00）A.ABCDEF B.BCDEFAC.FEDCBAD.DEFABC解析：解析：前序遍历次序：根左右；中序遍历次序：左根右。 由定义可以知道：前序遍历中第一个就是树根结点，即 A 结点；在中序遍历中，根结点左边的是芹子树集，右边的是右子树集，即 BCDEF 是根结点 A 的右子树集合。问题就会转化为：求前序遍历是 BCDEF，中序遍历是 BCDEF 的子树，方法同上。详细推理过程：步骤 1：由 ABCDEF 得出根结点为 A，由中序遍历可知：左子树为空，ABCDE F；步骤2：由BCDEF 得出右子树集合的根节点为 B，由中序可知：左子树为空，BCDEF；步骤 3：同理，二叉树更新后如下。32.下列叙述中正确的是（分数：2.00）A.对数据进行压缩存储会降低算法的空间复杂度 B.算法的优化主要通过程序的编制技巧来实现C.算法的复杂度与问题的规模无关D.数值型算法只需考虑计算结果的可靠性解析：解析：算法的空间复杂度是指执行这个算法所需要的内存空间，包括 3 个部分：输入数据所占的存储空间；程序本身所占的存储空间：算法执行过程中所需要的额外空间。为了降低算法的空间复杂度，主要应减少输入数据所占的存储空间以及额外空间，通常采用压缩存储技术，A 选项正确。
