国家二级ACCESS机试选择题(数据结构与算法)模拟试卷5

国家二级ACCESS机试选择题（数据结构与算法）模拟试卷5(总分：60.00，做题时间：90分钟)一、选择题(总题数：30，分数：60.00)1.设顺序表的长度为n。下列算法中，最坏情况下比较次数小于n的是（分数：2.00）A.寻找最大项√B.堆排序C.快速排序D.顺序查找法解析：解析：如果顺序表是线性存储的(不包括线性的链式表)，那么元素要不就是从大到小，要不就是小到大的顺序，假设第一个数就是最大值，那么需要比较1次，n一1应该是最坏情况下要比较的次数，所以选项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，则按层次输出(同一层从左到右)的序列为（分数：2.00）A.FEDCBA√B.CBAFEDC.DEFCBAD.ABCDEF解析：解析：后序遍历次序：左右根；中序遍历次序：左根右。由定义可知：①后序遍历中最后一个是树的根结点，即F结点；②在中序遍历中，根结点左边的是左子树集，右边的是右子树集，即ABCDE是根结点F的左子树集合。问题就会转化为：求后序遍历是ABC。DE，中序遍历是ABCDE的子树。方法同上，因为中序遍历中，E结点右边没有结点了，所以E结点不包含右子树，否则就会被分为2个子问题。以下是这道题的详细推理过程：步骤1：由ABCDEF。得出根结点为F，由中序遍历可知：{ABCDE}F，右子树为空；步骤2：由ABCDE得出左子树集合的根节点为E，由中序可知：{ABCD}E，右子树为空；步骤3：同理，二叉树更新后如下。所以按层次输出(同一层从左到右)的序列为FEDCBA。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来判别队列是“空”还是“满”。对于这个题目来说，经过一系列正常的入队与退队操作后，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，即0．1=-1，出现下溢错误，所以选项A正确。6.下列排序法中，最坏情况下时间复杂度最小的是（分数：2.00）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，则按层次输出(同一层从左到右)的序列为（分数：2.00）A.ABCDEF√B.BCDEFAC.FEDCBAD.DEFABC解析：解析：前序遍历次序：根左右；中序遍历次序：左根右。由定义可以知道：①前序遍历中第一个就是树根结点，即A结点；②在中序遍历中，根结点左边的是左子树集，右边的是右子树集，即BCDEF是根结点A的右子树集合。问题就会转化为：求前序遍历是BCDEF，中序遍历是BCDEF的子树，方法同上。详细推理过程：步骤1：由ABCDEF得出根结点为A，由中序遍历可知：左子树为空，A{BCDEF}；步骤2：由BCDEF得出右子树集合的根节点为B，由中序可知：左子树为空，B{CDEF}；步骤3：同理，二叉树更新后如下。所以按层次输出(同一层从左到右)的序列为ABCDEF，选项A正确。8.下列叙述中正确的是（分数：2.00）A.对数据进行压缩存储会降低算法的空间复杂度√B.算法的优化主要通过程序的编制技巧来实现C.算法的复杂度与问题的规模无关D.数值型算法只需考虑计算结果的可靠性解析：解析：算法的空间复杂度是指执行这个算法所需要的内存空间，包括3个部分：输入数据所占的存储空间；程序本身所占的存储空间；算法执行过程中所需要的额外空间。为了降低算法的空间复杂度，主要应减少输入数据所占的存储空间以及额外空间，通常采用压缩存储技术，A选项正确。9.设数据结构B=(D，R)，其中D={a，b，c，d，e，DR={(a,b)，(b,c)，(c,(d)，(d,e)，(e，D，(f,(a)}该数据结构为（分数：2.00）A.非线性结构√B.循环队列C.循环链表D.线性结构解析：解析：该逻辑结构为非线性结构，在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=10。该队列中的元素个数为（分数：2.00）A.1√B.0C.1或0D.不确定解析：解析：循环队列用数组A[0；m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列的元素个数是(rear-front+m)％m=1，所以选项A正确。12.某完全二叉树按层次输出(同一层从左到右)的序列为ABCDEFGH。该完全二叉树的前序序列为（分数：2.00）A.ABDHECFG√B.ABCDEFGHC.HDBEAFCGD.HDEBFGCA解析：解析：完全二叉树的特点是除最后一层外，每一层上的节点数均达到最大值；在最后一层上只缺少右边的若干结点。根据上述的特点，完全二叉树按层次输出(同一层从左到右)的序列为ABCDEFGH，可以得到其结构如下：所以此完全二叉树的前序序列是ABDHECFG，选项A正确。13.下列叙述中正确的是（分数：2.00）A.有的二叉树也能用顺序存储结构表示√B.有两个指针域的链表就是二叉链表C.多重链表一定是非线性结构D.顺序存储结构一定是线性结构解析：解析：完全二叉树如果“根”从1开始编号，则第i结点的左孩子编号为2i，右孩子为2i+1，双亲编号为(i／2)下取整，空间紧密，适合顺序存储结构。所以选项A正确。小提示：取整是指取不超过实数x的最大整数，称为x的整数部分。上取整就是对实数取大于当前实数的第一个整数；下取整就是对当前实数去掉小数取整。14.下列各排序法中，最坏情况下时间复杂度最小的是（分数：2.00）A.堆排序√B.快速排序C.希尔排序D.冒泡排序解析：解析：快速排序、冒泡排序最坏情况下时间复杂度是O(n2)：希尔排序最坏情况下时间复杂度是O(n1.2)。堆排序最坏情况下时间复杂度是O(nlog2n)，所以选项A正确。15.某带链队列初始状态为front=rear=NULL。经过一系列正常入队与退队操作后，front=10，rear=5。该队列中的元素个数为（分数：2.00）A.不确定√B.5C.4D.6解析：解析：循环队列用数组A[0：m-1]存放其元素值，己知其头尾指针分别是front和rear，则当前队列的元素个数是(rear-front+m)％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进行同样的推理，得到这个二叉树的结构如下ABCDEFGH，所以选项A正确。该二叉树按层次输出(同一层从左到右)的序列为17.某带链栈初始状态为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*14／2=105。所以选项A正确。19.设循环队列的存储空间为Q(1：100)，初始状态为空。现经过一系列正常操作后，front=49，则循环队列中的元素个数为（分数：2.00）A.不确定√B.49C.51D.50解析：解析：循环队列用数组Q[1：100]存放其元素值，已知其头尾指针分别是front和rear，则当前队列的元素个数是(rear—front+100)％100，题目中首指针rear的值未知，所以循环队列中的元素个数不能确定。所以选项A正确。20.某完全二叉树按层次输出(同一层从左到右)的序列为ABCDEFGH。该完全二叉树的中序序列为（分数：2.00）A.HDBEAFCG√B.HDEBFGCAC.ABDHECFGD.ABCDEFGH解析：解析：完全二叉树的特点是除最后一层外，每一层上的节点数均达到最大值：在最后一层上只缺少右边的若干结点。根据上述特点，完全二叉树按层次输出(同一层从左到右)的序列为ABCDEFGH。可以得到其结构如下：所以此完全二叉树的中序序列是HDBEAFCG。所以选项A正确。21.下列叙述中正确的是（分数：2.00）A.解决一个问题可以有不同的算法，且它们的时间复杂度可以是不同的√B.解决一个问题可以有不同的算法，但它们的时间复杂度必定是相同的C.解决一个问题的算法是唯一的D.算法的时间复杂度与计算机系统有关解析：解析：算法的时间复杂度和问题有关系，因为一个问题很有可能有许多类算法，但是它们的时间复杂度不同，如排序问题就有10种左右算法，它们复杂度显然是不一样的。所以选项A正确。22.设表的长度为n。下列查找算法中，在最坏情况下，比较次数最少的是（分数：2.00）A.有序表的二分查找√B.顺序查找C.寻找最大项D.寻找最小项解析：解析：有序表的二分法查找只适用于顺序存储的有序表。二分查找的基本方法是：将被查元素x与线性表的中间项进行比较，若中间项的值等于x，则说明查到；若小于中间项的值则在线性表的前半部分以相同的方法进行查找；若大于中间项的值则在线性表的后半部分以相同的方法进行查找。在最坏情况下，二分查找需要比较log2n次。顺序查找、寻找最大项、寻找最小项，在最坏情况下，比较次数都是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解析：解析：由于二叉树的前序序列ABDFHCEG，可以确定这个二叉树的根结点是A。再由中序序列HFDBACEG，可以得到，HFDB为A的左子树，CEG为A的右子树子同理依次对左子树。HFDB和右子树CEG进行同样的推理，得到这个二叉树的结构如下：以选项A正确。对该二叉树的后序遍历序列为HFDBGECA，所25.下列叙述中错误的是（分数：2.00）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正确。26.设表的长度为20。则在最坏情况下，冒泡排序的比较次数为（分数：2.00）A.90B.20C.19D.190√解析：解析：假设线性表的长度为n，则在最坏情况下，冒泡排序的比较次数为n(n一1)／2。本题中，n=20，所以20*19／2=190。所以选项D正确。27.在带链栈中，经过一系列正常的操作后，如果top=bosom，则栈中的元素个数为（分数：2.00）A.1B.0C.0或I√D.栈满解析：解析：链栈就是没有附加头结点的、运算受限的单链表。栈顶指针就是链表的头指针。如果栈底，指针指向的存储单元中存有1元素，则当top=bottom时，栈中的元素个数为1；如果栈底指针指向的存储单元中没有存元素，则当top=bottom时，栈中的元素个数为0。所以选项C正确。28.设一棵树的度为3，共有27个结点，其中度为3，2，0的结点数分别为4，1，10。该树中度为l的结点数为（分数：2.00）A.11B.12√C.13D