国家二级ACCESS机试选择题（数据结构与算法）模拟试卷17
选择题
1.设数据结构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)}中，各结点之间形成一个循环链。
2.下列排序法中，每经过一次元素的交换会产生新的逆序的是(A)
A. 快速排序
B. 冒泡排序
C. 简单插入排序
D. 简单选择排序
解析：冒泡排序只交换相邻元素，但不是每次移动都产生新的逆序。简单插入排序的元素移动不会产生新的逆序。快速排序每一次交换移动都会产生新的逆序，因为当不会有新的逆序产生时，本轮比较结束。故选项A正确。
3.某带链的队列初始状态为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正确。
4.某完全二叉树按层次输出(同一层从左到右)的序列为ABCDEFGH。该完全二叉树的前序序列为(A)
A. ABDHECFG
B. ABCDEFGH
C. HDBEAFCG
D. HDEBFGCA
解析：完全二叉树的特点是除最后一层外，每一层上的节点数均达到最大值；在最后一层上只缺少右边的若干结点。根据上述的特点，完全二叉树按层次输出(同一层从左到右)的序列为ABCDEFGH，可以得到其结构如下：
5.下列叙述中正确的是(A)
A. 有的二叉树也能用顺序存储结构表示
B. 有两个指针域的链表就是二叉链表
C. 多重链表一定是非线性结构
D. 顺序存储结构一定是线性结构
解析：完全二叉树如果“根”从1开始编号，则第i结点的左孩子编号为2i，右孩子为2i+1，双亲编号为(i／2)下取整，空间紧密．适合顺序存储结构。所以选项A正确。
小提示：取整是指取不超过实数x的最大整数，称为x的整数部分。上取整就是对实数取大于当前实数的第一个整数：下取整就足对当前实数去掉小数取整。
6.下列各排序法中，最坏情况下时间复杂度最小的是(A)
A. 堆排序
B. 快速排序
C. 希尔排序
D. 冒泡排序
解析：快速排序、冒泡排序最坏情况下时间复杂度是o(n2)；希尔排序最坏情况下时间复杂度是0(n1．2)。堆排序最坏情况下时间复杂度是O(nlog2n)，所以选项A正确。
7.某带链队列初始状态为front=rear=NULL。经过一系列正常入队与退队操作后，front=10，rear=5。该队列中的元素个数为(A)
A. 不确定
B. 5
C. 4
D. 6
解析：循环队列用数组A[0：m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列的元素个数是(rear-front+m)％m=(5-10+In)％m=(m-5)％m。因为本题中的m值不确定，所以(m-5)％m的值不能确定。所以选项A正确。
8.某二叉树的前序序列为ABDFHCEG，中序序列为HFDBACEG。该二叉树按层次输出(同一层从左到右)的序列为(A)
A. ABCDEFGH
B. HFDBGECA
C. HGFEDCBA
D. ACEGBDFH
解析：由于二叉树的前序序列ABDFHCEG，可以确定这个二叉树的根结点是A。再由中序序列HFDBACEG，可以得到，HFDBt为A的左子树，CEG为A的右子树。同理依次对左子树HFDB和右子树CEG进行同样的推理，得到这个二叉树的结构如下：
9.某带链栈初始状态为top=bottom=NULL，经过一系列正常的入栈与退栈操作后，top=10，bottom=20。该栈中的元素个数为(A)
A. 不确定
B. 10
C. 1
D. 0
解析：对于链栈而言，使用了链表来实现栈，链表中的元素存储在不连续的地址。所以当top=10，bottom=20时，不能确定栈中的元素个数，所以选项A正确。
10.设表的长度为15。则在最坏情况下，快速排序所需要的比较次数为(A)
A. 105
B. 55
C. 15
D. 75
解析：假设线性表的长度为n，在最坏情况下，快速排序法的比较次数是n(n-1)／2。题中n=15，所以15*14／2=105。所以选项A正确。
11.设循环队列的存储空间为Q(1：100)，初始状态为空。现经过一系列正常操作后，front=49，则循环队列中的元素个数为(A)
A. 不确定
B. 49
C. 51
D. 50
解析：循环队列用数组Q[1：100]存放其元素值，已知其头尾指针分别是front和rear，则当前队列的元素个数是(rear-front+100)％100，题目中首指针rear的值未知，所以循环队列中的元素个数不能确定。所以选项A正确。
12.某完全二叉树按层次输出(同一层从左到右)的序列为ABCDEFGH。该完全二叉树的中序序列为(A)
A. HDBEAFCG
B. HDEBFGCA
C. ABDHECFG
D. ABCDEFGH
解析：完全二叉树的特点是除最后一层外，每一层上的节点数均达到最大值；在最后一层上只缺少右边的若干结点。根据上述特点，完全二叉树按层次输出(同一层从左到右)的序列为ABCDEFGH。可以得到其结构如下：
13.下列叙述中正确的是(A)
A. 解决一个问题可以有不同的算法，且它们的时间复杂度可以是不同的
B. 解决一个问题可以有不同的算法，但它们的时间复杂度必定是相同的
C. 解决一个问题的算法是唯一的
D. 算法的时间复杂度与计算机系统有关
解析：算法的时间复杂度和问题有关系，因为一个问题很有可能有许多类算法，但是它们的时间复杂度不同，如排序问题就有10种左右算法，它们复杂度显然是不一样的。所以选项A正确。
14.设表的长度为n。下列查找算法中，在最坏情况下，比较次数最少的是(A)
A. 有序表的二分查找
B. 顺序查找
C. 寻找最大项
D. 寻找最小项
解析：有序表的二分法查找只适用
本文档预览：3600字符，共8838字符，源文件无水印，下载后包含无答案版和有答案版，查看完整word版点下载
