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