1、国家二级 ACCESS机试选择题（数据结构与算法）模拟试卷 5及答案与解析 一、选择题 1 设顺序表的长度为 n。下列算法中，最坏情况下比较次数小于 n的是 （ A）寻找最大项 （ B）堆排序 （ C）快速排序 （ D）顺序查找法 2 设栈的顺序存储空间为 S(1： m)，初始状态为 top=m+1。现经过一系列正常的入栈与退栈操作后， top=0；则栈中的元素个数为 （ A）不可能 （ B） m+1 （ C） 1 （ D） m 3 某二叉树的后序遍历序列与中序遍历序列相同，均为 ABCDEF，则按层次输出(同一层从 左到右 )的序列为 （ A） FEDCBA （ B） CBAFED （ C）
2、 DEFCBA （ D） ABCDEF 4 循环队列的存储空间为 Q(1： 200)，初始状态为 front=rear=200。经过一系列正常的入队与退队操作后， front=rear=1，则循环队列中的元素个数为 （ A） 0或 200 （ B） 1 （ C） 2 （ D） 199 5 设栈的顺序存储空间为 S(1： m)，初始状态为 top=0。现经过一系列正常的入栈与退栈操作后， top=m+1，则栈中的元素个数为 （ A）不可能 （ B） m+1 （ C） 0 （ D） m 6 下列排序法中，最坏情况下时间复杂度最小的是 （ A）堆排序 （ B）快速排序 （ C）希尔排序 （ D）冒泡
3、排序 7 某二叉树的前序遍历序列与中序遍历序列相同，均为 ABCDEF，则按层次输出(同一层从左到右 )的序列为 （ A） ABCDEF （ B） BCDEFA （ C） FEDCBA （ D） DEFABC 8 下列叙述中正确的是 （ A）对数据进行压缩存储会降低算法的空间复杂度 （ B）算法的优化主要通过程序的编制技巧来实现 （ C）算法的复杂度与问题的规模无关 （ D）数值 型算法只需考虑计算结果的可靠性 9 设数据结构 B=(D， R)，其中 D=a， b， c， d， e， D R=(a,b)， (b,c)， (c,(d)， (d,e)， (e， D， (f,(a) 该数据结构为 （
4、 A）非线性结构 （ B）循环队列 （ C）循环链表 （ D）线性结构 10 下列排序法中，每经过一次元素的交换会产生新的逆序的是 （ A）快速排序 （ B）冒泡排序 （ C）简单插入排序 （ D）简单选择排序 11 某带链的队列初始状态为 front=rear=NULL。经过一系列正常的 入队与退队操作后， front=rear=10。该队列中的元素个数为 （ A） 1 （ B） 0 （ C） 1或 0 （ D）不确定 12 某完全二叉树按层次输出 (同一层从左到右 )的序列为 ABCDEFGH。该完全二叉树的前序序列为 （ A） ABDHECFG （ B） ABCDEFGH （ C） HD
5、BEAFCG （ D） HDEBFGCA 13 下列叙述中正确的是 （ A）有的二叉树也能用顺序存储结构表示 （ B）有两个指针域的链表就是二叉链表 （ C）多重链表一定是非线性结构 （ D）顺序存储结构一定是线性结构 14 下列各排序法中，最坏情况下时间复杂度最小的是 （ A）堆排序 （ B）快速排序 （ C）希尔排序 （ D）冒泡排序 15 某带链队列初始状态为 front=rear=NULL。经过一系列正常入队与退队操作后， front=10， rear=5。该队列中的元素个数为 （ A）不确定 （ B） 5 （ C） 4 （ D） 6 16 某二叉树的前序序列为 ABDFHCEG，中序
6、序列为 HFDBACEG。该二叉树按层次输出 (同一层从左到右 )的序列为 （ A） ABCDEFGH （ B） HFDBGECA （ C） HGFEDCBA （ D） ACEGBDFH 17 某带链栈初始状态为 top=bottom=NULL，经过一系列正常的入栈与退栈操作后， top=10， bottom=20，该栈中的元素个数为 （ A）不确定 （ B） 10 （ C） 1 （ D） 0 18 设表的长度为 15。则在最坏情况下，快速排序所需要的比较次数为 （ A） 105 （ B） 55 （ C） 15 （ D） 75 19 设循环队列的存储空间为 Q(1： 100)，初始状态为空。现
7、经过一系列正常操作后， front=49，则循环队列中的元素个数为 （ A） 不确定 （ B） 49 （ C） 51 （ D） 50 20 某完全二叉树按层次输出 (同一层从左到右 )的序列为 ABCDEFGH。该完全二叉树的中序序列为 （ A） HDBEAFCG （ B） HDEBFGCA （ C） ABDHECFG （ D） ABCDEFGH 21 下列叙述中正确的是 （ A）解决一个问题可以有不同的算法，且它们的时间复杂度可以是不同的 （ B）解决一个问题可以有不同的算法，但它们的时间复杂度必定是相同的 （ C）解决一个问题的算法是唯一的 （ D）算法的时间复杂度与计算机系统有关 22
8、设表的长度为 n。下列查找算法中，在最坏情况下，比较次数最少的是 （ A）有序表的二分查找 （ B）顺序查找 （ C）寻找最大项 （ D）寻找最小项 23 某带链栈的初始状态为 top=bottom=NULL，经过一系列正常的入栈与退栈操作后， top=bottom=20。该栈中的元素个数为 （ A） 1 （ B） 0 （ C） 20 （ D）不确定 24 某二叉树的前序序列为 ABDFHCEG，中序序列为 HFDBACEG。该二叉树的后序序列为 （ A） HFDBGECA （ B） ABCDEFGH （ C） HGFEDCBA （ D） ACEGBDFH 25 下列叙述中错误的是 （ A）算
9、法的时间复杂度与问题规模无关 （ B）算法的时间复杂度与计算机系统无关 （ C）算法的时间复杂度与空间复杂度没有必然的联系 （ D）算法的空间复杂度与算法运行输出结果的数据量无关 26 设表的长度为 20。则在最坏情况下，冒泡排序的比较次数为 （ A） 90 （ B） 20 （ C） 19 （ D） 190 27 在带链栈中，经过一系列正常的操作后，如果 top=bosom，则栈中的元素个数为 （ A） 1 （ B） 0 （ C） 0或 I （ D）栈满 28 设一棵树的度为 3，共有 27个结点，其中度为 3， 2， 0的结点数分别为 4， 1，10。该树中度为 l的结点数为 （ A） 1
10、1 （ B） 12 （ C） 13 （ D）不可能有这样的树 29 设数据结构 B=(D， R)，其中 D=a， b， c， d， e， f R=(f， (a)， (d,b)， (e,(d)， (c,e)， (a， c) 该数据结构为 （ A）线性结构 （ B）循环队列 （ C）循环链表 （ D）非线性结构 30 下列叙述中错误的是 （ A）循环队列空的条件是队头指针与队尾指针相 同 （ B）若二叉树没有叶子结点，则为空二叉树 （ C）带链栈的栈底指针是随栈的操作而动态变化的 （ D）若带链队列中只有一个元素，则队头指针与队尾指针必定相同 国家二级 ACCESS机试选择题（数据结构与算法）模拟
11、试卷 5答案与解析 一、选择题 1 【正确答案】 A 【试题解析】 如果顺序表是线性存储的 (不包括线性的链式表 )，那么元素要不就是从大到小，要不就是小到大的顺序，假设第一个数就是最大值，那么需要比较 1次， n一 1应该是最坏情况下要比较的次数，所以选项 A正确。 【知识模块】 数据结构 与算法 2 【正确答案】 A 【试题解析】 栈是向上增长的，每次压入一个元素，栈的 TOP指针向上移动一位，即 top-1。对于这个题目，由于 top初始值等于 m+1，此时入栈一个元素， top值减 1，即 m+1-1=m，依次类推，当栈满时， top的值等于 1，不会出现 top的值等于 0。所以选项
12、 A正确。 【知识模块】 数据结构与算法 3 【正确答案】 A 【试题解析】 后序遍历次序：左右根；中序遍历次序：左根右。由定义可知： 后序遍历中最后一个是树的根结点，即 F结点； 在中序遍历中，根结点左边的是 左子树集，右边的是右子树集，即 ABCDE是根结点 F的左子树集合。问题就会转化为：求后序遍历是 ABC。 DE，中序遍历是 ABCDE的子树。方法同上，因为中序遍历中， E结点右边没有结点了，所以 E结点不包含右子树，否则就会被分为 2个子问题。以下是这道题的详细推理过程：步骤 1：由 ABCDEF。得出根结点为 F，由中序遍历可知： ABCDEF，右子树为空；步骤 2：由 ABCD
13、E得出左子树集合的根节点为 E，由中序可知： ABCDE，右子树为空；步骤 3：同理，二叉树更新后如下。 所以按层次输出 (同一层从左到右 )的序列为 FEDCBA。 【知识模块】 数据结构与算法 4 【正确答案】 A 【试题解析】 循环队列中，由于入队时尾指针 rear向前追赶头指针 front；出队时头指针 front向前追赶尾指针 rear，造成队空和队满时头尾指针均相等。因此，无法通过条件 front=rear来判别队列是 “空 ”还是 “满 ”。对于这个题目来说，经过一系列正常的入队与退队操作后， front=rear=1，此时，要么队列为空 (元素个数为 0)，要么队列为满 (元素
14、个数为 200)。所以选项 A正确。 【知识模块】 数据结构与算法 5 【正确答案】 A 【试题解析】 栈是向上增长的，每次压入一个元素，栈的 TOP指针向上移动一位，即 top-1。对于这个题目，由于 top初始值等于 0，此时入栈一个元素， top值减 1，即 0 1=-1，出现下溢错误，所以选项 A正确。 【知识模块】 数据结构与算法 6 【正确答案】 A 【试题解析】 假设线性表的长度为 n，则在最坏情况下，冒泡排序需要经过 n 2遍的从前往后扫描和 n 2遍的从后往前扫描，需要比较次数为 n(n1) 2。快速排序法的最坏情况比较次数也是 n(n-1) 2。简单插入排序，无论是否最坏都
15、需要n(n一 1) 2比较。堆排序，无论是否最坏情况都是比较 O(nlog2n)次。所以选项 A正确。 【知识模块】 数据结构与算法 7 【正确答案】 A 【试题解析】 前序遍历次序：根左右；中序遍历次序：左根右。由定义可以知道： 前序遍历中第一个就是树根结点，即 A结点； 在中序 遍历中，根结点左边的是左子树集，右边的是右子树集，即 BCDEF是根结点 A的右子树集合。问题就会转化为：求前序遍历是 BCDEF，中序遍历是 BCDEF的子树，方法同上。详细推理过程：步骤 1：由 ABCDEF得出根结点为 A，由中序遍历可知：左子树为空， ABCDE F；步骤 2：由 BCDEF得出右子树集合的
16、根节点为 B，由中序可知：左子树为空， BCDEF；步骤 3：同理，二叉树更新后如下。所以按层次输出 (同一层从左到右 )的序列为 ABCDEF，选项 A正确。 【知识模块】 数据结构与算法 8 【正确答案】 A 【试题解析】 算法的空间复杂度是指执行这个算法所需要的内存空间，包括 3个部分：输入数据所占的存储空间；程序本身所占的存储空间；算法执行过程中所需要的额外空间。为了降低算法的空间复杂度，主要应减少输入数据所占的存储空间以及额外空间，通常采用压缩存储技术， A选项正确。 【知识模块】 数据结构与算法 9 【正确答案】 A 【试题解析】 该逻辑结构为非线性结构，在 R=(a,b)， (b
17、,c)， (c,d)， (d,e)，(e,f)， (f,a)中，各结点之间形成一个循环链。 【知识模块】 数据结构与算法 10 【正确答案】 A 【试题解析】 冒泡排序只交换相令昏元素，但不是每次移动都产生新韵逆序。简单插入排序的元素移动不会产生新的逆序。快速排序每一次交换移动都会产生新的逆序，因为当不会有新的逆序产生时，本轮比较结束。故选项 A正确。 【知识模块】 数据结构与算法 11 【正确答案】 A 【试题解析】 循环队列用数组 A0； m-1存放其元素值，已知其头尾指针分别是front和 rear，则当前队列的元素个数是 (rear-front+m) m=1，所以选项 A正确。 【知识
18、模块】 数据结构与算法 12 【正确答案】 A 【试题解析】 完全二叉树的特点是除最后一层外，每一层上的节点数均达到最大值；在最后一层上只缺少右边的若干结点。根据上述的特点，完全二叉树按层次输出 (同一层从左到右 )的序列为 ABCDEFGH，可以得到其结构如下：所以此完全二叉树的前序序列是 ABDHECFG，选项 A正确。 【知识模块】 数据结构与算法 13 【正确答案】 A 【试题解析】 完全二叉树如果 “根 ”从 1开始编号，则第 i结点的左孩子编号为2i，右孩子为 2i+1，双亲编号为 (i 2)下取整，空间紧密，适合顺序存储结构。所以选项 A正确。小提示：取整是指取不超过实数 x的最
19、大整数，称为 x的整数部分。上取整就是对实数取大于当前实数的第一个整数；下取整就是对当前实数去掉小数取整。 【知识模块】 数据结构与算法 14 【正确答案】 A 【试题解析】 快速排序、冒泡排序最坏情况下时间复杂度是 O(n2)：希尔排序最坏情况下时间复杂度是 O(n1.2)。堆排序最坏情况下时间复杂度是 O(nlog2n)，所以选项 A正确。 【知识模块】 数据结构与算法 15 【正确答案】 A 【试题解析】 循环队列用数组 A0： m-1存放其元素值，己知其头尾指针分别是front和 rear，则当前队列的元素个数是 (rear-front+m) m=(5-10+m) m=(m-5)m。因
20、为本题中的 m值不确定，所以 (m-5) m的值不能确定。所以选项 A正确。 【知识模块】 数据结构与算法 16 【正确答案】 A 【试题解析】 由于二叉树的前序序列 ABDFHCEG，可以确定这个二叉树的根结点是 A。再由中序序列 HFDBACEG，可以得到， HFDB为 A的左子树， CEG为A的右子树。同理依次对 左子树 HFDB和右子树 CEG进行同样的推理，得到这个二叉树的结构如下 该二叉树按层次输出 (同一层从左到右 )的序列为 ABCDEFGH，所以选项 A正确。 【知识模块】 数据结构与算法 17 【正确答案】 A 【试题解析】 对于链栈而言，使用了链表来实现栈，链表中的元素存
21、储在不连续的地址。所以当 top=10， bottom=20时，不能确定栈中的元素个数，所以选项 A正确。 【知识模块】 数据结构与算法 18 【正确答案】 A 【试题解析】 假设线性表的长度为 n，在最坏情况下，快速排序 法的比较次数是n(n-1) 2。题中 n=15，所以 15*14 2=105。所以选项 A正确。 【知识模块】 数据结构与算法 19 【正确答案】 A 【试题解析】 循环队列用数组 Q1： 100存放其元素值，已知其头尾指针分别是front和 rear，则当前队列的元素个数是 (rearfront+100) 100，题目中首指针rear的值未知，所以循环队列中的元素个数不能
22、确定。所以选项 A正确。 【知识模块】 数据结构与算法 20 【正确答案】 A 【试题解析】 完全二叉树的特点是除最后 一层外，每一层上的节点数均达到最大值：在最后一层上只缺少右边的若干结点。根据上述特点，完全二叉树按层次输出 (同一层从左到右 )的序列为 ABCDEFGH。可以得到其结构如下：所以此完全二叉树的中序序列是 HDBEAFCG。所以选项 A正确。 【知识模块】 数据结构与算法 21 【正确答案】 A 【试题解析】 算法的时间复杂度和问题有关系，因为一个问题很有可能有许多类算法，但是它们的时间复杂度不同，如排序问题就有 10种左右算法，它们复杂度显然是不一样的。所以选项 A正确。
23、【知识模块】 数据结构 与算法 22 【正确答案】 A 【试题解析】 有序表的二分法查找只适用于顺序存储的有序表。二分查找的基本方法是：将被查元素 x与线性表的中间项进行比较，若中间项的值等于 x，则说明查到；若小于中间项的值则在线性表的前半部分以相同的方法进行查找；若大于中间项的值则在线性表的后半部分以相同的方法进行查找。在最坏情况下，二分查找需要比较 log2n次。顺序查找、寻找最大项、寻找最小项，在最坏情况下，比较次数都是 n次。所以选项 A正确。 【知识模块】 数据结构与算法 23 【正确答案】 D 【试题解析 】 对于链栈而言，使用了链表来实现栈，链表中的元素存储在不连续的地址。所以
24、当 top=bottom=20时，不能确定栈中的元素个数。所以选项 D正确。 【知识模块】 数据结构与算法 24 【正确答案】 A 【试题解析】 由于二叉树的前序序列 ABDFHCEG，可以确定这个二叉树的根结点是 A。再由中序序列 HFDBACEG，可以得到， HFDB为 A的左子树， CEG为A的右子树子同理依次对左子树。 HFDB和右子树 CEG进行同样的推理，得到这个二叉树的结构如下： 对该二叉树的后序遍历序列为HFDBGECA，所以 选项 A正确。 【知识模块】 数据结构与算法 25 【正确答案】 A 【试题解析】 一般情况下，算法中基本操作重复执行的次数是问题规模 n的某个函数，用
25、 T(n)表示，若有某个辅助函数 f(n)，使得当 n趋近于无穷大时， T(n)f(n)的极限值为不等于零的常数，则称 f(n)是 T(n)的同数量级函数。记作T(n)=O(f(n)，称 O(f(n)为算法的渐进时间复杂度，简称时间复杂度。所以选项 A正确。 【知识模块】 数据结构与算法 26 【正确答案】 D 【试题解析】 假设线性表的长 度为 n，则在最坏情况下，冒泡排序的比较次数为n(n一 1) 2。本题中， n=20，所以 20*19 2=190。所以选项 D正确。 【知识模块】 数据结构与算法 27 【正确答案】 C 【试题解析】 链栈就是没有附加头结点的、运算受限的单链表。栈顶指针
26、就是链表的头指针。如果栈底，指针指向的存储单元中存有 1元素，则当 top=bottom时，栈中的元素个数为 1；如果栈底指针指向的存储单元中没有存元素，则当top=bottom时，栈中的元素个数为 0。所以选项 C正确。 【知识模块】 数据结构与算法 28 【正确答案】 B 【试题解析】 因为任一棵树中，结点总数：总分支数目 +1，所以：27=(0*10+n1*1+2*1+3*4)+1。运算结果 n1=12。其中， n1表示叶子结点，所以选项B正确。 【知识模块】 数据结构与算法 29 【正确答案】 A 【试题解析】 由结点之间的关系 R=(f,a)， (d,b)， (e,d)， (c,e)
27、， (a,c)可以得到，该数据结构为： “fa-c-e-d-b”。由此可知结点 f没有前驱，结点 b没有后继结点，并且其它的结点只有一个前驱结点和一个后继结点，所 以该数据结构为线性结构。所以应选 A选项。 【知识模块】 数据结构与算法 30 【正确答案】 A 【试题解析】 初始化建空队时，令 front=rear=0，当队空时： front=rear；当队满时： front=rear亦成立。因此，只凭等式 front=rear无法判断队空还是队满。有两种方法处理上述问题： 另设一个标志位以区别队列是空还是满； 少用一个元素空间，约定以 “队列头指针 front在队尾指针 rear的下一个位置上 ”作为队列“满 ”状态的标志。即：队空时： front=rear；队满时： (rear+1) maxsize=front。所以选项 A正确。 【知识模块】 数据结构与算法
