1、国家二级 MS Office高级应用机试（数据结构与算法）模拟试卷 9及答案与解析 一、选择题 1 对长度为 n的线性表排序，存最坏情况下，比较次数不是 n(n一 1) 2的排序方法是 （ A）快速排序 （ B）冒泡排序 （ C）直接插入排序 （ D）堆排序 2 对于循环队列，下列叙述中正确的是 （ A）队头指针是固定不变的 （ B）队头指针一定大于队尾指针 （ C）队头指针一定小于队尾指针 （ D）队头指针可以大于队尾指针，也可以小于队尾指针 3 下列叙述中正确的是 （ A）栈是 “先进先出 ”的线性表 （ B）队列是 “先进后出 ”的线性表 （ C）循环队列是非线性结构 （ D）有序线性表
2、既可以采用顺序存储结构，也可以采用链式存储结构 4 下列叙述中正确的是 （ A）在栈中，栈中元素随栈底指针与栈顶指针的变化而动态变化 （ B）在栈中，栈顶指针不变，栈中元素随栈底指针的变化而动态变化 （ C）在栈中，栈底指针不变，栈中元素随栈顶指针的变化而动态变化 （ D）上述三种说法都不对 5 下列叙述中正确的是 （ A）循环队列是队列的一种链式存储结构 （ B）循环队列是队列的一种顺序存储结构 （ C）循环队列是 非线性结构 （ D）循环队列是一种逻辑结构 6 设二叉树共有 150个结点，其中度为 1的结点有 10个，则该二叉树中的叶子结点数为 （ A） 71 （ B） 70 （ C） 6
3、9 （ D）不可能有这样的二叉树 7 一棵二叉树中共有 80个叶子结点与 70个度为 1的结点，则该二叉树中的总结点数为 （ A） 219 （ B） 229 （ C） 230 （ D） 231 8 下列叙述中错误的是 （ A）在双向链表中，可以从任何一个结点开始直接遍历到所有结点 （ B）在循环链表中，可以从任何一个结点开始直接遍历到所有结点 （ C）在线性单链表中，可以从任何一个结点开始直接遍历到所有结点 （ D）在二叉链表中，可以从根结点开始遍历到所有结点 9 设某二叉树的后序序列为 CBA，中序序列为 ABC，则该二叉树的前序序列为 （ A） BCA （ B） CBA （ C） ABC
4、（ D） CAB 10 算法空间复杂度的度量方法是 （ A）算法程序的长度 （ B）算法所处理的数据量 （ C）执行算法所需要的工作单元 （ D）执行算法所需要的存储空间 11 下列叙述中正确的是 （ A）存储空间连续的数据结构一定是线性结构 （ B）存储空间 不连续的数据结构一定是非线性结构 （ C）没有根结点的非空数据结构一定是线性结构 （ D）具有两个根结点的数据结构一定是非线性结构 12 下列叙述中正确的是 （ A）链表结点中具有两个指针域的数据结构可以是线性结构，也可以是非线性结构 （ B）线性表的链式存储结构中，每个结点必须有指向前件和指向后件的两个指针 （ C）线性表的链式存储结
5、构中，每个结点只能有一个指向后件的指针 （ D）线性表的链式存储结构中，叶子结点的指针只能是空 13 下列叙述中正确的是 （ A）循环队列是顺序存储结构 （ B）循环 队列是链式存储结构 （ C）循环队列是非线性结构 （ D）循环队列的插入运算不会发生溢出现象 14 设有二叉树如下图所示，则后序序列为 （ A） ABDEGCFH （ B） DBGEAFHC （ C） DGEBHFCA （ D） ABCDEFGH 15 设栈的存储空间为 S(1： 50)，初始状态为 top=51。现经过一系列正常的入栈与退栈操作后， top=50，则栈中的元素个数为 （ A） 1 （ B） 0 （ C） 50
6、（ D） 49 16 在具有 2n个结点的完全二叉树中，叶子结点个数为 （ A） n （ B） n+1 （ C） n-1 （ D） n 2 17 在长度为 n的顺序表中查找一个元素，假设需要查找的元素有一半的机会在表中，并且如果元素在表中，则出现在表中每个位置上的可能性是相同的。则在平均情况下需要比较的次数大约为 （ A） (3 n)， 4 （ B） n （ C） n 2 （ D） n 4 18 循环队列的存储空间为 Q(1： 100)，初始状态为 front=rear=100。经过一系列正常的入队与退队操作后， front=rear=99，则循环队列中的元素个数为 （ A） 0或 100 （
7、 B） 1 （ C） 2 （ D） 99 19 某二叉树的前序遍历序列与中序遍历序列相同，均为 ABCDEF，则按层次输出(同一层从左到右 )的序列为 （ A） ABCDEF （ B） BCDEFA （ C） FEDCBA （ D） DEFABC 20 下列各排序法中，最坏情况下时间复杂度最小的是 （ A）堆排序 （ B）快速排序 （ C）希尔排序 （ D）冒泡排序 21 下列叙述中正确的是 （ A）解决一个问题可以有不同的算法，且它们的时间复杂度可以是不同的 （ B）解决一个问题可以有不同的算法，但它们的时间复杂度必定是相同的 （ C）解 决一个问题的算法是唯一的 （ D）算法的时间复杂度与
8、计算机系统有关 22 设一棵树的度为 3，共有 27个结点，其中度为 3， 2， 0的结点数分别为 4， 1，10。该树中度为 1的结点数为 （ A） 11 （ B） 12 （ C） 13 （ D）不可能有这样的树 23 在带链队列中，经过一系列正常的操作后，如果 front=rear，则队列中的元素个数为 （ A） 0或 1 （ B） 0 （ C） 1 （ D）队列满 24 设某棵树的度为 3，其中度为 3、 2、 1的结点个数分别为 3、 0、 4。则该树中的叶子结点数为 （ A） 7 （ B） 8 （ C） 6 （ D）不可能有这样的树 25 下列结构中属于非线性结构的是 （ A）二叉链
9、表 （ B）二维数组 （ C）循环队列 （ D）双向链表 26 设某棵树的度为 3，其中度为 2、 1、 0的结点个数分别为 3、 4、 15。则该树中总结点数为 （ A） 22 （ B） 30 （ C） 35 （ D）不可能有这样的树 27 设循环队列的存储空间为 Q(1： 50)，初始状态为 front=rear=50。经过一系列正常的操作后， front-1=rear。为了在该队列中寻找值最大的元素，在最坏情况下需要的 比较次数为 （ A） 0 （ B） 1 （ C） 48 （ D） 49 国家二级 MS Office高级应用机试（数据结构与算法）模拟试卷 9答案与解析 一、选择题 1
10、【正确答案】 D 【试题解析】 各种排序方法中最坏情况下需要比较的次数分别为：冒泡排序 n(n-1) 2、快速排序 n(n-1) 2、简单插入排序 n(n-1) 2、希尔排序 O(n1 5)、简单选择排序 n(n-1) 2、堆排序 O(nlog2n)。 【知识模块】 数据结构与算法 2 【正确答案】 D 【试题解析】 所谓循环队列，就是将 队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。在循环队列中，用队尾指针 rear指向队列中的队尾元素，用队头指针 front指向队头元素的前一个位置。循环队列的主要操作是：入队运算和退队运算。每进行一次入队运算，队尾指针就进
11、一。每进行一次退队运算，队头指针就进一。当 rear或 front等于队列的长度加 1时，就把 rear或 front值置为 1。所以在循环队列中，队头指针可以大于队尾指针，也可以小于队尾指针。 【知识模块】 数据结构与算法 3 【正确答案】 D 【试题 解析】 本题主要考查了栈、队列、循环队列的概念，栈是先进后出的线性表，队列是先进先出的线性表。根据数据结构中各数据元素之间的前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。有序线性表既可以采用顺序存储结构，又可以采用链式存储结构。 【知识模块】 数据结构与算法 4 【正确答案】 C 【试题解析】 在栈中，允许插入与删除
12、的一端称为栈顶，而不允许插入与删除的另一端称为栈底。栈跟队列不同，元素只能在栈顶压入或弹出，栈底指针不变，栈中元素随栈顶指针的变化而动态变化，遵循后进先 出的规则。 【知识模块】 数据结构与算法 5 【正确答案】 B 【试题解析】 本题主要考查循环队列的概念，循环队列作为队列的一种也应该是线性结构。队列是一种逻辑结构，而循环队列是一种顺序存储结构的队列。 【知识模块】 数据结构与算法 6 【正确答案】 D 【试题解析】 根据二叉树的性质 3，在任意一颗二叉树中，度为 0的结点 (即叶子结点 )总是比度为 2的结点多一个。即有 n0=n2+1。对于这个题来说，总结点数150=n0+n1+n2=n
13、2+1+10+n2=2n2+11，所以 2n2=139，度为 2个结点个数不能确定。选项 D正确。 【知识模块】 数据结构与算法 7 【正确答案】 B 【试题解析】 根据二叉树的性质，在任意二叉树中，度为 0的结点 (即叶子结点 )总是比度为 2的结点多一个，故总结点数 =叶子节点数 +度为 2的节点数 +度为 1的节点数 =80+79+70=229。 【知识模块】 数据结构与算法 8 【正确答案】 C 【试题解析】 线性队列是一种线性单链表，对线性队列的遍历只能从队列的头开始，从中间的结点开始不能够遍历到所有的结点。选项 C的描述是错误的。 【知识模块】 数据结构与算法 9 【正确答案】 C
14、 【试题解析】 二叉树的前序遍历顺序为首先访问根结点，再依次访问左结点和右结点。中序遍历的顺序为首先访问左结点，然后依次访问根结点和右结点。后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点。根据后序可以很快确定根结点，然后可以查看根在中序中位置，将中序分为左右两部分，左边和右边两颗树，在按照上述方式递推出确定左子树的根和右子树。 本题根据后序，可以确定 A为根结点；根据 B在中序中的位置，可以确定 A没有左子树， BC为 A的右子树， C为 B的右子树。本 题的具体二叉树如下，因此，这棵二叉树的前序是ABC，选项 C正确。 【知识模块】 数据结构与算法 10 【正确答案】 D 【试题解析
15、】 算法空间复杂度是对一个算法在运行过程中临时占用存储空间大小的度量，因此选项 D正确。 【知识模块】 数据结构与算法 11 【正确答案】 D 【试题解析】 数据结构从逻辑上来划分，分为线性结构和非线性结构，一对一是线性结构，其它的为非线性结构。判断一个非空的数据结构是否为线性结构必须满足以下两个条件： 有且只有一个根结点； 每一个结点 最多有一个前件，也最多有一个后件。根据这两个条件，可知选项A、 B和 C都不能判定是否是线性结构，选项 D正确。 【知识模块】 数据结构与算法 12 【正确答案】 A 【试题解析】 在链式存储方式中，每个结点由两部分组成：数据域和指针域，指针域用于指向该节点的
16、前一个或后一个结点，所以选项 B、 C、 D说法错误。选项A中，例如双向链表就具有两个指针，也属于线性结构，所以选项 A正确。 【知识模块】 数据结构与算法 13 【正确答案】 A 【试题解析】 循环队列属于队列的特例和栈同属于线性结 构，所以选项 C不正确。 在顺序队列中，由于数组空间不够而产生的溢出叫真溢出；顺序队列因多次入队列和出队列操作后出现的有存储空间但不能进行入队列操作的溢出称为假溢出；假溢出是由于队尾 rear的值和队头 front的值不能由所定义数组下界值自动转为数组上界值而产牛的，解决的办法是把顺序队列所使用的存储空伺构造成一个逻辑上首尾相连的循环队列。因此，顺序队列通常都采
17、用顺序循环队列结构；栈的存储方式有顺序存储和链式存储，故选项 A正确，选项 B不正确。循环队列虽然能解决假溢出，却不能解决在顺序队列中，由于数组空间不够而产生 的真溢出，故选项 D不正确。 【知识模块】 数据结构与算法 14 【正确答案】 C 【试题解析】 后序遍历 (LRD)首先遍历左子树，然后访问遍历右子树，最后访问根结点，可知选项 C正确。 【知识模块】 数据结构与算法 15 【正确答案】 A 【试题解析】 栈的存储空间为 S(1： 50)，初始状态为 top=51。现经过一系列正常的入栈与退栈操作后， top=50，则栈中有 51-50=1个元素，选项 A正确。 【知识模块】 数据结构
18、与算法 16 【正确答案】 A 【试题解析 】 在具有 2n个结点的完全二叉树中，叶子结点个数为： (2n+1) 2取整，其值等于 n。所以选项 A正确。 【知识模块】 数据结构与算法 17 【正确答案】 A 【试题解析】 在长度为 n的顺序表中查找一个元素，最好的情况是目标在第一个，一次找到；最坏的情况是目标在最后一个， n次找到。那么平均长度为：(1+2+n) n=(n(n+1) 2) n=(n+1) 2 本题需要查找的元素有一半的机会在表中，则在平均情况下需要比较的次数大约为 (1+n) 2+1) 2=(3+n) 4。所以选项 A正确。 【知识模块】 数据结构与算法 18 【正确答案】
19、A 【试题解析】 循环队列中，由于入队时尾指针 rear向前追赶头指针 front；出队时头指针 front向前追赶尾指针 rear，造成队空和队满时头尾指针均相等。因此，无法通过条件 front=rear来判别队列是 “空 ”还是 “满 ”。 对于这个题目来说，经过一系列正常的入队与退队操作后， front=rear=99，此时，要么队列为空 (元素个数为 0)，要么队列为满 (元素个数为 100)，因此选项 A正确。 【知识模块】 数据结构与算法 19 【正 确答案】 A 【试题解析】 前序遍历次序：根左右；中序遍历次序：左根右。由定义可以知道： 前序遍历中第一个就是树根结点，即 A结点；
20、 在中序遍历中，根结点左边的是左子树集，右边的是右子树集，即 BCDEF是根结点 A的右子树集合。问题就会转化为：求前序遍历是 BCDEF，中序遍历是 BCDEF的子树，方法同上。详细推理过程：步骤 1：由 ABCDEF得出根结点为 A，由中序遍历可知：左子树为空， A BCDEF；步骤 2：由 BCDEF得出右子树集合的根节点为 B，由中序可知：左子树为空， BCDEF；步骤 3：同理，二叉树更 新后如下。 所以按层次输出 (同一层从左到右 )的序列为 ABCDEF，选项 A正确。 【知识模块】 数据结构与算法 20 【正确答案】 A 【试题解析】 快速排序、冒泡排序最坏情况下时间复杂度是
21、O(n2)；希尔排序最坏情况下时间复杂度是 O(n1 2)。堆排序最坏情况下时间复杂度是 O(nlog2n)，所以选项 A正确。 【知识模块】 数据结构与算法 21 【正确答案】 A 【试题解析】 算法的时间复杂度和问题有关系，因为一个问题很有可能有许多类算法，但是它们的时间复杂度不同，如排序问题就有 10种左右算法，它们复杂度显然是不一样的。所以选项 A正确。 【知识模块】 数据结构与算法 22 【正确答案】 B 【试题解析】 因为任一棵树中，结点总数 =总分支数目 +1，所以：27=(0*10+n1*1+2*1+3*4)+1。运算结果 n1=12。其中， n1表示叶子结点，所以选项B正确。
22、 【知识模块】 数据结构与算法 23 【正确答案】 A 【试题解析】 队列是一种特殊的线性表，特殊之处在于它只允许在表的前端(front)进行删除操作，而在表的后端 (rear)进行插入操作，和栈一样 ，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。 队列的链式存储也称为链队列。为了便于操作，可给链队列添加 1个头结点，并令头指针指向头结点。队列为空的判断条件是头指针和尾指针的值相同，且均指向头结点。当队列为空 (0)或 l时， front=rear。 【知识模块】 数据结构与算法 24 【正确答案】 A 【试题解析】 树的度是指一棵树中，最大的结点的度称为
23、 “树的度 ”。根据题目可知本树中没有度为 2的结点。树的总结点 =(度 1*个数 +度 2*个数 )+1 ，这里 我们设总结点数为 n，那么 n=3*3+2*0+1*4+1=14。树的叶子结点数等于总结点减去所有度不为 0的结点，也就是 14 3 4=7。 【知识模块】 数据结构与算法 25 【正确答案】 B 【试题解析】 线性结构是一个有序数据元素的集合。常用的线性结构有：线性表，栈，队列，双队列，数组，串：常见的非线性结构有：二维数组，多维数组，广义表，树 (二叉树等 )，图。循环队列、双向链表和二叉链表都是线性结构，而二维数组是非线性结构。 【知识模块】 数据结构与算法 26 【正确答
24、案】 D 【试题解析】 本题采用画图法来求出结果。首先先画出包含 3个度为 2的结点；然后再添加 4个度为 1的结点。根据题目中描述的度为 0的结点数有 15个，这时要在书中添加度为 3的结点，不管怎么添加都不能添加出 15个度为 0的结点，因此不可能有这样的树。 【知识模块】 数据结构与算法 27 【正确答案】 C 【试题解析】 front指向队头位置，删除一个元素就将。 front顺时针移动一位；rear指尾指针，指向元素要插入的位置，插入一个元素就将 rear顺时针移动一位；操作后，循环队列的队头指针 -1等于尾指针 ，说明出队一位，那么总数就是49了。在该队列中寻找最大值元素，最多比较次数是总数 -1，因此是 49一 1=48次。 【知识模块】 数据结构与算法
