国家二级ACCESS机试选择题（数据结构与算法）模拟试卷11
选择题
1.设顺序表的长度为n。下列算法中，最坏情况下比较次数小于n的是(A)
A. 寻找最大项
B. 堆排序
C. 快速排序
D. 顺序查找法
解析：如果顺序表是线性存储的(不包括线性的链式表)，那么元素要不就是从大到小，要不就是小到大的顺序，假设第一个数就是最大值，那么需要比较1次，n-1应该是最坏情况下要比较的次数，所以选项A正确。
2.设栈的顺序存储空间为S(1：m)，初始状态为top=m+1。现经过一系列正常的入栈与退栈操作后，top=0，则栈中的元素个数为(A)
A. 不可能
B. m+1
C. 1
D. m
解析：栈是向上增长的，每次压入一个元素，栈的TOP指针向上移动一位，即top—1。对于这个题目，由于top初始值等于m+1，此时入栈一个元素，top值减1，即m+1一1=m，依次类推，当栈满时，top的值等于1，不会出现top的值等丁0。所以选项A正确。
3.某二叉树的后序遍历序列与中序遍历序列相同，均为ABCDEF，则按层次输出(同一层从左到右)的序列为(A)
A. FEDCBA
B. CBAFED
C. DEFCBA
D. ABCDEF
解析：后序遍历次序：左右根；中序遍历次序：左根右。
由定义可知：①后序遍历中最后一个是树的根结点，即F结点；②在中序遍历中，根结点左边的是左子树集，右边的是右子树集，即ABCDE是根结点F的左子树集合。问题就会转化为：求后序遍历是ABCDE，中序遍历是ABCDE的子树。方法同上，因为中序遍历中，E结点右边没有结点了，所以E结点不包含右子树，否则就会被分为2个子问题。以下是这道题的详细推理过程：步骤1：由ABCDEF得出根结点为F，由中序遍历可知：{ABCDE}F，右子树为空；步骤2：由ABCDE得出左子树集合的根节点为E，由中序可知：{ABCD}E，右子树为空；步骤3：同理，二叉树更新后如下。
4.循环队列的存储空间为Q(1：200)，初始状态为front=rear=200。经过一系列正常的入队与退队操作后，front=rear=1，则循环队列中的元素个数为(A)
A. 0或200
B. 1
C. 2
D. 199
解析：循环队列中，由于入队时尾指针rear向前追赶头指针front；出队时头指针front向前追赶尾指针rear，造成队空和队满时头尾指针均相等。因此，无法通过条件front=rear来判别队列是“空”还是“满”。对于这个题目来说，经过一系列正常的入队与退队操作后，front=rear=1，此时，要么队列为空(元素个数为0)，要么队列为满(元素个数为200)。所以选项A正确。
5.设栈的顺序存储空间为S(1：m)，初始状态为top=0。现经过一系列正常的入栈与退栈操作后，top=m+1，则栈中的元素个数为(A)
A. 不可能
B. m+1
C. 0
D. m
解析：栈是向上增长的，每次压入一个元素，栈的TOP指针向上移动一位，即top-1。对于这个题目，由于top初始值等于0，此时入栈一个元素，top值减1，即0-1=一1，出现下溢错误，所以选项A正确。
6.下列排序法中，最坏情况下时间复杂度最小的是(A)
A. 堆排序
B. 快速排序
C. 希尔排序
D. 冒泡排序
解析：假设线性表的长度为n，则在最坏情况下，冒泡排序需要经过n／2遍的从前往后扫描和n／2遍的从后往前扫描，需要比较次数为n(n-1)／2。快速排序法的最坏情况比较次数也是n(n一1)／2。简单插入排序，无论是否最坏都需要n(n—1)／2比较。堆排序，无论是否最坏情况都是比较O(nlog2n)次。所以选项A正确。
7.某二叉树的前序遍历序列与中序遍历序列相同，均为ABCDEF，则按层次输出(同一层从左到右)的序列为(A)
A. ABCDEF
B. BCDEFA
C. FEDCBA
D. DEFABC
解析：前序遍历次序：根左右；中序遍历次序：左根右。
由定义可以知道：①前序遍历中第一个就是树根结点，即A结点；②在中序遍历中，根结点左边的是左子树集，右边的是右子树集，即BCDEF是根结点A的右子树集合。问题就会转化为：求前序遍历是BCDEF，中序遍历是BCDEF的子树，方法同上。详细推理过程：步骤1：由ABCDEF得出根结点为A，由中序遍历可知：左子树为空，A{BCDEF}；步骤2：由BCDEF得出右子树集合的根节点为B，由中序可知：左子树为空，B{CDEF}：步骤3：同理，二叉树更新后如下。
8.下列叙述中正确的是(A)
A. 对数据进行压缩存储会降低算法的空间复杂度
B. 算法的优化主要通过程序的编制技巧来实现
C. 算法的复杂度与问题的规模无关
D. 数值型算法只需考虑计算结果的可靠性
解析：算法的空间复杂度是指执行这个算法所需要的内存空间，包括3个部分：输入数据所占的存储空间；程序本身所占的存储空间；算法执行过程中所需要的额外空间。为了降低算法的空间复杂度，主要应减少输入数据所占的存储空间以及额外空间，通常采用压缩存储技术，A选项正确。
9.设数据结构B=(D,R)，其中
D={a,b,c,d,e,f}
R={(a,b)，(b,c)，(c,d)，(d,e)，(e，f)，(f，a)}
该数据结构为(A)
A. 非线性结构
B. 循环队列
C. 循环链表
D. 线性结构
解析：该逻辑结构为非线性结构，在R={(a,b)，(b,c)，(c,d)，(d,e)，(e，f)，(f，a)}中，各结点之间形成一个循环链。
10.下列排序法中，每经过一次元素的交换会产生新的逆序的是(A)
A. 快速排序
B. 冒泡排序
C. 简单插入排序
D. 简单选择排序
解析：冒泡排序只交换相邻元素，但不是每次移动都产生新的逆序。简单插入排序的元素移动不会产生新的逆序。快速排序每一次交换移动都会产生新的逆序，因为当不会有新的逆序产生时，本轮比较结束。故选项A正确。
11.某带链的队列初始状态为front=rear=NULL。经过一系列正常的入队与退队操作后，front=rear=10，该队列中的元素个数为(A)
A. 1
B. 0
C. 1或0
D. 不确定
解析：循环队列用数组A[0；m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列的元素个数是(rear—front+m)％m=1，所以选项A正确。
12.某完全二叉树按层次输出(同一层从左到右)的序列为ABCDEFGH。该完全二叉树的前序序列为(A)
A. ABDHECFG
B. ABCDEFGH
C. HDBEAFCG
D. HDEBFGCA
解析：完全二叉树的特点是除最后一层外，每一层上的节点数均达到最大值；在最后一层上只缺少右边的若干结点。根据上述的特点
本文档预览：3600字符，共9017字符，源文件无水印，下载后包含无答案版和有答案版，查看完整word版点下载
