国家二级ACCESS机试选择题（数据结构与算法）模拟试卷24
选择题
1.某二叉树的前序序列为ABDFHCEG，中序序列为HFDBACEG。该二叉树按层次输出(同一层从左到右)的序列为(A)
A. ABCDEFGH
B. HFDBGECA
C. HGFEDCBA
D. ACEGBDFH
解析：由于二叉树的前序序列ABDFHCEG，可以确定这个二叉树的根结点是A。再由中序序列HFDBACEG，可以得到，HFDB为A的左子树，CEG为A的右子树。同理依次对左子树HFDB和右子树CEG进行同样的推理，得到这个二叉树的结构如下：
2.某带链栈初始状态为top=bottom=NULL，经过一系列正常的入栈与退栈操作后，top=10，bottom=20。该栈中的元素个数为(A)
A. 不确定
B. 10
C. 1
D. 0
解析：对于链栈而言，使用了链表来实现栈，链表中的元素存储在不连续的地址。所以当top=10，bottom=20时，不能确定栈中的元素个数，所以选项A正确。
3.设表的长度为15。则在最坏情况下，快速排序所需要的比较次数为(A)
A. 105
B. 55
C. 15
D. 75
解析：假设线性表的长度为n，在最坏情况下，快速排序法的比较次数是n(n-1)／2。题中n=15，所以15*14／2=105。所以选项A正确。
4.设循环队列的存储空间为Q(1：100)，初始状态为空。现经过一系列正常操作后，front=49，则循环队列中的元素个数为(A)
A. 不确定
B. 49
C. 51
D. 50
解析：循环队列用数组Q[1：100]存放其元素值，己知其头尾指针分别是front和rear，则当前队列的元素个数是(rear-front+100)％100，题目中首指针rear的值未知，所以循环队列中的元素个数不能确定。所以选项A正确。
5.某完全二叉树按层次输出(同一层从左到右)的序列为ABCDEFGH。该完全二叉树的中序序列为(A)
A. HDBEAFCG
B. HDEBFGCA
C. ABDHECFG
D. ABCDEFGH
解析：完全二叉树的特点是除最后一层外，每一层上的节点数均达到最大值；在最后一层上只缺少右边的若干结点。根据上述特点，完全二叉树按层次输出(同一层从左到右)的序列为ABCDEFGH。可以得到其结构如下：
6.下列叙述中正确的是(A)
A. 解决一个问题可以有不同的算法，且它们的时间复杂度可以是不同的
B. 解决一个问题可以有不同的算法，但它们的时间复杂度必定是相同的
C. 解决一个问题的算法是唯一的
D. 算法的时间复杂度与计算机系统有关
解析：算法的时间复杂度和问题有关系，因为一个问题很有可能有许多类算法，但是它们的时间复杂度不同，如排序问题就有10种左右算法，它们复杂度显然是不一样的。所以选项A正确。
7.设表的长度为n。下列查找算法中，在最坏情况下，比较次数最少的是(A)
A. 有序表的二分查找
B. 顺序查找
C. 寻找最大项
D. 寻找最小项
解析：有序表的二分法查找只适用于顺序存储的有序表。二分查找的基本方法是：将被查元素x与线性表的中间项进行比较，若中间项的值等于x，则说明查到；若小于中间项的值则在线性表的前半部分以相同的方法进行查找：若大于中间项的值则在线性表的后半部分以相同的方法进行查找。在最坏情况下，二分查找需要比较log2n次。顺序查找、寻找最大项、寻找最小项，在最坏情况下，比较次数都是n次。所以选项A正确。
8.某带链栈的初始状态为top=bottom=NULL，经过一系列正常的入栈与退栈操作后，top=boRom=20。该栈中的元素个数为(D)
A. 1
B. 0
C. 20
D. 不确定
解析：对于链栈而言，使用了链表来实现栈，链表中的元素存储在不连续的地址。所以当top=bottom=20时，不能确定栈中的元素个数。所以选项D正确。
9.某二叉树的前序序列为ABDFHCEG，中序序列为HFDBACEG，该二叉树的后序序列为(A)
A. HFDBGECA
B. ABCDEFGH
C. HGFEDCBA
D. ACEGBDFH
解析：由于二叉树的前序序列ABDFHCEG，可以确定这个二叉树的根结点是A。再由中序序列HFDBACEG，可以得到，HFDB为A的左子树，CEG为A的右子树。同理依次对左子树HFDB和右子树CEG进行同样的推理，得到这个二叉树的结构如下：
10.下列叙述中错误的是(A)
A. 算法的时间复杂度与问题规模无关
B. 算法的时间复杂度与计算机系统无关
C. 算法的时间复杂度与空间复杂度没有必然的联系
D. 算法的空间复杂度与算法运行输出结果的数据量无关
解析：一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n)／f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))，称O(f(n))为算法的渐进时间复杂度，简称时间复杂度。所以选项A正确。
11.设表的长度为20。则在最坏情况下，冒泡排序的比较次数为(D)
A. 90
B. 20
C. 19
D. 190
解析：假设线性表的长度为n，则在最坏情况下，冒泡排序的比较次数为n(n-1)／2。本题中，n=20，所以20*19／2=190。所以选项D正确。
12.在带链栈中，经过一系列正常的操作后，如果top=bottom，则栈中的元素个数为(C)
A. 1
B. 0
C. 0或1
D. 栈满
解析：链栈就是没有附加头结点的、运算受限的单链表。栈顶指针就是链表的头指针。如果栈底指针指向的存储单元中存有1元素，则当top=bottom时，栈中的元素个数为1；如果栈底指针指向的存储单元中没有存元素，则当top=bottom时，栈中的元素个数为0。所以选项C正确。
13.设一棵树的度为3，共有27个结点，其中度为3，2，0的结点数分别为4，1，10。该树中度为1的结点数为(B)
A. 11
B. 12
C. 13
D. 不可能有这样的树
解析：因为任一棵树中，结点总数=总分支数目+1，所以：27=(0*10+n1*1+2*1+3*4)+1。运算结果n1=12。其中，n1表示叶子结点，所以选项B正确。
14.设数据结构B=(D，R)，其中
D={a，b，c，d，e，f}
R={(f，a)，(d，b)，(e，d)，(c，e)，(a，c)}
该数据结构为(A)
A. 线性结构
本文档预览：3600字符，共7512字符，源文件无水印，下载后包含无答案版和有答案版，查看完整word版点下载
