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

国家二级ACCESS机试选择题（数据结构与算法）模拟试卷2（共9套）（共289题）国家二级ACCESS机试选择题（数据结构与算法）模拟试卷第1套一、选择题(本题共30题，每题1.0分，共30分。)1、对长度为n的线性表排序，在最坏情况下，比较次数不是n(n—1)／2的排序方法是A、快速排序B、冒泡排序C、直接插入排序D、堆排序标准答案：D知识点解析：各种排序方法中最坏情况下需要比较的次数分别为：冒泡排序n(n一1)／2、快速排序n(n一1)／2、简单插入排序n(n-1)／2、希尔排序0(n1.5)、简单选择排序n(n-1)／2、堆排序O(nlog2n)。2、下列关于栈的叙述正确的是A、栈按“先进先出”组织数据B、栈按“先进后出”组织数据C、只能在栈底插入数据D、不能删除数据标准答案：B知识点解析：栈是限定在一端进行插入和删除的线性表，允许进行插入和删除元素的一端称为栈顶，另一端称为栈底。栈是按照“先进后出”的原则组织数据的。3、某二叉树有5个度为2的结点，则该二叉树中的叶子结点数是A、10B、8C、6D、4标准答案：C知识点解析：根据二叉树的性质，在任意二叉树中，度为0的结点总是比度为2的结点多一个。4、下列叙述中正确的是A、算法复杂度是指算法控制结构的复杂程度B、算法复杂度是指设计算法的难度C、算法的时间复杂度是指设计算法的工作量D、算法的复杂度包括时间复杂度与空间复杂度标准答案：D知识点解析：算法复杂度，即算法在编写成可执行程序后，运行时所需要的资源，资源包括时间资源和内存资源。一个算法的评价主要从时间复杂度和空间复杂度来考虑。算法的时间复杂度是指执行算法所需要的计算工作量。空间复杂度是指算法在计算机内执行时所需存储空间的度量。5、下列叙述中正确的是A、循环队列有队头和队尾两个指针，因此，循环队列是非线性结构B、在循环队列中，只需要队头指针就能反映队列中元素的动态变化情况C、在循环队列中，只需要队尾指针就能反映队列中元素的动态变化情况D、循环队列中元素的个数是由队头指针和队尾指针共同决定标准答案：D知识点解析：循环队列中元素的个数是由队头指针和队尾指针共同决定的，元素的动态变化也是通过队头指针和队尾指针来反映的。6、在长度为n的有序线性表中进行二分查找，最坏情况下需要比较的次数是A、O(n)B、O(n2)C、O(log2n)D、O(nlog2n)标准答案：C知识点解析：对于长度为n的有序线性表，在最坏情况下，二分法查找只需比较log2n次，而顺序查找需要比较n次。7、下列叙述中正确的是A、顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的B、顺序存储结构只针对线性结构，链式存储结构只针对非线性结构C、顺序存储结构能存储有序表，链式存储结构不能存储有序表D、链式存储结构比顺序存储结构节省存储空间标准答案：A知识点解析：顺序存储方式主要用于线性的数据结构，它把逻辑上相邻的数据元素存储在物理上相邻的存储单元里，结点之间的关系由存储单元的邻接关系来体现。而链式存储结构的存储空间不一定是连续的。8、对于循环队列，下列叙述中正确的是A、队头指针是固定不变的B、队头指针一定大于队尾指针C、队头指针一定小于队尾指针D、队头指针可以大于队尾指针，也可以小于队尾指针标准答案：D知识点解析：所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。在循环队列中，用队尾指针rear指向队列中的队尾元素，用队头指针front指向队头元素的前一个位置。循环队列的主要操作是：入队运算和退队运算。每进行一次入队运算，队尾指针就进一。每进行一次退队运算，队头指针就进一。当rear或front等于队列的长度加1时，就把rear或front值置为1。所以在循环队列中，队头指针。可以大于队尾指针，也可以小于队尾指针。9、算法的空间复杂度是指A、算法在执行过程中所需要的计算机存储空间B、算法所处理的数据量C、算法程序中的语句或指令条数D、算法在执行过程中所需要的临时工作单元数标准答案：A知识点解析：算法的空间复杂度是指执行这个算法所需要的内存空间。这个内存空间包括算法程序所占的空间，输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。10、一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是A、12345ABCDEB、EDCBA54321C、ABCDE12345D、54321EDCBA标准答案：B知识点解析：栈是按照“先进后出”或“后进先出”的原则组织数据的。所以出栈顺序是EDCBA54321。11、下列排序方法中，最坏情况下比较次数最少的是A、冒泡排序B、简单选择排序C、直接插入排序D、堆排序标准答案：D知识点解析：冒泡排序、简单选择排序和直接插入排序法在最坏的情况下比较次数为：n(n-l)／2。而堆排序法在最坏的情况下需要比较的次数为0(nlog2n)。其中堆排序的比较次数最少。12、支持子程序调用的数据结构是A、栈B、树C、队列D、二叉树标准答案：A知识点解析：栈是一种限定在一端进行插入与删除的线性表。在主函数调用子函数时，要首先保存主函数当前的状态，然后转去执行子函数，把子函数的运行结果返回到主函数调用子函数时的位置，主函数再接着往下执行，这种过程符合栈的特点。所以一般采用栈式存储方式。13、算法的有穷性是指A、算法程序的运行时间是有限的B、算法程序所处理的数据量是有限的C、算法程序的长度是有限的D、算法只能被有限的用户使用标准答案：A知识点解析：算法的有穷性，是指算法必须能在有限的时间内做完，即算法必须能在执行有限个步骤之后终止。14、下列数据结构中，属于非线性结构的是A、循环队列B、带链队列C、二叉树D、带链栈标准答案：C知识点解析：根据数据结构中各数据元素之间的前后件关系的复杂程度，一般将数据结构分为两大类：线性结构和非线性结构。循环队列、带链队列和带链栈都是线性结构，而二叉树是非线性结构。15、下列叙述中正确的是A、栈是“先进先出”的线性表B、队列是“先进后出”的线性表C、循环队列是非线性结构D、有序线性表既可以采用顺序存储结构，也可以采用链式存储结构标准答案：D知识点解析：本题主要考查了栈、队列、循环队列的概念，栈是先进后出的线性表，队列是先进先出的线性表。根据数据结构中各数据元素之间的前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。有序线性表既可以采用顺序存储结构，又可以采用链式存储结构。16、下列数据结构中，能够按照“先进后出”原则存取数据的是A、循环队列B、栈C、队列D、二叉树标准答案：B知识点解析：栈按照“先进后出”(FILO)或“后进先出”(LIFO)组织数据；队列是“先进先出”(FIFO)或“后进后出”(LILO)的线性表。17、下列叙述中正确的是A、线性表的链式存储结构与顺序存储结构所需要的存储空间是相同的B、线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构C、线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构D、以上三项均正确标准答案：B知识点解析：线性表的存储分为顺序存储和链式存储。在顺序存储中，所有元素所占的存储空间是连续的。而在链式存储的方式中，将存储空间的每一个存储结点分为两部分，一部分用于存储数据元素的值，称为数据域：另一部分用于存储下一个元素的存储序号，称为指针域。所以线性表的链式存储方式比顺序存储方式的存储空间要大一些。18、下列叙述中正确的是A、栈是一种先进先出的线性表B、队列是一种后进先出的线性表C、栈与队列都是非线性结构D、栈与队列都是线性结构标准答案：D知识点解析：栈是先进后出，队列是先进先出。栈和队列都是一种线性表，属于线性结构。19、一棵完全二叉树共有360个结点，则在该二叉树中度为l的结点个数为A、0B、1C、180D、181标准答案：B知识点解析：对于一个具有n个结点的完全二叉树，其深度为[10g2n]+l。本题中这个二叉树的深度为[log23601+1=8+1=9。根据满二叉树的性质，深度为8的满二叉树其结点数为28一1=256．1=255。这个完全二叉树的第9层的结点数为360．255=105。完全二叉树的性质非叶子结点的子结点都为2，105除以2其商为52余数为1。因此该二叉树中度为1的结点个数为1。选项B正确。20、算法的时间复杂度是指A、设计该算法所需的工作量B、执行该算法所需要的时间C、执行该算法时所需要的基本运算次数D、算法中指令的条数标准答案：D知识点解析：算法的时间复杂度，是指执行算法所需要的计算工作量。算法的工作量可以用算法在执行过程中所需基本运算的执行次数来度量。21、下列关于栈叙述正确的是A、栈顶元素最先能被删除B、栈顶元素最后才能被删除C、栈底元素永远不能被删除D、以上三种说法都不对标准答案：A知识点解析：栈是先进后出的线性表，栈顶的元素最先被删除，栈底的元素最后被删除。22、下列叙述中正确的是A、在栈中，栈中元素随栈底指针与栈顶指针的变化而动态变化B、在栈中，栈顶指针不变，栈中元素随栈底指针的变化而动态变化C、在栈中，栈底指针不变，栈中元素随栈顶指针的变化而动态变化D、上述三种说法都不对标准答案：C知识点解析：在栈中，允许插入与删除的一端称为栈顶，而不允许插入与删除的另一端称为栈底。栈跟队列不同，元素只能在栈项压入或弹出，栈底指针不变，栈中元素随栈顶指针的变化而动态变化，遵循后进先出的规则。23、某二叉树共有7个结点，其中叶子结点只有1个，则该二叉树的深度为(假设根结点在第l层)A、3B、4C、6D、7标准答案：D知识点解析：根据二叉树的性质，度为0的结点(即叶子结点)总是比度为2的结点多一个。题目中的二叉树的叶子结点为1，因此度为2的结点的数目为0，故该二叉树为7层，每层只有一个结点。24、设循环队列存储空间为Q(1：50)，初始状态为front=rear=50。经过一系列入队和退队操作后，front=rear=25，则该循环队列中元素个数为A、26B、25C、24D、0或50标准答案：D知识点解析：在循环队列中，用队尾指针rear指向队列中的队尾元素，用排头指针front指向排头元素的前一个位置。因此，从排头指针front指向的后一个位置直到队尾指针rear指向的位置之间所有的元素为队列中的元素。在循环队列动态变化过程中，当循环队列满时有front=rear，而当循环队列空时也有front=rear。即在循环队列中，当front=rear时，不能确定是队列满还是队列空。所以对于这个题目来说，当front=rear=25，要么队列为空，队列中的元素个数为0；要么队列为满，队列中的元素个数为50，选项D正确。25、下列叙述中正确的是A、算法就是程序B、设计算法时只需要考虑数据结构的设计C、设计算法时只需要考虑结果的可靠性D、设计算法时要考虑时间复杂度和空间复杂度标准答案：D知识点解析：算法复杂度，即算法在编写成可执行程序后，运行时所需要的资源，资源包括时间资源和内存资源。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。26、下列叙述中正确的是A、有一个以上根结点的数据结构不一定是非线性结构B、只有一个根结点的数据结构不一定是线性结构C、循环链表是非线性结构D、双向链表是非线性结构标准答案：B知识点解析：在数据结构中，树这类的数据结构只有一个根结点，但它不是线性结构。27、下列关于二叉树的叙述中，正确的是A、叶子结点总是比度为2的结点少一个B、叶子结点总是比度为2的结点多一个C、叶子结点数是度为2的结点数的两倍D、度为2的结点数是度为l的结点数的两倍标准答案：B知识点解析：由二叉树的性质可以知道在二叉树中叶子结点总是比度为2的结点多一个。28、下列各组的排序方法中，最坏情况下比较次数相同的是A、冒泡排序与快速排序B、简单插入排序与希尔排序C、堆排序与希尔排序D、快速排序与希尔排序标准答案：A知识点解析：最坏情况下冒泡排序需要比较n(n-1)／2次，即序列逆序的情况。简单插入排序，无论是否最坏情况，都需要n(n-1)／2次。直接插入排序，最坏情况需要比较次n(n-1)／2次。堆排序，无论是否最坏都要比较O(nlog，n)次。快速排序，最坏情况退化为冒泡排序，需要比较n(n-1)／2次。在最坏情况下，希尔排序所需要的比较次数为O(n’。1。29、下列叙述中正确的是A、循环队列是队列的一种链式存储结构B、循环队列是队列的一种顺序存储结构C、循环队列是非线性结构D、循环队列是一种逻辑结构标准答案：B知识点解析：本题主要考查循环队列的概念，循环队列作为队列的一种也应该是线性结构。队列是一种逻辑结构，而循环队列是一种顺序存储结构的队列。30、下列关于线性链表的叙述中，正确的是A、各数据结点的存储空间可以不连续，但它们的存储顺序与逻辑顺序必须一致B、各数据结点的存储顺序与逻辑顺序可以不一致，但它们的存储空间必须连续C、进行插入与删除时，不需要移动表中的元素D、以上都不正确标准答案：C知识点解析：线性表的链式存储结构称为线性链表。在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。国家二级ACCESS机试选择题（数据结构与算法）模拟试卷第2套一、选择题(本题共31题，每题1.0分，共31分。)1、一棵二叉树共有25个结点，其中5个是叶子结点，则度为1的结点数为A、16B、10C、6D、4标准答案：A知识点解析：根据二叉树的性质，在任意二叉树中，度为O的结点(即叶子结点)总是比度为2的结点多一个，故此度为1的结点个数：总结点数．叶子节点数．度为2的节点数=25-5-4=16。2、设循环队列存储空间为Q(1：50)。初始状态为front=rear=50。经过一系列入队和退队操作后，front=14，rear=19，则该循环队列中的元素个数为A、46B、45C、6D、5标准答案：D知识点解析：在循环队列中，用队尾指针rear指向队列中的队尾元素，用排头指针front指向排头元素的前一个位置。因此，从排头指针front指向的后一个位置直到队尾指针rear指向的位置之间所有的元素为队列中的元素。本题中的元素个数是从队列的索引15位置开始到索引19位置，共有5元素。3、下列链表中，其逻辑结构属于非线性结构的是A、二叉链表B、循环链表C、双向链表D、带链的栈标准答案：A知识点解析：二叉链表作为树的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。4、设循环队列的存储空间为Q(1：35)，初始状态为front=rear=35。现经过一系列入队与退队运算后，front=15，rear=15，则循环队列中的元素个数为A、15B、16C、20D、0或35标准答案：D知识点解析：循环队列的队头指针和尾指针都等于15，此循环队列中元素的个数有两种情况，第一种情况是队头指针和尾指针都是第一次到达15，此时元素个数为O：第二种情况是队头指针第一次到达15，而尾指针第二次到达15，此时元素个数为35。5、下列关于栈的叙述中，正确的是A、栈底元素一定是最后入栈的元素B、栈顶元素一定是最先入栈的元素C、栈操作遵循先进后出的原则D、以上三种说法都不对标准答案：C知识点解析：栈是限定只能在表的一端进行插入和删除操作的线性表，必须按“后进先出”的规则操作元素。6、设二叉树共有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个结点个数不能确定。7、下列叙述中正确的是A、程序执行的效率与数据的存储结构密切相关B、程序执行的效率只取决于程序的控制结构C、程序执行的效率只取决于所处理的数据量D、以上都不正确标准答案：A知识点解析：影响程序执行效率的因素有很多，如数据的存储结构、程序处理的数据量、程序的算法等。顺序存储结构和链式存储结构在数据插入和删除操作上的效率就存在差别。其中，链式存储结构的效率要高一些。8、下列与队列结构有关联的是A、函数的递归调用B、数组元素的引用C、多重循环的执行D、先到先服务的作业调度标准答案：D知识点解析：队列中最先插入的元素将最先被删除，最后插入的元素将最后被删除。9、对如下图所示的二叉树进行前序遍历的结果为A、DYBEAFCZXB、YDEBFZXCAC、ABDYECFXZD、ABCDEFXYZ标准答案：C知识点解析：二叉树前序遍历的简单描述：若二叉树为空，则结束返回；否则：①访问根结点；②前序遍历左子树；③前序遍历右子树。可见，前序遍历二叉树的过程是一个递归的过程。根据题目中给出的二叉树的结构可知前序遍历的结果是ABDYECFXZ。10、一个栈的初始状态为空。现将元素1，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。11、下列叙述中正确的是A、一个算法的空间复杂度大，则其时间复杂度也必定大B、一个算法的空间复杂度大，则其时间复杂度必定小C、一个算法的时间复杂度大，则其空间复杂度必定小D、算法的时间复杂度与空间复杂度没有直接关系标准答案：D知识点解析：算法的复杂度主要包括时间复杂度和空间复杂度。算法的时间复杂度是指执行算法所需要的计算工作量，算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数，即算法的工作量=f(n)，其中n是问题的规模；算法的空间复杂度，一般是指执行这个算法所需要的内存空间。一个算法所占用的存储空间包括算法程序所占用的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。根据各自的定义可知，算法的时间复杂度与空间复杂度并不相关。12、下列叙述中正确的是A、循环队列中的元素个数随队头指针与队尾指针的变化而动态变化B、循环队列中的元素个数随队头指针的变化而动态变化C、循环队列中的元素个数随队尾指针的变化而动态变化D、循环队列中的元素个数不会变化标准答案：A知识点解析：所谓循环结构就是将队列存储空间的最后一个位置绕到第一个位置上，形成逻辑上的环状空间，循环使用。在循环队列中，用队尾指针rear指向队列中的队尾元素，用队头指针front指向队头元素的前一个位置，因此，队列中的元素数等于从队头指针front指向的后一个位置与队尾指针rear指向位置之间的元素数量。13、一棵二叉树中共有80个叶子结点与70个度为1的结点，则该二叉树中的总结点数为A、219B、229C、230D、231标准答案：B知识点解析：根据二叉树的性质，在任意二叉树中，度为0的结点(即叶子结点)总是比度为2的结点多一个，故总结点数=叶子节点数+度为2的节点数+度为1的节点数=80+79+70=229。14、对长度为10的线性表进行冒泡排序，最坏情况下需要比较的次数为A、9B、10C、45D、90标准答案：C知识点解析：线性表的长度为n，最坏情况下冒泡排序需要比较的次数为n(n一1)／2。15、下列叙述中正确的是A、算法的效率只与问题的规模有关，而与数据的存储结构无关B、算法的时间复杂度是指执行算法所需要的计算工作量C、数据的逻辑结构与存储结构是一一对应的D、算法的时间复杂度与空间复杂度一定相关标准答案：B知识点解析：算法的时间复杂度是指执行算法所需要的计算工作量。算法的工作量用算法所执行的基本运算的次数来度量，而算法所执行的基本运算次数是问题规模的函数，算法的空间复杂度一般是指执行这个算法所需要的内存空间。算法的时间复杂度与空间复杂度并不相关。数据的逻辑结构就是数据元素之间的逻辑关系，它是从逻辑上描述数据元素之间的关系，是独立于计算机的；数据的存储结构是研究数据元素和数据元素之间的关系如何在计算机中表示，它们并非一一对应。算法的执行效率不仅与问题的规模有关，还与数据的存储结构有关。16、下列叙述中正确的是A、线性表链式存储结构的存储空间一般要少于顺序存储结构B、线性表链式存储结构与顺序存储结构的存储空间都是连续的C、线性表链式存储结构的存储空间可以是连续的，也可以是不连续的D、以上都不正确标准答案：C知识点解析：线性表的存储分为顺序存储和链式存储。在顺序存储中，所有元素所占的存储空间是连续的。而在链式存储的方式中，将存储空间的每一个存储结点分为两部分，一部分用于存储数据元素的值，称为数据域；另一部分用于存储下一个元素的存储序号，称为指针域。所以线性表的链式存储方式比顺序存储方式的存储空间要大一些。17、某二叉树共有12个结点，其中叶子结点只有1个。则该二叉树的深度为(根结点在第1层)A、3B、6C、8D、12标准答案：D知识点解析：根据二叉树的性质，度为0的结点(即叶子结点)总是比度为2的结点多一个。题目中的二叉树的叶子结点为1，因此度为2的结点的数目为0，故该二叉树为12层，每层只有一个结点。18、对长度为n的线性表作快速排序，在最坏情况下，比较次数为A、nB、n一1C、n(n一1)D、n(n-1)／2标准答案：D知识点解析：假设线性表的长度为n，则在最坏情况下，冒泡排序需要经过n／2遍的从前往后的扫描和n／2遍的从后往前的扫描，需要的比较次数为n(n-1)／2。快速排序法也是一种互换类的排序方法，但由于它比冒泡排序法的速度快，因此，称为快速排序法。19、下列叙述中正确的是A、有且只有一个根结点的数据结构一定是线性结构B、每一个结点最多有一个前件也最多有一个后件的数据结构一定是线性结构C、有且只有一个根结点的数据结构一定是非线性结构D、有且只有一个根结点的数据结构可能是线性结构，也可能是非线性结构标准答案：D知识点解析：根据数据结构中各数据元素之间的前后件关系的复杂程度，一般将数据结构分这两大类型：线性结构与非线性结构。如果一个非空的数据结构满足两个条件：①有且只有一个根结点；②每一个结点最多有一个前件，也最多有一个后件。称该数据结构为线性结构，又称为线性表。对于这个题目来说，有且只有一个根结点的数据结构可能是线性结构，也可能是非线性结构。具有一个根结点的树就是一个非线性结构，选项D正确。20、下列叙述中错误的是A、在双向链表中，可以从任何一个结点开始直接遍历到所有结点B、在循环链表中，可以从任何一个结点开始直接遍历到所有结点C、在线性单链表中，可以从任何一个结点开始直接遍历到所有结点D、在二叉链表中，可以从根结点开始遍历到所有结点标准答案：C知识点解析：线性队列是一种线性单链表，对线性队列的遍历只能从队列的头开始，从中间的结点开始不能够遍历到所有的结点。选项C的描述是错误的。21、某二叉树共有13个结点，其中有4个度为1的结点，则叶子结点数为A、5B、4C、3D、2标准答案：A知识点解析：根据二叉树性质，在任意一颗二叉树中，度为0的结点(即叶子结点)总是比度为2的结点多一个，即有n0=n2+1。本题总结点数：13=n0+n1+n2=n2+1+4+n2=2n2+5，n2=4，所以叶子结点数等于4+1=5，选项A正确。22、设栈的顺序存储空间为s(1：50)，初始状态为top=0。现经过一系列入栈与退栈运算后，top=20，则当前栈中的元素个数为A、30B、29C、20D、19标准答案：C知识点解析：栈是允许在栈顶进行插入和删除的线性表，不允许在栈底进行插入与删除。通常用指针top来指示栈顶的位置，用指针bottom指向栈底。对栈的操作有入栈和退栈两种。入栈运算：首先将栈顶指针进一(即top加1)，然后将新元素插入到栈顶指针指向的位置。退栈运算：首先将栈顶元素(栈顶指针指向的元素)赋给一个指定的变量，然后将栈顶指针退一(即top减1)。因为初始状态为top=0，经过入栈和退栈操作后栈中的元素个数就是too指针指向的位置。选项C正确。23、下列叙述中正确的是A、栈与队列都只能顺序存储B、循环队列是队列的顺序存储结构C、循环链表是循环队列的链式存储结构D、以上三项均错误标准答案：B知识点解析：栈和队列是按数据的逻辑结构划分是线性结构。数据在内存或磁盘上的存储分为顺序存储结构和链式存储结构。线性结构的数据可以按顺序存储结构存储，也可以按链式存储结构存储，而循环队列是队列的顺序存储结构。选项B正确。24、设某二叉树的前序序列为ABC，中序序列为CBA，则该二叉树的后序序列为A、BCAB、CBAC、ABCD、CAB标准答案：B知识点解析：二叉树的前序遍历的顺序为首先访问根结点，再依次访问左结点和右结点。中序遍历的顺序为首先访问左结点，然后依次访问根结点和右结点。后序遍历的顺序为首先访问左结点，然后依次访问右结点和根结点。根据前序可以很快确定根，然后可以查看根在中序中位置，将中序分为左右两部分，左边和右边两颗树，在按照上述方式递推出确定左子树的根和右子树。对于本题根据前序，可以确定A为根，A在中序中的位置，可以确定CB为A的左子树上的结点，没有右子树。确定A之后，再看中序第二个值为B，查看B在中序中的位置，C在B左边，确定C为B的左子树。因此，后序是CBA。25、下列排序方法中，最坏情况下时间复杂度最小的是A、冒泡排序B、快速排序C、堆排序D、直接插入排序标准答案：C知识点解析：排序方法中最坏情况下时间复杂度的大小如下表：根据上表可知选项C正确。26、为了对有序表进行对分查找，则要求有序表A、只能顺序存储B、只能链式存储C、可以顺序存储也可以链式存储D、任何存储方式标准答案：A知识点解析：有序表的对分查找条件是有序表为顺序存储。顺序查找：①如果线性表为无序表(即表中元素的排序是无序的)，则无论是顺序存储结构还是链式存储结构，都只能用顺序查找；②即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。分块查找(又称索引顺序查找)：分块有序表结构分为两部分，①线性表本身采用顺序存储结构；②在建立一个索引表，在索引表中，对线性表的每个子表建立一个索引结点，每个结点包括两个域：一是数据域，用于存放对应子表中的最大元素值：一是指针域。用于指示对应子表的第一个元素在整个线性表中的序号。显然索引表关于数据域是有序的。27、设某二叉树的后序序列为CBA，中序序列为ABC，则该二叉树的前序序列为A、BCAB、CBAC、ABCD、CAB标准答案：C知识点解析：二叉树的前序遍历顺序为首先访问根结点，再依次访问左结点和右结点。中序遍历的顺序为首先访问左结点，然后依次访问根结点和右结点。后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点。根据后序可以很快确定根结点，然后可以查看根在中序中位置，将中序分为左右两部分，左边和右边两颗树，在按照上述方式递推出确定左子树的根和右子树。本题根据后序，可以确定A为根结点；根据B在中序中的位置，可以确定A没有左子树，BC为A的右子树，C为B的右子树。本题的具体二叉树如下：因此，这棵二叉树的前序是ABC，选项C正确。28、下列叙述中正确的是A、存储空间不连续的所有链表一定是非线性结构B、结点中有多个指针域的所有链表一定是非线性结构C、能顺序存储的数据结构一定是线性结构D、带链的栈与队列是线性结构标准答案：D知识点解析：计算机中数据按照其数据逻辑结构，可以分为线性结构和非线性结构。而数据在内存或磁盘中的存储，可以分为顺序存储和链式存储。数据的逻辑结构与存储结构之间没有对应的关系。所以选项ABC都是错误的，栈和队列按照数据的逻辑划分都是线性结构。29、算法时间复杂度的度量方法是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正确。30、设循环队列为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正确。31、设顺序表的长度为40，对该表进行冒泡排序。在最坏情况下需要的比较次数为A、780B、820C、40D、41标准答案：A知识点解析：冒泡排序(BubbleSort)，是一种计算机科学领域的较简单的排序算法。冒泡排序算法的运作如下：比较相邻的元素。如果第一个比第二个大，就交换它们两个；对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数；针对所有的元素重复以上的步骤，除了最后一个：持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。冒泡排序的最坏时间复杂度为(n*(n—1))／2=780。国家二级ACCESS机试选择题（数据结构与算法）模拟试卷第3套一、选择题(本题共32题，每题1.0分，共32分。)1、带链栈空的条件是A、top=bottom=NULLB、top=-1~bottom=NULLC、top=NULL且bottom-1D、top=bottom=-1标准答案：A知识点解析：栈的链式存储结构称为链栈。在链栈中，只会出现栈空和非空两种状态。当栈为空时，有too=bottom=NuLL；当栈非空时，top指向链表的第一个结点(栈顶)。所以选项A正确。2、设一棵度为3的树，其中度为2，1，0的结点数分别为3，1，6。该树中度为3的结点数为A、1B、2C、3D、不可能有这样的树标准答案：A知识点解析：因为任一棵树中，结点总数=总分支数目+1，所以：6+1+3+n3=(0*6+1*1+2*3+3*n3)+1。运算结果n3=1。其中，n3表示度为3的结点数，所以选项A正确。3、下列数据结构中，不能采用顺序存储结构的是A、栈B、堆C、队列D、非完全二叉树标准答案：D知识点解析：堆中某个结点的值总是不大于或不小于其父结点的值、堆总是一棵完全二叉树，可以以顺序存储结构存储；队列的存储结构分为链式存储、顺序存储两种；栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表，可以以顺序存储结构存储。4、设二叉树共有375个结点，其中度为2的结点有187个。则度为1的结点个数是A、0B、1C、188D、不可能有这样的二叉树标准答案：A知识点解析：二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2i-1个结点；深度为k的二叉树至多有2k-1个结点：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。本题中，度为2的结点有187个，叶子结点应该有187+1=188个，度为1的结点个数=375一187-188=0。5、在带链队列中，经过一系列正常的操作后，如果front=rear，则队列中的元素个数为A、0或1B、0C、1D、队列满标准答案：A知识点解析：队列是一种特殊的线性表，特殊之处在于它只允许在表的前端(front)进行删除操作，而在表的后端(rear)进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列的链式存储也称为链队列.为了便于操作，可给链队列添加1个头结点，并令头指针指向头结点。队列为空的判断条件是头指针和尾指针的值相同，且均指向头结点。当队列为空(0)或1时，front=rear。6、设一棵树的度为3，其中没有度为2的结点，且叶子结点数为5。该树中度为3的结点数为A、1B、2C、3D、不可能有这样的树标准答案：B知识点解析：树的度是指一棵树中，最大的结点的度称为树的度。本题中树的度为3，那么树中最少有一个结点的度为3。而树中没有度为2的结点，叶子结点数为5，度为1的结点下面只有一个叶子结点。因此，该树中含2个度为3的结点满足题目要求。7、设二叉树共有500个结点，其中叶子结点有250个。则度为2的结点个数是A、0B、1C、249D、不可能有这样的二叉树标准答案：C知识点解析：二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2i-1个结点；深度为k的二叉树至多有2k—1个结点；对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。本题中，叶子结点有250个，度为2的结点数为n2=n0-1=250-1=249。8、下列叙述中正确的是A、带链栈的栈底指针是固定的B、带链栈的栈底指针是随栈的操作而动态变化的C、若带链队列的队头指针与队尾指针相同，则队列为空D、若带链队列的队头指针与队尾指针相同，则队列中至少有一个元素标准答案：B知识点解析：栈(stack)又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈项元素；从一个栈删除元素又称作出栈或退栈，它是把栈项元素删除掉，使其相邻的元素成为新的栈顶元素。带链栈的栈底指针是随栈的操作而动态变化的；若带链队列的队头指针与队尾指针相同，则队列可能为0也可能为1。9、带链队列空的条件是A、front=rear=NULLB、front=rear=一1C、from=NULL且rear=-1D、front=-1且rear=NULL标准答案：A知识点解析：带链队列空的条件有两个：一个是front=rear，一个是它们都等于空。10、设一棵树的度为3，其中没有度为2的结点，且叶子结点数为6。该树中度为3的结点数为A、1B、2C、3D、不可能有这样的树标准答案：D知识点解析：树的度是指一棵树中，最大的结点的度称为树的度。本题中树的度为3，也就是最少有一个度为3的结点。要求没有度为2的结点，且叶子结点为6，如果要有度为3的结点，那么最多只有5个叶子结点，而画不出6个叶子结点。因此这样的树是没有的。11、下列叙述中正确的是A、循环队列是线性结构B、循环队列是线性逻辑结构C、循环队列是链式存储结构D、循环队列是非线性存储结构标准答案：A知识点解析：为充分利用向量空间，克服“假溢出”现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列(CircularQueue)。线性结构是一个有序数据元素的集合。常用的线性结构有：线性表，栈，队列，双队列，数组，串。常见的非线性结构有：二维数组，多维数组，广义表，树(二叉树等)，图。12、设某棵树的度为3，其中度为3、2、1的结点个数分别为3、0、4。则该树中的叶子结点数为A、7B、8C、6D、不可能有这样的树标准答案：A知识点解析：树的度是指一棵树中，最大的结点的度称为“树的度”。根据题目可知本树中没有度为2的结点。树的总结点=(度1*个数+度2*个数…)+1，这里我们设总结点数为n，那么n=3*3+2*0+1*4+1=14。树的叶子结点数等于总结点减去所有度不为0的结点，也就是14-3-4=7。13、设有一个栈与一个队列的初始状态均为空。现有一个序列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,EE标准答案：A知识点解析：栈(stack)又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。因此栈的出栈顺序是先入后出，所以顺序是D,C,B,A。队列是一种特殊的线性表，特殊之处在于它只允许在表的前端(front)进行删除操作，而在表的后端(rear)进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。因此，队的出队顺序是，先入先出，所以顺序是E，F,G,H。最后的顺序是：D,C,B,A,E,F,G,H。14、下列叙述中错误的是A、具有两个根结点的数据结构一定属于非线性结构B、具有两个以上指针域的链式结构一定属于非线性结构C、具有两个以上叶子结点的数据结构一定属于非线性结构D、具有一个根结点且只有一个叶子结点的数据结构也可能是非线性结构标准答案：B知识点解析：非线性结构，数学用语，其逻辑特征是一个结点元素可能有多个直接前驱和多个直接后继。常见的非线性结构有：二维数组，多维数组，广义表，树(二叉树等)，图。15、下列结构中属于线性结构链式存储的是A、双向链表B、循环队列C、二叉链表D、二维数组标准答案：A知识点解析：数据元素之间的关系有两种不同的表示方法：顺序映象和非顺序映象，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构。数据的存储结构是指数据的逻辑结构在计算机中的表示。双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱，它的存储方式是线性结构链式。循环队列、二叉链表和二维数组都是顺序存储结构。16、下列叙述中错误的是A、循环链表中有一个表头结点B、循环链表的存储空间是连续的C、循环链表实现了空表与非空表运算的统一D、循环链表的表头指针与循环链表中最后一个结点的指针均指向表头结点标准答案：B知识点解析：循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。循环链表的结点是指针指向，它不一定要是连续的存储空间，也可以是断开的空间。17、度为3的一棵树共有30个结点，其中度为3、1的结点个数分别为3、4。则该树中的叶子结点数为A、14B、15C、16D、不可能有这样的树标准答案：B知识点解析：根据题目可知本树中还有度为2的结点。树的总结点=(度1*个数+度2*个数…)+1，这里我们设度为2的结点数为x，那么30=3*3+2*x+1*4+1=2*x+14，由此可计算出x=8。树的叶子结点数等于总结点减去所有度不为0的结点，也就是30．3—8—4=15。18、在长度为97的顺序有序表中作二分查找，最多需要的比较次数为A、7B、96C、48D、6标准答案：A知识点解析：二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。最多比较次数的计算方式：k=log2n。其中n代表长度，k为比较次数。本题中可以计算出k=7。19、下列结构中属于非线性结构的是A、二叉链表B、二维数组C、循环队列D、双向链表标准答案：B知识点解析：线性结构是一个有序数据元素的集合。常用的线性结构有：线性表，栈，队列，双队列，数组，串：常见的非线性结构有：二维数组，多维数组，广义表，树(二叉树等)，图。循环队列、双向链表和二叉链表都是线性结构，而二维数组是非线性结构。20、从表中任何一个结点位置出发就可以不重复地访问到表中其他所有结点的链表是A、循环链表B、双向链表C、单向链表D、二叉链表标准答案：A知识点解析：循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环，循环一圈就访问到了表中其它所有结点而不重复。21、设二叉树的前序序列与中序序列均为ABCDEFGH，则该二叉树的后序序列为A、HGFEDCBAB、ABCDEFGHC、ABCDHGFED、DCBAHGFE标准答案：A知识点解析：前序遍历(DLR)是二叉树遍历的一种，也叫做先根遍历、先序遍历、前序周游，可记做根左右；中序遍历(LDR)是二叉树遍历的一种，也叫做中根遍历、中序周游，可记做左根右，后序遍历(LRD)是二叉树遍历的一种，也叫做后根遍历、后序周游，可记做左右根。根据题中前序和中序序列均为ABCDEFGH，可画出二叉树，该二叉树是一个子结点全部在右侧二叉树，然后根据后序遍历方法，可得出后序遍历为HGFEDCBA。22、设某棵树的度为3，其中度为3、1、0的结点个数分别为3、4、15。则该树中总结点数为A、22B、30C、35D、不可能有这样的树标准答案：B知识点解析：本题采用画图法来求出结果。首先先画出包含3个度为3的结点；然后再添加4个度为1的结点，此时最大度为0的结点数为8。根据题目中描述的度为0的结点数有15个，这时要在书中添加度为2的结点，直到度为0的结点数位15。画图结束后，不管是什么样的树，总结点数都是30。23、下列叙述中正确的是A、矩阵是非线性结构B、数组是长度固定的线性表C、对线性表只能作插入与删除运算D、线性表中各元素的数据类型可以不同标准答案：B知识点解析：所谓数组，就是相同数据类型的元素按一定顺序排列的集合，就是把有限个类型相同的变量用一个名字命名，然后用编号区分它们的变量的集合，这个名字称为数组名，编号称为下标。24、在快速排序法中，每经过一次数据交换(或移动)后A、能消除多个逆序B、只能消除一个逆序C、不会产生新的逆序D、消除的逆序个数一定比新产生的逆序个数多标准答案：A知识点解析：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。25、线性表的长度为n。在最坏情况下，比较次数为n-1的算法是A、顺序查找B、有序表的插入C、寻找最大项D、同时寻找最大项与最小项标准答案：C知识点解析：寻找最大项算法是，首先取出第一个数作为最大数，然后和后面的所有项进行比较查找。因此，比较次数为n-1。26、设某棵树的度为3，其中度为2、1、0的结点个数分别为3、4、15。则该树中总结点数为A、22B、30C、35D、不可能有这样的树标准答案：D知识点解析：本题采用画图法来求出结果。首先先画出包含3个度为2的结点；然后再添加4个度为1的结点。根据题目中描述的度为0的结点数有15个，这时要在书中添加度为3的结点，不管怎么添加都不能添加出15个度为0的结点，因此不可能有这样的树。27、下列叙述中错误的是A、向量是线性结构B、非空线性结构中只有一个结点没有前件C、非空线性结构中只有一个结点没有后件D、只有一个根结点和一个叶子结点的结构必定是线性结构标准答案：D知识点解析：线性结构是n个数据元素的有序(次序)集合。①集合中必存在唯一的一个“第一个元素”；②集合中必存在唯一的一个“最后的元素”；③除最后元素之外，其它数据元素均有唯一的“后件”；④除第一元素之外，其它数据元素均有唯一的“前件”。相对应于线性结构，非线性结构的逻辑特征是一个结点元素可能对应多个直接前驱和多个后继。向量符合线性结构特点。非线性结构也会存在只有一个根结点和叶子结点的情况。28、在希尔排序法中，每经过一次数据交换后A、能消除多个逆序B、只能消除一个逆序C、不会产生新的逆序D、消除的逆序个数一定比新产生的逆序个数多标准答案：A知识点解析：希尔排序法(缩小增量法)属于插入类排序，是将整个无序列分割成若干小的子序列分别进行插入排序的方法。插入排序能够消除多个逆序，也会产生新的逆序。消除的逆序与新产生的逆序有多有少。29、设二叉树的后序序列与中序序列均为ABCDEFGH，则该二叉树的前序序列为A、HGFEDCBAB、ABCDEFGHC、ABCDHGFED、DCBAHGFE标准答案：A知识点解析：后序遍历中，最后一个字母是根结点，也就是H是根结点；在中序遍历中，根结点前面的是左子树、后面的是右子树，H后面没有，因此该树没有右子树。同理，可判断出该树是第一个完全的左子树。由此可画出这个二叉树，然后根据二叉树可的前序序列为HGFEDCBA。30、下列叙述中正确的是A、循环队列是队列的链式存储结构B、能采用顺序存储的必定是线性结构C、所有的线性结构都可以采用顺序存储结构D、具有两个以上指针的链表必定是非线性结构标准答案：C知识点解析：根据数据结构中各数据元素之间的前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。有序线性表既可以采用顺序存储结构，又可以采用链式存储结构。所有的线性结构都可以采用顺序存储结构。31、设循环队列的存储空间为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。32、设二叉树的后序序列为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机试选择题（数据结构与算法）模拟试卷第4套一、选择题(本题共32题，每题1.0分，共32分。)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、非线性结构B、循环队列C、循环链表D、线性结构标准答案：A知识点解析：该逻辑结构为非线性结构，在R={(a，b)，(b，c)，(c，d)，(d，e)，(e，f)，(f，a)}中，各结点之间形成一个循环链。2、下列排序法中，每经过一次元素的交换会产生新的逆序的是A、快速排序B、冒泡排序C、简单插入排序D、简单选择排序标准答案：A知识点解析：冒泡排序只交换相邻元素，但不是每次移动都产生新的逆序。简单插入排序的元素移动不会产生新的逆序。快速排序每一次交换移动都会产生新的逆序，因为当不会有新的逆序产生时，本轮比较结束。故选项A正确。3、某带链的队列初始状态为front=rear=NULL。经过一系列正常的入队与退队操作后，front=rear=10。该队列中的元素个数为A、1B、0C、1或0D、不确定标准答案：A知识点解析：循环队列用数组A[0；m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列的元素个数是(rear-front+m)％m=1，所以选项A正确。4、某完全二叉树按层次输出(同一层从左到右)的序列为ABCDEFGH。该完全二叉树的前序序列为A、ABDHECFGB、ABCDEFGHC、HDBEAFCGD、HDEBFGCA标准答案：A知识点解析：完全二叉树的特点是除最后一层外，每一层上的节点数均达到最大值；在最后一层上只缺少右边的若干结点。根据上述的特点，完全二叉树按层次输出(同一层从左到右)的序列为ABCDEFGH，可以得到其结构如下：所以此完全二叉树的前序序列是ABDHECFG，选项A正确。5、下列叙述中正确的是A、有的二叉树也能用顺序存储结构表示B、有两个指针域的链表就是二叉链表C、多重链表一定是非线性结构D、顺序存储结构一定是线性结构标准答案：A知识点解析：完全二叉树如果“根”从1开始编号，则第i结点的左孩子编号为2i，右孩子为2i+1，双亲编号为(i／2)下取整，空间紧密．适合顺序存储结构。所以选项A正确。小提示：取整是指取不超过实数x的最大整数，称为x的整数部分。上取整就是对实数取大于当前实数的第一个整数：下取整就足对当前实数去掉小数取整。6、下列各排序法中，最坏情况下时间复杂度最小的是A、堆排序B、快速排序C、希尔排序D、冒泡排序标准答案：A知识点解析：快速排序、冒泡排序最坏情况下时间复杂度是o(n2)；希尔排序最坏情况下时间复杂度是0(n1．2)。堆排序最坏情况下时间复杂度是O(nlog2n)，所以选项A正确。7、某带链队列初始状态为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+In)％m=(m-5)％m。因为本题中的m值不确定，所以(m-5)％m的值不能确定。所以选项A正确。8、某二叉树的前序序列为ABDFHCEG，中序序列为HFDBACEG。该二叉树按层次输出(同一层从左到右)的序列为A、ABCDEFGHB、HFDBGECAC、HGFEDCBAD、ACEGBDFH标准答案：A知识点解析：由于二叉树的前序序列ABDFHCEG，可以确定这个二叉树的根结点是A。再由中序序列HFDBACEG，可以得到，HFDBt为A的左子树，CEG为A的右子树。同理依次对左子树HFDB和右子树CEG进行同样的推理，得到这个二叉树的结构如下：该二叉树按层次输出(同一层从左到右)的序列为ABCDEFGH，所以选项A正确。9、某带链栈初始状态为top=bottom=NULL，经过一系列正常的入栈与退栈操作后，top=10，bottom=20。该栈中的元素个数为A、不确定B、10C、1D、0标准答案：A知识点解析：对于链栈而言，使用了链表来实现栈，链表中的元素存储在不连续的地址。所以当top=10，bottom=20时，不能确定栈中的元素个数，所以选项A正确。10、设表的长度为15。则在最坏情况下，快速排序所需要的比较次数为A、105B、55C、15D、75标准答案：A知识点解析：假设线性表的长度为n，在最坏情况下，快速排序法的比较次数是n(n-1)／2。题中n=15，所以15*14／2=105。所以选项A正确。11、设循环队列的存储空间为Q(1：100)，初始状态为空。现经过一系列正常操作后，front=49，则循环队列中的元素个数为A、不确定B、49C、51D、50标准答案：A知识点解析：循环队列用数组Q[1：100]存放其元素值，已知其头尾指针分别是front和rear，则当前队列的元素个数是(rear-front+100)％100，题目中首指针rear的值未知，所以循环队列中的元素个数不能确定。所以选项A正确。12、某完全二叉树按层次输出(同一层从左到右)的序列为ABCDEFGH。该完全二叉树的中序序列为A、HDBEAFCGB、HDEBFGCAC、ABDHECFGD、ABCDEFGH标准答案：A知识点解析：完全二叉树的特点是除最后一层外，每一层上的节点数均达到最大值；在最后一层上只缺少右边的若干结点。根据上述特点，完全二叉树按层次输出(同一层从左到右)的序列为ABCDEFGH。可以得到其结构如下：所以此完全二叉树的中序序列是HDBEAFCG。所以选项A正确。13、下列叙述中正确的是A、解决一个问题可以有不同的算法，且它们的时间复杂度可以是不同的B、解决一个问题可以有不同的算法，但它们的时间复杂度必定是相同的C、解决一个问题的算法是唯一的D、算法的时间复杂度与计算机系统有关标准答案：A知识点解析：算法的时间复杂度和问题有关系，因为一个问题很有可能有许多类算法，但是它们的时间复杂度不同，如排序问题就有10种左右算法，它们复杂度显然是不一样的。所以选项A正确。14、设表的长度为n。下列查找算法中，在最坏情况下，比较次数最少的是A、有序表的二分查找B、顺序查找C、寻找最大项D、寻找最小项标准答案：A知识点解析：有序表的二分法查找只适用于顺序存储的有序表。二分查找的基本方法是：将被查元素x与线性表的中间项进行比较，若中间项的值等于x，则说明查到；若小于中间项的值则在线性表的前半部分以相同的方法进行查找；若大于中间项的值则在线性表的后半部分以相同的方法进行查找。在最坏情况下，二分查找需要比较log2n次。顺序查找、寻找最大项、寻找最小项，在最坏情况下，比较次数都是n次。所以选项A正确。15、某带链栈的初始状态为top=bottom=NULL，经过一系列正常的入栈与退栈操作后，top=bottom=20。该栈中的元素个数为A、1B、0C、20D、不确定标准答案：D知识点解析：对于链栈而言，使用了链表来实现栈，链表中的元素存储在不连续的地址。所以当top=bottom=20时，不能确定栈中的元素个数。所以选项D正确。16、某二叉树的前序序列为ABDFHCEG，中序序列为HFDBACEG。该二叉树的后序序列为A、HFDBGECAB、ABCDEFGHC、HGFEDCBAD、ACEGBDFH标准答案：A知识点解析：由于二叉树的前序序列ABDFHCEG，可以确定这个二叉树的根结点是A。再由中序序列HFDBACEG，可以得到，HFDB为A的左子树，CEG为A的右子树。同理依次对左子树HFDB和右子树CEG进行同样的推理，得到这个二叉树的结构如下：对该二叉树的后序遍历序列为HFDBGECA，所以选项A正确。17、下列叙述中错误的是A、算法的时间复杂度与问题规模无关B、算法的时间复杂度与计算机系统无关C、算法的时间复杂度与空间复杂度没有必然的联系D、算法的空间复杂度与算法运行输出结果的数据量无关标准答案：A知识点解析：一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n)／f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))，称O(f(n))为算法的渐进时间复杂度，简称时间复杂度。所以选项A正确。18、设表的长度为20。则在最坏情况下，冒泡排序的比较次数为A、90B、20C、19D、190标准答案：D知识点解析：假设线性表的长度为n，则在最坏情况下，冒泡排序的比较次数为n(n-1)／2。本题中，n=20，所以20*19／2=190。所以选项D正确。19、在带链栈中，经过一系列正常的操作后，如果top=bottom，则栈中的元素个数为A、1B、0C、0或1D、栈满标准答案：C知识点解析：链栈就是没有附加头结点的、运算受限的单链表。栈顶指针就是链表的头指针。如果栈底指针指向的存储单元中存有1元素，则当top=bottom时，栈中的元素个数为1；如果栈底指针指向的存储单元中没有存元素，则当top=bottom时，栈中的元素个数为0。所以选项C正确。20、设一棵树的度为3，共有27个结点，其中度为3，2，0的结点数分别为4，1，10。该树中度为1的结点数为A、11B、12C、13D、不可能有这样的树标准答案：B知识点解析：因为任一棵树中，结点总数=总分支数目+1，所以：27=(0*10+n1*1+2*1+3*4)+1。运算结果n1=12。其中，n1表示叶子结点，所以选项B正确。21、设数据结构B=(D，R)，其中D={a，b，c，d，e，f}R={(f，a)，(d，b)，(c，d)，(c，e)，(a，c)}该数据结构为A、线性结构B、循环队列C、循环链表D、非线性结构标准答案：A知识点解析：由结点之间的关系R={(ea)，(d，b)，(e，d)，(c，e)，(a，c)}可以得到，该数据结构为：“f-a-c-e-d-b”。由此可知结点f没有前驱，结点b没有后继结点，并且其它的结点只有一个前驱结点和一个后继结点，所以该数据结构为线性结构。所以应选A选项。22、下列叙述中错误的是A、循环队列空的条件是队头指针与队尾指针相同B、若二叉树没有叶子结点，则为空二叉树C、带链栈的栈底指针是随栈的操作而动态变化的D、若带链队列中只有一个元素，则队头指针与队尾指针必定相同标准答案：A知识点解析：初始化建空队时，令front=rear=0，当队空时：front=rear；当队满时：front=rear亦成立。因此，只凭等式front=rear无法判断队空还是队满。有两种方法处理上述问题：①另设一个标志位以区别队列是空还是满；②少用一个元素空间，约定以“队列头指针front在队尾指针rear的下一个位置上”作为队列“满”状态的标志。即：队空时：front=rear；队满时：(rear+1)％maxsize=front。所以选项A正确。23、带链栈空的条件是A、top=bottom=NULLB、top=-1且bottom=NULLC、top=NULL且boaom-1D、too=bottom=-1标准答案：A知识点解析：栈的链式存储结构称为链栈。在链栈中，只会出现栈空和非空两种状态。当栈为空时，有top=bottom=NULL；当栈非空时，top指向链表的第一个结点(栈顶)。所以选项A正确。24、设一棵度为3的树，其中度为2，1，0的结点数分别为3，1，6。该树中度为3的结点数为A、1B、2C、3D、不可能有这样的树标准答案：A知识点解析：因为任一棵树中，结点总数=总分支数目+1，所以：6+1+3+n3=(0*6+1*1+2*3+3*n3)+1。运算结果n3=1。其中，n3表示度为3的结点数，所以选项A正确。25、下列数据结构中，不能采用顺序存储结构的是A、栈B、堆C、队列D、非完全二叉树标准答案：D知识点解析：堆中某个结点的值总是不大于或不小于其父结点的值、堆总是一棵完全二叉树，可以以顺序存储结构存储；队列的存储结构分为链式存储、顺序存储两种；栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表，可以以顺序存储结构存储。26、设二叉树共有375个结点，其中度为2的结点有187个。则度为1的结点个数是A、0B、1C、188D、不可能有这样的二叉树标准答案：A知识点解析：二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2i-1个结点；深度为k的二叉树至多有2k-1个结点；对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。本题中，度为2的结点有187个，叶子结点应该有187+1=188个，度为1的结点个数=375—187—188=0。27、在带链队列中，经过一系列正常的操作后，如果front=rear，则队列中的元素个数为A、0或1B、0C、1D、人列满标准答案：A知识点解析：队列是一种特殊的线性表，特殊之处在于它只允许在表的前端(front)进行删除操作，而在表的后端(rear)进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列的链式存储也称为链队列。为了便于操作，可给链队列添加1个头结点，并令头指针指向头结点。队列为空的判断条件是头指针和尾指针的值相同，且均指向头结点。当队列为空(0)或1时，front=rear。28、设一棵树的度为3，其中没有度为2的结点，且叶子结点数为5。该树中度为3的结点数为A、1B、2C、3D、不可能有这样的树标准答案：B知识点解析：树的度是指一棵树中，最大的结点的度称为树的度。本题中树的度为3，那么树中最少有一个结点的度为3。而树中没有度为2的结点，叶子结点数为5，度为1的结点下面只有一个叶子结点。因此，该树中含2个度为3的结点满足题目要求。29、设二叉树共有500个结点，其中叶子结点有250个。则度为2的结点个数是A、0B、1C、249D、不可能有这样的二叉树标准答案：C知识点解析：二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2i-1个结点；深度为k的二叉树至多有2k-1个结点；对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。本题中，叶子结点有250个，度为2的结点数为n2=n0-1=250-1=249。30、下列叙述中正确的是A、带链栈的栈底指针是固定的B、带链栈的栈底指针是随栈的操作而动态变化的C、若带链队列的队头指针与队尾指针相同，则队列为空D、若带链队列的队头指针与队尾指针相同，则队列中至少有一个元素标准答案：B知识点解析：栈(stack)又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。带链栈的栈底指针是随栈的操作而动态变化的；若带链队列的队头指针与队尾指针相同，则队列可能为0也可能为1。31、带链队列空的条件是A、front=rear=NULLB、front=rear=-1C、front=NULL且rear=-1D、front=-1且rear=NULL标准答案：A知识点解析：带链队列空的条件有两个：一个是front=rear，一个是它们都等于空。32、设一棵树的度为3，其中没有度为2的结点，且叶子结点数为6。该树中度为3的结点数为A、1B、2C、3D、不可能有这样的树标准答案：D知识点解析：树的度是指一棵树中，最大的结点的度称为树的度。本题史树的度为3，也就是最少有一个度为3的结点。要求没有度为2的结点，且叶子结点为6，如果要有度为3的结点，那么最多只有s个叶了结点，而画不出6个叶子结点。因此这样的树是没有的。国家二级ACCESS机试选择题（数据结构与算法）模拟试卷第5套一、选择题(本题共30题，每题1.0分，共30分。)1、一棵二叉树共有25个结点，其中5个是叶子结点，则度为1的结点数为A、16B、10C、6D、4标准答案：A知识点解析：根据二叉树的性质，在任意二叉树中，度为0的结点(即叶子结点)总是比度为2的结点多一个，故此度为1的结点个数=总结点数．叶子节点数．度为2的节点数=25-5-4=16。2、设循环队列存储空间为Q(1：50)。初始状态为front=rear=50。经过一系列入队和退队操作后，front=14，rear=19，则该循环队列中的元素个数为A、46B、45C、6D、5标准答案：D知识点解析：在循环队列中，用队尾指针rear指向队列中的队尾元素，用排头指针front指向排头元素的前一个位置。因此，从排头指针front指向的后一个位置直到队尾指针rear指向的位置之间所有的元素为队列中的元素。本题中的元素个数是从队列的索引15位置开始到索引19位置，共有5元素。3、下列链表中，其逻辑结构属于非线性结构的是A、二叉链表B、循环链表C、双向链表D、带链的栈标准答案：A知识点解析：二叉链表作为树的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。4、设循环队列的存储空间为Q(1：35)，初始状态为front=rear=35。现经过一系列入队与退队运算后，front=15，rear=15，则循环队列中的元素个数为A、15B、16C、20D、0或35标准答案：D知识点解析：循环队列的队头指针和尾指针都等于15，此循环队列中元素的个数有两种情况，第一种情况是队头指针和尾指针都是第一次到达15，此时元素个数为0；第二种情况是队头指针第一次到达15，而尾指针第二次到达15，此时元素个数为35。5、下列关于栈的叙述中，正确的是A、栈底元素一定是最后入栈的元素B、栈项元素一定是最先入栈的元素C、栈操