1、国家二级 MS Office高级应用机试（数据结构与算法）模拟试卷 13及答案与解析 一、选择题 1 下列叙述中正确的是 （ A）循环队列有队头和队尾两个指针，因此，循环队列是非线性结构 （ B）在循环队列中，只需要队头指针就能反映队列中元素的动态变化情况 （ C）在循环队列中，只需要队尾指针就能反映队列中元素的动态变化情况 （ D）循环队列中元素的个数是由队头指针和队尾指针共同决定 2 支持子程序调用的数据结构是 （ A）栈 （ B）树 （ C）队列 （ D）二叉树 3 一棵完全二叉树共有 360个结点，则在该二叉树中度为 1的结点个数为 （ A） 0 （ B） 1 （ C） 180 （ D
2、） 181 4 下列叙述中正确的是 （ A）有一个以上根结点的数据结构不一定是非线性结构 （ B）只有一个根结点的数据结构不一定是线性结构 （ C）循环链表是非线性结构 （ D）双向链表是非线性结构 5 下列链表中，其逻辑结构属于非线性结构的是 （ A）二叉链表 （ B）循环链表 （ C）双向链表 （ D）带链的栈 6 一个栈的初始状态为空。现将元素 1， 2,3， A,B,C依次入栈，然后再依次出栈，则元素出栈的顺 序是 （ A） 1， 2， 3， A， B， C （ B） C， B， A， 1， 2， 3 （ C） C， B， A， 3， 2， 1 （ D） 1， 2， 3， C， B，
3、A 7 某二叉树共有 12个结点，其中叶子结点只有 1个。则该二叉树的深度为 (根结点在第 1层 ) （ A） 3 （ B） 6 （ C） 8 （ D） 12 8 设某二叉树的前序序列为 ABC，中序序列为 CBA，则该二叉树的后序序列为 （ A） BCA （ B） CBA （ C） ABC （ D） CAB 9 在最坏情况下 （ A）快速排序的时间复杂度比冒泡排序的时间复杂度要小 （ B）快速排 序的时间复杂度比希尔排序的时间复杂度要小 （ C）希尔排序的时间复杂度比直接插入排序的时间复杂度要小 （ D）快速排序的时间复杂度与希尔排序的时间复杂度是一样的 10 下列叙述中错误的是 （ A）算
4、法的时间复杂度与算法所处理数据的存储结构有直接关系 （ B）算法的空间复杂度与算法所处理数据的存储结构有直接关系 （ C）算法的时间复杂度与空间复杂度有直接关系 （ D）算法的时间复杂度与空间复杂度没有必然的联系 11 下列叙述中正确的是 （ A）在链表中，如果每个结点有两个指针域，则该链表一定是非线性结 构 （ B）在链表中，如果有两个结点的同一个指针域的值相等，则该链表一定是非线性结构 （ C）在链表中，如果每个结点有两个指针域，则该链表一定是线性结构 （ D）在链表中，如果有两个结点的同一个指针域的值相等，则该链表一定是线性结构 12 下列各序列中不是堆的是 （ A） (91， 85，
5、53， 36， 47， 30， 24， 12) （ B） (91， 85， 53， 47， 36， 30， 24， 12) （ C） (47， 91， 53， 85， 30， 12， 24， 36) （ D） (91， 85， 53， 47， 30， 12， 24， 36) 13 线性表的链式存储结构与顺序存储结构相比，链式存储结构的优点有 （ A）节省存储空间 （ B）插入与删除运算效率高 （ C）便于查找 （ D）排序时减少元素的比较次数 14 某二叉树的前序序列为 ABCD，中序序列为 DCBA，则后序序列为 （ A） BADC （ B） DCBA （ C） CDAB （ D） ABCD
6、 15 设非空二叉树的所有予树中，其左子树上的结点值均小于根结点值，而右子树上的结点值均不小于根结点值，则称该二叉树为排序二叉树。对排序二叉树的遍历结果为有序序列的是 （ A）中序序列 （ B）前序序列 （ C）后序序列 （ D）前序序列或后序序列 16 下列叙述中正确的是 （ A）在循环队列中，队头指针和队尾指针的动态变化决定队列的长度 （ B）在循环队列中，队尾指针的动态变化决定队列的长度 （ C）在带链的队列中，队头指针与队尾指针的动态变化决定队列的长度 （ D）在带链的栈中，栈顶指针的动态变化决定栈中元素的个数 17 设表的长度为 n。下列算法中，最坏情况下比较次数小于 n的是 （ A
7、）二分查找法 （ B）堆排序 （ C）快速排序 （ D）顺序查找法 18 循环队列的存储空间为 Q(1： 200)，初始状态为 front=rear=200。经过一系列正常的入队与退队操作后， front=rear=1，则循环队列中的元素个数为 （ A） 0或 200 （ B） 1 （ C） 2 （ D） 199 19 某带链的队列初始状态为 front=rear=NULL。经过一系列正常的入队与退队操作后， front=rear=10。该队列中的元素个数为 （ A） 1 （ B） 0 （ C） 1或 0 （ D）不确定 20 设表的长度为 15。则在最坏情况下，快速排序所需要的比较次数为 （
8、 A） 105 （ B） 55 （ C） 15 （ D） 75 21 下列叙述中错误的是 （ A）算法的时间复杂度与问题规模无关 （ B）算法的时间复杂度与计算机系统无关 （ C）算法的时间复杂度与空间复杂度没有必然的联系 （ D）算法的空间复杂度与算法运行输出结果的数据量无关 22 设一棵度为 3的树，其中度为 2， 1， 0的结点数分别为 3， 1， 6。该树中度为 3的结点数为 （ A） 1 （ B） 2 （ C） 3 （ D）不可能有这样的树 23 带链队列空的条件是 （ A） front=rear=NULL （ B） front=rear= 1 （ C） front=NULL且 re
9、ar= 1 （ D） front= 1且 rear=NULL 24 下列叙述中错误的是 （ A）循环链表中有一个表头结点 （ B）循环链表的存储空间是连续的 （ C）循环链表实现了空表与非空表运算的统一 （ D）循环链表的表头指针与循环链表中最后一个结点的指针均指向表头结点 25 下列叙述中正确的是 （ A）矩阵是非线性结构 （ B）数组是长度固定的线性表 （ C）对线性表只能作插入与删除运算 （ D）线性表中各元素的数据类型可以不同 26 下列叙述中正确的是 （ A） 循环队列是队列的链式存储结构 （ B）能采用顺序存储的必定是线性结构 （ C）所有的线性结构都可以采用顺序存储结构 （ D）
10、具有两个以上指针的链表必定是非线性结构 27 设二叉树的前序序列为 ABDEGHCFIJ，中序序列为 DBGEHACIFJ。则后序序列为 （ A） DGHEBIJFCA （ B） JIHGFEDCBA （ C） GHIJDEFBCA （ D） ABCDEFGHIJ 28 设表的长度为 n。在下列结构所对应的算法中，最坏情况下时间复杂度最低的是 （ A）堆排序 （ B）有序链表查找 （ C）希 尔排序 （ D）循环链表中寻找最大项 国家二级 MS Office高级应用机试（数据结构与算法）模拟试卷 13答案与解析 一、选择题 1 【正确答案】 D 【试题解析】 循环队列中元素的个数是由队头指针和
11、队尾指针共同决定的，元素的动态变化也是通过队头指针和队尾指针来反映的。 【知识模块】 数据结构与算法 2 【正确答案】 A 【试题解析】 栈是一种限定在一端进行插入与删除的线性表。在主函数调用子函数时，要首先保存主函数当前的状态，然后转去执行子函数，把子函数的运行结果返回到主函数调 用子函数时的位置，主函数再接着往下执行，这种过程符合栈的特点。所以一般采用栈式存储方式。 【知识模块】 数据结构与算法 3 【正确答案】 B 【试题解析】 对于一个具有 n个结点的完全二叉树，其深度为 log2n+1。本题中这个二叉树的深度为 log2360+1=8+1=9。根据满二叉树的性质，深度为 8的满二叉树
12、其结点数为 28-1=256-1=255。这个完全二叉树的第 9层的结点数为 360-255=105。完全二叉树的性质非叶子结点的子结点都为 2， 105除以 2其商为 52余数为 1。因此该二叉树中 度为 1的结点个数为 1。选项 B正确。 【知识模块】 数据结构与算法 4 【正确答案】 B 【试题解析】 在数据结构中，树这类的数据结构只有一个根结点，但它不是线性结构。 【知识模块】 数据结构与算法 5 【正确答案】 A 【试题解析】 二叉链表作为树的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。 【知识模块】 数据结构与算法 6 【正确答案】 C 【试题解析
13、】 栈是按照 “先进后出 ”或 “后进先出 ”的原则组织数据的。所以出栈顺序是 CBA321。 【知识模块】 数据结构与算法 7 【正确答案】 D 【试题解析】 根据二叉树的性质，度为 0的结点 (即叶子结点 )总是比度为 2的结点多一个。题目中的二叉树的叶子结点为 1，因此度为 2的结点的数目为 0，故该二叉树为 12层，每层只有一个结点。 【知识模块】 数据结构与算法 8 【正确答案】 B 【试题解析】 二叉树的前序遍历的顺序为首先访问根结点，再依次访问左结点和右结点。中序遍历的顺序为首先访问左结点，然后依次访问根结点和右结点。后序遍历的顺序为首先访问左结点，然后依次访问右结点和根结点。
14、根据前序可以很快确定根，然后可以查看根在中序中位置，将中序分为左右两部分，左边和右边两颗树，在按照上述方式递推出确定左子树的根和右子树。对于本题根据前序，可以确定 A为根， A在中序中的位置，可以确定 CB为 A的左子树上的结点，没有右子树。确定 A之后，再看中序第二个值为 B，查看 B在中序中的位置， C在 B左边，确定 C为 B的左子树。本题的具体二叉树如下，因此，后序是CBA。 【知识模块】 数据结构与算法 9 【正确答案】 C 【试题解析】 按平均时间将排序分为四类： 平方阶 (O(n2)排序：各类简单排序，例如直接插入、直接选择和冒泡排序； 线性对数阶 (O(n1og2n)排序：如快
15、速排序、堆排序和归并排序： O(nl+)排序： 是介于 0和 1之间的常数。希尔排序便是一种； 线性阶 (O(n)排序：本程序中的基数排序，此外还有桶、箱排序。根据以上 4点，可以判断选项 C正确。 【知识模块】 数据结 构与算法 10 【正确答案】 C 【试题解析】 算法的时间复杂度，是指执行算法所需要的计算工作量。算法的空间复杂度，是指执行这个算法所需要的内存空间。两者与算法所处理数据的存储结构都有直接关系，但两者之间没有直接关系，因此选项 C错误。 【知识模块】 数据结构与算法 11 【正确答案】 B 【试题解析】 选项 A叙述是错误的，例如在双向链表中，每个结点有两个指针域，但该链表是
16、线性结构；选项 C叙述也是错误的，例如每个二叉树的结点都有两个指针域，但是其结构是非线性结构；选项 D叙述也是错误的 ，线性结构只有唯一的一个前驱和唯一的一个后继 (头、尾除外 )；排除法可判断选项 B正确。 【知识模块】 数据结构与算法 12 【正确答案】 C 【试题解析】 堆可以看成一棵完全二叉树：任一根节点 =左右孩子 (或者 =)，(大的叫大根堆，小的叫小根堆 )。注意一个堆中的这种性质有一致性，不能既有大于又有小于情况存在。此题可以这么做，把结点按照完全二叉树画出来就一目了然了。这个题目很明显 91是最大的根，而选项 C是 “左根右 ”的排序，那么 91的左边只有 47，其他都在右边
17、，而右边无法按照此顺序排列，所以选项 C不是堆。 【知识模块】 数据结构与算法 13 【正确答案】 B 【试题解析】 顺序存储时，相邻数据元素的存放地址也相邻 (逻辑与物理统一 )；要求内存中可用存储单元的地址必须是连续的。优点是存储密度大 (=1)，存储空间利用率高；缺点是插入或删除元素时不方便。 链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表不结点间关系的指针优点是插入或删除元素时很方便效率高，使用灵活。缺点是存储密度小 ( 1)，存储空间利用率低，故选项 B正确。 【知识模块 】 数据结构与算法 14 【正确答案】 B 【试题解析】 在二叉树
18、前序遍历中 ABCD中 A是根节点，而在后序遍历中根结点位于最后，所以选项 B正确。 【知识模块】 数据结构与算法 15 【正确答案】 A 【试题解析】 中序遍历的次序是先遍历左子树，再遍历根节点，最后遍历右子树。而左子树结点值根节点节点值 右子树节点值，是有序序列，因此选项 A正确。 【知识模块】 数据结构与算法 16 【正确答案】 A 【试题解析】 循环队列是将顺序队列首尾相连形成的，随着插入元素或删除 元素的进行，其队头指针及队尾指针是在不断变化的，有时可能会出现队头指针大于队尾指针的情况，也可能是队尾指针大于队头指针。 循环队列中计算元素的个数公式为： (rear-front queu
19、e_size) queue_size。所以选项 A正确。 【知识模块】 数据结构与算法 17 【正确答案】 A 【试题解析】 二分法查找只适用于顺序存储的有序表。二分查找的基本方法是： 将被查元素 x与线性表的中间项进行比较，若中间项的值等于 x，则说明查到： 若小于中间项的值则在线性表的前半部分； 以相同的方法进行查 找； 若大于中间项的值，则在线性表的后半部分以相同的方法进行查找。 在最坏情况下，二分查找需要比较 log2n次。所以选项 A正确。 【知识模块】 数据结构与算法 18 【正确答案】 A 【试题解析】 循环队列中，由于入队时尾指针 rear向前追赶头指针 front；出队时头指
20、针 front向前追赶尾指针 rear，造成队空和队满时头尾指针均相等。 因此，无法通过条件 front=rear来判别队列是 “空 ”还是 “满 ”。 对于本题来说，经过一系列正常的入队与退队操作后， front=rear=1。 此时，要么 队列为空 (元素个数为 0)，要么队列为满 (元素个数为 200)。所以选项 A正确。 【知识模块】 数据结构与算法 19 【正确答案】 A 【试题解析】 循环队列用数组 A0； m-1存放其元素值，已知其头尾指针分别是front和 rear，则当前队列的元素个数是 (rear-front+m) m=1，所以选项 A正确。 【知识模块】 数据结构与算法
21、20 【正确答案】 A 【试题解析】 假设线性表的长度为 n，在最坏情况下，快速排序法的比较次数是n(n一 1) 2。题中 n=15，所以 15*14 2=105。所以选项 A正确。 【知识模块】 数据结构与算法 21 【正确答案】 A 【试题解析】 一般情况下，算法中基本操作重复执行的次数是问题规模 n的某个函数，用 T(n)表示，若有某个辅助函数 f(n)，使得当 n趋近于无穷大时， T(n)f(n)的极限值为不等于零的常数，则称 f(n)是 T(n)的同数量级函数。记作T(n)=O(f(n)，称 O(f(n)为算法的渐进时间复杂度，简称时间复杂度。所以选项 A正确。 【知识模块】 数据结
22、构与算法 22 【正确答案】 A 【试题解析】 因为任一棵树中，结点总数 =总分支数目 +1，所以： 6+1+3+n3=(0*6+1*1+2*3+3*n3)+1。运算结果 n3=1。 其中， n3表示度为 3的结点数，所以选项 A正确。 【知识模块】 数据结构与算法 23 【正确答案】 A 【试题解析】 带链队列空的条件有两个：一个是 front=rear，一个是它们都等于空。 【知识模块】 数据结构与算法 24 【正确答案】 B 【试题解析】 循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表 形成一个环。循环链表的结点是指针指向，它不一定要是连续的存
23、储空间，也可以是断开的空间。 【知识模块】 数据结构与算法 25 【正确答案】 B 【试题解析】 所谓数组，就是相同数据类型的元素按一定顺序排列的集合，就是把有限个类型相同的变量用一个名字命名，然后用编号区分它们的变量的集合，这个名字称为数组名，编号称为下标。 【知识模块】 数据结构与算法 26 【正确答案】 C 【试题解析】 根据数据结构中各数据元素之间的前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构与非 线性结构。有序线性表既可以采用顺序存储结构，又可以采用链式存储结构。所有的线性结构都可以采用顺序存储结构。 【知识模块】 数据结构与算法 27 【正确答案】 A 【试题解析】
24、前序遍历中，第一个字母是根结点，也就是 A是根结点；在中序遍历中，根结点前面的是左子树、后面的是右子树。前序中， 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的右结点。由此可画出这个二叉树，然后根据二叉树可的后序序列为 DGHEBIJFCA。 【知识模块】 数据结构与算法 28 【正确答案】 D 【试题解析】 在循环链表中寻找最大项算法是，首先取出第一个数作为最大数，然后和后面的所有项进行比较查找。因此，比较次数为 n-1。 【知识模块】 数据结构与算法
