1、国家二级 MS Office高级应用机试（数据结构与算法）模拟试卷 18及答案与解析 一、选择题 1 下列数据结构中属于非线性结构的是 ( )。 （ A）循环队列 （ B）带链队列 （ C）二叉树 （ D）带链栈 2 下列叙述中正确的是 ( )。 （ A）线性表的链式存储结构与顺序存储结构所需要的存储空间是相同的 （ B）线性表的链式存储结构所需要的存储结构一般多于顺序存储结构 （ C）线性表的链式存储结构所需要的存储空间一般少于顺序存储结构 （ D）线性表的链式存储结构所需要的存储空间与顺序 存储结构没有任何关系 3 下面叙述中正确的是 ( )。 （ A）循环队列属于队列的链式存储结构 （
2、B）双向链表是二叉树的链式存储结构 （ C）非线性结构只能采用链式存储结构 （ D）有的非线性结构也可以采用顺序存储结构 4 下列链表中，其逻辑结构属于非线性结构的是 ( )。 （ A）二叉链表 （ B）循环链表 （ C）双向链表 （ D）带链的栈 5 下列关于线性表和链表的比较，叙述错误的是 ( )。 （ A）顺序表随机存取表中的任意节点，无须额外的指针域 （ B）顺序表插入和删除运 算效率低；存储空间不便扩充；不能动态分配存储空间 （ C）链表的插入和删除运算不需要移动元素；存储空间易于扩充且可动态分配 （ D）链表的存储密度和顺序表一样 6 某系统总体结构图如下图所示： 该系统的深度是
3、( )。 （ A） 6 （ B） 2 （ C） 3 （ D） 2 7 下列关于二叉树的叙述中正确的是 ( )。 （ A）叶子节点总是比度为 2的节点少一个 （ B）叶子节点总是比度为 2的节点多一个 （ C）叶子节点数是度为 2的节点数的 2倍 （ D）度为 2的节点数是度为 1的节点数的 2倍 8 下列数据结 构哪个是非线性结构 ?( ) （ A）栈 （ B）队列 （ C）二叉树 （ D）链表 9 某二叉树度为 2的节点数是 n，那么度为 O的节点数是 ( )。 （ A） n （ B） n+1 （ C） n-1 （ D） 2n 10 某二叉树有 5个度为 2的节点，则该二叉树的叶子节点数是
4、( )。 （ A） 10 （ B） 8 （ C） 6 （ D） 4 11 一棵二叉树共有 25个节点，其中 5个是叶子节点，那么度为 1的节点数是( )。 （ A） 16 （ B） 10 （ C） 6 （ D） 4 12 某二叉树共 有 7个节点，其中叶子节点只有 1个，则该二叉树的深度为 ( )。 （ A） 3 （ B） 4 （ C） 6 （ D） 7 13 某二叉树有 10个度为 2的节点，那么该二叉树叶子节点数是 ( )。 （ A） 10 （ B） 11 （ C） 20 （ D）不确定 14 某二叉树有 30个度为 2的节点， 40个度为 1的节点，那么这个二叉树总的节点数是 ( )。
5、（ A） 70 （ B） 130 （ C） 101 （ D） 99 15 设树 T的深度是 4，其中度为 1， 2， 3， 4的节点是分别为 4， 2， 1， 1。则 T中的叶子节点 数是 ( )。 （ A） 5 （ B） 6 （ C） 7 （ D） 8 16 下列关于树的说法中，正确的是 ( )。 （ A）每个节点可以有多于一个父节点 （ B）树可以有多个根节点 （ C）满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树 （ D）只有根节点的不是树 17 下列关于二叉树叙述正确的是 ( )。 （ A）二叉树至少有一个节点 （ B）二叉树可以为空 （ C）二叉树的左右子树顺序可以颠倒 （ D
6、）二叉树的左右子树可以相交 18 下列关于二叉树性质说法错误的是 ( )。 （ A）一个非空二叉树的第 k层上最多有 2k-1个节点 （ B）深度为 m的满二叉树中有 2m-1个节点 （ C）对于任何一个二叉树，度为 0的节点数总是比度为 2的节点数多 1个 （ D）深度为 m的完全二叉树节点个数肯定小于 2m-1 19 下列关于二叉树描述错误的是 ( )。 （ A）具有 n个节点的二叉树的深度至少为 log2n+1，其中 log2n表示取 log2n的整数部分 （ B）具有 n个节点的完全二叉树的深度是 log2n+1 （ C）具有 n个节点的满二叉树的深度是 log2n （ D）一个二叉
7、树有 8个节点，那么其深度至少为 4，至多为 8 20 二叉树的遍历不包括 ( )。 （ A）前序遍历 （ B）中序遍历 （ C）倒序遍历 （ D）后序遍历 21 如下二叉树： 那么它的前序遍历结果是 ( )。 （ A） ABDCE （ B） ACBED （ C） BDAEC （ D） DBECA 22 上题中二叉树的后序遍历结果是 ( )。 （ A） EDCBA （ B） ABDEC （ C） CDADB （ D） DBECA 23 一个二叉树的前序遍历结果是 ACFEKDBHJI，中序遍历结果是FCKEABDHJI，那么后序遍历结果是 ( )。 （ A） IJHBDKEFCA （ B） F
8、KECBIJHDA （ C） EKCFIJHDBA （ D） ABDHJIFCKE 24 下列关于二叉树遍历的叙述中错误的是 ( )。 （ A）已知二叉树的前序遍历结果和中序遍历结果，则可以唯一确定这个二叉树 （ B）已知二叉树的后序遍历结果和中序遍历结果，则可以唯一确定这个二叉树 （ C）已知二叉树的前序遍历结果和后序遍历结果，则可以唯一确定这个二叉树 （ D）已知二叉树的前序遍历结果和后序遍历结果，不可以唯一确定这个 二叉树 25 二叉树的遍历用到的算法思想是 ( )。 （ A）分治 （ B）回溯 （ C）贪心 （ D）动态规划 26 下列关于时间复杂度说法错误的是 ( )。 （ A）时间
9、复杂度是指执行算法所需要的计算工作量，它是问题规模的函数 （ B）时间复杂度一般采用 O(n)表示，其中 n是问题规模 （ C）时间复杂度 O(1)，表示该算法只需进行 1次运算 （ D）时间复杂度一般用 n的最高项表示，忽略低阶项、常数项和最高项前面的系数 27 下列关于顺序查找描述错误的是 ( )。 （ A）在最好情况 下，查找次数是 1 （ B）在最坏情况下，查找次数是 n （ C）平均情况下，查找次数是 n 2 （ D）查找的时间复杂度是 O(n) 28 下列叙述正确的是 ( )。 （ A）采用链式存储的有序表可以用二分法查找 （ B）二分法的时机复杂度是 O(log10n) （ C）
10、顺序存储的线性表，可以用二分法查找 （ D）只有顺序存储的有序表才能用二分法查找 国家二级 MS Office高级应用机试（数据结构与算法）模拟试卷 18答案与解析 一、选择题 1 【正确答案】 C 【试题解析】 二叉树属于非线性 结构，因为二叉树的节点最多有 2个后继节点。 【知识模块】 数据结构与算法 2 【正确答案】 B 【试题解析】 链式存储结构需要额外的指针域，比顺序存储结构存储密度低，浪费空间。 【知识模块】 数据结构与算法 3 【正确答案】 D 【试题解析】 顺序存储方式不仅能用于存储线性结构，还能用来存储非线性结构，如完全二叉树属于非线性结构，但是却适合使用顺序存储方式。二叉树
11、的链式存储结构是二叉链表。 【知识模块】 数据结构与算法 4 【正确答案】 A 【试题解析】 二叉 链表作为二叉树的存储结构，链表中节点的两个链域分别指向该节点的第一个孩子节点和第一个孩子的下一个兄弟节点，有 2个后继节点，属于非线性结构。 【知识模块】 数据结构与算法 5 【正确答案】 D 【试题解析】 链表需要指针域表示数据元素直接的逻辑关系；存储密度比顺序表要低。 【知识模块】 数据结构与算法 6 【正确答案】 C 【试题解析】 定义一棵树的根节点所在的层次为 1，其他节点所在的层次等于它的父节点所在层次加 1，树的最大层次称为树的深度。题目中树的层次为 3，故深度为 3。 【知识模块】
12、 数据结构与算法 7 【正确答案】 B 【试题解析】 二叉树有一个性质：对于任何一棵二叉树而言，度为 0的节点 (叶子节点 )总是比度为 2的节点多一个。 【知识模块】 数据结构与算法 8 【正确答案】 C 【试题解析】 有且只有一个根节点，且每一个节点最多只有一个前驱和最多只有一个后继，这种被称为线性结构，否则是非线性结构。栈、队列和链表都符合线性结构，二叉树是一种简单的非线性结构。 【知识模块】 数据结构与算法 9 【正确答案】 B 【试题解析】 根据二 叉树的性质：对于任何一棵二叉树而言，度为 O的节点总是比度为 2的节点多一个。题目中度为 2的节点数为 n，那么度为 O的节点数就是 n
13、+1个。 【知识模块】 数据结构与算法 10 【正确答案】 C 【试题解析】 根据二叉树的性质：对于任何一棵二叉树而言，叶子节点总是比度为 2的节点多一个。题目中度为 2的节点有 5个，那么叶子节点数就是 5+16个。 【知识模块】 数据结构与算法 11 【正确答案】 A 【试题解析】 二叉树有一个性质：对于任何一棵二叉树而言，度为 0的节点 (叶子节点 )总是比度为 2的节点多一个。叶子节点是 5个，那么度为 2的节点数是4， 25-5-4=16，故答案是 A。 【知识模块】 数据结构与算法 12 【正确答案】 D 【试题解析】 二叉树的叶子节点比度为 2的节点数多 1，叶子节点数是 1，那
14、么度为 2的节点数是 0，度为 1的节点数是 7-1-0=6，这样我们知道这个二叉树除了最后一个叶子节点，其余的节点都只有一个子节点，这个二叉树的深度就是 7。 【知识模块】 数据结构与算法 13 【正确答案】 B 【试题解析】 二叉树有一个性质：对于任何一棵二叉树而言，度为 0的节点 (叶子节点 )总是比度为 2的节点多一个。因此这棵二叉树的叶子节点数为 10+1=11。 【知识模块】 数据结构与算法 14 【正确答案】 C 【试题解析】 二叉树有一个性质：对于任何一棵二叉树而言，度为 0的节点 (叶子节点 )总是比度为 2的节点多一个。度为 2的节点数是 30，那么度为 0的节点数就是 3
15、1， 30+31+40=101。 【知识模块】 数据结构与算法 15 【正确答案】 D 【试题解析】 树中每个节点和子节点连接的线段称为该节点的边，一个节点的度为 n，则该节点的边数也是 n，度为 0的节点边数是 0，度为 1的节点边数是 1，度为 2的节点边数是 2，依此类推，一个树的总边数等于该树的节点数和其度数乘积，然后求和。一个树的边数总是比节点数少 1个。题目中边数总和为41+22+13+14=15，那么节点数总和为 15+1=16，而度为 1、 2、 3、 4的节点数之和是 4+2+1+1=8，则叶子节点数为 16-8=8。 【知识模块】 数据结构与算法 16 【正确答案】 C 【
16、试题解析】 树最多只有一个根节点，且每个节点最多只有一个父节点。根节点是没有父节点的，只有根节点的也是树 。满二叉树是指除最后一层外，每一层上的节点数都有 2个子节点的二叉树。完全二叉树是指除最后一层外。每一层上的节点数都达到最大值，在最后一层上只缺少右边的若干节点。满二叉树顾名思义就是整个树除了叶子节点的其他节点都是满的，而完全二叉树是从满二叉树移除了一些叶子节点，且移除顺序是从右往左的。满二叉树一定是完全二叉树，但是反过来不一定成立。 【知识模块】 数据结构与算法 17 【正确答案】 B 【试题解析】 二叉树是一个有限的节点集合，该集合或者为空，或者由一个根节点及其两棵互不相交的左右二叉子
17、树组 成，二叉树的子树有左右之分，次序不能颠倒。因此答案是 B。 【知识模块】 数据结构与算法 18 【正确答案】 D 【试题解析】 ABC三个选项都是二叉树的性质。完全二叉树的节点个数小于等于满二叉树中的节点数。 【知识模块】 数据结构与算法 19 【正确答案】 C 【试题解析】 满二叉树的深度是 log2n+1。 【知识模块】 数据结构与算法 20 【正确答案】 C 【试题解析】 二叉树遍历顺序有前序遍历、中序遍历和后序遍历。 【知识模块】 数据结构与算法 21 【正确答案】 A 【试题解析】 前序遍历是先访问根节点，然后前序遍历左子树，最后前序遍历右子树。前序遍历结果是 ABDCE。 【
18、知识模块】 数据结构与算法 22 【正确答案】 D 【试题解析】 后序遍历是先后序遍历左子树，然后后序遍历右子树，最后访问根节点。左子树的后序遍历结果是 DB，右子树后序遍历结果是 EC，整个树的后序遍历是 DBECA。 【知识模块】 数据结构与算法 23 【正确答案】 B 【试题解析】 二叉树有三种遍历顺序，分别为前序遍历、中序遍历和后序遍历。前 序遍历顺序：访问根节点。遍历左子树，遍历右子树，对左右子树按前面 3个步骤继续遍历。中序遍历顺序：遍历左子树，访问根节点，遍历右子树。对左右子树按前面 3个步骤继续遍历。后序遍历顺序：遍历左子树，遍历右子树，访问根节点，对左右子树按前面 3个步骤继
19、续遍历。不管哪种方式遍历，左子树先遍历，右子树后遣历，只是根节点的访问时机不同，对左右子树的遍历采用同样的规则，这在计算机中称为递归。题目中根据前序遍历结果知道二叉树的根节点是A，根据中序遍历结果知道 FCKE是 A的左子树的节点， BDHJI是 A的右子树的节点， A的左子树 FCKE在前序遍历结果中是 CFEK，我们得知 C是 A的左子树的根节点， F是 C的左子树节点， KE是 C的右子树节点，而 KE在前序遍历结果中是 EK，因此我们知道 E是 C的右子树根节点， K是 E的左子树节点，因此 A和它的左子树如下图 1； A的右子树节点 BDHJI，前序遍历结果是 DBHJI，则 D是
20、A的右子树的根节点，根据中序遍历结果 BDKJI， B是 D的左子树， HJI是 D的右子树，依此类推， H是 D的右子树根节点， JI是 H的右子树节点， J是 H的右子树根节点， I是 J的右子树节点。至此整个二叉树的结构已经出来了，如下图2，它的后序遍历 结果是 FKECBIJHDA，答案是 B项。【知识模块】 数据结构与算法 24 【正确答案】 C 【试题解析】 只有知道中序遍历结果再加上前序或者后序遍历才能唯一确定这个二叉树，只知道前序遍历和后序遍历结果是不能唯一确定这个二叉树的，如图 3两个二叉树，它们的前序遍历都是 ABDC，后序遍历都是 DBCA。【知识模块】 数据结构与算法
21、25 【正确答案】 A 【试题解析】 分治法是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题，直到最后子问题可以简单 地直接求解，原问题的解即子问题的解的合并。二叉树有 2个分支，适合使用分治法。 【知识模块】 数据结构与算法 26 【正确答案】 C 【试题解析】 时间复杂度用大写的 O符号表示， O(1)表示复杂度是一个常量，和问题规模基本没关系，但是并不意味着只运算一次。时间复杂度的低阶项和常数项以及高阶项的系数相对于高阶项来说影响比较小，因此在表示的时候不予考虑。 【知识模块】 数据结构与算法 27 【正确答案】 D 【试题解析】 在最好情况下，第一个元素就是要查找的元素，因此查找次数是1， 最坏情况下最后一个元素是查找元素，查找次数是 n，平均情况是 n 2次，时间复杂度是 O(n)。 【知识模块】 数据结构与算法 28 【正确答案】 D 【试题解析】 二分法查找是折半查找，必须满足两个条件： 顺序存储结构； 线性表是有序表。二分法时间复杂度是 D(log2n)。 【知识模块】 数据结构与算法
