1、国家二级 ACCESS机试选择题（数据结构与算法）模拟试卷 5及答案解析(总分：60.00，做题时间：90 分钟)一、选择题(总题数：30，分数：60.00)1.设顺序表的长度为 n。下列算法中，最坏情况下比较次数小于 n的是（分数：2.00）A.寻找最大项B.堆排序C.快速排序D.顺序查找法2.设栈的顺序存储空间为 S(1：m)，初始状态为 top=m+1。现经过一系列正常的入栈与退栈操作后，top=0；则栈中的元素个数为（分数：2.00）A.不可能B.m+1C.1D.m3.某二叉树的后序遍历序列与中序遍历序列相同，均为 ABCDEF，则按层次输出(同一层从左到右)的序列为（分数：2.00）
2、A.FEDCBAB.CBAFEDC.DEFCBAD.ABCDEF4.循环队列的存储空间为 Q(1：200)，初始状态为 front=rear=200。经过一系列正常的入队与退队操作后，front=rear=1，则循环队列中的元素个数为（分数：2.00）A.0或 200B.1C.2D.1995.设栈的顺序存储空间为 S(1：m)，初始状态为 top=0。现经过一系列正常的入栈与退栈操作后，top=m+1，则栈中的元素个数为（分数：2.00）A.不可能B.m+1C.0D.m6.下列排序法中，最坏情况下时间复杂度最小的是（分数：2.00）A.堆排序B.快速排序C.希尔排序D.冒泡排序7.某二叉树的前
3、序遍历序列与中序遍历序列相同，均为 ABCDEF，则按层次输出(同一层从左到右)的序列为（分数：2.00）A.ABCDEFB.BCDEFAC.FEDCBAD.DEFABC8.下列叙述中正确的是（分数：2.00）A.对数据进行压缩存储会降低算法的空间复杂度B.算法的优化主要通过程序的编制技巧来实现C.算法的复杂度与问题的规模无关D.数值型算法只需考虑计算结果的可靠性9.设数据结构 B=(D，R)，其中 D=a，b，c，d，e，D R=(a,b)，(b,c)，(c,(d)，(d,e)，(e，D，(f,(a)该数据结构为（分数：2.00）A.非线性结构B.循环队列C.循环链表D.线性结构10.下列排
4、序法中，每经过一次元素的交换会产生新的逆序的是（分数：2.00）A.快速排序B.冒泡排序C.简单插入排序D.简单选择排序11.某带链的队列初始状态为 front=rear=NULL。经过一系列正常的入队与退队操作后，front=rear=10。该队列中的元素个数为（分数：2.00）A.1B.0C.1或 0D.不确定12.某完全二叉树按层次输出(同一层从左到右)的序列为 ABCDEFGH。该完全二叉树的前序序列为（分数：2.00）A.ABDHECFGB.ABCDEFGHC.HDBEAFCGD.HDEBFGCA13.下列叙述中正确的是（分数：2.00）A.有的二叉树也能用顺序存储结构表示B.有两个
5、指针域的链表就是二叉链表C.多重链表一定是非线性结构D.顺序存储结构一定是线性结构14.下列各排序法中，最坏情况下时间复杂度最小的是（分数：2.00）A.堆排序B.快速排序C.希尔排序D.冒泡排序15.某带链队列初始状态为 front=rear=NULL。经过一系列正常入队与退队操作后，front=10，rear=5。该队列中的元素个数为（分数：2.00）A.不确定B.5C.4D.616.某二叉树的前序序列为 ABDFHCEG，中序序列为 HFDBACEG。该二叉树按层次输出(同一层从左到右)的序列为（分数：2.00）A.ABCDEFGHB.HFDBGECAC.HGFEDCBAD.ACEGBD
6、FH17.某带链栈初始状态为 top=bottom=NULL，经过一系列正常的入栈与退栈操作后，top=10，bottom=20，该栈中的元素个数为（分数：2.00）A.不确定B.10C.1D.018.设表的长度为 15。则在最坏情况下，快速排序所需要的比较次数为（分数：2.00）A.105B.55C.15D.7519.设循环队列的存储空间为 Q(1：100)，初始状态为空。现经过一系列正常操作后，front=49，则循环队列中的元素个数为（分数：2.00）A.不确定B.49C.51D.5020.某完全二叉树按层次输出(同一层从左到右)的序列为 ABCDEFGH。该完全二叉树的中序序列为（分数
7、：2.00）A.HDBEAFCGB.HDEBFGCAC.ABDHECFGD.ABCDEFGH21.下列叙述中正确的是（分数：2.00）A.解决一个问题可以有不同的算法，且它们的时间复杂度可以是不同的B.解决一个问题可以有不同的算法，但它们的时间复杂度必定是相同的C.解决一个问题的算法是唯一的D.算法的时间复杂度与计算机系统有关22.设表的长度为 n。下列查找算法中，在最坏情况下，比较次数最少的是（分数：2.00）A.有序表的二分查找B.顺序查找C.寻找最大项D.寻找最小项23.某带链栈的初始状态为 top=bottom=NULL，经过一系列正常的入栈与退栈操作后，top=bottom=20。该
8、栈中的元素个数为（分数：2.00）A.1B.0C.20D.不确定24.某二叉树的前序序列为 ABDFHCEG，中序序列为 HFDBACEG。该二叉树的后序序列为（分数：2.00）A.HFDBGECAB.ABCDEFGHC.HGFEDCBAD.ACEGBDFH25.下列叙述中错误的是（分数：2.00）A.算法的时间复杂度与问题规模无关B.算法的时间复杂度与计算机系统无关C.算法的时间复杂度与空间复杂度没有必然的联系D.算法的空间复杂度与算法运行输出结果的数据量无关26.设表的长度为 20。则在最坏情况下，冒泡排序的比较次数为（分数：2.00）A.90B.20C.19D.19027.在带链栈中，经
9、过一系列正常的操作后，如果 top=bosom，则栈中的元素个数为（分数：2.00）A.1B.0C.0或 ID.栈满28.设一棵树的度为 3，共有 27个结点，其中度为 3，2，0 的结点数分别为 4，1，10。该树中度为 l的结点数为（分数：2.00）A.1 1B.12C.13D.不可能有这样的树29.设数据结构 B=(D，R)，其中 D=a，b，c，d，e，fR=(f，(a)，(d,b)，(e,(d)，(c,e)，(a，c)该数据结构为（分数：2.00）A.线性结构B.循环队列C.循环链表D.非线性结构30.下列叙述中错误的是（分数：2.00）A.循环队列空的条件是队头指针与队尾指针相同B
10、.若二叉树没有叶子结点，则为空二叉树C.带链栈的栈底指针是随栈的操作而动态变化的D.若带链队列中只有一个元素，则队头指针与队尾指针必定相同国家二级 ACCESS机试选择题（数据结构与算法）模拟试卷 5答案解析(总分：60.00，做题时间：90 分钟)一、选择题(总题数：30，分数：60.00)1.设顺序表的长度为 n。下列算法中，最坏情况下比较次数小于 n的是（分数：2.00）A.寻找最大项 B.堆排序C.快速排序D.顺序查找法解析：解析：如果顺序表是线性存储的(不包括线性的链式表)，那么元素要不就是从大到小，要不就是小到大的顺序，假设第一个数就是最大值，那么需要比较 1次，n 一 1应该是最
11、坏情况下要比较的次数，所以选项 A正确。2.设栈的顺序存储空间为 S(1：m)，初始状态为 top=m+1。现经过一系列正常的入栈与退栈操作后，top=0；则栈中的元素个数为（分数：2.00）A.不可能 B.m+1C.1D.m解析：解析：栈是向上增长的，每次压入一个元素，栈的 TOP指针向上移动一位，即 top-1。对于这个题目，由于 top初始值等于 m+1，此时入栈一个元素，top 值减 1，即 m+1-1=m，依次类推，当栈满时，top的值等于 1，不会出现 top的值等于 0。所以选项 A正确。3.某二叉树的后序遍历序列与中序遍历序列相同，均为 ABCDEF，则按层次输出(同一层从左到
12、右)的序列为（分数：2.00）A.FEDCBA B.CBAFEDC.DEFCBAD.ABCDEF解析：解析：后序遍历次序：左右根；中序遍历次序：左根右。由定义可知：后序遍历中最后一个是树的根结点，即 F结点；在中序遍历中，根结点左边的是左子树集，右边的是右子树集，即 ABCDE是根结点 F的左子树集合。问题就会转化为：求后序遍历是 ABC。DE，中序遍历是 ABCDE的子树。方法同上，因为中序遍历中，E 结点右边没有结点了，所以 E结点不包含右子树，否则就会被分为 2个子问题。以下是这道题的详细推理过程：步骤 1：由 ABCDEF。得出根结点为 F，由中序遍历可知：ABCDEF，右子树为空；步
13、骤 2：由 ABCDE得出左子树集合的根节点为 E，由中序可知：ABCDE，右子树为空；步骤 3：同理，二叉树更新后如下。4.循环队列的存储空间为 Q(1：200)，初始状态为 front=rear=200。经过一系列正常的入队与退队操作后，front=rear=1，则循环队列中的元素个数为（分数：2.00）A.0或 200 B.1C.2D.199解析：解析：循环队列中，由于入队时尾指针 rear向前追赶头指针 front；出队时头指针 front向前追赶尾指针 rear，造成队空和队满时头尾指针均相等。因此，无法通过条件 front=rear来判别队列是“空”还是“满”。对于这个题目来说，经
14、过一系列正常的入队与退队操作后，front=rear=1，此时，要么队列为空(元素个数为 0)，要么队列为满(元素个数为 200)。所以选项 A正确。5.设栈的顺序存储空间为 S(1：m)，初始状态为 top=0。现经过一系列正常的入栈与退栈操作后，top=m+1，则栈中的元素个数为（分数：2.00）A.不可能 B.m+1C.0D.m解析：解析：栈是向上增长的，每次压入一个元素，栈的 TOP指针向上移动一位，即 top-1。对于这个题目，由于 top初始值等于 0，此时入栈一个元素，top 值减 1，即 01=-1，出现下溢错误，所以选项 A正确。6.下列排序法中，最坏情况下时间复杂度最小的是
15、（分数：2.00）A.堆排序 B.快速排序C.希尔排序D.冒泡排序解析：解析：假设线性表的长度为 n，则在最坏情况下，冒泡排序需要经过 n2 遍的从前往后扫描和n2 遍的从后往前扫描，需要比较次数为 n(n1)2。快速排序法的最坏情况比较次数也是 n(n-1)2。简单插入排序，无论是否最坏都需要 n(n一 1)2 比较。堆排序，无论是否最坏情况都是比较O(nlog 2 n)次。所以选项 A正确。7.某二叉树的前序遍历序列与中序遍历序列相同，均为 ABCDEF，则按层次输出(同一层从左到右)的序列为（分数：2.00）A.ABCDEF B.BCDEFAC.FEDCBAD.DEFABC解析：解析：前
16、序遍历次序：根左右；中序遍历次序：左根右。由定义可以知道：前序遍历中第一个就是树根结点，即 A结点；在中序遍历中，根结点左边的是左子树集，右边的是右子树集，即 BCDEF是根结点 A的右子树集合。问题就会转化为：求前序遍历是 BCDEF，中序遍历是 BCDEF的子树，方法同上。详细推理过程： 步骤 1：由 ABCDEF得出根结点为 A，由中序遍历可知：左子树为空，ABCDE F； 步骤2：由 BCDEF得出右子树集合的根节点为 B，由中序可知：左子树为空，BCDEF； 步骤 3：同理，二叉树更新后如下。8.下列叙述中正确的是（分数：2.00）A.对数据进行压缩存储会降低算法的空间复杂度 B.算
17、法的优化主要通过程序的编制技巧来实现C.算法的复杂度与问题的规模无关D.数值型算法只需考虑计算结果的可靠性解析：解析：算法的空间复杂度是指执行这个算法所需要的内存空间，包括 3个部分：输入数据所占的存储空间；程序本身所占的存储空间；算法执行过程中所需要的额外空间。为了降低算法的空间复杂度，主要应减少输入数据所占的存储空间以及额外空间，通常采用压缩存储技术，A 选项正确。9.设数据结构 B=(D，R)，其中 D=a，b，c，d，e，D R=(a,b)，(b,c)，(c,(d)，(d,e)，(e，D，(f,(a)该数据结构为（分数：2.00）A.非线性结构 B.循环队列C.循环链表D.线性结构解析
18、：解析：该逻辑结构为非线性结构，在 R=(a,b)，(b,c)，(c,d)，(d,e)，(e,f)，(f,a)中，各结点之间形成一个循环链。10.下列排序法中，每经过一次元素的交换会产生新的逆序的是（分数：2.00）A.快速排序 B.冒泡排序C.简单插入排序D.简单选择排序解析：解析：冒泡排序只交换相令昏元素，但不是每次移动都产生新韵逆序。简单插入排序的元素移动不会产生新的逆序。快速排序每一次交换移动都会产生新的逆序，因为当不会有新的逆序产生时，本轮比较结束。故选项 A正确。11.某带链的队列初始状态为 front=rear=NULL。经过一系列正常的入队与退队操作后，front=rear=1
19、0。该队列中的元素个数为（分数：2.00）A.1 B.0C.1或 0D.不确定解析：解析：循环队列用数组 A0；m-1存放其元素值，已知其头尾指针分别是 front和 rear，则当前队列的元素个数是(rear-front+m)m=1，所以选项 A正确。12.某完全二叉树按层次输出(同一层从左到右)的序列为 ABCDEFGH。该完全二叉树的前序序列为（分数：2.00）A.ABDHECFG B.ABCDEFGHC.HDBEAFCGD.HDEBFGCA解析：解析：完全二叉树的特点是除最后一层外，每一层上的节点数均达到最大值；在最后一层上只缺少右边的若干结点。根据上述的特点，完全二叉树按层次输出(同
20、一层从左到右)的序列为 ABCDEFGH，可以得到其结构如下：13.下列叙述中正确的是（分数：2.00）A.有的二叉树也能用顺序存储结构表示 B.有两个指针域的链表就是二叉链表C.多重链表一定是非线性结构D.顺序存储结构一定是线性结构解析：解析：完全二叉树如果“根”从 1开始编号，则第 i结点的左孩子编号为 2i，右孩子为 2i+1，双亲编号为(i2)下取整，空间紧密，适合顺序存储结构。所以选项 A正确。小提示：取整是指取不超过实数 x的最大整数，称为 x的整数部分。上取整就是对实数取大于当前实数的第一个整数；下取整就是对当前实数去掉小数取整。14.下列各排序法中，最坏情况下时间复杂度最小的是
21、（分数：2.00）A.堆排序 B.快速排序C.希尔排序D.冒泡排序解析：解析：快速排序、冒泡排序最坏情况下时间复杂度是 O(n 2 )：希尔排序最坏情况下时间复杂度是O(n 1.2 )。堆排序最坏情况下时间复杂度是 O(nlog 2 n)，所以选项 A正确。15.某带链队列初始状态为 front=rear=NULL。经过一系列正常入队与退队操作后，front=10，rear=5。该队列中的元素个数为（分数：2.00）A.不确定 B.5C.4D.6解析：解析：循环队列用数组 A0：m-1存放其元素值，己知其头尾指针分别是 front和 rear，则当前队列的元素个数是(rear-front+m)
22、m=(5-10+m)m=(m-5)m。因为本题中的 m值不确定，所以(m-5)m的值不能确定。所以选项 A正确。16.某二叉树的前序序列为 ABDFHCEG，中序序列为 HFDBACEG。该二叉树按层次输出(同一层从左到右)的序列为（分数：2.00）A.ABCDEFGH B.HFDBGECAC.HGFEDCBAD.ACEGBDFH解析：解析：由于二叉树的前序序列 ABDFHCEG，可以确定这个二叉树的根结点是 A。再由中序序列HFDBACEG，可以得到，HFDB 为 A的左子树，CEG 为 A的右子树。同理依次对左子树 HFDB和右子树 CEG进行同样的推理，得到这个二叉树的结构如下17.某带
23、链栈初始状态为 top=bottom=NULL，经过一系列正常的入栈与退栈操作后，top=10，bottom=20，该栈中的元素个数为（分数：2.00）A.不确定 B.10C.1D.0解析：解析：对于链栈而言，使用了链表来实现栈，链表中的元素存储在不连续的地址。所以当top=10，bottom=20 时，不能确定栈中的元素个数，所以选项 A正确。18.设表的长度为 15。则在最坏情况下，快速排序所需要的比较次数为（分数：2.00）A.105 B.55C.15D.75解析：解析：假设线性表的长度为 n，在最坏情况下，快速排序法的比较次数是 n(n-1)2。题中 n=15，所以 15*142=10
24、5。所以选项 A正确。19.设循环队列的存储空间为 Q(1：100)，初始状态为空。现经过一系列正常操作后，front=49，则循环队列中的元素个数为（分数：2.00）A.不确定 B.49C.51D.50解析：解析：循环队列用数组 Q1：100存放其元素值，已知其头尾指针分别是 front和 rear，则当前队列的元素个数是(rearfront+100)100，题目中首指针 rear的值未知，所以循环队列中的元素个数不能确定。所以选项 A正确。20.某完全二叉树按层次输出(同一层从左到右)的序列为 ABCDEFGH。该完全二叉树的中序序列为（分数：2.00）A.HDBEAFCG B.HDEBF
25、GCAC.ABDHECFGD.ABCDEFGH解析：解析：完全二叉树的特点是除最后一层外，每一层上的节点数均达到最大值：在最后一层上只缺少右边的若干结点。根据上述特点，完全二叉树按层次输出(同一层从左到右)的序列为 ABCDEFGH。可以得到其结构如下：21.下列叙述中正确的是（分数：2.00）A.解决一个问题可以有不同的算法，且它们的时间复杂度可以是不同的 B.解决一个问题可以有不同的算法，但它们的时间复杂度必定是相同的C.解决一个问题的算法是唯一的D.算法的时间复杂度与计算机系统有关解析：解析：算法的时间复杂度和问题有关系，因为一个问题很有可能有许多类算法，但是它们的时间复杂度不同，如排序
26、问题就有 10种左右算法，它们复杂度显然是不一样的。所以选项 A正确。22.设表的长度为 n。下列查找算法中，在最坏情况下，比较次数最少的是（分数：2.00）A.有序表的二分查找 B.顺序查找C.寻找最大项D.寻找最小项解析：解析：有序表的二分法查找只适用于顺序存储的有序表。二分查找的基本方法是：将被查元素 x与线性表的中间项进行比较，若中间项的值等于 x，则说明查到；若小于中间项的值则在线性表的前半部分以相同的方法进行查找；若大于中间项的值则在线性表的后半部分以相同的方法进行查找。在最坏情况下，二分查找需要比较 log 2 n次。顺序查找、寻找最大项、寻找最小项，在最坏情况下，比较次数都是
27、n次。所以选项 A正确。23.某带链栈的初始状态为 top=bottom=NULL，经过一系列正常的入栈与退栈操作后，top=bottom=20。该栈中的元素个数为（分数：2.00）A.1B.0C.20D.不确定 解析：解析：对于链栈而言，使用了链表来实现栈，链表中的元素存储在不连续的地址。所以当top=bottom=20时，不能确定栈中的元素个数。所以选项 D正确。24.某二叉树的前序序列为 ABDFHCEG，中序序列为 HFDBACEG。该二叉树的后序序列为（分数：2.00）A.HFDBGECA B.ABCDEFGHC.HGFEDCBAD.ACEGBDFH解析：解析：由于二叉树的前序序列
28、ABDFHCEG，可以确定这个二叉树的根结点是 A。再由中序序列HFDBACEG，可以得到，HFDB 为 A的左子树，CEG 为 A的右子树子同理依次对左子树。HFDB 和右子树 CEG进行同样的推理，得到这个二叉树的结构如下：25.下列叙述中错误的是（分数：2.00）A.算法的时间复杂度与问题规模无关 B.算法的时间复杂度与计算机系统无关C.算法的时间复杂度与空间复杂度没有必然的联系D.算法的空间复杂度与算法运行输出结果的数据量无关解析：解析：一般情况下，算法中基本操作重复执行的次数是问题规模 n的某个函数，用 T(n)表示，若有某个辅助函数 f(n)，使得当 n趋近于无穷大时，T(n)f(
29、n)的极限值为不等于零的常数，则称 f(n)是T(n)的同数量级函数。记作 T(n)=O(f(n)，称 O(f(n)为算法的渐进时间复杂度，简称时间复杂度。所以选项 A正确。26.设表的长度为 20。则在最坏情况下，冒泡排序的比较次数为（分数：2.00）A.90B.20C.19D.190 解析：解析：假设线性表的长度为 n，则在最坏情况下，冒泡排序的比较次数为 n(n一 1)2。本题中，n=20，所以 20*192=190。所以选项 D正确。27.在带链栈中，经过一系列正常的操作后，如果 top=bosom，则栈中的元素个数为（分数：2.00）A.1B.0C.0或 I D.栈满解析：解析：链栈
30、就是没有附加头结点的、运算受限的单链表。栈顶指针就是链表的头指针。如果栈底，指针指向的存储单元中存有 1元素，则当 top=bottom时，栈中的元素个数为 1；如果栈底指针指向的存储单元中没有存元素，则当 top=bottom时，栈中的元素个数为 0。所以选项 C正确。28.设一棵树的度为 3，共有 27个结点，其中度为 3，2，0 的结点数分别为 4，1，10。该树中度为 l的结点数为（分数：2.00）A.1 1B.12 C.13D.不可能有这样的树解析：解析：因为任一棵树中，结点总数：总分支数目+1，所以：27=(0*10+n 1 *1+2*1+3*4)+1。运算结果 n 1 =12。其
31、中，n 1 表示叶子结点，所以选项 B正确。29.设数据结构 B=(D，R)，其中 D=a，b，c，d，e，fR=(f，(a)，(d,b)，(e,(d)，(c,e)，(a，c)该数据结构为（分数：2.00）A.线性结构 B.循环队列C.循环链表D.非线性结构解析：解析：由结点之间的关系 R=(f,a)，(d,b)，(e,d)，(c,e)，(a,c)可以得到，该数据结构为：“fa-c-e-d-b”。由此可知结点 f没有前驱，结点 b没有后继结点，并且其它的结点只有一个前驱结点和一个后继结点，所以该数据结构为线性结构。所以应选 A选项。30.下列叙述中错误的是（分数：2.00）A.循环队列空的条件
32、是队头指针与队尾指针相同 B.若二叉树没有叶子结点，则为空二叉树C.带链栈的栈底指针是随栈的操作而动态变化的D.若带链队列中只有一个元素，则队头指针与队尾指针必定相同解析：解析：初始化建空队时，令 front=rear=0，当队空时：front=rear；当队满时：front=rear 亦成立。因此，只凭等式 front=rear无法判断队空还是队满。有两种方法处理上述问题：另设一个标志位以区别队列是空还是满；少用一个元素空间，约定以“队列头指针 front在队尾指针 rear的下一个位置上”作为队列“满”状态的标志。即：队空时：front=rear；队满时：(rear+1)maxsize=front。所以选项 A正确。
