1、国家二级 MS Office高级应用机试（数据结构与算法）模拟试卷 15及答案与解析 一、选择题 1 下列叙述中正确的是 （ A）顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的 （ B）顺序存储结构只针对线性结构，链式存储结构只针对非线性结构 （ C）顺序存储结构能存储有序表，链式存储结构不能存储有序表 （ D）链式存储结构比顺序存储结构节省存储空间 2 下列数据结构中，属于非线性结构的是 （ A）循环队列 （ B）带链队列 （ C）二叉树 （ D）带链栈 3 下列关于栈叙述 正确的是 （ A）栈顶元素最先能被删除 （ B）栈顶元素最后才能被删除 （ C）栈底元素永远不能
2、被删除 （ D）以上三种说法都不对 4 下列各组的排序方法中，最坏情况下比较次数相同的是 （ A）冒泡排序与快速排序 （ B）简单插入排序与希尔排序 （ C）堆排序与希尔排序 （ D）快速排序与希尔排序 5 下列关于栈的叙述中，正确的是 （ A）栈底元素一定是最后入栈的元素 （ B）栈项元素一定是最先入栈的元素 （ C）栈操作遵循先进后出的原则 （ D）以上三种说法都不对 6 下列叙述中正确的是 （ A）循环队列中的元素个数随队头指针与队尾指针的变化而动态变化 （ B）循环队列中的元素个数随队头指针的变化而动态变化 （ C）循环队列中的元素个数随队尾指针的变化而动态变化 （ D）循环队列中的元
3、素个数不会变化 7 下列叙述中正确的是 （ A）有且只有一个根结点的数据结构一定是线性结构 （ B）每一个结点最多有一个前件也最多有一个后件的数据结构一定是线性结构 （ C）有且只有一个根结点的数据结构一定是非线性结构 （ D）有且只有一个根结点的数据结构可能是线性结构，也可能是非线性结构 8 为了对有序表 进行对分查找，则要求有序表 （ A）只能顺序存储 （ B）只能链式存储 （ C）可以顺序存储也可以链式存储 （ D）任何存储方式 9 设栈的顺序存储空间为 S(1： m)，初始状态为 top=m+1。现经过一系列入栈与退栈运算后， top=20，则当前栈中的元素个数为 （ A） 30 （
4、B） 20 （ C） m-19 （ D） m-20 10 某二叉树的前序序列为 ABCDEFG，中序序列为 DCBAEFG，则该二叉树的深度 (根结点在第 1层 )为 （ A） 2 （ B） 3 （ C） 4 （ D） 5 11 设数据元素的集 合 D=1， 2， 3， 4， 5，则满足下列关系 R的数据结构中为线性结构的是 （ A） R= (1， 2)， (3， 4)， (5， 1) （ B） R= (1， 3)， (4， 1)， (3， 2)， (5， 4) （ C） R= (1， 2)， (2,3)， (4， 5) （ D） R= (1， 3)， (2,4)， (3,5) 12 有二叉树
5、如下图所示，则前序序列为 （ A） ABDEGCFH （ B） DBGEAFHC （ C） DGEBHFCA （ D） ABCDEFGH 13 下列叙述中正确的是 （ A）所谓有序表是指在顺序存储空间内连 续存放的元素序列 （ B）有序表只能顺序存储在连续的存储空间内 （ C）有序表可以用链接存储方式存储在不连续的存储空间内 （ D）任何存储方式的有序表均能采用二分法进行查找 14 下列各排序法中，最坏情况下的时间复杂度最低的是 （ A）堆排序 （ B）快速排序 （ C）希尔排序 （ D）冒泡排序 15 下列算法中均以比较作为基本运算，则平均情况与最坏情况下的时间复杂度相同的是 （ A）在顺序
6、存储的线性表中寻找最大项 （ B）在顺序存储的线性表中进行顺序查找 （ C）在顺序存储的有序表中进行对分查找 （ D）在链式存储的有序表中进行查找 16 设顺序表的长度为 n。下列排序方法中，最坏情况下比较次数小于 n(n-1) 2的是 （ A）堆排序 （ B）快速排序 （ C）简单插入排序 （ D）冒泡排序 17 设一棵树的度为 4，其中度为 4， 3， 2， 1的结点个数分别为 2， 3， 3， 0。则该棵树中的叶子结点数为 （ A） 16 （ B） 15 （ C） 17 （ D）不可能有这样的树 18 下列排序法中，最坏情况下时间复杂度最小的是 （ A）堆排序 （ B）快速排序 （ C）
7、希尔排序 （ D）冒泡排序 19 下列叙述中正确的是 （ A）有的二叉树也能用顺序存储结构表示 （ B）有两个指针域的链表就是二叉链表 （ C）多重链表一定是非线性结构 （ D）顺序存储结构一定是线性结构 20 某完全二叉树按层次输出 (同一层从左到右 )的序列为 ABCDEFGH。该完全二叉树的中序序列为 （ A） HDBEAFCG （ B） HDEBFGCA （ C） ABDHECFG （ D） ABCDEFGH 21 在带链栈中，经过一系列正常的操作后，如果 top=bottom，则栈中的元素个数为 （ A） 1 （ B） 0 （ C） 0或 1 （ D）栈满 22 设二叉树共有 375
8、个结点，其中度为 2的结点有 187个。则度为 1的结点个数是 （ A） 0 （ B） 1 （ C） 188 （ D）不可能有这样的二叉树 23 下列叙述中正确的是 （ A）循环队列是线性结构 （ B）循环队列是线性逻辑结构 （ C）循环队列是链式存储结构 （ D）循环队列是非线性存储结构 24 在长度为 97的顺序有序表中作二分查找，最多需要的比较次数为 （ A） 7 （ B） 96 （ C） 48 （ D） 6 25 线性表的长度为 n。在最坏情况下，比较次数为 n-1的算法是 （ A）顺序查找 （ B）有序表的插入 （ C）寻找最大项 （ D）同时寻找最大项与最小项 26 设二叉树的前序
9、序列为 ABDEGHCFIJ，中序序列为 DBGEHACIFJ。则按层次输出 (从上到下，同一层从左到右 )的序列为 （ A） ABCDEFGHIJ （ B） DGHEBIJFCA （ C） JIHGFEDCBA （ D） GHIJDEFBCA 27 下列结构中为非线性结构的是 （ A）树 （ B）向量 （ C）二维表 （ D）矩阵 28 设二叉树的后序序列为 DGHEBIJFCA，中序序列为 DBGEHACIFJ。则前序序列为 （ A） ABDEGHCFIJ （ B） JIHGFEDCBA （ C） GHIJDEFBCA （ D） ABCDEFGHIJ 国家二级 MS Office高级应用机
10、试（数据结构与算法）模拟试卷 15答案与解析 一、选择题 1 【正确答案】 A 【试题解析】 顺序存储方式主要用于线性的数据结构，它把逻辑上相邻的数据元素存储在物理上相邻的存储单元里，结点之间的关系由存储单元的邻接关系来体现。而链式存储结构的存储空间不一定是连续的。 【知识模块】 数据结构与算法 2 【正 确答案】 C 【试题解析】 根据数据结构中各数据元素之间的前后件关系的复杂程度，一般将数据结构分为两大类：线性结构和非线性结构。循环队列、带链队列和带链栈都是线性结构，而二叉树是非线性结构。 【知识模块】 数据结构与算法 3 【正确答案】 A 【试题解析】 栈是先进后出的线性表，栈顶的元素最
11、先被删除，栈底的元素最后被删除。 【知识模块】 数据结构与算法 4 【正确答案】 A 【试题解析】 最坏情况下冒泡排序需要比较 n(n-1) 2次，即序列逆序的情况。简单插入排序，无论是否 最坏情况，都需要 n(n-1) 2次。直接插入排序，最坏情况需要比较次 n(n-1) 2次。堆排序，无论是否最坏都要比较 O(nlog2n)次。快速排序，最坏情况退化为冒泡排序，需要比较 n(n-1) 2次。在最坏情况下，希尔排序所需要的比较次数为 O(n1 5)。选项 A正确。 【知识模块】 数据结构与算法 5 【正确答案】 C 【试题解析】 栈是限定只能在表的一端进行插入和删除操作的线性表，必须按“后进
12、先出 ”的规则操作元素。 【知识模块】 数据结构与算法 6 【正确答案】 A 【试题 解析】 所谓循环结构就是将队列存储空间的最后一个位置绕到第一个位置上，形成逻辑上的环状空间，循环使用。在循环队列中，用队尾指针 rear指向队列中的队尾元素，用队头指针 front指向队头元素的前一个位置，因此，队列中的元素数等于从队头指针 front指向的后一个位置与队尾指针 rear指向位置之间的元素数量。 【知识模块】 数据结构与算法 7 【正确答案】 D 【试题解析】 根据数据结构中各数据元素之间的前后件关系的复杂程度，一般将数据结构分这两大类型：线性结构与非线性结构。 如果一个非空的数据结 构满足两
13、个条件： 有且只有一个根结点； 每一个结点最多有一个前件，也最多有一个后件。称该数据结构为线性结构，又称为线性表。对于这个题目来说，有且只有一个根结点的数据结构可能是线性结构，也可能是非线性结构。具有一个根结点的树就是一个非线性结构，选项 D正确。 【知识模块】 数据结构与算法 8 【正确答案】 A 【试题解析】 有序表的对分查找条件是有序表为顺序存储。 顺序查找： 如果线性表为无序表 (即表中元素的排序是无序的 )，则无论是顺序存储结构还是链式存储结构，都只能用顺序查找； 即使是 有序线性表，如果采用链式存储结构，也只能用顺序查找。 分块查找 (又称索引川页序查找 )：分块有序表结构分为两部
14、分， 线性表本身采用顺序存储结构； 在建立一一个索引表，在索引表中，对线性表的每个子表建立一个索引结点，每个结点包括两个域：一是数据域，用于存放对应子表中的最大元素值；二是指针域，用于指示对应子表的第一个元素在整个线性表中的序号。显然索引表关于数据域是有序的。 【知识模块】 数据结构与算法 9 【正确答案】 C 【试题解析】 根据题意，栈空间如图所示： 栈是向上增长的，每次压入一个元素，栈的 TOP指针向上移动一位。 当压入第一个元素时， TOP指针指向 m+1-1=m；当压入第二个元素时， TOP指针指向 m+1-2=m-1； ；以此类推，当压入第 N个元素时， TOP指针指向 m+1-N=
15、20；则 N=m+1-20=m-19。因此选项 C正确。 【知识模块】 数据结构与算法 10 【正确答案】 C 【试题解析】 该二叉树的前序序列为 ABCDEFG，中序序列为 DCBAEFG，可知A为根结点，结点 B、 C、 D位于根结点的左子树上，结点 E、 F、 G位于根结点的右子树上 ；并且结点 B、 C、 D在前序序列和中序序列中顺序颠倒，则说明这三个结点依次位于前一个结点的左子树上；结点 E、 F、 G顺序未变，则说明这三个结点依次位于前一个结点的右子树上。所以得到的二叉树为，所以这个二叉树的深度为 4。选项 C为正确答案。 【知识模块】 数据结构与算法 11 【正确答案】 B 【试
16、题解析】 把每个答案中的第一个元素集合取出来，例如 A： (1， 2)，先写下来就是 12，然后看后面的 (3， 4)，在 (1， 2)中找不到前驱和后继，只能和 (1， 2)暂时先并列，然后是 (5， 1)，这里我们已经写过 12了，那么 5在 1前面就是 512，但是 34要单排，所以 A就是两个根节点 3和 5，两个顺序是 512,34。同理选项 B是541， 32；选项 C是： 123和 45；选项 D是 135,24所以选项 B正确。 【知识模块】 数据结构与算法 12 【正确答案】 A 【试题解析】 前序遍历首先访问根结点然后遍历左子树，最后遍历右子树；在遍历左、右子树时，仍然先访
17、问根结点，然后遍历左子树，最后遍历右子树。故选项 A正确，选项 B为中序遍历，选项 C为后序遍历，选项 D不正确。 【知识模块】 数据结构与算法 13 【 正确答案】 C 【试题解析】 有序表可以用顺序存储空间内连续存放的元素序列来实现，也可以用链接存储方式存储在不连续的存储空间内，己达到逻辑上连续，存储空间上不一定连续的效果。二分法进行查找只适用于顺序存储的有序表。故选项 C正确。 【知识模块】 数据结构与算法 14 【正确答案】 A 【试题解析】 堆排序法，最坏情况需要 O(nlog2n)次比较。相比以上几种 “除希尔排序法外 ”，堆排序法的时间复杂度最小，故选项 A正确。 【知识模块】
18、数据结构与算法 15 【正确答案】 A 【试 题解析】 最坏情况下的时间复杂度称为最坏时间复杂度。一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度。 最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，这就保证了算法的运行时间不会比任何情况更长。平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间。 在输入不同的情况下算法的运行时间复杂度可能会发生变化。平均时间复杂度给出了算法的期望运行时间，有助于算法好坏的评价以及在不同算法之间比较时有一个统一标准。 在顺序存储的线性表中寻找最大项， 其平均情况与最坏情况下的时间复杂度都是 n 2。 【知识模块】
19、数据结构与算法 16 【正确答案】 A 【试题解析】 假设线性表的长度为 n，则在最坏情况下，冒泡排序需要经过 n 2遍的从前往后扫描和 n 2遍的从后往前扫描，需要比较次数为 n(n-1) 2。快速排序法的最坏情况比较次数也是 n(n-1) 2。 简单插入排序，无论是否最坏都需要n(n-1) 2比较。堆排序，无论是否最坏都需要比较 O(nlog2n)次。所以选项 A正确。 【知识模块】 数据结构与算法 17 【正确答案】 A 【试题解 析】 因为任一棵树中，结点总数 =总分支数目 +1，所以：n0+2+3+3+0=(n0*0+4*2+3*3+2*3+1*0)+1。计算得出 n0=16。其中，
20、 n0表示叶子结点，所以选项 A正确。 【知识模块】 数据结构与算法 18 【正确答案】 A 【试题解析】 假设线性表的长度为 n，则在最坏情况下，冒泡排序需要经过 n 2遍的从前往后扫描和 n 2遍的从后往前扫描，需要比较次数为 n(n-1) 2。快速排序法的最坏情况比较次数也是 n(n-1) 2。 简单插入排序，无论是否最坏都需要n(n-1) 2比较。堆排 序，无论是否最坏情况都是比较 O(nlog2n)次。所以选项 A正确。 【知识模块】 数据结构与算法 19 【正确答案】 A 【试题解析】 完全二叉树如果 “根 ”从 1开始编号，则第 i结点的左孩了编号为2i，右孩子为 2i+1，双亲
21、编号为 (i 2)下取整，空间紧密，适合顺序存储结构。所以选项 A正确。 小提示：取整是指取不超过实数 x的最大整数，称为 x的整数部分。上取整就是对实数取大于当前实数的第一个整数；下取整就是对当前实数去掉小数取整。 【知识模块】 数据结构与算法 20 【正确答案】 A 【试题解析】 完全二叉树的特点是除最后一层外，每一层上的节点数均达到最大值；在最后一层上只缺少右边的若干结点。根据上述特点，完全二叉树按层次输出 (同一层从左到右 )的序列为 ABCDEFGH。可以得到其结构如下，所以此完全二叉树的中序序列是 HDBEAFCG。所以选项 A正确。 【知识模块】 数据结构与算法 21 【正确答案
22、】 C 【试题解析】 链栈就是没有附加头结点的、运算受限的单链表。栈顶指针就是链表的头指针。如果栈底指针指向的存储单元中存有 1元素，则当 top=bottom时，栈中的元素个数 为 1；如果栈底指针指向的存储单元中没有存元素，则当top=bottom时，栈中的元素个数为 0。所以选项 C正确。 【知识模块】 数据结构与算法 22 【正确答案】 A 【试题解析】 二叉树的每个结点至多只有二棵子树 (不存在度大于 2的结点 )，二叉树的子树有左右之分，次序不能颠倒。二叉树的第 ii-1层至多有 2个结点；深度为 k的二叉树至多有 2k-1个结点；对任何一棵二叉树 T，如果其终端结点数为n0，度为
23、 2的结点数为 n2，则 n0=n1+1。本题中，度为 2的结点有 187个，叶子结点应该有 187+1=188个 ，度为 1的结点个数 =375 187188=0。 【知识模块】 数据结构与算法 23 【正确答案】 A 【试题解析】 为充分利用向量空间，克服 “假溢出 ”现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列 (Circular Queue)。线性结构是一个有序数据元素的集合。常用的线性结构有：线性表，栈，队列，双队列，数组，串。常见的非线性结构有：二维数组，多维数组，广义表，树 (二叉树等 )，图。 【知识模块】 数据结构与算
24、法 24 【正 确答案】 A 【试题解析】 二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。最多比较次数的计算方式： k=log2n。其中 n代表长度， k为比较次数。本题中可以计算出 k=7。 【知识模块】 数据结构与算法 25 【正确答案】 C 【试题解析】 寻找最大项算法是，首先取出第一个数作为最大数，然后和后面的所有项进行比较查找。因此，比较次数为 n-1。 【知识模块】 数据结构与算法 26 【正确答案】 A 【试题解析】 前序遍 历中，第一个字母是根结点，也就是 A是根结点；在中序遍历中，根结点前面的是左子树、后面的是右子
25、树。前序中， B在 A的后面，中序中在左子树中，可知 B为 A的左结点。中序中 D在 B的前面，前序中在 B的后面，可知 D为 B的左结点， GEH为 B的右子树。 前序中顺序为 EGH，由此可知， E为 B的右结点， G为 E的左结点、 H为 E的右结点。 右子树中，前序中 C在最前，因为右子树根结点，也就是 A的右结点，根据前序中的子树 FIJ和中序中的 IFJ子树可知 F为 C的右结点， I为 F的左结点、 J为F的右结点。由此可画出这个二叉树，然 后根据二叉树，可知按层次输出 (从上到下，同一层从左到右 )的序列为： ABCDEFGHIJ。 【知识模块】 数据结构与算法 27 【正确答
26、案】 A 【试题解析】 线性结构是一个有序数据元素的集合。常用的线性结构有：线性表，栈，队列，双队列，数组，串。常见的非线性结构有：二维数组，多维数组，广义表，树 (二叉树等 )，图。 【知识模块】 数据结构与算法 28 【正确答案】 A 【试题解析】 后序遍历中，最后一个字母是根结点，也就是 A是根结点；在中序遍历中，根结点前面的是左子树、后面的是 右子树。后序中 C在 A前面、中序中 C在 A的后面，说明 C是 A的右结点；后序中 F在 C的前面、中序中在 C后面，且后序和中序中， I均在 F前面由此可确定， I为 F的左结点， F为 C的右结点。同 C理 J为 F的右结点。后序中 B为左子树的根结点，因此 B为 A的左结点，以此划分，在中序中 B前面的 D为左结点，后面的 GEH为右子树，后序中E在最后，应为剩下 3个结点的根结点，也就是 B的右子树，再根据中序中的顺序，可得出 G为 E的左结点， H为 E的右结点。由此可画出这个二叉树，然后根据二叉树可的前序序列为 ABDEGHCFIJ。 【知识模块】 数据结构与算法
