1、国家二级 MS Office高级应用机试（数据结构与算法）模拟试卷 14及答案与解析 一、选择题 1 在长度为 n的有序线性表中进行二分查找，最坏情况下需要比较的次数是 （ A） O(n) （ B） O(n2) （ C） O(1og2n) （ D） O(nlog2n) 2 算法的有穷性是指 （ A）算法程序的运行时间是有限的 （ B）算法程序所处理的数据量是有限的 （ C）算法程序的长度是有限的 （ D）算法只能被有限的用户使用 3 算法的时间复杂度是指 （ A）设计该算法所需的工作量 （ B）执行该算法所 需要的时间 （ C）执行该算法时所需要的基本运算次数 （ D）算法中指令的条数 4 下
2、列关于二叉树的叙述中，正确的是 （ A）叶子结点总是比度为 2的结点少一个 （ B）叶子结点总是比度为 2的结点多一个 （ C）叶子结点数是度为 2的结点数的两倍 （ D）度为 2的结点数是度为 l的结点数的两倍 5 设循环队列的存储空间为 Q(1： 35)，初始状态为 front=rear=35。现经过一系列入队与退队运算后， front=15， rear=15，则循环队列中的元素个数为 （ A） 15 （ B） 16 （ C） 20 （ D） 0或 35 6 下列叙述中正确的是 （ A）一个算法的空间复杂度大，则其时间复杂度也必定大 （ B）一个算法的空间复杂度大，则其时间复杂度必定小 （
3、 C）一个算法的时间复杂度大，则其空间复杂度必定小 （ D）算法的时间复杂度与空间复杂度没有直接关系 7 对长度为 n的线性表作快速排序，在最坏情况下，比较次数为 （ A） n （ B） n-1 （ C） n(n 1) （ D） n(n 1) 2 8 下列排序方法中，最坏情况下时间复杂度最小的是 （ A）冒泡排序 （ B）快速排序 （ C）堆排序 （ D） 直接插入排序 9 在深度为 7的满二叉树中，度为 2的结点个数为 （ A） 64 （ B） 63 （ C） 32 （ D） 31 10 设栈的顺序存储空间为 S(0： 49)，栈底指针 bottom=49，栈顶指针 top=30(指向栈顶元
4、素 )。则栈中的元素个数为 （ A） 30 （ B） 29 （ C） 20 （ D） 19 11 下列叙述中错误的是 （ A）在带链队列中，队头指针和队尾指针都是在动态变化的 （ B）在带链栈中，栈顶指针和栈底指针都是在动态变化的 （ C）在带链栈中，栈顶指针是在动态变化的，但栈底指针是不 变的 （ D）以上三项都错误 12 深度为 5的完全二叉树的结点数不可能是 （ A） 15 （ B） 16 （ C） 17 （ D） 18 13 深度为 7的完全二叉树中共有 125个结点，则该完全二叉树中的叶子结点数为 （ A） 62 （ B） 63 （ C） 64 （ D） 65 14 下列叙述中正确的
5、是 （ A）算法的时间复杂度与运行算法时特定的输入有关 （ B）算法的时间复杂度与计算机的运行速度有关 （ C）算法的时间复杂度与算法程序中的语句条数成正比 （ D）算法的时间复杂度与算法程序编制者的水平有关 15 循环队列的存储空间为 Q(1： 50)，初始状态为 front=rear=50。经过一系列正常的入队与退队操作后， front=rear=25，此后又插入一个元素，则循环队列中的元素个数为 （ A） 1或 50且产生上溢错误 （ B） 51 （ C） 26 （ D） 2 16 设栈的存储空间为 S(1： 60)，初始状态为 top=61。现经过一系列正常的入栈与退栈操作后， top
6、=1，则栈中的元素个数为 （ A） 60 （ B） 59 （ C） 0 （ D） 1 17 下列叙述中错误的是 （ A）循环链表是循环队列的存储结构 （ B）二叉链表是二叉树的存储结构 （ C）栈是线性结构 （ D）循环队列是队列的存储结构 18 设栈的顺序存储空间为 S(1： m)，初始状态为 top=0。现经过一系列正常的入栈与退栈操作后， top=m+1，则栈中的元素个数为 （ A）不可能 （ B） m+1 （ C） 0 （ D） m 19 某完全二叉树按层次输出 (同一层从左到右 )的序列为 ABCDEFGH。该完全二叉树的前序序列为 （ A） ABDHECFG （ B） ABCDEF
7、GH （ C） HDBEAFCG （ D） HDEBFGCA 20 设循环队 列的存储空间为 Q(1： 100)，初始状态为空。现经过一系列正常操作后， front=49，则循环队列中的元素个数为 （ A）不确定 （ B） 49 （ C） 51 （ D） 50 21 设表的长度为 20。则在最坏情况下，冒泡排序的比较次数为 （ A） 90 （ B） 20 （ C） 19 （ D） 190 22 下列数据结构中，不能采用顺序存储结构的是 （ A）栈 （ B）堆 （ C）队列 （ D）非完全二叉树 23 设一棵树的度为 3，其中没有度为 2的结点，且叶子结点数为 6。该树中度为 3的结点数为 （
8、A） 1 （ B） 2 （ C） 3 （ D）不可能有这样的树 24 度为 3的一棵树共有 30个结点，其中度为 3、 1的结点个数分别为 3、 4。则该树中的叶子结点数为 （ A） 14 （ B） 15 （ C） 16 （ D）不可能有这样的树 25 在快速排序法中，每经过一次数据交换 (或移动 )后 （ A）能消除多个逆序 （ B）只能消除一个逆序 （ C）不会产生新的逆序 （ D）消除的逆序个数一定比新产生的逆序个数多 26 下列叙述中正确的是 （ A）算法的复杂度是指算法所处理的数据量 （ B）算法的复杂度是指算法程序中指 令的数量 （ C）算法的复杂度是指算法控制结构的复杂程度 （
9、D）算法的复杂度包括时间复杂度与空间复杂度 27 设顺序表的长度为 16，对该表进行简单插入排序。在最坏情况下需要的比较次数为 （ A） 15 （ B） 30 （ C） 60 （ D） 120 28 设循环队列的存储空间为 Q(1： m)，初始状态为 front=rear=m。经过一系列正常的操作后， front=1， rear=m。为了在该队列中寻找值最大的元素，在最坏情况下需要的比较次数为 （ A） m （ B） m-1 （ C） m-2 （ D） 1 国家 二级 MS Office高级应用机试（数据结构与算法）模拟试卷 14答案与解析 一、选择题 1 【正确答案】 C 【试题解析】 对于
10、长度为 n的有序线性表，在最坏情况下，二分法查找只需比较log2n次，而顺序查找需要比较 n次。 【知识模块】 数据结构与算法 2 【正确答案】 A 【试题解析】 算法的有穷性，是指算法必须能在有限的时间内做完，即算法必须能在执行有限个步骤之后终止。 【知识模块】 数据结构与算法 3 【正确答案】 D 【试题解析】 算法的时间复杂度，是指执行算法所 需要的计算工作量。算法的工作量可以用算法在执行过程中所需基本运算的执行次数来度量。 【知识模块】 数据结构与算法 4 【正确答案】 B 【试题解析】 由二叉树的性质可以知道在二叉树中叶子结点总是比度为 2的结点多一个。 【知识模块】 数据结构与算法
11、 5 【正确答案】 D 【试题解析】 循环队列的队头指针和尾指针都等于 15，此循环队列中元素的个数有两种情况，第一种情况是队头指针和尾指针都是第一次到达 115，此时元素个数为 0：第二种情况是队头指针第一次到达 15，而尾指针第二次到达 15，此时元素个数为 35。 【知识模块】 数据结构与算法 6 【正确答案】 D 【试题解析】 算法的复杂度主要包括时间复杂度和空间复杂度。 算法的时间复杂度是指执行算法所需要的计算工作量，算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数，即算法的工作量 =f(n)，其中 n是问题的规模；算法的空间复杂度，一般是指执
12、行这个算法所需要的内存空间。 一个算法所占用的存储空间包括算法程序所占用的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。根据各自的定义可知，算法的时间复杂度与空间复杂度并不相关。 【知识模块】 数据结构与算法 7 【正确答案】 D 【试题解析】 假设线性表的长度为 n，则在最坏情况下，冒泡排序需要经过 n 2遍的从前往后的扫描和 n 2遍的从后往前的扫描，需要的比较次数为 n(n-1)2。快速排序法也是一种互换类的排序方法，但由于它比冒泡排序法的速度快，因此，称为快速排序法。 【知识模块】 数据结构与算法 8 【正确答案】 C 【试题解析】 排序方法中最坏情况下时间复杂
13、度的大小如下表，根据下表可知选项 C正确。 【知识模块】 数据结构与算法 9 【正确答案】 B 【试题解析】 因为在任意的二叉树中，度为 0的结点 (即叶子结点 )总比度为 2的结点的个数多 1个，而度为 0的结点数 n0=2m-1(其中 m为二叉树的深度 )。本题的度为 0的结点个数 n0=27-1=26=64。因此，度为 2的结点数 n2=n0-1=63。所以选项 B正确 【知识模块】 数据结构与算法 10 【正确答案】 C 【试题解析】 在操作系统中，栈是向下生长的，如下图如示。 所以，当栈底指针bottom=49，栈顶指针 top=30时，栈中的元素个数为：栈底 -栈顶 +1=4930
14、+1=20。因此选项 C正确。 【知识模块】 数据结构与算法 11 【正确答案】 B 【试题解析】 栈是只在一端进行增加和删除的线性表，进行操作的那端称为栈顶，另一端称为栈底。所以在带链栈中，栈顶指针是在动态变化的，但栈底指针是不变的，选项 C的说法正确，选项 B的说法是错误的。 队列是允许在队列的头和尾都可以进行操作的线 性表，所以在带链队列中，队头指针和队尾指针都是在动态变化的选项 A这一说法是正确的。 【知识模块】 数据结构与算法 12 【正确答案】 A 【试题解析】 对于满二叉树，叶子结点的数目等于 2(n-1)， n为深度，这里就是 2的 5-1=4次方，就是 16。所以选项 A为正
15、确答案。 【知识模块】 数据结构与算法 13 【正确答案】 B 【试题解析】 对于满二叉树，结点的数目等于 2n-1，叶子结点数目为 2n-1， n为深度，这里就是 2的 7次方 -1，就是 127个结点，叶子结点是 64个。然而题目中只有 125个结点，说明少了两个结点，那么就少了一个叶子结点，即 63个。 【知识模块】 数据结构与算法 14 【正确答案】 A 【试题解析】 算法的时间复杂度，是指执行算法所需要的计算工作量，算法的工作量用算法所执行的基本运行次数来度量，所以与运行算法时特定的输入有关，选项 A正确。 【知识模块】 数据结构与算法 15 【正确答案】 A 【试题解析】 循环队列
16、初始状态 front=rear=50，经过一系列入队和出队操作后，结束状态还是 front=rear=25，这说明入队元素个数和出队 元素个数一样多。这样一来最后的元素个数就和原来的元素个数一样多，明显不是 0就是 50，即要么队空 (0个元素 )，要么队满 (50个元素 )。这时进行入队操作，如果是队空 (0个元素 )的情况，此时元素个数为 1；如果是队满 (50个元素 )的情况，就会产生上溢错误。 【知识模块】 数据结构与算法 16 【正确答案】 A 【试题解析】 栈是向上增长的，每次压入一个元素，栈的 TOP指针向上移动一位，即 top-1。当压入第一个元素时， TOP指针指向 60+1
17、-1=60；当压入第二个元素时， TOP指针指向 60+1-2=59； ；以此类推，当压入第 N个元素时， TOP指针指向 60+1-N=1，刚 N=60，所以选项 A正确。 【知识模块】 数据结构与算法 17 【正确答案】 A 【试题解析】 循环队列属于逻辑结构，其实质还是顺序存储，只是使用指针进行首尾的联结，其实现的存储方式可分为：分散的链表和连续的线性表，与其逻辑结构实现功能无关。所以选项 A正确。 【知识模块】 数据结构与算法 18 【正确答案】 A 【试题解析】 栈是向上增长的，每次压入一个元素，栈的 TOP指针向上移动一位，即 top-1。 对于这个题目，由于 top初始值等于 0
18、，此时入栈一个元素， top值减 1，即 0-1=-1，出现下溢错误，所以选项 A正确。 【知识模块】 数据结构与算法 19 【正确答案】 A 【试题解析】 完全二叉树的特点是除最后一层外，每一层上的节点数均达到最大值；在最后一层上只缺少右边的若干结点。 根据上述的特点，完全二叉树按层次输出 (同一层从左到右 )的序列为 ABCDEFGH，可以得到其结构如下，所以此完全二叉树的前序序列是 ABDHECFG，选项 A正确。 【知识模块】 数据结构与算法 20 【正确答 案】 A 【试题解析】 循环队列用数组 Q1： 100存放其元素值，已知其头尾指针分别是front和 rear，则当前队列的元素
19、个数是 (rear-front 100) 100，题目中首指针rear的值未知，所以循环队列中的元素个数不能确定。所以选项 A正确。 【知识模块】 数据结构与算法 21 【正确答案】 D 【试题解析】 假设线性表的长度为 n，则在最坏情况下，冒泡排序的比较次数为n(n-1) 2。本题中， n=20，所以 20*19 2=190。所以选项 D正确。 【知识模块】 数据结 构与算法 22 【正确答案】 D 【试题解析】 堆中某个结点的值总是不大于或不小于其父结点的值、堆总是一棵完全二叉树，可以以顺序存储结构存储；队列的存储结构分为链式存储、顺序存储两种；栈作为一种数据结构，是一种只能在一端进行插入
20、和删除操作的特殊线性表，可以以顺序存储结构存储。 【知识模块】 数据结构与算法 23 【正确答案】 D 【试题解析】 树的度是指一棵树中，最大的结点的度称为树的度。本题中树的度为 3，也就是最少有一个度为 3的结点。要求没有度为 2的结点，且叶子结点为6，如果要有 度为 3的结点，那么最多只有 5个叶子结点，而画不出 6个叶子结点。因此这样的树是没有的。 【知识模块】 数据结构与算法 24 【正确答案】 B 【试题解析】 根据题目可知本树中还有度为 2的结点。树的总结点 =(度 1*个数 +度 2*个数 )+1 ，这里我们设度为 2的结点数为 x，那么30=3*3+2*x+1*4+1=2*x+
21、14，由此可计算出 x=8。树的叶子结点数等于总结点减去所有度不为 0的结点，也就是 30 3 8 4=15。 【知识模块】 数据结构与算法 25 【正确答案】 A 【试题解 析】 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 【知识模块】 数据结构与算法 26 【正确答案】 D 【试题解析】 算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。 【知识模块】 数据结构与算法 27 【正确答案】 D 【试题解析】 插入排序的基本思想是：每步将一个待排序的记 录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。最坏情况计算方法 (n*(n-1) 2=16*15 2=120。 【知识模块】 数据结构与算法 28 【正确答案】 C 【试题解析】 经过一系列正常的操作后， front=1， rear=m，那么最坏情况下需要的比较次数为 rear-front-1=m-1-1=m-2。 【知识模块】 数据结构与算法
