国家二级ACCESS机试选择题（数据结构与算法）模拟试卷1（共192题）

国家二级ACCESS机试选择题（数据结构与算法）模拟试卷1（共7套）（共192题）国家二级ACCESS机试选择题（数据结构与算法）模拟试卷第1套一、选择题(本题共27题，每题1.0分，共27分。)1、下列各组的排序方法中，最坏情况下比较次数相同的是A、冒泡排序与快速排序B、简单插入排序与希尔排序C、堆排序与希尔排序D、快速排序与希尔排序标准答案：A知识点解析：最坏情况下冒泡排序需要比较n(n-1)／2次，即序列逆序的情况。简单插入排序，无论是否最坏情况，都需要n(n-1)／2次。直接插入排序，最坏情况需要比较次n(n-1)／2次。堆排序，无论是否最坏都要比较O(nlog2n)次。快速排序，最坏情况退化为冒泡排序，需要比较n(n-1)／2次。在最坏情况下，希尔排序所需要的比较次数为O(n1．5)。2、下列叙述中正确的是A、循环队列是队列的一种链式存储结构B、循环队列是队列的一种顺序存储结构C、循环队列是非线性结构D、循环队列是一种逻辑结构标准答案：B知识点解析：本题主要考查循环队列的概念，循环队列作为队列的·种也应该是线性结构。队列是一种逻辑结构，而循环队列是一种顺序存储结构的队列。3、下列关于线性链表的叙述中，正确的是A、各数据结点的存储空间可以不连续，但它们的存储顺序与逻辑顺序必须一致B、各数据结点的存储顺序与逻辑顺序可以不一致，但它们的存储空间必须连续C、进行插入与删除时，不需要移动表中的元素D、以上都不正确标准答案：C知识点解析：线性表的链式存储结构称为线性链表。在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。4、一棵二叉树共有25个结点，其中5个是叶子结点，则度为1的结点数为A、16B、10C、6D、4标准答案：A知识点解析：根据二叉树的性质，在任意二叉树中，度为0的结点(即叶子结点)总是比度为2的结点多一个，故此度为1的结点个数=总结点数-叶子节点数．度为2的节点数=25-5-4=16。5、设循环队列存储空间为Q(1：50)。初始状态为front=rear=50。经过一系列入队和退队操作后，front=14，rear=19，则该循环队列中的元素个数为A、46B、45C、6D、5标准答案：D知识点解析：在循环队列中，用队尾指针rear指向队列中的队尾元素，用排头指针front指向排头元素的前一个位置。因此，从排头指针front指向的后一个位置直到队尾指针rear指向的位置之间所有的元素为队列中的元素。本题中的元素个数是从队列的索引15位置开始到索引19位置，共有5元素。6、下列链表中，其逻辑结构属于非线性结构的是A、二叉链表B、循环链表C、双向链表D、带链的栈标准答案：A知识点解析：二叉链表作为树的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。7、设循环队列的存储空间为Q(1：35)，初始状态为front=rear=35。现经过一系列入队与退队运算后，front=15，rear=15，则循环队列中的元素个数为A、15B、16C、20D、0或35标准答案：D知识点解析：循环队列的队头指针和尾指针都等于15，此循环队列中元素的个数有两种情况，第一种情况是队头指针和尾指针都是第一次到达15，此时元素个数为0；第二种情况是队头指针第一次到达15，而尾指针第二次到达15，此时元素个数为35。8、下列关于栈的叙述中，正确的是A、栈底元素一定是最后入栈的元素B、栈顶元素一定是最先入栈的元素C、栈操作遵循先进后出的原则D、以上三种说法都不对标准答案：C知识点解析：栈是限定只能在表的一端进行插入和删除操作的线性表，必须按“后进先出”的规则操作元素。9、设二叉树共有150个结点，其中度为1的结点有10个，则该二叉树中的叶子结点数为A、71B、70C、69D、不可能有这样的二叉树标准答案：D知识点解析：根据二叉树的性质3，在任意一颗二叉树中，度为0的结点(即叶子结点)总是比度为2的结点多一个。即有n0-n2+1。对于这个题来说，总结点数150=n0+n1+n2=n2+1+10+n2=2n2+11，所以2n2=139，度为2个结点个数不能确定。10、下列叙述中正确的是A、程序执行的效率与数据的存储结构密切相关B、程序执行的效率只取决于程序的控制结构C、程序执行的效率只取决于所处理的数据量D、以上都不正确标准答案：A知识点解析：影响程序执行效率的因素有很多，如数据的存储结构、程序处理的数据量、程序的算法等。顺序存储结构和链式存储结构在数据插入和删除操作上的效率就存在差别。其中，链式存储结构的效率要高一些。11、下列与队列结构有关联的是A、函数的递归调用B、数组元素的引用C、多重循环的执行D、先到先服务的作业调度标准答案：D知识点解析：队列中最先插入的元素将最先被删除，最后插入的元素将最后被删除。12、对如下图所示的二叉树进行前序遍历的结果为A、DYBEAFCZXB、YDEBFZXCAC、ABDYECFXZD、ABCDEFXYZ标准答案：C知识点解析：二叉树前序遍历的简单描述：若二叉树为空，则结束返回；否则：①访问根结点：②前序遍历左子树；③前序遍历右子树。可见，前序遍历二叉树的过程是一个递归的过程。根据题目中给出的二叉树的结构可知前序遍历的结果是ABDYECFXZ。13、一个栈的初始状态为空。现将元素l，2,3，A，B,C依次入栈，然后再依次出栈，则元素出栈的顺序是A、1，2，3，A，B，CB、C，B，A，1，2，3C、C，B，A，3,2，1D、1，2，3，C，B，A标准答案：C知识点解析：栈是按照“先进后出”或“后进先出”的原则组织数据的。所以出栈顺序是CBA321。14、下列叙述中正确的是A、一个算法的空间复杂度大，则其时间复杂度也必定大B、一个算法的空间复杂度大，则其时间复杂度必定小C、一个算法的时间复杂度大，则其空间复杂度必定小D、算法的时间复杂度与空间复杂度没有直接关系标准答案：D知识点解析：算法的复杂度主要包括时间复杂度和空间复杂度。算法的时间复杂度是指执行算法所需要的计算工作量，算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数，即算法的工作量=f(n)，其中n是问题的规模；算法的空间复杂度，一般是指执行这个算法所需要的内存空间。一个算法所占用的存储空间包括算法程序所占用的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。根据各自的定义可知，算法的时间复杂度与空间复杂度并不相关。15、下列叙述中正确的是A、循环队列中的元素个数随队头指针与队尾指针的变化而动态变化B、循环队列中的元素个数随队头指针的变化而动态变化C、循环队列中的元素个数随队尾指针的变化而动态变化D、循环队列中的元素个数不会变化标准答案：A知识点解析：所谓循环结构就是将队列存储空间的最后一个位置绕到第一个位置上，形成逻辑上的环状空间，循环使用。在循环队列中，用队尾指针rear指向队列中的队尾元素，用队头指针。front指向队头元素的前一个位置，因此，队列中的元素数等于从队头指针front指向的后一个位置与队尾指针rear指向位置之间的元素数量。16、一棵二叉树中共有80个叶子结点与70个度为1的结点，则该二叉树中的总结点数为A、219B、229C、230D、231标准答案：B知识点解析：根据二叉树的性质，在任意二叉树中，度为0的结点(即叶子结点)总是比度为2的结点多一个，故总结点数=叶子节点数+度为2的节点数+度为1的节点数=80+79+70=229。17、对长度为10的线性表进行冒泡排序，最坏情况下需要比较的次数为A、9B、10C、45D、90标准答案：C知识点解析：线性表的长度为n，最坏情况下冒泡排序需要比较的次数为n(n-1)／2。18、下列叙述中正确的是A、算法的效率只与问题的规模有关，而与数据的存储结构无关B、算法的时间复杂度是指执行算法所需要的计算工作量C、数据的逻辑结构与存储结构是一一对应的D、算法的时间复杂度与空间复杂度一定相关标准答案：B知识点解析：算法的时间复杂度是指执行算法所需要的计算工作量。算法的工作量用算法所执行的基本运算的次数来度量，而算法所执行的基本运算次数是问题规模的函数；算法的空间复杂度一般是指执行这个算法所需要的内存空间。算法的时间复杂度与空间复杂度并不相关。数据的逻辑结构就是数据元素之间的逻辑关系，它是从逻辑上描述数据元素之间的关系，是独立于计算机的；数据的存储结构是研究数据元素和数据元素之间的关系如何在计算机中表示，它们并非一一对应。算法的执行效率不仅与问题的规模有关，还与数据的存储结构有关。19、下列叙述中正确的是A、线性表链式存储结构的存储空间一般要少于顺序存储结构B、线性表链式存储结构与顺序存储结构的存储空间都是连续的C、线性表链式存储结构的存储空间可以是连续的，也可以是不连续的D、以上都不正确标准答案：C知识点解析：线性表的存储分为顺序存储和链式存储。在顺序存储中，所有元素所占的存储空间是连续的。而在链式存储的方式中，将存储空间的每一个存储结点分为两部分，一部分用于存储数据元素的值，称为数据域；另一部分用于存储下一个元素的存储序号，称为指针域。所以线性表的链式存储方式比顺序存储方式的存储空间要大一些。20、某二叉树共有12个结点，其中叶子结点只有1个。则该二叉树的深度为(根结点在第1层)A、3B、6C、8D、12标准答案：D知识点解析：根据二叉树的性质，度为0的结点(即叶子结点)总是比度为2的结点多一个。题目中的二叉树的叶子结点为1，因此度为2的结点的数目为0，故该二叉树为12层，每层只有一个结点。21、对长度为n的线性表作快速排序，在最坏情况下，比较次数为A、nB、n-1C、n(n-1)D、n(n-1)／2标准答案：D知识点解析：假设线性表的长度为n，则在最坏情况下，冒泡排序需要经过n／2遍的从前往后的扫描和n／2遍的从后往前的扫描，需要的比较次数为n(n-1)／2。快速排序法也是一种互换类的排序方法，但由于它比冒泡排序法的速度快，因此，称为快速排序法。22、下列叙述中正确的是A、有且只有一个根结点的数据结构一定是线性结构B、每一个结点最多有一个前件也最多有一个后件的数据结构一定是线性结构C、有且只有一个根结点的数据结构一定是非线性结构D、有且只有一个根结点的数据结构可能是线性结构，也可能是非线性结构标准答案：D知识点解析：根据数据结构中各数据元素之间的前后件关系的复杂程度，一般将数据结构分这两大类型：线性结构与非线性结构。如果一个非空的数据结构满足两个条件：①有且只有一个根结点；②每一个结点最多有一个前件，也最多有一个后件。称该数据结构为线性结构，又称为线性表。对于这个题目来说，有且只有一个根结点的数据结构可能是线性结构，也可能是非线性结构。具有一个根结点的树就是一个非线性结构，选项D正确。23、下列叙述中错误的是A、在双向链表中，可以从任何一个结点开始直接遍历到所有结点B、在循环链表中，可以从任何一个结点开始直接遍历到所有结点C、在线性单链表中，可以从任何一个结点开始直接遍历到所有结点D、在二叉链表中，可以从根结点开始遍历到所有结点标准答案：C知识点解析：线性队列是一种线性单链表，对线性队列的遍历只能从队列的头开始，从中间的结点开始不能够遍历到所有的结点。选项C的描述是错误的。24、某二叉树共有13个结点，其中有4个度为1的结点，则叶子结点数为A、5B、4C、3D、2标准答案：A知识点解析：根据二叉树性质，在任意一颗二叉树中，度为O的结点(即叶子结点)总是比度为2的结点多一个，即有n0=n2+1。本题总结点数：13=n0+n1+n2=n2+1+4+n2=2n2+5，n2=4，所以叶子结点数等于4+1=5，选项A正确。25、设栈的顺序存储空间为S(1：50)，初始状态为top=0。现经过一系列入栈与退栈运算后，top=20，则当前栈中的元素个数为A、30B、29C、20D、19标准答案：C知识点解析：栈是允许在栈顶进行插入和删除的线性表，不允许在栈底进行插入与删除。通常用指针top来指示栈顶的位置，用指针bottom指向栈底。对栈的操作有入栈和退栈两种。入栈运算：首先将栈顶指针进一(即top加1)，然后将新元素插入到栈顶指针指向的位置。退栈运算：首先将栈顶元素(栈顶指针指向的元素)赋给一个指定的变量，然后将栈顶指针退一(即top减1)。因为初始状态为top=0，经过入栈和退栈操作后栈中的元素个数就是top指针指向的位置。选项C正确。26、下列叙述中正确的是A、栈与队列都只能顺序存储B、循环队列是队列的顺序存储结构C、循环链表是循环队列的链式存储结构D、以上三项均错误标准答案：B知识点解析：栈和队列是按数据的逻辑结构划分是线性结构。数据在内存或磁盘上的存储分为顺序存储结构和链式存储结构。线性结构的数据可以按顺序存储结构存储，也可以按链式存储结构存储，而循环队列是队列的顺序存储结构。选项B正确。27、设某二叉树的前序序列为ABC，中序序列为CBA，则该二叉树的后序序列为A、BCAB、CBAC、ABCD、CAB标准答案：B知识点解析：二叉树的前序遍历的顺序为首先访问根结点，再依次访问左结点和右结点。中序遍历的顺序为首先访问左结点，然后依次访问根结点和右结点。后序遍历的顺序为首先访问左结点，然后依次访问右结点和根结点。根据前序可以很快确定根，然后可以查看根在中序中位置，将中序分为左右两部分，左边和右边两颗树，在按照上述方式递推出确定左子树的根和右子树。对于本题根据前序，可以确定A为根，A在中序中的位置，可以确定CB为A的左子树上的结点，没有右子树。确定A之后，再看中序第二个值为B，查看B在中序中的位置，C在B左边，确定C为B的左子树。因此，后序是CBA。国家二级ACCESS机试选择题（数据结构与算法）模拟试卷第2套一、选择题(本题共30题，每题1.0分，共30分。)1、设有一个栈与一个队列的初始状态均为空。现有一个序列A，B，C，D，E，F，G，H。先分别将序列中的前4个元素依次入栈，后4个元素依次入队；然后分别将栈中的元素依次退栈，再将队列中的元素依次退队。最后得到的序列为A、D，C，B，A，E，F，G，HB、D，C，B，A，H，G，F，EC、A，B，C，D，E，F，G，HD、A，B，C，D，H，G，E，F标准答案：A知识点解析：栈(stack)又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。因此栈的出栈顺序是先入后出，所以顺序是D，C，B，A。队列是一种特殊的线性表，特殊之处在于它只允许在表的前端(front)进行删除操作，而在表的后端(rear)进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。因此，队的出队顺序是，先入先出，所以顺序是E，F，G，H。最后的顺序是：D，C，B，A，E，F，G，H。2、下列叙述中错误的是A、具有两个根结点的数据结构一定属于非线性结构B、具有两个以上指针域的链式结构一定属于非线性结构C、具有两个以上叶子结点的数据结构一定属于非线性结构D、具有一个根结点且只有一个叶子结点的数据结构也可能是非线性结构标准答案：B知识点解析：非线性结构，数学用语，其逻辑特征是一个结点元素可能有多个直接前驱和多个直接后继。常见的非线性结构有：二维数组，多维数组，广义表，树(二叉树等)，图。3、下列结构中属于线性结构链式存储的是A、双向链表B、循环队列C、二叉链表D、二维数组标准答案：A知识点解析：数据元素之间的关系有两种不同的表示方法：顺序映象和非顺序映象，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构。数据的存储结构是指数据的逻辑结构在计算机中的表示。双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱，它的存储方式是线性结构链式。循环队列、二叉链表和二维数组都是顺序存储结构。4、下列叙述中错误的是A、循环链表中有一个表头结点B、循环链表的存储空间是连续的C、循环链表实现了空表与非空表运算的统一D、循环链表的表头指针与循环链表中最后一个结点的指针均指向表头结点标准答案：B知识点解析：循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。循环链表的结点是指针指向，它不一定要是连续的存储空间，也可以是断开的空间。5、度为3的一棵树共有30个结点，其中度为3、1的结点个数分别为3、4。则该树中的叶子结点数为A、14B、15C、16D、不可能有这样的树标准答案：B知识点解析：根据题目可知本树中还有度为2的结点。树的总结点=(度1*个数+度2*个数…)+1，这里我们设度为2的结点数为x，那么30=3*3+2*×+1*4+1=2*x+14，由此可计算出x=8。树的叶子结点数等于总结点减去所有度不为0的结点，也就是30-3-8-4=15。6、在长度为97的顺序有序表中作二分查找，最多需要的比较次数为A、7B、96C、48D、6标准答案：A知识点解析：二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。最多比较次数的计算方式：k=log2n。其中n代表长度，k为比较次数。本题中可以计算出k=7。7、下列结构中属于非线性结构的是A、二叉链表B、二维数组C、循环队列D、双向链表标准答案：B知识点解析：线性结构是一个有序数据元素的集合。常用的线性结构有：线性表，栈，队列，双队列，数组，串；常见的非线性结构有：二维数组，多维数组，广义表，树(二叉树等)，图。循环队列、双向链表和二叉链表都是线性结构，而二维数组是非线性结构。8、从表中任何一个结点位置出发就可以不重复地访问到表中其他所有结点的链表是A、循环链表B、双向链表C、单向链表D、二叉链表标准答案：A知识点解析：循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环，循环一圈就访问到了表中其它所有结点而不重复。9、设二叉树的前序序列与中序序列均为ABCDEFGH，则该二叉树的后序序列为A、HGFEDCBAB、ABCDEFGHC、ABCDHGFED、DCBAHGFE标准答案：A知识点解析：前序遍历(DLR)是二叉树遍历的一种，也叫做先根遍历、先序遍历、前序周游，可记做根左右；中序遍历(LDR)是二叉树遍历的一种，也叫做中根遍历、中序周游，可记做左根右：后序遍历(LRD)是二叉树遍历的一种，也叫做后根遍历、后序周游，可记做左右根。根据题中前序和中序序列均为ABCDEFGH，可画出二叉树，该二叉树是一个子结点全部在右侧二叉树，然后根据后序遍历方法，可得出后序遍历为，GFEDCBA。10、设某棵树的度为3，其中度为3、1、0的结点个数分别为3、4、15。则该树中总结点数为A、22B、30C、35D、不可能有这样的树标准答案：B知识点解析：本题采用画图法来求出结果。首先先画出包含3个度为3的结点；然后再添加4个度为1的结点，此时最大度为0的结点数为8。根据题目中描述的度为0的结点数有15个，这时要在书中添加度为2的结点，直到度为0的结点数位15。画图结束后，不管是什么样的树，总结点数都是30。11、下列叙述中正确的是A、矩阵是非线性结构B、数组是长度固定的线性表C、对线性表只能作插入与删除运算D、线性表中各元素的数据类型可以不同标准答案：B知识点解析：所谓数组，就是相同数据类型的元素按一定顺序排列的集合，就是把有限个类型相同的变量用一个名字命名，然后用编号区分它们的变量的集合，这个名字称为数组名，编号称为下标。12、在快速排序法中，每经过一次数据交换(或移动)后A、能消除多个逆序B、只能消除一个逆序C、不会产生新的逆序D、消除的逆序个数一定比新产生的逆序个数多标准答案：A知识点解析：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。13、线性表的长度为n。在最坏情况下，比较次数为n-1的算法是A、顺序查找B、有序表的插入C、寻找最大项D、同时寻找最大项与最小项标准答案：C知识点解析：寻找最大项算法是，首先取出第一个数作为最大数，然后和后面的所有项进行比较查找。因此，比较次数为n-1。14、设某棵树的度为3，其中度为2、1、0的结点个数分别为3、4、15。则该树中总结点数为A、22B、30C、35D、不可能有这样的树标准答案：D知识点解析：本题采用画图法来求出结果。首先先画出包含3个度为2的结点；然后再添加4个度为1的结点。根据题目中描述的度为0的结点数有15个，这时要在书中添加度为3的结点，不管怎么添加都不能添加出15个度为0的结点，因此不可能有这样的树。15、下列叙述中错误的是A、向量是线性结构B、非空线性结构中只有一个结点没有前件C、非空线性结构中只有一个结点没有后件D、只有一个根结点和一个叶子结点的结构必定是线性结构标准答案：D知识点解析：线性结构是n个数据元素的有序(次序)集合。①集合中必存在唯一的一个“第一个元素”；②集合中必存在唯一的一个“最后的元素”；③除最后元素之外，其它数据元素均有唯一的“后件”：④除第一元素之外，其它数据元素均有唯一的“前件”。相对应于线性结构，非线性结构的逻辑特征是一个结点元素可能对应多个直接前驱和多个后继。向量符合线性结构特点。非线性结构也会存在只有一个根结点和叶子结点的情况。16、在希尔排序法中，每经过一次数据交换后A、能消除多个逆序B、只能消除一个逆序C、不会产生新的逆序D、消除的逆序个数一定比新产生的逆序个数多标准答案：A知识点解析：希尔排序法(缩小增量法)属于插入类排序，是将整个无序列分割成若干小的子序列分别进行插入排序的方法。插入排序能够消除多个逆序，也会产生新的逆序。消除的逆序与新产生的逆序有多有少。17、设二叉树的后序序列与中序序列均为ABCDEFGH，则该二叉树的前序序列为A、HGFEDCBAB、ABCDEFGHC、ABCDHGFED、DCBAHGFE标准答案：A知识点解析：后序遍历中，最后一个字母是根结点，也就是H是根结点；在中序遍历中，根结点前面的是左子树、后面的是右子树，H后面没有，因此该树没有右孚树。同理，可判断出该树是第一个完全的左子树。由此可画出这个二叉树，然后根据二叉树可的前序序列为HGFEDCBA。18、下列叙述中正确的是A、循环队列是队列的链式存储结构B、能采用顺序存储的必定是线性结构C、所有的线性结构都可以采用顺序存储结构D、具有两个以上指针的链表必定是非线性结构标准答案：C知识点解析：根据数据结构中各数据元素之间的前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。有序线性表既可以采用顺序存储结构，又可以采用链式存储结构。所有的线性结构都可以采用顺序存储结构。19、下列叙述中正确的是A、算法的复杂度是指算法所处理的数据量B、算法的复杂度是指算法程序中指令的数量C、算法的复杂度是指算法控制结构的复杂程度D、算法的复杂度包括时间复杂度与空间复杂度标准答案：D知识点解析：算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。20、设二叉树的前序序列为ABDEGHCFIJ，中序序列为DBGEHACIFJ。则按层次输出(从上到下，同一层从左到右)的序列为A、ABCDEFGHIJB、DGHEBIJFCAC、JIHGFEDCBAD、GHIJDEFBCA标准答案：A知识点解析：前序遍历中，第一个字母是根结点，也就是A是根结点：在中序遍历中，根结点前面的是左子树、后面的是右子树。前序中，B在A的后面，中序中在左子树中，可知B为A的左结点。中序中D在B的前面，前序中在B的后面，可知D为B的左结点，GEH为B的右子树。前序中顺序为EGH，由此可知，E为B的右结点，G为E的左结点、H为E的右结点。右子树中，前序中c在最前，因为右子树根结点，也就是A的右结点，根据前序中的子树FIJ和中序中的IFJ子树可知F为C的右结点，I为F的左结点、J为F的右结点。由此可画出这个二叉树，然后根据二叉树，可知按层次输出(从上到下，同一层从左到右)的序列为：ABCDEFGHIJ。21、设循环队列的存储空间为Q(1：50)，初始状态为front=rear=50。经过一系列正常的操作后，front1=rear。为了在该队列中寻找值最大的元素，在最坏情况下需要的比较次数为A、0B、1C、48D、49标准答案：C知识点解析：front指向队头位置，删除一个元素就将front顺时针移动一位；rear指尾指针指向元素要插入的位置，插入一个元素就将rear顺时针移动一位；操作后循环队列的队头指针-1等于尾指针，说明出队一位，那么总数就是49了。在该队列中寻找最大值元素，最多比较次数是总数-1，因此是49-1=48次。22、设顺序表的长度为40，对该表进行冒泡排序。在最坏情况下需要的比较次数为A、780B、820C、40D、41标准答案：A知识点解析：冒泡排序(BubbleSort)，是一种计算机科学领域的较简单的排序算法。冒泡排序算法的运作如下：比较相邻的元素。如果第一个比第二个大，就交换它们两个；对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数；针对所有的元素重复以上的步骤，除了最后一个；持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。冒泡排序的最坏时间复杂度为(n*(n-1))／2=780。23、设表的长度为n。在下列算法中，最坏情况下时间复杂度最高的是A、堆排序B、希尔排序C、有序链表查找D、循环链表中寻找最大项标准答案：B知识点解析：希尔排序(ShellSort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。排序方法最坏时间复杂度：直接插入为O(n2)、简单选择为O(n2)、起泡排序为O(n2)、快速排序为O(n2)、堆排序为O(nlog2n)、归并排序为O(nlog2n)。24、设循环队列的存储空间为Q(1：50)，初始状态为front=rear=50。经过一系列正常的操作后，front=rear-1。为了在该队列中寻找值最大的元素，在最坏情况下需要的比较次数为A、0B、1C、49D、50标准答案：A知识点解析：front指定队头位置，删除一个元素就将front顺时针移动一位；rear指尾指针，指向元素要插入的位置，插入一个元素就将rear顺时针移动一位；操作后，循环队列的队头指针等于尾指针-1，说明此时队列已经是空队列，那么就不用比较了。25、设二叉树的前序序列为ABDEGHCFIJ，中序序列为DBGEHACIFJ。则后序序列为A、DGHEBIJFCAB、JIHGFEDCBAC、GHIJDEFBCAD、ABCDEFGHIJ标准答案：A知识点解析：前序遍历中，第一个字母是根结点，也就是A是根结点；在中序遍历中，根结点前面的是左子树、后面的是右子树。前序中，B在A的后面，中序中在左子树中，可知B为A的左结点。中序中D在B的前面，前序中在B的后面，可知D为B的左结点，GEH为B的右子树。前序中顺序为EGH，由此可知，E为B的右结点，G为E的左结点、H为E的右结点。右子树中，前序中c在最前，因为右子树根结点，也就是A的右结点，根据前序中的子树FIJ和中序中的IFJ子树可知F为C的右结点，I为F的左结点、J为F的右结点。由此可画出这个二叉树，然后根据二叉树可的后序序列为DGHEBIJFCA。26、设顺序表的长度为16，对该表进行简单插入排序。在最坏情况下需要的比较次数为A、15B、30C、60D、120标准答案：D知识点解析：插入排序的基本思想是：每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止：最坏情况计算方法(n*(n-1))／2=16*15／2=120。27、下列结构中为非线性结构的是A、树B、向量C、二维表D、矩阵标准答案：A知识点解析：线性结构是一个有序数据元素的集合。常用的线性结构有：线性表，栈，队列，双队列，数组，串。常见的非线性结构有：二维数组，多维数组，广义表，树(二叉树等)，图。28、设表的长度为n。在下列结构所对应的算法中，最坏情况下时间复杂度最低的是A、堆排序B、有序链表查找C、希尔排序D、循环链表中寻找最大项标准答案：D知识点解析：在循环链表中寻找最大项算法是，首先取出第一个数作为最大数，然后和后面的所有项进行比较查找。因此，比较次数为n-1。29、设循环队列的存储空间为Q(1：m)，初始状态为front=rear=m。经过一系列正常的操作后，front=1，rear=m。为了在该队列中寻找值最大的元素，在最坏情况下需要的比较次数为A、mB、m-1C、m-2D、1标准答案：C知识点解析：经过一系列正常的操作后，front=1，rear=m，那么最坏情况下需要的比较次数为rear-front-1=m-1-1=m-2。30、设二叉树的后序序列为DGHEBIJFCA，中序序列为DBGEHACIFJ。则前序序列为A、ABDEGHCFIJB、JIHGFEDCBAC、GHIJDEFBCAD、ABCDEFGHIJ标准答案：A知识点解析：后序遍历中，最后一个字母是根结点，也就是A是根结点；在中序遍历中，根结点前面的是左子树、后面的是右子树。后序中C在A前面、中序中c在A的后面，说明C是A的右结点；后序中F在C的前面、中序中在C后面，且后序和中序中，I均在F前面由此可确定，I为F的左结点，F为C的右结点。同C理J为F的右结点。后续中B为左子树的根结点，因此B为A的左结点，以此划分，在中序中B前面的D为左结点，后面的GEH为右子树，后序中，E在最后，应为剩下3个结点的根结点，也就是B的右子树，再根据中序中的顺序，可得出G为E的左结点，H为E的右结点。由此可画出这个二叉树，然后根据二叉树可的前序序列为ABDEGHCFIJ。国家二级ACCESS机试选择题（数据结构与算法）模拟试卷第3套一、选择题(本题共27题，每题1.0分，共27分。)1、下列排序方法中，最坏情况下时间复杂度最小的是A、冒泡排序B、快速排序C、堆排序D、直接插入排序标准答案：C知识点解析：排序方法中最坏情况下时间复杂度的大小如下表：根据上表可知选项C正确。2、为了对有序表进行对分查找，则要求有序表A、只能顺序存储B、只能链式存储C、可以顺序存储也可以链式存储D、任何存储方式标准答案：A知识点解析：有序表的对分查找条件是有序表为顺序存储。顺序查找：①如果线性表为无序表(即表中元素的排序是无序的)，则无论是顺序存储结构还是链式存储结构，都只能用顺序查找；②即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。分块查找(又称索引顺序查找)：分块有序表结构分为两部分，①线性表本身采用顺序存储结构：②在建立一个索引表，在索引表中，对线性表的每个子表建立一个索引结点，每个结点包括两个域：一是数据域，用于存放对应子表中的最大元素值；二是指针域，用于指示对应子表的第一个元素在整个线性表中的序号。显然索引表关于数据域是有序的。3、设某二叉树的后序序列为CBA，中序序列为ABC，则该二叉树的前序序列为A、BCAB、CBAC、ABCD、CAB标准答案：C知识点解析：二叉树的前序遍历顺序为首先访问根结点，再依次访问左结点和右结点。中序遍历的顺序为首先访问左结点，然后依次访问根结点和右结点。后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点。根据后序可以很快确定根结点，然后可以查看根在中序中位置，将中序分为左右两部分，左边和右边两颗树，在按照上述方式递推出确定左子树的根和右子树。本题根据后序，可以确定A为根结点；根据B在中序中的位置，可以确定A没有左子树，BC为A的右子树，C为B的右子树。本题的具体二叉树如下：因此，这棵二叉树的前序是ABC，选项C正确。4、下列叙述中正确的是A、存储空间不连续的所有链表一定是非线性结构B、结点中有多个指针域的所有链表一定是非线性结构C、能顺序存储的数据结构一定是线性结构D、带链的栈与队列是线性结构标准答案：D知识点解析：计算机中数据按照其数据逻辑结构，可以分为线性结构和非线性结构。而数据在内存或磁盘中的存储，可以分为顺序存储和链式存储。数据的逻辑结构与存储结构之间没有对应的关系。所以选项ABC都是错误的，栈和队列按照数据的逻辑划分都是线性结构。5、算法时间复杂度的度量方法是A、算法程序的长度B、执行算法所需要的基本运算次数C、执行算法所需要的所有运算次数D、执行算法所需要的时间标准答案：B知识点解析：算法的时间复杂度：分析算法时，语句总执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)。算法的时间复杂度也就是算法的时间量度，记作T(n)=O(f(n))。它表示问题输入规模n的增大，算法执行时间的增长率和f(n)的增长率相同，因此称作渐近时间复杂度，也称作时间复杂度。f(n)是问题规模n的某个函数。选项B正确。6、设循环队列为Q(1：m)，初始状态为front=rear=m。现经过一系列的入队与退队运算后，front=rear=1，则该循环队列中的元素个数为A、1B、2C、m．1D、0或m标准答案：D知识点解析：在循环队列中，用队尾指针rear指向队列中的队尾元素，用排头指针front指向排头元素的前一个位置。因此，从排头指针front指向的后一个位置直到队尾指针rear指向的位置之间，所有的元素为队列中的元素。在循环队列动态变化过程中，当循环队列满时有front=rear，而当循环队列空时也有front=rear。即在循环队列中，当：front=rear时，不能确定是队列满、还是队列空。当front=rear=1，要么队列为空，队列中的元素个数为0，要么队列为满，队列中元素个数为m。选项D正确。7、在最坏情况下A、快速排序的时间复杂度比冒泡排序的时间复杂度要小B、快速排序的时间复杂度比希尔排序的时间复杂度要小C、希尔排序的时间复杂度比直接插入排序的时间复杂度要小D、快速排序的时间复杂度与希尔排序的时间复杂度是一样的标准答案：C知识点解析：按平均时间将排序分为四类：①平方阶(O(n2))排序：各类简单排序，例如直接插入、直接选择和冒泡排序；②线性对数阶(O(nlog2n))排序：如快速排序、堆排序和归并排序；③O(n1+§))排序：§是介于0和1之间的常数。希尔排序便是一种；④线性阶(O(n))排序：本程序中的基数排序，此外还有桶、箱排序。8、在深度为7的满二叉树中，度为2的结点个数为A、64B、63C、32D、31标准答案：B知识点解析：因为在任意的二叉树中，度为0的结点(即叶子结点)总比度为2的结点的个数多1个，而度为0的结点数n0=2m-1(其中m为二叉树的深度)。本题的度为0的结点个数n0=27-1=26=64。因此，度为2的结点数n2=n0-1=63。所以选项B正确9、设栈的顺序存储空间为S(1：m)，初始状态为top=m+1。现经过一系列入栈与退栈运算后，top=20，则当前栈中的元素个数为A、30B、20C、m-19D、m-20标准答案：C知识点解析：根据题意，栈空间如下图所示。栈是向上增长的，每次压入一个元素，栈的TOP指针向上移动一位。当压入第一个元素时，TOP指针指向n1+1-1=m；当压入第二个元素时，TOP指针指向m+1-2=m-1；……；以此类推，当压入第N个元素时，TOP指针指向m+1-N=20；则N=m+1-20=m-19。因此选项C正确。10、算法空间复杂度的度量方法是A、算法程序的长度B、算法所处理的数据量C、执行算法所需要的工作单元D、执行算法所需要的存储空间标准答案：D知识点解析：算法空间复杂度是对一个算法在运行过程中临时占用存储空间大小的度量，因此选项D正确。11、设循环队列为Q(1：m)，其初始状态为front=rear=m。经过一系列入队与退队运算后，front=15，rear=20。现要在该循环队列中寻找最大值的元素，最坏情况下需要比较的次数为A、4B、6C、m-5D、m-6标准答案：A知识点解析：初始状态为：front=rear=m，rear-front=0，此时队列为空。经过一系列入队与退队运算后，front=15，rear=20。队尾大于队头，则队尾rear减队头front等于5个元素。此时队列中有5个元素，而查找最大项至少要比较n-1次，就是4次。因此选项A正确。12、下列叙述中正确的是A、循环队列属于队列的链式存储结构B、双向链表是二叉树的链式存储结构C、非线性结构只能采用链式存储结构D、有的非线性结构也可以采用顺序存储结构标准答案：D知识点解析：顺序存储方式不仅能用于存储线性结构，还可以用来存放非线性结构。例如，完全二叉树是属于非线性结构，但其最佳存储方式是顺序存储方式。13、某二叉树中有n个叶子结点，则该二叉树中度为2的结点数为A、n+1B、n-1C、2nD、n／2标准答案：B知识点解析：任意一棵二叉树，如果叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；N2=N0-1。所以如果二叉树中有n个叶子结点，则该二叉树中度为2的结点数为n-1。因此选项B正确。14、下列叙述中错误的是A、算法的时间复杂度与算法所处理数据的存储结构有直接关系B、算法的空间复杂度与算法所处理数据的存储结构有直接关系C、算法的时间复杂度与空间复杂度有直接关系D、算法的时间复杂度与空间复杂度没有必然的联系标准答案：C知识点解析：算法的时间复杂度，是指执行算法所需要的计算工作量。算法的空间复杂度，是指执行这个算法所需要的内存空间。两者与算法所处理数据的存储结构都有直接关系，但两者之间没有直接关系，因此选项C错误。15、设栈的顺序存储空间为S(0：49)，栈底指针bosom=49，栈项指针top=30(指向栈顶元素)。则栈中的元素个数为A、30B、29C、20D、19标准答案：C知识点解析：在操作系统中，栈是向下生长的，如下图如示：所以当栈底指针bottom=49，栈顶指针top=30时，栈中的元素个数为：栈底-栈顶+1=49-30+1=20。因此选项C正确。16、某二叉树的前序序列为：ABCDEFG，中序序列为：DCBAEFG，则该二叉树的深度(根结点在第1层)为A、2B、3C、4D、5标准答案：C知识点解析：该二叉树的前序序列为ABCDEFG，中序序列为DCBAEFG，可知A为根结点，结点B、C、D位于根结点的左子树上，结点E、F、G位于根结点的右子树上；并且结点B、C、D在前序序列和中序序列中顺序颠倒，则说明这三个结点依次位于前一个结点的左子树上；结点E、F、G顺序未变，则说明这三个结点依次位于前一个结点的右子树上。所以得到的二叉树为：所以这个二叉树的深度为4。选项C为正确答案。17、下列叙述中正确的是A、存储空间连续的数据结构一定是线性结构B、存储空间不连续的数据结构一定是非线性结构C、没有根结点的非空数据结构一定是线性结构D、具有两个根结点的数据结构一定是非线性结构标准答案：D知识点解析：数据结构从逻辑上来划分，分为线性结构和非线性结构，一对一是线性结构，其它的为非线性结构。判断一个非空的数据结构是否为线性结构必须满足以下两个条件：①有且只有一个根结点；②每一个结点最多有一个前件，也最多有一个后件。根据这两个条件，可知选项A)、B)和C)都不能判定是否是线性结构。18、下列叙述中正确的是A、带链队列的存储空间可以不连续，但队头指针必须大于队尾指针B、带链队列的存储空间可以不连续，但队头指针必须小于队尾指针C、带链队列的存储空间可以不连续，且队头指针可以大于也可以小于队尾指针D、以上三项都错误标准答案：C知识点解析：带链队列的存储空间可以不连续，且队头指针与队尾指针大小没有可比性，选项C正确。19、设循环队列为Q(1：m)，其初始状态为front=rear=m。经过一系列入队与退队运算后，front=20，rear=15。现要在该循环队列中寻找最小值的元素，最坏情况下需要比较的次数为A、5B、6C、m-5D、m-6标准答案：D知识点解析：在循环队列中元素的个数为“(rear-front=M)％M”，式中rear为队尾指针，front为队首指针，M为存储容量，％为取余符号。对于找最小值的最坏情况下的比较次数，为循环队列中元素值个数减一。所以对于这个题目来说初始时元素个数为0；运算后，元素个数为m-5，找最小值的最坏情况下的比较次数为m-5-1=m-6。20、某二叉树的前序序列为ABCDEFG，中序序列为DCBAEFG，则该二叉树的后序序列为A、EFGDCBAB、DCBEFGAC、BCDGFEAD、DCB6FEA标准答案：D知识点解析：该二叉树的前序序列为ABCDEFG，中序序列为DCBAEPG，可知A为根结点，结点B、C、D位于根结点的左子树上，结点E、F、G位于根结点的右子树上；并且结点B、C、D在前序序列和中序序列中顺序颠倒，则说明这三个结点依次位于前一个结点的左子树上；结点E、F、G顺序未变，则说明这三个结点依次位于前一个结点的右子树上。根据以上分析，可以画出这个二叉树的形状如下：根据该二叉树，可得出后序遍历序列为：DCBGFEA，选项D正确。21、下列叙述中正确的是A、在链表中，如果每个结点有两个指针域，则该链表一定是非线性结构B、在链表中，如果有两个结点的同一个指针域的值相等，则该链表一定是非线性结构C、在链表中，如果每个结点有两个指针域，则该链表一定是线性结构D、在链表中，如果有两个结点的同一个指针域的值相等，则该链表一定是线性结构标准答案：B知识点解析：选项A叙述是错误的，如在双向链表中，每个结点有两个指针域，但该链表是线性结构；选项C叙述也是错误的，如每个二叉树的结点都有两个指针域，但是其结构是非线性结构；选项D叙述也是错误的，线性结构只有唯一的一个前驱和唯一的一个后继(头、尾除外)；排除法可判断选项B正确。22、下列叙述中错误的是A、在带链队列中，队头指针和队尾指针都是在动态变化的B、在带链栈中，栈顶指针和栈底指针都是在动态变化的C、在带链栈中，栈顶指针是在动态变化的，但栈底指针是不变的D、以上三项都错误标准答案：B知识点解析：栈是只在一端进行增加和删除的线性表，进行操作的那端称为栈顶，另一端称为栈底。所以在带链栈中，栈顶指针是在动态变化的，但栈底指针是不变的，选项C的说法正确，选项B的说法是错误的。队列是允许在队列的头和尾都可以进行操作的线性表，所以在带链队列中，队头指针和队尾指针都是在动态变化的选项A这一说法是正确的。23、设数据元素的集合D={1，2，3，4，5}，则满足下列关系R的数据结构中为线性结构的是A、R={(1，2)，(3，4)，(5，1)}B、R={(1，3)，(4，1)，(3，2)，(5，4)}C、R={(1，2)，(2，3)，(4，5)}D、R={(1，3)，(2,4)，(3，5)}标准答案：B知识点解析：把每个答案中的第一个元素集合取出来，例如A：(1，2)，先写下来就是12，然后看后面的(3,4)，在(1，2)中找不到前驱和后继，只能和(1，2)暂时先并列，然后是(5，1)，这里我们已经写过12了，那么5在1前面就是512，但是34要单排，所以A就是两个根节点3和5，两个顺序是512，34。同理选项B是541，32：选项C是：123和45；选项D是135,24所以选项B正确。24、下列叙述中正确的是A、链表结点中具有两个指针域的数据结构可以是线性结构，也可以是非线性结构B、线性表的链式存储结构中，每个结点必须有指向前件和指向后件的两个指针C、线性表的链式存储结构中，每个结点只能有一个指向后件的指针D、线性表的链式存储结构中，叶子结点的指针只能是空标准答案：A知识点解析：在链式存储方式中，每个结点由两部分组成：数据域和指针域，指针域用于指向该节点的前一个或后一个结点，所以选项B、C、D说法错误。选项A中，例如双向链表就具有两个指针，也属于线性结构，所以选项A正确。25、一个栈的初始状态为空，现将元素A、B、C、D、E依次入栈，然后依次退栈三次，并将退栈的三个元素依次入队(原队列为空)，最后将队列中的元素全部退出。则元素退队的顺序为A、ABCB、CBAC、EDCD、CDE标准答案：C知识点解析：栈是根据先进后出的原则组织数据，所以退栈三次的元素依次为E、D、C；队列是根据先进先出的原则组织数据的，所以退队的顺序依次为E、D、C，所以选项C正确。26、某二叉树中序序列为DCBAEFG，后序序列为DCBGFEA，则该二叉树的深度(根结点在第1层)为A、5B、4C、3D、2标准答案：B知识点解析：该二叉树的中序序列为DCBAEFG，后序序列为DCBGFEA，可知A为根结点，结点B、C、D位于根结点的左子树上，结点E、F、G位于根结点的右子树上；并且结点B、C、D在中序序列和后序序列中顺序未变，则说明这三个结点依次位于前一个结点的左子树上；结点E、F、G顺序颠倒，则说明这三个结点依次位于前一个结点的右子树上。根据以上分析，该二叉树的深度为4，所以选项B正确。27、下列叙述中正确的是A、所谓算法就是计算方法B、程序可以作为算法的一种描述方法C、算法设计只需考虑得到计算结果D、算法设计可以忽略算法的运算时间标准答案：B知识点解析：算法是一组有穷指令集，是解题方案的准确而完整的描述。通俗地说，算法就是计算机解题的过程，重在解题方案的设计，并且不等于计算方法，故选项A和选项C不正确。程序的编制不可能优于算法的设计，但算法的描述可以用程序、伪代码、流程图来描述，故选项B正确。算法要求执行过程中所需要的基本运算次数和时间最少，即时间复杂度最低，所以选项D错误。国家二级ACCESS机试选择题（数据结构与算法）模拟试卷第4套一、选择题(本题共27题，每题1.0分，共27分。)1、某二叉树的中序遍历序列为CBADE，后序遍历序列为CBADE，则前序遍历序列为A、EDABCB、CBEDAC、CBADED、EDCBA标准答案：A知识点解析：后序遍历次序是“左右根”，中序遍历次序是“左根右”。由定义可知：①后序遍历中最后一个就是树根结点，即E结点；②在中序遍历中，根结点左边的是左子树集，右边的是右子树集，即CBAD是根结点E的左子树集合。问题就会转化为：求后序遍历是CBAD，中序遍历是CBAD的子树，方法同上。因为中序遍历中，D结点右边没有结点了，所以D结点不包含右子树，否则就会被分为2个子问题以下是这道题的详细推理过程：步骤1：由CBADE得出根结点为E，由中序遍历可知{CBAD}E，右子树为空；步骤2：由CBAD得出左子树集合的根节点为D，由中序可知{CBA}D，右子树为空；步骤3：同理，二叉树更新后如下图所示。由上图可得，前序遍历为：EDABC。2、下列叙述中正确的是A、在循环队列中，队头指针和队尾指针的动态变化决定队列的长度B、在循环队列中，队尾指针的动态变化决定队列的长度C、在带链的队列中，队头指针与队尾指针的动态变化决定队列的长度D、在带链的栈中，栈顶指针的动态变化决定栈中元素的个数标准答案：A知识点解析：循环队列是将顺序队列首尾相连形成的，随着插入元素或删除元素的进行，其队头指针及队尾指针是在不断变化的，有时可能会出现队头指针大于队尾指针的情况，也可能是队尾指针大于队头指针。循环队列中计算元素的个数公式为：(rear-front+queuc_size)％queue_size。所以选项A正确。3、设栈的存储空间为S(1：60)，初始状态为top=61。现经过一系列正常的入栈与退栈操作后，top=1，则栈中的元素个数为A、60B、59C、0D、1标准答案：A知识点解析：栈是向上增长的，每次压入一个元素，栈的TOP指针向上移动一位，即top-1。当压入第一个元素时，TOP指针指向60+1-1=60；当压入第二个元素时，TOP指针指向60+1-2=59；……；以此类推，当压入第N个元素时，TOP指针指向60+1-N=1，则N=60。所以选项A正确。4、设顺序表的长度为n。下列排序方法中，最坏情况下比较次数小于n(n-1)／2的是A、堆排序B、快速排序C、简单插入排序D、冒泡排序标准答案：A知识点解析：假设线性表的长度为n，则在最坏情况下，冒泡排序需要经过n／2遍的从前往后扫描和n／2遍的从后往前扫描，需要比较次数为n(n-1)／2。快速排序法的最坏情况比较次数也是n(n-1)／2。简单插入排序，无论是否最坏都需要n(n-1)／2比较。堆排序，无论是否最坏都需要比较O(nlog2n)次。5、在长度为n的顺序表中查找一个元素，假设需要查找的元素有一半的机会在表中，并且如果元素在表中，则出现在表中每个位置上的可能性是相同的。则在平均情况下需要比较的次数大约为A、(3+n)／4B、nC、n／2D、n／4标准答案：A知识点解析：在长度为n的顺序表中查找一个元素，最好的情况是目标在第一个，一次找到；最坏的情况是目标在最后一个，n次找到。那么平均长度为：(1+2+…+n)／n=(n(n+1)／2)／n=(n+1)／2。本题需要查找的元素有一半的机会在表中，则在平均情况下需要比较的次数大约为((1+n)／2+1)／2=(3+n)／4。6、设一棵树的度为3，其中度为3，2，1的结点个数分别为4，1，3。则该棵树中的叶子结点数为A、10B、11C、12D、不可能有这样的树标准答案：A知识点解析：因为任一棵树中，结点总数=总分支数目+1，所以：n0+4+1+3=(n0*0+3*4+2*1+1*3)+1，计算结果n0=10。其中，n0表示叶子结点。所以选项A正确。7、设栈的存储空间为S(1：50)，初始状态为top=0。现经过一系列正常的入栈与退栈操作后，top=51，则栈中的元素个数为A、不可能B、50C、0D、1标准答案：A知识点解析：栈是向上增长的，每次压入一个元素，栈的。TOP指针向上移动一位，即top-1。对于这个题目，由于top初始值等于0，此时入栈一个元素，top值减1，即0-1=-1，发生下溢错误。8、设顺序表的长度为n。下列算法中，最坏情况下比较次数等于n(n-1)／2的是A、快速排序B、堆排序C、顺序查找D、寻找最大项标准答案：A知识点解析：假设线性表的长度为n，则在最坏情况下，快速排序法的最坏情况比较次数也是n(n-1)／2；堆排序，无论是否最坏都是比较O(nlog2n)次，所以选项A正确。9、设表的长度为n。下列算法中，最坏情况下比较次数小于n的是A、二分查找法B、堆排序C、快速排序D、顺序查找法标准答案：A知识点解析：二分法查找只适用于顺序存储的有序表。二分查找的基本方法是：将被查元素x与线性表的中间项进行比较，若中间项的值等于x，则说明查到；若小于中间项的值则在线性表的前半部分；以相同的方法进行查找；若大于中间项的值，则在线性表的后半部分以相同的方法进行查找。在最坏情况下，二分查找需要比较log2n次。所以选项A正确。10、下列叙述中错误的是A、循环链表是循环队列的存储结构B、二叉链表是二叉树的存储结构C、栈是线性结构D、循环队列是队列的存储结构标准答案：A知识点解析：循环队列属于逻辑结构，其实质还是顺序存储，只是使用指针进行首尾的联结，其实现的存储方式可分为：分散的链表和连续的线性表，与其逻辑结构实现功能无关。所以选项A正确。11、设一棵树的度为4，其中度为4，3，2，1的结点个数分别为2，3，3，0。则该棵树中的叶子结点数为A、16B、15C、17D、不可能有这样的树标准答案：A知识点解析：因为任一棵树中，结点总数=总分支数目+1，所以：n0+2+3+3+0=(n0*0+4*2+3*3+2*3+1*0)+1。计算得出n0=16。其中，n0表示叶子结点，所以选项A正确。12、循环队列的存储空间为Q(1：100)，初始状态为front=rear=100。经过一系列正常的入队与退队操作后，front=rear=99，则循环队列中的元素个数为A、0或100B、1C、2D、99标准答案：A知识点解析：循环队列中，由于入队时尾指针rear。向前追赶头指针front；出队时头指针front向前追赶尾指针rear，造成队空和队满时头尾指针均相等。因此，无法通过条件front=rear来判别队列是“空”还是“满”。对于这个题目来说，经过一系列正常的入队与退队操作后，front=rear=99，此时，要么队列为空(元素个数为0)，要么队列为满(元素个数为100)，因此选项A正确。13、设顺序表的长度为n。下列算法中，最坏情况下比较次数小于n的是A、寻找最大项B、堆排序C、快速排序D、顺序查找法标准答案：A知识点解析：如果顺序表是线性存储的(不包括线性的链式表)，那么元素要不就是从大到小，要不就是小到大的顺序，假设第一个数就是最大值，那么需要比较1次，n-1应该是最坏情况下要比较的次数，所以选项A正确。14、设栈的顺序存储空间为S(1：m)，初始状态为top=m+1。现经过一系列正常的入栈与退栈操作后，top=0，则栈中的元素个数为A、不可能B、m+1C、1D、m标准答案：A知识点解析：栈是向上增长的，每次压入一个元素，栈的TOP指针向上移动一位，即top-1。对于这个题目，由于top初始值等于m+1，此时入栈一个元素，top值减1，即m+1-1=m，依次类推，当栈满时，top的值等于1，不会出现top的值等于0。所以选项A正确。15、某二叉树的后序遍历序列与中序遍历序列相同，均为ABCDEF，则按层次输出(同一层从左到右)的序列为A、FEDCBAB、CBAFEDC、DEFCBAD、ABCDEF标准答案：A知识点解析：后序遍历次序：左右根：中序遍历次序：左根右。由定义可知：①后序遍历中最后一个是树的根结点，即F结点；②在中序遍历中，根结点左边的是左子树集，右边的是右子树集，即ABCDE是根结点F的左子树集合。问题就会转化为：求后序遍历是ABCDE，中序遍历是ABCDE的子树。方法同上，因为中序遍历中，E结点右边没有结点了，所以E结点不包含右子树，否则就会被分为2个子问题。以下是这道题的详细推理过程：步骤1：由ABCDEF得出根结点为F，由中序遍历可知：{ABCDE}F，右子树为空；步骤2：由ABCDE得出左子树集合的根节点为E，由中序可知：{ABCD}E，右子树为空；步骤3：同理，二叉树更新后如下。所以按层次输出(同一层从左到右)的序列为FEDCBA。16、循环队列的存储空间为Q(1：200)，初始状态为front=rear=200。经过一系列正常的入队与退队操作后，front=rear=1，则循环队列中的元素个数为A、0或200B、1C、2D、199标准答案：A知识点解析：循环队列中，由于入队时尾指针rear向前追赶头指针front；出队时头指针front向前追赶尾指针rear，造成队空和队满时头尾指针均相等。因此，无法通过条件front=rear来判别队列是“空”还是“满”。对于这个题目来说，经过一系列正常的入队与退队操作后，front=tear=1，此时，要么队列为空(元素个数为0)，要么队列为满(元素个数为200)。所以选项A正确。17、设栈的顺序存储空间为S(1：m)，初始状态为top=0。现经过一系列正常的入栈与退栈操作后，top=m+1，则栈中的元素个数为A、不可能B、m+1C、0D、m标准答案：A知识点解析：栈是向上增长的，每次压入一个元素，栈的TOP指针向上移动一位，即top-1。对于这个题目，由于top初始值等于0，此时入栈一个元素，top值减1，即0-1=-1，出现下溢错误，所以选项A正确。18、下列排序法中，最坏情况下时间复杂度最小的是A、堆排序B、快速排序C、希尔排序D、冒泡排序标准答案：A知识点解析：假设线性表的长度为n，则在最坏情况下，冒泡排序需要经过n／2遍的从前往后扫描和n／2遍的从后往前扫描，需要比较次数为n(n-1)／2。快速排序法的最坏情况比较次数也是n(n-1)／2。简单插入排序，无论是否最坏都需要n(n-1)／2比较。堆排序，无论是否最坏情况都是比较O(nlog2n)次。所以选项A正确。19、某二叉树的前序遍历序列与中序遍历序列相同，均为ABCDEF，则按层次输出(同、一层从左到右)的序列为A、ABCDEFB、BCDEFAC、FEDCBAD、DEFABC标准答案：A知识点解析：前序遍历次序：根左右；中序遍历次序：左根右。由定义可以知道：①前序遍历中第一个就是树根结点，即A结点；②在中序遍历中，根结点左边的是左子树集，右边的是右子树集，即BCDEF是根结点A的右子树集合。恫题就会转化为：求前序遍历是BCDEF，中序遍历是BCDEF的子树，方法同上。详细推理过程：步骤1：由ABCDEF得出根结点为A，由中序遍历可知：左子树为空，A{BCDEF}；步骤2：由BCDEF得出右子树集合的根节点为B，由中序可知：左子树为空，B{CDEF}；步骤3：同理，二叉树更新后如下。所以按层次输出(同一层从左到右)的序列为ABCDEF，选项A正确。20、下列叙述中正确的是A、对数据进行压缩存储会降低算法的空间复杂度B、算法的优化主要通过程序的编制技巧来实现C、算法的复杂度与问题的规模无关D、数值型算法只需考虑计算结果的可靠性标准答案：A知识点解析：算法的空间复杂度是指执行这个算法所需要的内存空间，包括3个部分：输入数据所占的存储空间：程序本身所占的存储空间；算法执行过程中所需要的额外空间。为了降低算法的空间复杂度，主要应减少输入数据所占的存储空间以及额外空间，通常采用压缩存储技术，A选项正确。21、设数据结构B=(D，R)，其中D={a，b，c，d，e，f}R={(a，b)，(b，c)，(c，d)，(d，e)，(e，f)，(f，a)}该数据结构为A、非线性结构B、循环队列C、循环链表D、线性结构标准答案：A知识点解析：该逻辑结构为非线性结构，在R={(a，b)，(b，c)，(c，d)，(d，e)，(e，D，(f，a)}中，各结点之间形成一个循环链。22、下列排序法中，每经过一次元素的交换会产生新的逆序的是A、快速排序B、冒泡排序C、简单插入排序D、简单选择排序标准答案：A知识点解析：冒泡排序只交换相邻元素，但不是每次移动都产生新的逆序。。简单插入排序的元素移动不会产生新的逆序。快速排序每一次交换移动都会产生新的逆序，’因为当不会有新的逆序产生时，本轮比较结束。故选项A正确。23、某带链的队列初始状态为front=rear=NULL。经过一系列正常的入队与退队操作后，front=rear=10。该队列中的元素个数为A、1B、0C、1或0D、不确定标准答案：A知识点解析：循环队列用数组A[0；m-1]存放其元素值．已知其头尾指针分别是front和rear，则当前队列的元素个数是(rear-front+m)％m=1，所以选项A正确。24、某完全二叉树按层次输出(同一层从左到右)的序列为ABCDEFGH。该完全二叉树的前序序列为A、ABDHECFGB、ABCDEFGHC、HDBEAFCGD、HDEBFGCA标准答案：A知识点解析：完全二叉树的特点是除最后一层外，每一层上的节点数均达到最大值；在最后一层上只缺少右边的若干结点。根据上述的特点，完全二叉树按层次输出(同一层从左到右)的序列为ABCDEFGH，可以得到其结构如下：所以此完全二叉树的前序序列是ABDHECFG，选项A正确。25、下列叙述中正确的是A、有的二叉树也能用顺序存储结构表示B、有两个指针域的链表就是二叉链表C、多重链表一定是非线性结构D、顺序存储结构一定是线性结构标准答案：A知识点解析：完全二叉树如果“根”从1开始编号，则第i结点的左孩子编号为2i，右孩子为2i+1，双亲编号为(i／2)下取整，空间紧密，适合顺序存储结构。所以选项A正确。小提示：取整是指取不超过实数x的最大整数，称为x的整数部分。上取整就是对实数取大于当前实数的第一个整数；下取整就是对当前实数去掉小数取整。26、下列各排序法中，最坏情况下时间复杂度最小的是A、堆排序B、快速排序C、希尔排序D、冒泡排序标准答案：A知识点解析：快速排序、冒泡排序最坏情况下时间复杂度是O(n2)；希尔排序最坏情况下时间复杂度是O(n1．2)。堆排序最坏情况下时间复杂度是O(nlog2n)，所以选项A正确。27、某带链队列初始状态为front=rear=NULL。经过一系列正常入队与退队操作后，front=10，rear=5。该队列中的元素个数为A、不确定B、5C、4D、6标准答案：A知识点解析：循环队列用数组A[0：m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列的元素个数是(rear-front+m)％m=(5-10+m)％m=(m-5)％m。因为本题中的m值不确定，所以(m-5)％m的值不能确定。所以选项A正确。国家二级ACCESS机试选择题（数据结构与算法）模拟试卷第5套一、选择题(本题共27题，每题1.0分，共27分。)1、下列各序列中不是堆的是A、(91，85，53，36，47，30，24，12)B、(91，85，53，47，36，30，24，12)C、(47，91，53，85，30，12，24，36)D、(91，85，53，47，30，12，24，36)标准答案：C知识点解析：堆可以看成一棵完全二叉树：任一根节点＞=左右孩子(或者＜=)，(大的叫大根堆，小的叫小根堆)。注意一个堆中的这种性质有一致性，不能既有大于又有小于情况存在。此题可以这么做，把结点按照完全二叉树画出来就一目了然了。这个题目很明显91是最大的根，而选项C是“左根右”的排序，那么91的左边只有47，其他都在右边，而右边无法按照此顺序排列，所以选项C不是堆。2、深度为5的完全二叉树的结点数不可能是A、15B、16C、17D、18标准答案：B知识点解析：对于满二叉树，叶子结点的数目等于2(n-1)，n为深度，这里就是2的5-1=4次方，就是16。所以选项A为正确答案。3、有二叉树如下图所示：则前序序列为A、ABDEGCFHB、DBGEAFHCC、DGEBHFCAD、ABCDEFGH标准答案：A知识点解析：前序遍历首先访问根结点然后遍历左子树，最后遍历右子树；在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。故选项A正确，选项B为中序遍历，选项C为后序遍历，选项D不正确。4、下列叙述中正确的是A、循环队列是顺序存储结构B、循环队列是链式存储结构C、循环队列是非线性结构D、循环队列的插入运算不会发生溢出现象标准答案：A知识点解析：循环队列属于队列的特例和栈同属于线性结构，所以选项C不正确。在顺序队列中，由于数组空间不够而产生的溢出叫真溢出；顺序队列因多次入队列和出队列操作后出现的有存储空间但不能进行入队列操作的溢出称为假溢出；假溢出是由于队尾rear的值和队头front的值不能由所定义数组下界值自动转为数组上界值而产生的，解决的办法是把顺序队列所使用的存储空间构造成一个逻辑上首尾相连的循环队列。因此，顺序队列通常都采用顺序循环队列结构；栈的存储方式有顺序存储和链式存储，故选项A正确，选项B不正确。循环队列虽然能解决假溢出，却不能解决在顺序队列中，由于数组空间不够而产生的真溢出，故选项D不正确。5、下列叙述中正确的是A、所有数据结构必须有根结点B、所有数据结构必须有终端结点(即叶子结点)C、只有一个根结点，且只有一个叶子结点的数据结构一定是线性结构D、没有根结点或没有叶子结点的数据结构一定是非线性结构标准答案：D知识点解析：只有一个空节点的结构也属数据结构，所以选项A和选项B不正确；有且只有一个根结点，每一个结点最多有一个前件，也最多有一个后件的数据结构才属于线性结构，其它的都属于非线性结构，故选项C不正确，选项D正确。6、下列关于算法的描述中错误的是A、算法强调动态的执行过程，不同于静态的计算公式B、算法必须能在有限个步骤之后终止C、算法设计必须考虑算法的复杂度D、算法的优劣取决于运行算法程序的环境标准答案：D知识点解析：算法的优劣取决自身的运行效率，时间和空间复杂度高低，并不取决于运行算法程序的环境，故选项D错误。7、设有二叉树如下图所示：则中序序列为A、ABDEGCFHB、DBGEAFHCC、DGEBHFCAD、ABCDEFGH标准答案：B知识点解析：中序遍历(LDR)是指首先遍历左子树，然后访问根结点，最后遍历右子树，选项B正确。8、线性表的链式存储结构与顺序存储结构相比，链式存储结构的优点有A、节省存储空间B、插入与删除运算效率高C、便于查找D、排序时减少元素的比较次数标准答案：B知识点解析：顺序存储时，相邻数据元素的存放地址也相邻(逻辑与物理统一)；要求内存中可用存储单元的地址必须是连续的。优点是存储密度大(=1)，存储空间利用率高；缺点是插入或删除元