1、国家二级 MS Office高级应用机试（数据结构与算法）模拟试卷 25及答案与解析 一、选择题 1 下列叙述中正确的是 ( )。 （ A）算法的复杂度包括时间复杂度与空间复杂度 （ B）算法的复杂度是指算法控制结构的复杂程度 （ C）算法的复杂度是指算法程序中指令的数量 （ D）算法的复杂度是指算法所处理的数据量 2 下列叙述中正确的是 ( )。 （ A）算法的空间复杂度是指算法程序中指令的条数 （ B）压缩数据存储空间不会降低算法的空间复杂度 （ C）算法的空间复杂度与算法所处理的数据存储 空间有关 （ D）算法的空间复杂度是指算法程序控制结构的复杂程度 3 下列叙述中正确的是 ( )。
2、（ A）非线性结构可以为空 （ B）只有一个根结点和一个叶子结点的必定是线性结构 （ C）只有一个根结点的必定是线性结构或二叉树 （ D）没有根结点的一定是非线性结构 4 下列叙述中正确的是 ( )。 （ A）矩阵是非线性结构 （ B）数组是长度固定的线性表 （ C）对线性表只能作插入与删除运算 （ D）线性表中各元素的数据类型可以不同 5 下列叙述中正确的是 ( )。 （ A）能采用 顺序存储的必定是线性结构 （ B）所有的线性结构都可以采用顺序存储结构 （ C）具有两个以上指针的链表必定是非线性结构 （ D）循环队列是队列的链式存储结构 6 设栈的顺序存储空间为 S(1： m)，初始状态为
3、 top=0。现经过一系列正常的入栈与退栈操作后， top=m+1，则栈中的元素个数为 ( )。 （ A） 0 （ B） m （ C）不可能 （ D） m+1 7 设栈的存储空间为 S(1： 50)，初始状态为 top=51。现经过一系列正常的入栈与退栈操作后， top=20，则栈中的元素个数为 ( )。 （ A） 31 （ B） 30 （ C） 21 （ D） 20 8 设有栈 S和队列 Q，初始状态均为空。首先依次将 A， B， C， D， E， F入栈，然后从栈中退出三个元素依次入队，再将 X， Y， Z入栈后，将栈中所有元素退出并依次入队，最后将队列中所有元素退出，则退队元素的顺序为
4、( )。 （ A） DEFXYZABC （ B） FEDZYXCBA （ C） FEDXYZCBA （ D） DEFZYXABC 9 设循环队列的存储空间为 Q(1： 50)，初始状态为 front=rear=50。现经过一系列入队与退队操作后， front=rear=1，此后又正常地插入了两个元素。最后该队列中的元素个数为 ( )。 （ A） 3 （ B） 1 （ C） 2 （ D） 52 10 设循环队列的存储空间为 Q(1： m)，初始状态为空。现经过一系列正常的入队与退队操作后， front=m， rear=m一 1，此后从该循环队列中删除一个元素，则队列中的元素个数为 ( )。 （
5、A） m 1 （ B） m一 2 （ C） 0 （ D） 1 11 在线性表的链式存储结构中，其存储空间一般是不连续的，并且 ( )。 （ A）前件结点的存储序号小于后件结点 的存储序号 （ B）前件结点的存储序号大于后件结点的存储序号 （ C）前件结点的存储序号可以小于也可以大于后件结点的存储序号 （ D）以上三种说法均不正确 12 带链的栈与顺序存储的栈相比，其优点是 ( )。 （ A）入栈与退栈操作方便 （ B）可以省略栈底指针 （ C）入栈操作时不会受栈存储空间的限制而发生溢出 （ D）所占存储空间相同 13 某带链栈的初始状态为 top=bottom=NULL，经过一系列正常的入栈与
6、退栈操作后， top=bottom=20。该栈中的元素个数为 ( )。 （ A） 0 （ B） 1 （ C） 20 （ D）不确定 14 某带链的队列初始状态为 front=rear=NULL。经过一系列正常的入队与退队操作后， front=rear=10。该队列中的元素个数为 ( )。 （ A） 0 （ B） 1 （ C） 1或 0 （ D）不确定 15 下列叙述中错误的是 ( )。 （ A）循环链表中有一个表头结点 （ B）循环链表是循环队列的存储结构 （ C）循环链表的表头指针与循环链表中最后一个结点的指针均指向表头结点 （ D）循环链表实现了空表与非空表运算的统一 16 度为 3的一棵
7、树共有 30个结点，其中度为 3， 1的结点个数分别为 3， 4。则该树中的叶子结点数为 ( )。 （ A） 14 （ B） 15 （ C） 16 （ D）不可能有这样的树 17 深度为 5的完全二叉树的结点数不可能是 ( )。 （ A） 15 （ B） 16 （ C） 17 （ D） 18 18 在具有 2n个结点的完全二叉树中，叶子结点个数为 ( )。 （ A） n （ B） n 1 （ C） n 1 （ D） n 2 19 有二叉树如下图所示： 则前序序列为 ( )。 （ A） ABDEGCFH （ B） DBGEAFHC （ C） DGEBHFCA （ D） ABCDEFGH 20 某
8、二叉树的中序遍历序列为 CBADE，后序遍历序列为 CBEDA，则前序遍历序列为 ( )。 （ A） CBADE （ B） CBEDA （ C） ABCDE （ D） EDCBA 21 某二叉树的前序序列为 ABDFHCEG，中序序列为 HFDBACEG。该二叉树按层次输出 (同一层从左到右 )的序列为 ( )。 （ A） HGFEDCBA （ B） HFDBGECA （ C） ABCDEFGH （ D） ACEGBDFH 22 设非空二叉 树的所有子树中，其左子树上的结点值均小于根结点值，而右子树上的结点值均不小于根结点值，则称该二叉树为排序二叉树。对排序二叉树的遍历结果为有序序列的是 (
9、)。 （ A）前序序列 （ B）中序序列 （ C）后序序列 （ D）前序序列或后序序列 23 在长度为 n的顺序表中查找一个元素，假设需要查找的元素一定在表中，并且元素出现在表中每个位置上的可能性是相同的，则在平均情况下需要比较的次数为( )。 （ A） n 4 （ B） n （ C） 3n 4 （ D） (n+1) 2 24 下列算法中均以比较作 为基本运算，则平均情况与最坏情况下的时间复杂度相同的是 ( )。 （ A）在顺序存储的线性表中寻找最大项 （ B）在顺序存储的线性表中进行顺序查找 （ C）在顺序存储的有序表中进行对分查找 （ D）在链式存储的有序表中进行查找 25 下列叙述中正确
10、的是 ( )。 （ A）二分查找法只适用于顺序存储的有序线性表 （ B）二分查找法适用于任何存储结构的有序线性表 （ C）二分查找法适用于有序循环链表 （ D）二分查找法适用于有序双向链表 26 下列序列中不满足堆条件的是 ( )。 （ A） (98， 95， 93， 94， 89， 90， 76， 80， 55， 49) （ B） (98， 95， 93， 94， 89， 85， 76， 64， 55， 49) （ C） (98， 95， 93， 94， 89， 90， 76， 64， 55， 49) （ D） (98， 95， 93， 96， 89， 85， 76， 64， 55， 49)
11、 27 设顺序表的长度为 16，对该表进行简单插入排序。在最坏情况下需要的比较次数为 ( )。 （ A） 120 （ B） 60 （ C） 30 （ D） 15 国家二级 MS Office高级应用机试（数据结构与算法）模拟试卷 25答案 与解析 一、选择题 1 【正确答案】 A 【试题解析】 算法复杂度是指算法在编写成可执行程序后，运行时所需要的资源，资源包括时间资源和内存资源。算法的复杂度包括时间复杂度与空间复杂度。算法的时间复杂度是指执行算法所需要的计算工作量；算法的空间复杂度是指算法在执行过程中所需要的内存空间。 【知识模块】 数据结构与算法 2 【正确答案】 C 【试题解析】 算法的
12、空间复杂度是指算法在执行过程中所需要的内存空间。算法执行期间所需的存储空间包括 3个部分：输入数据所占的存储空间；程序本身所占的 存储空间；算法执行过程中所需要的额外空间。在许多实际问题中，为了减少算法所占的存储空间，通产采用压缩存储技术，以便尽量减少不必要的额外空间。 【知识模块】 数据结构与算法 3 【正确答案】 A 【试题解析】 如果一个非空的数据结构满足下列两个条件： 有且只有一个根结点； 每一个结点最多有一个前件，也最多有一个后件。则称该数据结构为线性结构。如果一个数据结构不是线性结构，则称之为非线性结构。线性结构和非线性结构都可以是空的数据结构。树只有一个根结点，但不论有几个叶子结
13、点，树都是非线性结构。 【知识模块】 数据结构与算法 4 【正确答案】 B 【试题解析】 矩阵也是线性表，只不过是比较复杂的线性表。线性表中各元素的数据类型必须相同。在线性表中，不仅可以做插入与删除运算，还可以进行查找或对线性表进行排序等操作。 【知识模块】 数据结构与算法 5 【正确答案】 B 【试题解析】 所有的线性结构都可以用数组保存，即都可以采用顺序存储结构。而反过来不可以，完全二叉树也能用数组保存 (按层次依次存放到数据元素中 )，但完全二叉树属于非线性结构。双向链表具有两个以上的指针，但属于线性结构。循环队列是队列的顺序存储结构。 【知识模块】 数据结构与算法 6 【正确答案】 C
14、 【试题解析】 栈为空时，栈顶指针 top=0，经过入栈和退栈运算，指针始终指向栈顶元素。初始状态为 top=0，当栈满 top=m。无法继续入栈， top值不可能为m+1。 【知识模块】 数据结 构与算法 7 【正确答案】 A 【试题解析】 栈的初始状态 top=51，故本栈是 51在栈底，入栈时栈顶指针是减操作 (top=top一 1)，退栈时栈顶指针是加操作 (top=top+1)。当 top=20时，元素存储在 (20： 50)空间中，因此共有 5020+1=31个元素。 【知识模块】 数据结构与算法 8 【正确答案】 B 【试题解析】 栈是一种特殊的线性表，它所有的插入与删除都限定在
15、表的同一端进行。队列是指允许在一端进行插入，而在另一端进行删除的线性表。将 A， B，C， D， E， F入栈 后，栈中元素为 ABCDEF，退出三个元素入队，队列元素为FED，将 X， Y， Z入栈后栈中元素为 ABCXYZ，退栈全部入队后，队列元素为FEDZYXCBA。 【知识模块】 数据结构与算法 9 【正确答案】 C 【试题解析】 由初始状态为 front=rear=50可知此时循环队列为空。经过一系列正常的入队和退队操作，由 front=rear=1可知队列空或者队列满，此后又可以正常地插入了两个元素，说明插入前队列为空，则插入后队列元素个数为 2。 【知识模块】 数据结构与算法 1
16、0 【正确答案 】 B 【试题解析】 在循环队列中，如果 rear一 front 0，则队列中的元素个数为 real一 front个；如果 rear一 front 0，则队列中的元素个数为 rear一 front+m。该题中 m一 1 m，即 reai一 front 0，则该循环队列中的元素个数为 (m一 1)一m+m=m1。此后从该循环队列中删除一个元素，则队列中的元素个数为 m一11=m一 2。 【知识模块】 数据结构与算法 11 【正确答案】 C 【试题解析】 在线性表的链式存储结构中，各数据结点的存储序号是不连续的，并且 各结点在存储空间中的付置关系与逻辑关系也不一致，因此前件结点的存
17、储序号与后件结点的存储序号之间不存在大小关系。 【知识模块】 数据结构与算法 12 【正确答案】 C 【试题解析】 带链的栈就是用一个线性链表来表示的栈，线性链表不受存储空间大小的限制，因此入栈操作时不会受栈存储空间的限制而发生溢出 (不需考虑栈满的问题 )。 【知识模块】 数据结构与算法 13 【正确答案】 B 【试题解析】 带链的栈就是用一个单链表来表示的栈，栈中的每一个元素对应链表中的一个结点。栈为空时，头指针 和尾指针都为 NULL，栈中只有一个元素时，头指针和尾指针都指向这个元素。 【知识模块】 数据结构与算法 14 【正确答案】 B 【试题解析】 带链队列空时，头指针和尾指针都为
18、NULL；队列中只有一个元素时，头指针和尾指针都指向这个元素。 【知识模块】 数据结构与算法 15 【正确答案】 B 【试题解析】 循环链表是指在单链表的第一个结点前增加一个表头结点，队头指针指向表头结点，最后一个结点的指针域的值由 NULL改为指向表头结点。循环链表是线性表的一种链式存储结构，循环队列是队 列的一种顺序存储结构。 【知识模块】 数据结构与算法 16 【正确答案】 B 【试题解析】 设叶子结点数为 n，则度为 2的结点数为 30一 34一 n=23一 n，根据树中的结点数 =树中所有结点的度之和 +1，得 33+2(23一n)+14+0n+1=30，则 n=15。 【知识模块】
19、 数据结构与算法 17 【正确答案】 A 【试题解析】 设完全二叉树的结点数为 n，根据深度为 k的二叉树至多有 2k一 1个结点，再根据完全二叉树的定义可知， 2k 1一 1 n2k一 1。本题中完全二叉树的深度为 55 1一 1 n25一 1， 15 n31。因此，结点数不能为 15。 【知识模块】 数据结构与算法 18 【正确答案】 A 【试题解析】 由二叉树的定义可知，树中必定存在度为 0的结点和度为 2的结点，设度为 0结点有 a个，根据度为 0的结点 (即叶子结点 )总比度为 2的结点多一个，得度为 2的结点有 a一 1个。再根据完全二叉树的定义，度为 1的结点有 0个或 1个，假
20、设度 1结点为 0个， a+0+a一 1=2n，得 2a=2n一 1，由于结点个数必须为整数，假设不成立；当度为 1的结点为 1个时， a+1+a1=2n，得 a=n，即叶子结点个数为 n。 【知识模块】 数据结构与算法 19 【正确答案】 A 【试题解析】 前序遍历首先访问根结点，然后遍历左子树，最后遍历右子树；在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。故本题前序序列是 ABDEGCFH。 中序遍历首先遍历左子树，然后访问跟结点，最后遍历右子树；在遍历左、右子树时，仍然先遍历左子树，然后访问跟结点，最后遍历右子树。故本题的中序序列是 DBGEAFHC。 后序遍历首
21、先遍历左子树，然后遍历右子树，最后访问根结点；在遍历左、右子树时， 仍然先遍历左子树，然后遍历右子树，最后访问根结点。故本题的后序序列是 DGEBHFCA。 【知识模块】 数据结构与算法 20 【正确答案】 C 【试题解析】 二叉树的后序遍历序列为 CBEDA，由于后序遍历最后访问根结点，可以确定该二叉树的根结点是 A。再由中序遍历序列为 CBADE，可以得到子序列 (CB)一定在左子树中，子序列 (DE)一定在右子树中。结点 C、 B在中序序列和后序序列中顺序未变，说明结点 B是结点 C的父结点；结点 D、 E在中序序列和后序序列中顺序相反，说明结点 D是结点 E的父结点。因此该二叉 树的前
22、序遍历序列为 ABCDE。 【知识模块】 数据结构与算法 21 【正确答案】 C 【试题解析】 二叉树的前序序列为 ABDFHCEC，可以确定这个二叉树的根结点是 A；再由中序序列 HFDBACEG可以得到 HFDB为根结点 A的左子树， CEG为根结点 A的右子树，同理依次对左子树 HFDB和右子树 CEG进行同样的推理，得到该二叉树的结构如下： 该二叉树按层次输出 (同一层从左到右 )的序列为 ABCDEFGH。 【知识模块】 数据结构与算法 22 【正确答案】 B 【试题解析】 中序遍历的次序 是先遍历左子树，再遍历根结点，最后遍历右子树。而在排序二叉树中，左子树结点值根结点值 右子树结
23、点值，要使对排序二叉树的遍历结果为有序序列，只能采用中序遍历。 【知识模块】 数据结构与算法 23 【正确答案】 D 【试题解析】 在顺序表中查找，最好情况下第一个元素就是要查找的元素，则比较次数为 1；在最坏情况下，最后一个元素才是要找的元素，则比较次数为 n。则平均比较次数： (1+2+n) n=(n(n+1) 2) n=(n+1) 2。 【知识模块】 数据结构与算法 24 【正确答案 】 A 【试题解析】 寻找最大项，无论如何都要查看所有的数据，与数据原始排列顺序没有多大关系，无所谓最坏情况和最好情况，或者说平均情况与最坏情况下的时间复杂度是相同的。而查找无论是对分查找还是顺序查找，都与
24、要找的数据和原始的数据排列情况有关，最好情况是第 1次查看的一个数据恰好是要找的数据，只需要比较 1次；如果没有找到再查看下一个数据，直到找到为止，最坏情况下是最后一次查看的数据才是要找的，顺序查找和对分查找在最坏情况下比较次数分别是 n和 log2n，平均情况则是 “1最坏情况 ”的平均，因而是不同的。 【知识模块】 数据结构与算法 25 【正确答案】 A 【试题解析】 二分查找法 (又称对分查找法 )只适用于顺序存储的有序表。在此所说的有序表是指线性表的中元素按值非递减排列 (即从小到大，但允许相邻元素值相等 )。 【知识模块】 数据结构与算法 26 【正确答案】 D 【试题解析】 根据堆的定义， n个元素的序列 (h1， h2， h n)，当且仅当 hih2i且hih2i 1时为小顶堆，当且仅当 hih2i且 hih2i 1时为大顶堆。 D项中， h2=95，h4=96， h2 h4，但 h5=89， h2 h5，不满足小顶堆和大顶堆条件。 【知识模块】 数据结构与算法 27 【正确答案】 A 【试题解析】 简单插入排序在最坏情况下，即初始排序序列是逆序的情况下，比较次数为 n(n一 1) 2，移动次数为 n(n1) 2。本题中 n=16， 16(161)2=815=120。 【知识模块】 数据结构与算法
