国家二级MS Office高级应用机试（数据结构与算法）模拟试卷12
选择题
1.下列叙述中正确的是(D)
A. 算法复杂度是指算法控制结构的复杂程度
B. 算法复杂度是指设计算法的难度
C. 算法的时间复杂度是指设计算法的工作量
D. 算法的复杂度包括时间复杂度与空间复杂度
解析：算法复杂度，即算法在编写成可执行程序后，运行时所需要的资源，资源包括时间资源和内存资源。一个算法的评价主要从时间复杂度和空间复杂度来考虑。算法的时间复杂度是指执行算法所需要的计算工作量。空间复杂度是指算法在计算机内执行时所需存储空间的度量。
2.下列排序方法中，最坏情况下比较次数最少的是(D)
A. 冒泡排序
B. 简单选择排序
C. 直接插入排序
D. 堆排序
解析：冒泡排序、简单选择排序和直接插入排序法在最坏的情况下比较次数为：n(n-1)／2。而堆排序法在最坏的情况下需要比较的次数为O(nlog2n)。其中堆排序的比较次数最少。
3.下列叙述中正确的是(D)
A. 栈是一种先进先出的线性表
B. 队列是一种后进先出的线性表
C. 栈与队列都是非线性结构
D. 栈与队列都是线性结构
解析：栈是先进后出，队列是先进先出。栈和队列都是一种线性表，属于线性结构。
4.下列叙述中正确的是(D)
A. 算法就是程序
B. 设计算法时只需要考虑数据结构的设计
C. 设计算法时只需要考虑结果的可靠性
D. 设计算法时要考虑时间复杂度和空间复杂度
解析：算法复杂度，即算法在编写成可执行程序后，运行时所需要的资源，资源包括时间资源和内存资源。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。
5.设循环队列存储空间为Q(1：50)。初始状态为front=rear=50。经过一系列入队和退队操作后，front=14，rear=19，则该循环队列中的元素个数为(D)
A. 46
B. 45
C. 6
D. 5
解析：在循环队列中，用队尾指针rear指向队列中的队尾元素，用排头指针front，指向排头元素的前一个位置。因此，从排头指针front指向的后一个位置直到队尾指针rear指向的位置之间所有的元素为队列中的元素。本题中的元素个数是从队列的索引15位置开始到索引19位置，共有5元素。选项D正确。
6.对如下图所示的二叉树，进行前序遍历的结果为
(C)
A. DYBEAFCZX
B. YDEBFZXCA
C. ABDYECFXZ
D. ABCDEFXYZ
解析：二叉树前序遍历的简单描述：若二叉树为空，则结束返回；否则：
①访问根结点；
②前序遍历左子树；
③前序遍历右子树。
可见，前序遍历二叉树的过程是一个递归的过程。根据题目中给出的二叉树的结构可知前序遍历的结果是ABDYECFXZ。
7.下列叙述中正确的是(C)
A. 线性表链式存储结构的存储空间一般要少于顺序存储结构
B. 线性表链式存储结构与顺序存储结构的存储空间都是连续的
C. 线性表链式存储结构的存储空间可以是连续的，也可以是不连续的
D. 以上都不正确
解析：线性表的存储分为顺序存储和链式存储。在顺序存储中，所有元素所占的存储空间是连续的。而在链式存储的方式中，将存储空间的每一个存储结点分为两部分，一部分用于存储数据元素的值，称为数据域；另一部分用于存储下一个元素的存储序号，称为指针域。所以线性表的链式存储方式比顺序存储方式的存储空间要大一些。
8.下列叙述中正确的是(B)
A. 栈与队列都只能顺序存储
B. 循环队列是队列的顺序存储结构
C. 循环链表是循环队列的链式存储结构
D. 以上三项均错误
解析：栈和队列是按数据的逻辑结构划分是线性结构。数据在内存或磁盘上的存储分为顺序存储结构和链式存储结构。
9.设循环队列为Q(1：m)，初始状态为front=rear=m。现经过一系列的入队与退队运算后，front=rear=1，则该循环队列中的元素个数为(D)
A. 1
B. 2
C. m-1
D. 0或m
解析：在循环队列中，用队尾指针rear指向队列中的队尾元素，用排头指针front指向排头元素的前一个位置。因此，从排头指针front指向的后一个位置直到队尾指针rear指向的位置之间，所有的元素为队列中的元素。
在循环队列动态变化过程中，当循环队列满时有front=rear，而当循环队列空时也有front=rear。即在循环队列中，当front=rear时，不能确定是队列满、还是队列空。当front=rear=1，要么队列为空，队列中的元素个数为0，要么队列为满，队列中元素个数为m。因此选项D正确。
10.某二叉树中有n个叶子结点，则该二叉树中度为2的结点数为(B)
A. n+1
B. n-1
C. 2n
D. n／2
解析：对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；N2=N0-1。所以如果二叉树中有n个叶子结点，则该二叉树中度为2的结点数为n-1。因此选项B正确。
11.某二叉树的前序序列为ABCDEFG，中序序列为DCBAEFG，则该二叉树的后序序列为(D)
A. EFGDCBA
B. DCBEFGA
C. BCDGFEA
D. DCBGFEA
解析：该二叉树的前序序列为ABCDEFG，中序序列为DCBAEFG，可知A为根结点，结点B、C、D位于根结点的左子树上，结点E、F、G位于根结点的右子树上，并且结点B、C、D在前序序列和中序序列中顺序颠倒，则说明这三个结点依次位于前一个结点的左子树上；结点E、F、G顺序未变，则说明这三个结点依次位于前一个结点的右子树上。根据以上分析，可以画出这个二叉树的形状如下：
12.下列叙述中正确的是(B)
A. 所谓算法就是计算方法
B. 程序可以作为算法的一种描述方法
C. 算法设计只需考虑得到计算结果
D. 算法设计可以忽略算法的运算时间
解析：算法是一组有穷指令集，是解题方案的准确而完整的描述。通俗地说，算法就是计算机解题的过程，重在解题方案的设计，并且不等于计算方法，故选项A和选项C不正确。
程序的编制不可能优于算法的设计，但算法的描述可以用程序、伪代码、流程图来描述，故选项B正确。算法要求执行过程中所需要的基本运算次数和时间最少，即时间复杂度最低，所以选项D错误。
13.设有二叉树如下图所示，则中序序列为
(B)
A. ABDEGC
本文档预览：3600字符，共7971字符，源文件无水印，下载后包含无答案版和有答案版，查看完整word版点下载
