1、国家二级 MS Office高级应用机试（数据结构与算法）模拟试卷 12及答案与解析 一、选择题 1 下列叙述中正确的是 （ A）算法复杂度是指算法控制结构的复杂程度 （ B）算法复杂度是指设计算法的难度 （ C）算法的时间复杂度是指设计算法的工作量 （ D）算法的复杂度包括时间复杂度与空间复杂度 2 下列排序方法中，最坏情况下比较次数最少的是 （ A）冒泡排序 （ B）简单选择排序 （ C）直接插入排序 （ D）堆排序 3 下列叙述中正确的是 （ A）栈是一种先进先出的线性表 （ B）队列是一种 后进先出的线性表 （ C）栈与队列都是非线性结构 （ D）栈与队列都是线性结构 4 下列叙述中正
2、确的是 （ A）算法就是程序 （ B）设计算法时只需要考虑数据结构的设计 （ C）设计算法时只需要考虑结果的可靠性 （ D）设计算法时要考虑时间复杂度和空间复杂度 5 设循环队列存储空间为 Q(1： 50)。初始状态为 front=rear=50。经过一系列入队和退队操作后， front=14， rear=19，则该循环队列中的元素个数为 （ A） 46 （ B） 45 （ C） 6 （ D） 5 6 对如下图所示的二叉 树，进行前序遍历的结果为 （ A） DYBEAFCZX （ B） YDEBFZXCA （ C） ABDYECFXZ （ D） ABCDEFXYZ 7 下列叙述中正确的是 （
3、A）线性表链式存储结构的存储空间一般要少于顺序存储结构 （ B）线性表链式存储结构与顺序存储结构的存储空间都是连续的 （ C）线性表链式存储结构的存储空间可以是连续的，也可以是不连续的 （ D）以上都不正确 8 下列叙述中正确的是 （ A）栈与队列都只能顺序存储 （ B）循环队列是队列的顺序存储结构 （ C）循环链表是循环队列的链式存 储结构 （ D）以上三项均错误 9 设循环队列为 Q(1： m)，初始状态为 front=rear=m。现经过一系列的入队与退队运算后， front=rear=1，则该循环队列中的元素个数为 （ A） 1 （ B） 2 （ C） m-1 （ D） 0或 m 10
4、 某二叉树中有 n个叶子结点，则该二叉树中度为 2的结点数为 （ A） n+1 （ B） n-1 （ C） 2n （ D） n 2 11 某二叉树的前序序列为 ABCDEFG，中序序列为 DCBAEFG，则该二叉树的后序序列为 （ A） EFGDCBA （ B） DCBEFGA （ C） BCDGFEA （ D） DCBGFEA 12 下列叙述中正确的是 （ A）所谓算法就是计算方法 （ B）程序可以作为算法的一种描述方法 （ C）算法设计只需考虑得到计算结果 （ D）算法设计可以忽略算法的运算时间 13 设有二叉树如下图所示，则中序序列为 （ A） ABDEGCFH （ B） DBGEAFH
5、C （ C） DGEBHFCA （ D） ABCDEFGH 14 带链的栈与顺序存储的栈相比，其优点是 （ A）入栈与退栈操作方便 （ B）可以省略栈底指针 （ C）入栈操作时不会受栈存储 空间的限制而发生溢出 （ D）所占存储空间相同 15 在长度为 n的顺序表中查找一个元素，假设需要查找的元素一定在表中，并且元素出现在表中每个位置上的可能性是相同的，则在平均情况下需要比较的次数为 （ A） (n+1) 2 （ B） n （ C） 3n 4 （ D） n 4 16 某二叉树的中序遍历序列为 CBADE，后序遍历序列为 CBADE，则前序遍历序列为 （ A） EDABC （ B） CBEDA
6、（ C） CBADE （ D） EDCBA 17 设顺序表的长度为 n。下列算法中，最坏情况下比较次数等于 n(n 1) 2的是 （ A）快速排序 （ B）堆排序 （ C）顺序查找 （ D）寻找最大项 18 某二叉树的后序遍历序列与中序遍历序列相同，均为 ABCDEF，则按层次输出(同一层从左到右 )的序列为 （ A） FEDCBA （ B） CBAFED （ C） DEFCBA （ D） ABCDEF 19 下列排序法中，每经过一次元素的交换会产生新的逆序的是 （ A）快速排序 （ B）冒泡排序 （ C）简单插入排序 （ D）简单选择排序 20 某带链栈初始状态为 top=bottom=NU
7、LL，经过一系列正常的入栈与退 栈操作后， top=10， bottom=20。该栈中的元素个数为 （ A）不确定 （ B） 10 （ C） 1 （ D） 0 21 某二叉树的前序序列为 ABDFHCEG，中序序列为 HFDBACEG。该二叉树的后序序列为 （ A） HFDBGECA （ B） ABCDEFGH （ C） HGFEDCBA （ D） ACEGBDFH 22 带链栈空的条件是 （ A） top=bottom=NULL （ B） top= 1且 bottom=NULL （ C） top=NULL且 bottom-1 （ D） top=bottom= 1 23 下列叙述中正确的是 （
8、 A）带链栈的栈底指针是固定的 （ B）带链栈的栈底指针是随栈的操作而动态变化的 （ C）若带链队列的队头指针与队尾指针相同，则队列为空 （ D）若带链队列的队头指针与队尾指针相同，则队列中至少有一个元素 24 下列结构中属于线性结构链式存储的是 （ A）双向链表 （ B）循环队列 （ C）二叉链表 （ D）二维数组 25 设某棵树的度为 3，其中度为 3、 1、 0的结点个数分别为 3、 4、 15。则该树中总结点数为 （ A） 22 （ B） 30 （ C） 35 （ D）不可能有 这样的树 26 设二叉树的后序序列与中序序列均为 ABCDEFGH，则该二叉树的前序序列为 （ A） HGF
9、EDCBA （ B） ABCDEFGH （ C） ABCDHGFE （ D） DCBAHGFE 27 设循环队列的存储空间为 Q(1： 50)，初始状态为 front=rear=50。经过一系列正常的操作后， front=rear-1。为了在该队列中寻找值最大的元素，在最坏情况下需要的比较次数为 （ A） 0 （ B） 1 （ C） 49 （ D） 50 国家二级 MS Office高级应用机试（数据结构与算法）模拟 试卷 12答案与解析 一、选择题 1 【正确答案】 D 【试题解析】 算法复杂度，即算法在编写成可执行程序后，运行时所需要的资源，资源包括时间资源和内存资源。一个算法的评价主要从
10、时间复杂度和空间复杂度来考虑。算法的时间复杂度是指执行算法所需要的计算工作量。空间复杂度是指算法在计算机内执行时所需存储空间的度量。 【知识模块】 数据结构与算法 2 【正确答案】 D 【试题解析】 冒泡排序、简单选择排序和直接插入排序法在最坏的情况下比较次数为： n(n-1) 2。而堆排序法在最坏的情况下需要比较 的次数为 O(nlog2n)。其中堆排序的比较次数最少。 【知识模块】 数据结构与算法 3 【正确答案】 D 【试题解析】 栈是先进后出，队列是先进先出。栈和队列都是一种线性表，属于线性结构。 【知识模块】 数据结构与算法 4 【正确答案】 D 【试题解析】 算法复杂度，即算法在编
11、写成可执行程序后，运行时所需要的资源，资源包括时间资源和内存资源。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。 【知识模块】 数据结构与算法 5 【正确答案】 D 【试题解析】 在循环队列中，用队尾指针 rear指向队列中的队尾元素，用排头指针 front，指向排头元素的前一个位置。因此，从排头指针 front指向的后一个位置直到队尾指针 rear指向的位置之间所有的元素为队列中的元素。本题中的元素个数是从队列的索引 15位置开始到索引 19位置，共有 5元素。选项 D正确。 【知识模块】 数据结构与算法 6 【正确答案】 C 【试题解析】 二叉
12、树前序遍历的简单描述：若二叉树为空，则结束返回；否则： 访问根结点； 前序遍历左子树 ； 前序遍历右子树。 可见，前序遍历二叉树的过程是一个递归的过程。根据题目中给出的二叉树的结构可知前序遍历的结果是 ABDYECFXZ。 【知识模块】 数据结构与算法 7 【正确答案】 C 【试题解析】 线性表的存储分为顺序存储和链式存储。在顺序存储中，所有元素所占的存储空间是连续的。而在链式存储的方式中，将存储空间的每一个存储结点分为两部分，一部分用于存储数据元素的值，称为数据域；另一部分用于存储下一个元素的存储序号，称为指针域。所以线性表的链式存储方式比顺序存储方式的存储空间要大一些。 【知识模块】 数据
13、结构与算法 8 【正确答案】 B 【试题解析】 栈和队列是按数据的逻辑结构划分是线性结构。数据在内存或磁盘上的存储分为顺序存储结构和链式存储结构。 【知识模块】 数据结构与算法 9 【正确答案】 D 【试题解析】 在循环队列中，用队尾指针 rear指向队列中的队尾元素，用排头指针 front指向排头元素的前一个位置。因此，从排头指针 front指向的后一个位置直到队尾指针 rear指向的位置之间，所有的元素为队列中的元素。 在循环队列动态变化过程中，当循环队列满时有 front=rear，而当循环队列空时也有 front=rear。即在循环队列中，当 front=rear时，不能确定是队列满、
14、还是队列空。当 front=rear=1，要么队列为空，队列中的元素个数为 0，要么队列为满，队列中元素个数为 m。因此选项 D正确。 【知识模块】 数据结构与算法 10 【正确答案】 B 【试题解析】 对于任意一棵二叉树，如果其叶结点数为 N0，而度数为 2的结点总数为 N2，则 N0=N2+1； N2=N0-1。所以如果二叉树中有 n个叶子 结点，则该二叉树中度为 2的结点数为 n-1。因此选项 B正确。 【知识模块】 数据结构与算法 11 【正确答案】 D 【试题解析】 该二叉树的前序序列为 ABCDEFG，中序序列为 DCBAEFG，可知A为根结点，结点 B、 C、 D位于根结点的左子
15、树上，结点 E、 F、 G位于根结点的右子树上，并且结点 B、 C、 D在前序序列和中序序列中顺序颠倒，则说明这三个结点依次位于前一个结点的左子树上；结点 E、 F、 G顺序未变，则说明这三个结点依次位于前一个结点的右子树上。根据以上分析，可以画出这个二叉树的形状如下： 根据该二叉 树，可得出后序遍历序列为： DCBGFEA，选项 D正确。 【知识模块】 数据结构与算法 12 【正确答案】 B 【试题解析】 算法是一组有穷指令集，是解题方案的准确而完整的描述。通俗地说，算法就是计算机解题的过程，重在解题方案的设计，并且不等于计算方法，故选项 A和选项 C不正确。 程序的编制不可能优于算法的设计
16、，但算法的描述可以用程序、伪代码、流程图来描述，故选项 B正确。算法要求执行过程中所需要的基本运算次数和时间最少，即时间复杂度最低，所以选项 D错误。 【知识模块】 数据结构与算法 13 【正确答案】 B 【试题解析】 中序遍历 (LDR)是指首先遍历左子树，然后访问根结点，最后遍历右子树，选项 B正确。 【知识模块】 数据结构与算法 14 【正确答案】 C 【试题解析】 带链的栈与顺序存储的栈相比优点是不受连续存储空间大小的限制，即不需考虑栈满的问题，故选项 C正确。 【知识模块】 数据结构与算法 15 【正确答案】 A 【试题解析】 在一个长度为 n的线性表中顺序查找值为 x的元素时，在等
17、概率情况下查找成功时平均查找长度为 (n+1) 2，所以选项 A正确。 【知识模块】 数据结构与算法 16 【正确答案】 A 【试题解析】 后序遍历次序是 “左右根 ”，中序遍历次序是 “左根右 ”。由定义可知： 后序遍历中最后一个就是树根结点，即 E结点； 在中序遍历中，根结点左边的是左子树集，右边的是右子树集，即 CBAD是根结点 E的左子树集合。问题就会转化为：求后序遍历是 CBAD，中序遍历是 CBAD的子树，方法同上。因为中序遍历中， D结点右边没有结点了，所以 D结点不包含右子树，否则就会被分为 2个子问题。以下是这道题的详细推理过程：步骤 1：由 CBADE得出根结点为 E，由中
18、序遍历可知 CBADE，右子树为空；步骤 2：由 CBAD得出左子树集合的根节点为 D，由中序可知 CBAD，右子树为空：步骤 3：同理，二叉树更新后如下图所示。由下图可得，前序遍历为： EDABC。 【知识模块】 数据结构与算法 17 【正确答案】 A 【试题解析】 假设线性表的长度为 n，则在最坏情况下，快速排序法的最坏情况比较次数也是 n(n1) 2；堆排序，无论是否最坏都是比较 O(nlog2n)次，所以选项 A正确。 【知识模块】 数据结构与算法 18 【正确答案】 A 【试题 解析】 后序遍历次序：左右根；中序遍历次序：左根右。由定义可知： 后序遍历中最后一个是树的根结点，即 F结
19、点； 在中序遍历中，根结点左边的是左子树集，右边的是右子树集，即 ABCDE是根结点 F的左子树集合。问题就会转化为：求后序遍历是 ABCDE，中序遍历是 ABCDE的子树。方法同上，因为中序遍历中， E结点右边没有结点了，所以 E结点不包含右子树，否则就会被分为 2个子问题。以下是这道题的详细推理过程：步骤 ：由 ABCDEF得出根结点为 F，由中序遍历可知： ABCDEF，右子树为空；步骤 2：由 ABCDE得出左子树集 合的根节点为 E，由中序可知： ABCDE，右子树为空；步骤 3：同理，二叉树更新后如下。 所以按层次输出 (同一层从左到右 )的序列为 FEDCBA。 【知识模块】 数
20、据结构与算法 19 【正确答案】 A 【试题解析】 冒泡排序只交换相邻元素，但不是每次移动都产生新的逆序。 简单插入排序的元素移动不会产生新的逆序。 快速排序每一次交换移动都会产生新的逆序，因为当不会有新的逆序产生时，本轮比较结束。 【知识模块】 数据结构与算法 20 【正确答案】 A 【试题解析】 对于链栈而言，使 用了链表来实现栈，链表中的元素存储在不连续的地址。所以当 top=10， bottom=20时，不能确定栈中的元素个数，所以选项 A正确。 【知识模块】 数据结构与算法 21 【正确答案】 A 【试题解析】 由于二叉树的前序序列 ABDFHCEG，可以确定这个二叉树的根结点是 A
21、。再由中序序列 HFDBACEG，可以得到， HFDB为 A的左子树， CEG为A的右子树。同理依次对左子树 HFDB和右子树 CEG进行同样的推理，得到这个二叉树的结构如下，对该二叉树的后序遍历序列为 HFDBGECA，所以选项 A正确。 【知识模块】 数据结构与算法 22 【正确答案】 A 【试题解析】 栈的链式存储结构称为链栈。在链栈中，只会出现栈空和非空两种状态。当栈为空时，有 top=bottom=NULL；当栈非空时， top指向链表的第一个结点 (栈顶 )。所以选项 A正确。 【知识模块】 数据结构与算法 23 【正确答案】 B 【试题解析】 栈 (stack)又名堆栈，它是一种
22、运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、 入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。 带链栈的栈底指针是随栈的操作而动态变化的；若带链队列的队头指针与队尾指针相同，则队列可能为 0也可能为 1。 【知识模块】 数据结构与算法 24 【正确答案】 A 【试题解析】 数据元素之间的关系有两种不同的表示方法：顺序映象和非顺序映象，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构。 数据的
23、存储结构是指数据的逻辑 结构在计算机中的表示。双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱，它的存储方式是线性结构链式。循环队列、二叉链表和二维数组都是顺序存储结构。 【知识模块】 数据结构与算法 25 【正确答案】 B 【试题解析】 本题采用画图法来求出结果。首先先画出包含 3个度为 3的结点；然后再添加 4个度为 1的结点，此时最大度为 0的结点数为 8。根据题目中描述的度为 0的结点数有 15个，这时要在书中添加度为 2的结点，直到度为 0的结点数位 15。画图结束后，不管是什么样的 树，总结点数都是 30。 【知识模块】 数据结构与算法
24、26 【正确答案】 A 【试题解析】 后序遍历中，最后一个字母是根结点，也就是 H是根结点；在中序遍历中，根结点前面的是左子树、后面的是右子树， H后面没有，因此该树没有右子树。同理，可判断出该树是第一个完全的左子树。由此可画出这个二叉树，然后根据二叉树可的前序序列为 HGFEDCBA。 【知识模块】 数据结构与算法 27 【正确答案】 A 【试题解析】 front指定队头位置，删除一个元素就将 front顺时针移动一位；rear指尾指针，指向元素要插入的位置，插入一个元素就将 rear顺时针移动一位；操作后，循环队列的队头指针等于尾指针 -1，说明此时队列已经是空队列，那么就不用比较了。 【知识模块】 数据结构与算法
