1、国家二级 ACCESS机试选择题（数据结构与算法）模拟试卷 7及答案解析(总分：66.00，做题时间：90 分钟)一、选择题(总题数：33，分数：66.00)1.对长度为 n的线性表排序，在最坏情况下，比较次数不是 n(n一 1)2 的排序方法是（分数：2.00）A.快速排序B.冒泡排序C.直接插入排序D.堆排序2.下列关于栈的叙述正确的是（分数：2.00）A.栈按“先进先出”组织数据B.栈按“先进后出”组织数据C.只能在栈底插入数据D.不能删除数据3.某二叉树有 5个度为 2的结点，则该二叉树中的叶子结点数是（分数：2.00）A.10B.8C.6D.44.下列叙述中正确的是（分数：2.00）
2、A.算法复杂度是指算法控制结构的复杂程度B.算法复杂度是指设计算法的难度C.算法的时间复杂度是指设计算法的工作量D.算法的复杂度包括时间复杂度与空间复杂度5.下列叙述中正确的是（分数：2.00）A.循环队列有队头和队尾两个指针，因此，循环队列是非线性结构B.在循环队列中，只需要队头指针就能反映队列中元素的动态变化情况C.在循环队列中，只需要队尾指针就能反映队列中元素的动态变化情况D.循环队列中元素的个数是由队头指针和队尾指针共同决定6.在长度为 n的有序线性表中进行二分查找，最坏情况下需要比较的次数是（分数：2.00）A.O(n)B.O(n 2 )C.O(log 2 n)D.O(nlog 2
3、n)7.下列叙述中正确的是（分数：2.00）A.顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的B.顺序存储结构只针对线性结构，链式存储结构只针对非线性结构C.顺序存储结构能存储有序表，链式存储结构不能存储有序表D.链式存储结构比顺序存储结构节省存储空间8.对于循环队列，下列叙述中正确的是（分数：2.00）A.队头指针是固定不变的B.队头指针一定大于队尾指针C.队头指针一定小于队尾指针D.队头指针可以大于队尾指针，也可以小于队尾指针9.算法的空间复杂度是指（分数：2.00）A.算法在执行过程中所需要的计算机存储空间B.算法所处理的数据量C.算法程序中的语句或指令条数D.算法
4、在执行过程中所需要的临时工作单元数10.一个栈的初始状态为空。现将元素 1、2、3、4、5、A、B、C、D、E 依次入栈，然后再依次出栈，则元素出栈的顺序是（分数：2.00）A.12345ABCDEB.EDCBA54321C.ABCDE12345D.54321EDCBA11.下列排序方法中，最坏情况下比较次数最少的是（分数：2.00）A.冒泡排序B.简单选择排序C.直接插入排序D.堆排序12.支持子程序调用的数据结构是（分数：2.00）A.栈B.树C.队列D.二叉树13.算法的有穷性是指（分数：2.00）A.算法程序的运行时间是有限的B.算法程序所处理的数据量是有限的C.算法程序的长度是有限的
5、D.算法只能被有限的用户使用14.下列数据结构中，属于非线性结构的是（分数：2.00）A.循环队列B.带链队列C.二叉树D.带链栈15.下列叙述中正确的是（分数：2.00）A.栈是“先进先出”的线性表B.队列是“先进后出”的线性表C.循环队列是非线性结构D.有序线性表既可以采用顺序存储结构，也可以采用链式存储结构16.下列数据结构中，能够按照“先进后出”原则存取数据的是（分数：2.00）A.循环队列B.栈C.队列D.二 3L树17.下列叙述中正确的是（分数：2.00）A.线性表的链式存储结构与顺序存储结构所需要的存储空问是相同的B.线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构C.
6、线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构D.以上三项均正确18.下列叙述中正确的是（分数：2.00）A.栈是一种先进先出的线性表B.队列是一种后进先出的线性表C.栈与队列都是非线性结构D.栈与队列都是线性结构19.一棵完全二叉树共有 360个结点，则在该二叉树中度为 1的结点个数为（分数：2.00）A.0B.1C.1 80D.1 8120.算法的时间复杂度是指（分数：2.00）A.设计该算法所需的工作量B.执行该算法所需要的时间C.执行该算法时所需要的基本运算次数D.算法中指令的条数21.下列关于栈叙述正确的是（分数：2.00）A.栈顶元素最先能被删除B.栈顶元素最后才能被删
7、除C.栈底元素永远不能被删除D.以上三种说法都不对22.下列叙述中正确的是（分数：2.00）A.在栈中，栈中元素随栈底指针与栈顶指针的变化而动态变化B.在栈中，栈顶指针不变，栈中元素随栈底指针的变化而动态变化C.在栈中，栈底指针不变，栈中元素随栈顶指针的变化而动态变化D.上述三种说法都不对23.某二叉树共有 7个结点，其中叶子结点只有 1个，则该二叉树的深度为(假设根结点在第 1层)（分数：2.00）A.3B.4C.6D.724.设循环队列存储空间为 Q(1：50)，初始状态为 front=rear=50。经过一系列入队和退队操作后，front=rear=25，则该循环队列中元素个数为（分数：
8、2.00）A.26B.25C.24D.0或 5025.下列叙述中正确的是（分数：2.00）A.算法就是程序B.设计算法时只需要考虑数据结构的设计C.设计算法时只需要考虑结果的可靠性D.设计算法时要考虑时间复杂度和空间复杂度26.下列叙述中正确的是（分数：2.00）A.有一个以上根结点的数据结构不一定是非线性结构B.只有一个根结点的数据结构不一定是线性结构C.循环链表是非线性结构D.双向链表是非线性结构27.下列关于二叉树的叙述中，正确的是（分数：2.00）A.叶子结点总是比度为 2的结点少一个B.叶子结点总是比度为 2的结点多一个C.叶子结点数是度为 2的结点数的两倍D.度为 2的结点数是度为
9、 1的结点数的两倍28.下列各组的排序方法中，最坏情况下比较次数相同的是（分数：2.00）A.冒泡排序与快速排序B.简单插入排序与希尔排序C.堆排序与希尔排序D.快速排序与希尔排序29.下列叙述中正确的是（分数：2.00）A.循环队列是队列的一种链式存储结构B.循环队列是队列的一种顺序存储结构C.循环队列是非线性结构D.循环队列是一种逻辑结构30.下列关于线性链表的叙述中，正确的是（分数：2.00）A.各数据结点的存储空间可以不连续，但它们的存储顺序与逻辑顺序必须一致B.各数据结点的存储顺序与逻辑顺序可以不一致，但它们的存储空间必须连续C.进行插入与删除时，不需要移动表中的元素D.以上都不正确
10、31.下列叙述中正确的是（分数：2.00）A.算法的复杂度是指算法所处理的数据量B.算法的复杂度是指算法程序中指令的数量C.算法的复杂度是指算法控制结构的复杂程度D.算法的复杂度包括时间复杂度与空间复杂度32.设二叉树的前序序列为 ABDEGHCFU，中序序列为 DBGEHACIFJ。则按层次输出(从上到下，同一层从左到右)的序列为（分数：2.00）A.ABCDEFGHUB.DGHEBUFCAC.JIHGFEDCBAD.GHIJDEFBCA33.设循环队列的存储空间为 Q(1：50)，初始状态为 front=rear=50，经过一系列正常的操作后，front-1=rear。为了在该队列中寻找值
11、最大的元素，在最坏情况下需要的比较次数为（分数：2.00）A.0B.1C.48D.49国家二级 ACCESS机试选择题（数据结构与算法）模拟试卷 7答案解析(总分：66.00，做题时间：90 分钟)一、选择题(总题数：33，分数：66.00)1.对长度为 n的线性表排序，在最坏情况下，比较次数不是 n(n一 1)2 的排序方法是（分数：2.00）A.快速排序B.冒泡排序C.直接插入排序D.堆排序 解析：解析：各种排序方法中最坏情况下需要比较的次数分别为：冒泡排序 n(n-1)2、快速排序 n(n1)2、简单插入排序 n(n-1)2、希尔排序 O(n 1.5 )、简单选择排序 n(n1)2、堆排
12、序 O(nlog 2 n)。2.下列关于栈的叙述正确的是（分数：2.00）A.栈按“先进先出”组织数据B.栈按“先进后出”组织数据 C.只能在栈底插入数据D.不能删除数据解析：解析：栈是限定在一端进行插入和删除的线性表，允许进行插入和删除元素的一端称为栈项，另一一端称为栈底。栈是按照“先进后出”的原则组织数据的。3.某二叉树有 5个度为 2的结点，则该二叉树中的叶子结点数是（分数：2.00）A.10B.8C.6 D.4解析：解析：根据二叉树的性质，在任意二叉树中，度为 0的结点总是比度为 2的结点多一个。4.下列叙述中正确的是（分数：2.00）A.算法复杂度是指算法控制结构的复杂程度B.算法复
13、杂度是指设计算法的难度C.算法的时间复杂度是指设计算法的工作量D.算法的复杂度包括时间复杂度与空间复杂度 解析：解析：算法复杂度，即算法在编写成可执行程序后，运行时所需要的资源，资源包括时间资源和内存资源。一个算法的评价主要从时间复杂度和空间复杂度来考虑。算法的时间复杂度是指执行算法所需要的计算工作量。空间复杂度是指算法在计算机内执行时所需存储空间的度量。5.下列叙述中正确的是（分数：2.00）A.循环队列有队头和队尾两个指针，因此，循环队列是非线性结构B.在循环队列中，只需要队头指针就能反映队列中元素的动态变化情况C.在循环队列中，只需要队尾指针就能反映队列中元素的动态变化情况D.循环队列中
14、元素的个数是由队头指针和队尾指针共同决定 解析：解析：循环队列中元素的个数是由队头指针和队尾指针共同决定的，元素的动态变化也是通过队头指针和队尾指针来反映的。6.在长度为 n的有序线性表中进行二分查找，最坏情况下需要比较的次数是（分数：2.00）A.O(n)B.O(n 2 )C.O(log 2 n) D.O(nlog 2 n)解析：解析：对于长度为 n的有序线性表，在最坏情况下，二分法查找只需比较 log 2 n次，而顺序查找需要比较 n次。7.下列叙述中正确的是（分数：2.00）A.顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的 B.顺序存储结构只针对线性结构，链式存储
15、结构只针对非线性结构C.顺序存储结构能存储有序表，链式存储结构不能存储有序表D.链式存储结构比顺序存储结构节省存储空间解析：解析：顺序存储方式主要用于线性的数据结构，它把逻辑上相邻的数据元素存储在物理上相邻的存储单元里，结点之间的关系由存储单元的邻接关系来体现。而链式存储结构的存储空间不一定是连续的。8.对于循环队列，下列叙述中正确的是（分数：2.00）A.队头指针是固定不变的B.队头指针一定大于队尾指针C.队头指针一定小于队尾指针D.队头指针可以大于队尾指针，也可以小于队尾指针 解析：解析：所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。在
16、循环队列中，用队尾指针 rear指向队列中的队尾元素，用队头指针 front指向队头元素的前一个位置。循环队列的主要操作是：入队运算和退队运算。每进行一次入队运算，队尾指针就进一。每进行一次退队运算，队头指针就进一。当 rear或 front等于队列的长度加 1时，就把 rear或 front值置为 1。所以在循环队列中，队头指针可以大于队尾指针，也可以小于队尾指针。9.算法的空间复杂度是指（分数：2.00）A.算法在执行过程中所需要的计算机存储空间 B.算法所处理的数据量C.算法程序中的语句或指令条数D.算法在执行过程中所需要的临时工作单元数解析：解析：算法的空间复杂度是指执行这个算法所需要
17、的内存空间。这个内存空间包括算法程序所占的空间，输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。10.一个栈的初始状态为空。现将元素 1、2、3、4、5、A、B、C、D、E 依次入栈，然后再依次出栈，则元素出栈的顺序是（分数：2.00）A.12345ABCDEB.EDCBA54321 C.ABCDE12345D.54321EDCBA解析：解析：栈是按照“先进后出”或“后进先出”的原则组织数据的。所以出栈顺序是 EDCBA54321。11.下列排序方法中，最坏情况下比较次数最少的是（分数：2.00）A.冒泡排序B.简单选择排序C.直接插入排序D.堆排序 解析：解析：冒泡排序、简单
18、选择排序和直接插入排序法在最坏的情况下比较次数为：n(n1)2。而堆排序法在最坏的情况下需要比较的次数为 O(nlog 2 n)。其中堆排序的比较次数最少。12.支持子程序调用的数据结构是（分数：2.00）A.栈 B.树C.队列D.二叉树解析：解析：栈是一种限定在一端进行插入与删除的线性表。在主函数调用子函数时，要首先保存主函数当前的状态，然后转去执行子函数，把子函数的运行结果返回到主函数调用子函数时的位置，主函数再接着往下执行，这种过程符合栈的特点。所以一般采用栈式存储方式。13.算法的有穷性是指（分数：2.00）A.算法程序的运行时间是有限的 B.算法程序所处理的数据量是有限的C.算法程序
19、的长度是有限的D.算法只能被有限的用户使用解析：解析：算法的有穷性，是指算法必须能在有限的时间内做完，即算法必须能在执行有限个步骤之后终止。14.下列数据结构中，属于非线性结构的是（分数：2.00）A.循环队列B.带链队列C.二叉树 D.带链栈解析：解析：根据数据结构中各数据元素之间的前后件关系的复杂程度，一般将数据结构分为两大类：线性结构和非线性结构。循环队列、带链队列和带链栈都是线性结构，而二叉树是非线性结构。15.下列叙述中正确的是（分数：2.00）A.栈是“先进先出”的线性表B.队列是“先进后出”的线性表C.循环队列是非线性结构D.有序线性表既可以采用顺序存储结构，也可以采用链式存储结
20、构 解析：解析：本题主要考查了栈、队列、循环队列的概念，栈是先进后出的线性表，队列是先进先出的线性表。根据数据结构中各数据元素之间的前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。有序线性表既可以采用顺序存储结构，又可以采用链式存储结构。16.下列数据结构中，能够按照“先进后出”原则存取数据的是（分数：2.00）A.循环队列B.栈 C.队列D.二 3L树解析：解析：栈按照“先进后出”(FILO)或“后进先出”(LIFO)组织数据；队列是“先进先出”(FIFO)或“后进后出”(LILO)的线性表。17.下列叙述中正确的是（分数：2.00）A.线性表的链式存储结构与顺序存储
21、结构所需要的存储空问是相同的B.线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构 C.线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构D.以上三项均正确解析：解析：线性表的存储分为顺序存储和链式存储。在顺序存储中，所有元素所占的存储空间是连续的。而在链式存储的方式中，将存储空间的每一个存储结点分为两部分，一部分用于存储数据元素的值，称为数据域；另一部分用于存储下一个元素的存储序号，称为指针域。所以线性表的链式存储方式比顺序存储方式的存储空间要大一些。18.下列叙述中正确的是（分数：2.00）A.栈是一种先进先出的线性表B.队列是一种后进先出的线性表C.栈与队列都是非线性结构
22、D.栈与队列都是线性结构 解析：解析：栈是先进后出，队列是先进先出。栈和队列都是一种线性表，属于线性结构。19.一棵完全二叉树共有 360个结点，则在该二叉树中度为 1的结点个数为（分数：2.00）A.0B.1 C.1 80D.1 81解析：解析：对于一个具有 n个结点的完全二义树，其深度为log 2 n+1。本题中这个二叉树的深度为log 2 360+1=8+1=9。根据满二叉树的性质，深度为 8的满二叉树其结点数为 2 8 -1=2561=255。这个完全二叉树的第 9层的结点数为 360-255=105。完全二叉树的性质非叶子结点的子结点都为 2，105 除以2其商为 52余数为 1。因
23、此该二叉树中度为 1的结点个数为 1。选项 B正确。20.算法的时间复杂度是指（分数：2.00）A.设计该算法所需的工作量B.执行该算法所需要的时间C.执行该算法时所需要的基本运算次数D.算法中指令的条数 解析：解析：算法的时间复杂度，是指执行算法所需要的计算工作量。算法的工作量可以用算法在执行过程中所需基本运算的执行次数来度量。21.下列关于栈叙述正确的是（分数：2.00）A.栈顶元素最先能被删除 B.栈顶元素最后才能被删除C.栈底元素永远不能被删除D.以上三种说法都不对解析：解析：栈是先进后出的线性表，栈顶的元素最先被删除，栈底的元素最后被删除。22.下列叙述中正确的是（分数：2.00）A
24、.在栈中，栈中元素随栈底指针与栈顶指针的变化而动态变化B.在栈中，栈顶指针不变，栈中元素随栈底指针的变化而动态变化C.在栈中，栈底指针不变，栈中元素随栈顶指针的变化而动态变化 D.上述三种说法都不对解析：解析：在栈中，允许插入与删除的一端称为栈顶，而不允许插入与删除的另一端称为栈底。栈跟队列不同，元素只能在栈顶压入或弹出，栈底指针不变，栈中元素随栈项指针的变化而动态变化，遵循后进先出的规则。23.某二叉树共有 7个结点，其中叶子结点只有 1个，则该二叉树的深度为(假设根结点在第 1层)（分数：2.00）A.3B.4C.6D.7 解析：解析：根据二叉树的性质，度为 0的结点(即叶子结点)总是比度
25、为 2的结点多一个。题目中的二叉树的叶子结点为 1，因此度为 2的结点的数目为 0，故该二叉树为 7层，每层只有一个结点。24.设循环队列存储空间为 Q(1：50)，初始状态为 front=rear=50。经过一系列入队和退队操作后，front=rear=25，则该循环队列中元素个数为（分数：2.00）A.26B.25C.24D.0或 50 解析：解析：在循环队列中，用队尾指针 rear指向队列中的队尾元素，用排头指针 front指向排头元素的前一个位置。因此，从排头指针 front指向的后一个位置直到队尾指针 rear指向的位置之间所有的元素为队列中的元素。在循环队列动态变化过程中，当循环队
26、列满时有 front=rear，而当循环队列空时也有 front=rear。即在循环队列中，当 front=rear时，不能确定是队列满还是队列空。所以对于这个题目来说，当 front=rear=25，要么队列为空，队列中的元素个数为 O；要么队列为满，队列中的元素个数为50，选项 D正确。25.下列叙述中正确的是（分数：2.00）A.算法就是程序B.设计算法时只需要考虑数据结构的设计C.设计算法时只需要考虑结果的可靠性D.设计算法时要考虑时间复杂度和空间复杂度 解析：解析：算法复杂度，即算法在编写成可执行程序后，运行时所需要的资源，资源包括时间资源和内存资源。算法分析的目的在于选择合适算法和
27、改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。26.下列叙述中正确的是（分数：2.00）A.有一个以上根结点的数据结构不一定是非线性结构B.只有一个根结点的数据结构不一定是线性结构 C.循环链表是非线性结构D.双向链表是非线性结构解析：解析：在数据结构中，树这类的数据结构只有一个根结点，但它不是线性结构。27.下列关于二叉树的叙述中，正确的是（分数：2.00）A.叶子结点总是比度为 2的结点少一个B.叶子结点总是比度为 2的结点多一个 C.叶子结点数是度为 2的结点数的两倍D.度为 2的结点数是度为 1的结点数的两倍解析：解析：由二叉树的性质可以知道在二叉树中叶子结点总是比度为
28、2的结点多一个。28.下列各组的排序方法中，最坏情况下比较次数相同的是（分数：2.00）A.冒泡排序与快速排序 B.简单插入排序与希尔排序C.堆排序与希尔排序D.快速排序与希尔排序解析：解析：最坏情况下冒泡排序需要比较 n(n-1)2 次，即序列逆序的情况。简单插入排序，无论是否最坏情况，都需要 n(n-1)2 次。直接插入排序，最坏情况需要比较次 n(n-1)2 次。堆排序，无论是否最坏都要比较 O(nlog 2 n)次。快速排序，最坏情况退化为冒泡排序，需要比较 n(n1)2 次。在最坏情况下，希尔排序所需要的比较次数为 O(n 1.5 )。29.下列叙述中正确的是（分数：2.00）A.循
29、环队列是队列的一种链式存储结构B.循环队列是队列的一种顺序存储结构 C.循环队列是非线性结构D.循环队列是一种逻辑结构解析：解析：本题主要考查循环队列的概念，循环队列作为队列的一种也应该是线性结构。队列是一种逻辑结构，而循环队列是一种顺序存储结构的队列。30.下列关于线性链表的叙述中，正确的是（分数：2.00）A.各数据结点的存储空间可以不连续，但它们的存储顺序与逻辑顺序必须一致B.各数据结点的存储顺序与逻辑顺序可以不一致，但它们的存储空间必须连续C.进行插入与删除时，不需要移动表中的元素 D.以上都不正确解析：解析：线性表的链式存储结构称为线性链表。在链式存储结构中，存储数据结构的存储空间可
30、以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。31.下列叙述中正确的是（分数：2.00）A.算法的复杂度是指算法所处理的数据量B.算法的复杂度是指算法程序中指令的数量C.算法的复杂度是指算法控制结构的复杂程度D.算法的复杂度包括时间复杂度与空间复杂度 解析：解析：算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。32.设二叉树的前序序列为 ABDEGHCFU，中序序列为 DBGEHACIFJ。则按层次输出(从上到下，同一层从左到右)的序列为（分数：2.00）A.ABCDEFGHU B.DG
31、HEBUFCAC.JIHGFEDCBAD.GHIJDEFBCA解析：解析：前序遍历中，第一个字母是根结点，也就是 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的右结点。
32、由此可画出这个二叉树，然后根据二叉树，可知按层次输出(从上到下，同一层从左到右)的序列为：ABCDEFGHIJ。33.设循环队列的存储空间为 Q(1：50)，初始状态为 front=rear=50，经过一系列正常的操作后，front-1=rear。为了在该队列中寻找值最大的元素，在最坏情况下需要的比较次数为（分数：2.00）A.0B.1C.48 D.49解析：解析：front 指向队头位置，删除一个元素就将 front顺时针移动一位：rear 指尾指针，指向元素要插入的位置，插入一个元素就将 rear顺时针移动一位；操作后，循环队列的队头指针-1 等于尾指针，说明出队二位，那么总数就是 49了。在该队列中寻找最大值元素，最多比较次数是总数-1，因此是 49-1=48次。
