1、国家二级 MS+Office高级应用机试（数据结构与算法）模拟试卷 10及答案解析(总分：54.00，做题时间：90 分钟)一、选择题(总题数：27，分数：54.00)1.下列关于栈的叙述正确的是（分数：2.00）A.栈按“先进先出”组织数据B.栈按“先进后出”组织数据C.只能在栈底插入数据D.不能删除数据2.算法的空间复杂度是指（分数：2.00）A.算法在执行过程中所需要的计算机存储空间B.算法所处理的数据量C.算法程序中的语句或指令条数D.算法在执行过程中所需要的临时工作单元数3.下列数据结构中，能够按照“先进后出”原则存取数据的是（分数：2.00）A.循环队列B.栈C.队列D.二叉树4.
2、某二叉树共有 7个结点，其中叶子结点只有 1个，则该二叉树的深度为(假设根结点在第 1层)（分数：2.00）A.3B.4C.6D.75.下列关于线性链表的叙述中，正确的是（分数：2.00）A.各数据结点的存储空间可以不连续，但它们的存储顺序与逻辑顺序必须一致B.各数据结点的存储顺序与逻辑顺序可以不一致，但它们的存储空间必须连续C.进行插入与删除时，不需要移动表中的元素D.以上都不正确6.下列叙述中正确的是（分数：2.00）A.程序执行的效率与数据的存储结构密切相关B.程序执行的效率只取决于程序的控制结构C.程序执行的效率只取决于所处理的数据量D.以上都不正确7.对长度为 10的线性表进行冒泡排
3、序，最坏情况下需要比较的次数为（分数：2.00）A.9B.10C.45D.908.某二叉树共有 13个结点，其中有 4个度为 1的结点，则叶子结点数为（分数：2.00）A.5B.4C.3D.29.下列叙述中正确的是（分数：2.00）A.存储空间不连续的所有链表一定是非线性结构B.结点中有多个指针域的所有链表一定是非线性结构C.能顺序存储的数据结构一定是线性结构D.带链的栈与队列是线性结构10.设循环队列为 Q(1：m)，其初始状态为 front=rear=m。经过一系列入队与退队运算后，front=15，rear=20。现要在该循环队列中寻找最大值的元素，最坏情况下需要比较的次数为（分数：2.
4、00）A.4B.6C.m-5D.m-611.下列叙述中正确的是（分数：2.00）A.带链队列的存储空间可以不连续，但队头指针必须大于队尾指针B.带链队列的存储空间可以不连续，但队头指针必须小于队尾指针C.带链队列的存储空间可以不连续，且队头指针可以大于也可以小于队尾指针D.以上三项都错误12.一个栈的初始状态为空，现将元素 A、B、C、D、E 依次入栈，然后依次退栈三次，并将退栈的三个元素依次入队(原队列为空)，最后将队列中的元素全部退出。则元素退队的顺序为（分数：2.00）A.ABCB.CBAC.EDCD.CDE13.下列叙述中正确的是（分数：2.00）A.所有数据结构必须有根结点B.所有数
5、据结构必须有终端结点(即叶子结点)C.只有一个根结点，且只有一个叶子结点的数据结构一定是线性结构D.没有根结点或没有叶子结点的数据结构一定是非线性结构14.下列叙述中正确的是（分数：2.00）A.结点中具有两个指针域的链表一定是二叉链表B.结点中具有两个指针域的链表可以是线性结构，也可以是非线性结构C.二叉树只能采用链式存储结构D.循环链表是非线性结构15.某二叉树共有 399个结点，其中有 199个度为 2的结点，则该二叉树中的叶子结点数为（分数：2.00）A.不存在这样的二叉树B.200C.198D.19916.下列叙述中正确的是（分数：2.00）A.在栈中，栈顶指针的动态变化决定栈中元素
6、的个数B.在循环队列中，队尾指针的动态变化决定队列的长度C.在循环链表中，头指针和链尾指针的动态变化决定链表的长度D.在线性链表中，头指针和链尾指针的动态变化决定链表的长度17.设一棵树的度为 3，其中度为 3，2，1 的结点个数分别为 4，1，3。则该棵树中的叶子结点数为（分数：2.00）A.10B.11C.12D.不可能有这样的树18.设顺序表的长度为 n。下列算法中，最坏情况下比较次数小于 n的是（分数：2.00）A.寻找最大项B.堆排序C.快速排序D.顺序查找法19.下列叙述中正确的是（分数：2.00）A.对数据进行压缩存储会降低算法的空间复杂度B.算法的优化主要通过程序的编制技巧来实
7、现C.算法的复杂度与问题的规模无关D.数值型算法只需考虑计算结果的可靠性20.某带链队列初始状态为 front=rear=NULL。经过一系列正常入队与退队操作后，front=10，rear=5。该队列中的元素个数为（分数：2.00）A.不确定B.5C.4D.621.设表的长度为 n。下列查找算法中，在最坏情况下，比较次数最少的是（分数：2.00）A.有序表的二分查找B.顺序查找C.寻找最大项D.寻找最小项22.设数据结构 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.循环
8、链表D.非线性结构23.设一棵树的度为 3，其中没有度为 2的结点，且叶子结点数为 5。该树中度为 3的结点数为（分数：2.00）A.1B.2C.3D.不可能有这样的树24.设有一个栈与一个队列的初始状态均为空。现有一个序列 A，B，C，D，E，F，G，H。先分别将序列中的前 4个元素依次入栈，后 4个元素依次入队；然后分别将栈中的元素依次退栈，再将队列中的元素依次退队。最后得到的序列为（分数：2.00）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，F，E25.从表中任何一个结点位置出发就可以不重复地访问到表中
9、其他所有结点的链表是（分数：2.00）A.循环链表B.双向链表C.单向链表D.二叉链表26.下列叙述中错误的是（分数：2.00）A.向量是线性结构B.非空线性结构中只有一个结点没有前件C.非空线性结构中只有一个结点没有后件D.只有一个根结点和一个叶子结点的结构必定是线性结构27.设顺序表的长度为 40，对该表进行冒泡排序。在最坏情况下需要的比较次数为（分数：2.00）A.780B.820C.40D.41国家二级 MS+Office高级应用机试（数据结构与算法）模拟试卷 10答案解析(总分：54.00，做题时间：90 分钟)一、选择题(总题数：27，分数：54.00)1.下列关于栈的叙述正确的是
10、（分数：2.00）A.栈按“先进先出”组织数据B.栈按“先进后出”组织数据 C.只能在栈底插入数据D.不能删除数据解析：解析：栈是限定在一端进行插入和删除的线性表，允许进行插入和删除元素的一端称为栈顶，另一端称为栈底。栈是按照“先进后出”的原则组织数据的。2.算法的空间复杂度是指（分数：2.00）A.算法在执行过程中所需要的计算机存储空间 B.算法所处理的数据量C.算法程序中的语句或指令条数D.算法在执行过程中所需要的临时工作单元数解析：解析：算法的空间复杂度是指执行这个算法所需要的内存空间。这个内存空间包括算法程序所占的空间，输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。3
11、.下列数据结构中，能够按照“先进后出”原则存取数据的是（分数：2.00）A.循环队列B.栈 C.队列D.二叉树解析：解析：栈按照“先进后出”(FILO)或“后进先出”(LIFO)组织数据；队列是“先进先出”(FIFO)或“后进后出”(LIL0)的线性表。4.某二叉树共有 7个结点，其中叶子结点只有 1个，则该二叉树的深度为(假设根结点在第 1层)（分数：2.00）A.3B.4C.6D.7 解析：解析：根据二叉树的性质，度为 0的结点(即叶子结点)总是比度为 2的结点多一个。题目中的二叉树的叶子结点为 1，因此度为 2的结点的数目为 0，故该二叉树为 7层，每层只有一个结点。5.下列关于线性链表
12、的叙述中，正确的是（分数：2.00）A.各数据结点的存储空间可以不连续，但它们的存储顺序与逻辑顺序必须一致B.各数据结点的存储顺序与逻辑顺序可以不一致，但它们的存储空间必须连续C.进行插入与删除时，不需要移动表中的元素 D.以上都不正确解析：解析：线性表的链式存储结构称为线性链表。在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据冗素之间的逻辑关系是由指针域来确定的。6.下列叙述中正确的是（分数：2.00）A.程序执行的效率与数据的存储结构密切相关 B.程序执行的效率只取决于程序的控制结构C.程序执行的效率只取决于所处理的数据量D
13、.以上都不正确解析：解析：影响程序执行效率的因素有很多，如数据的存储结构、程序处理的数据量、程序的算法等。顺序存储结构和链式存储结构在数据插入和删除操作上的效率就存在差别。其中，链式存储结构的效率要高一些。7.对长度为 10的线性表进行冒泡排序，最坏情况下需要比较的次数为（分数：2.00）A.9B.10C.45 D.90解析：解析：线性表的长度为 n，最坏情况下冒泡排序需要比较的次数为 n(n-1)2。8.某二叉树共有 13个结点，其中有 4个度为 1的结点，则叶子结点数为（分数：2.00）A.5 B.4C.3D.2解析：解析：根据二叉树的性质 3，在任意一颗二叉树中，度为 0的结点(即叶子结
14、点)总是比度为 2的结点多一个，即有 n 0 =n 2 +1。本题总结点数：13=n 0 +n 1 +n 2 =n 2 +1+4+n 2 =2n 2 +5，n 2 =4，所以叶子结点数等于 4+1=5，选项 A正确。9.下列叙述中正确的是（分数：2.00）A.存储空间不连续的所有链表一定是非线性结构B.结点中有多个指针域的所有链表一定是非线性结构C.能顺序存储的数据结构一定是线性结构D.带链的栈与队列是线性结构 解析：解析：计算机中数据按照其数据逻辑结构，可以分为线性结构和非线性结构。而数据在内存或磁盘中的存储，可以分为顺序存储和链式存储。数据的逻辑结构与存储结构之间没有对应的关系。所以选项A
15、BC都是错误的，栈和队列按照数据的逻辑划分都是线性结构。10.设循环队列为 Q(1：m)，其初始状态为 front=rear=m。经过一系列入队与退队运算后，front=15，rear=20。现要在该循环队列中寻找最大值的元素，最坏情况下需要比较的次数为（分数：2.00）A.4 B.6C.m-5D.m-6解析：解析：初始状态为 front=rear=m，rear-front=0，此时队列为空。经过一系列入队与退队运算后，front=15，rear=20。队尾大于队头，则队尾 rear减队头 front等于 5个元素。此时队列中有 5个元素，而查找最大项至少要比较 n-1次，就是 4次。因此选项
16、 A正确。11.下列叙述中正确的是（分数：2.00）A.带链队列的存储空间可以不连续，但队头指针必须大于队尾指针B.带链队列的存储空间可以不连续，但队头指针必须小于队尾指针C.带链队列的存储空间可以不连续，且队头指针可以大于也可以小于队尾指针 D.以上三项都错误解析：解析：带链队列的存储空间可以不连续，且队头指针与队尾指针大小没有可比性，选项 C正确。12.一个栈的初始状态为空，现将元素 A、B、C、D、E 依次入栈，然后依次退栈三次，并将退栈的三个元素依次入队(原队列为空)，最后将队列中的元素全部退出。则元素退队的顺序为（分数：2.00）A.ABCB.CBAC.EDC D.CDE解析：解析：
17、栈是根据先进后出的原则组织数据，所以退栈三次的元素依次为 E、D、C；一队列是根据先进先出的原则组织数据的，所以退队的顺序依次为 E、D、C，所以选项 C正确。13.下列叙述中正确的是（分数：2.00）A.所有数据结构必须有根结点B.所有数据结构必须有终端结点(即叶子结点)C.只有一个根结点，且只有一个叶子结点的数据结构一定是线性结构D.没有根结点或没有叶子结点的数据结构一定是非线性结构 解析：解析：只有一个空节点的结构也属数据结构，所以选项 A和选项 B不正确；有且只有一个根结点，每一个结点最多有一个前件，也最多有一个后件的数据结构才属于线性结构，其它的都属于非线性结构，故选项 C不正确，选
18、项 D正确。14.下列叙述中正确的是（分数：2.00）A.结点中具有两个指针域的链表一定是二叉链表B.结点中具有两个指针域的链表可以是线性结构，也可以是非线性结构 C.二叉树只能采用链式存储结构D.循环链表是非线性结构解析：解析：结点中尽管有两个指针域但没有分别指向两个不同的结点就不是二叉链表，故选项 A小正确；二叉树是非线性结构，即每个数据结点至多只有一个前驱，但可以有多个后继。 它可采用顺序存储结构和链式存储结构，故选项 C不正确；循环链表是在单链表中，将终端结点的指针域 NULL改为指向表头结点或开始结点的线性结构，故选 NULL不正确；当结点中两个指针分别指向前驱结点和后继结点时为线性
19、结构，当指向两个不同的前驱或后继结点时为非线性结构，故选项 B正确。15.某二叉树共有 399个结点，其中有 199个度为 2的结点，则该二叉树中的叶子结点数为（分数：2.00）A.不存在这样的二叉树B.200 C.198D.199解析：解析：在二叉树中，设叶子结点个数为 n 0 ，度为 2的结点个数为 n 2 ，叶子结点的个数计算方法 n 0 =n 2 +1=199+1=200，所以选项 B正确。16.下列叙述中正确的是（分数：2.00）A.在栈中，栈顶指针的动态变化决定栈中元素的个数 B.在循环队列中，队尾指针的动态变化决定队列的长度C.在循环链表中，头指针和链尾指针的动态变化决定链表的长
20、度D.在线性链表中，头指针和链尾指针的动态变化决定链表的长度解析：解析：栈是一种特殊的线性表，是一种只允许在表的一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶；表的另一端称为栈底。栈顶的当前位置是动态的，对栈顶当前位置的标记称为栈顶指针。在栈中，栈顶指针动态反映了栈中元素的变化情况。所以选项 A正确。17.设一棵树的度为 3，其中度为 3，2，1 的结点个数分别为 4，1，3。则该棵树中的叶子结点数为（分数：2.00）A.10 B.11C.12D.不可能有这样的树解析：解析：因为任一棵树中，结点总数=总分支数目+1，所以：n 0 +4+1+3=(n 0 *0+3*4+
21、2*1+1*3)+1。计算结果 n 0 =10。其中，n 0 表示叶子结点。所以选项 A正确。18.设顺序表的长度为 n。下列算法中，最坏情况下比较次数小于 n的是（分数：2.00）A.寻找最大项 B.堆排序C.快速排序D.顺序查找法解析：解析：如果顺序表是线性存储的(不包括线性的链式表)，那么元素要不就是从大到小，要不就是小到大的顺序，假设第一个数就是最大值，那么需要比较 1次，n-1 应该是最坏情况下要比较的次数，所以选项 A正确。19.下列叙述中正确的是（分数：2.00）A.对数据进行压缩存储会降低算法的空间复杂度 B.算法的优化主要通过程序的编制技巧来实现C.算法的复杂度与问题的规模无
22、关D.数值型算法只需考虑计算结果的可靠性解析：解析：算法的空间复杂度是指执行这个算法所需要的内存空间，包括 3个部分：输入数据所占的存储空间；程序本身所占的存储空间；算法执行过程中所需要的额外空间。 为了降低算法的空间复杂度，主要应减少输入数据所占的存储空间以及额外空间，通常采用压缩存储技术，A 选项正确。20.某带链队列初始状态为 front=rear=NULL。经过一系列正常入队与退队操作后，front=10，rear=5。该队列中的元素个数为（分数：2.00）A.不确定 B.5C.4D.6解析：解析：循环队列用数组 A0：m-1存放其元素值，已知其头尾指针分别是 front和 rear，
23、则当前队列的元素个数是(rear-front+m)m=(5-10+m)m=(m-5)m。因为本题中的 m值不确定，所以(m-5)m的值不能确定。所以选项 A正确。21.设表的长度为 n。下列查找算法中，在最坏情况下，比较次数最少的是（分数：2.00）A.有序表的二分查找 B.顺序查找C.寻找最大项D.寻找最小项解析：解析：有序表的二分法查找只适用于顺序存储的有序表。二分查找的基本方法是：将被查元素 x与线性表的中间项进行比较，若中间项的值等于 x，则说明查到；若小于中间项的值则在线性表的前半部分以相同的方法进行查找；若大于中间项的值则在线性表的后半部分以相同的方法进行查找。 在最坏情况下，二分
24、查找需要比较 log 2 n次。顺序查找、寻找最大项、寻找最小项，在最坏情况下，比较次数都是n次。所以选项 A正确。22.设数据结构 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)可以得到，该数据结构为：“f-a-c-e-d-b”。由此可知结点 f没有前驱，结点 b没有后继结点，并且其它的结点只有一个前驱结点和一个后继结点，所以该数据结构为线性结构。所以应选
25、A选项。23.设一棵树的度为 3，其中没有度为 2的结点，且叶子结点数为 5。该树中度为 3的结点数为（分数：2.00）A.1B.2 C.3D.不可能有这样的树解析：解析：树的度是指一棵树中，最大的结点的度称为树的度。本题中树的度为 3，那么树中最少有一个结点的度为 3。而树中没有度为 2的结点，叶子结点数为 5，度为 l的结点下面只有一个叶子结点。因此，该树中含 2个度为 3的结点满足题目要求。24.设有一个栈与一个队列的初始状态均为空。现有一个序列 A，B，C，D，E，F，G，H。先分别将序列中的前 4个元素依次入栈，后 4个元素依次入队；然后分别将栈中的元素依次退栈，再将队列中的元素依次
26、退队。最后得到的序列为（分数：2.00）A.D，C，B，A，E，F，G，H B.D，C，B，A，H，G，F，EC.A，B，C，D，E，F，G，HD.A，B，C，D，H，G，F，E解析：解析：栈(stack)又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。因此栈的出栈顺序是先入后出，所以顺序是 D,C,B,A。 队列是一种特殊的线性表，特殊之处在于它只允许在表的前端(front)进行删除操作，而在表的后端(rear)进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。因此，队的出队顺序是，先入先出，所以顺序是
27、E,F,G,H。最后的顺序是：D,C,B,A，E，F，G，H。25.从表中任何一个结点位置出发就可以不重复地访问到表中其他所有结点的链表是（分数：2.00）A.循环链表 B.双向链表C.单向链表D.二叉链表解析：解析：循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环，循环一圈就访问到了表中其它所有结点而不重复。26.下列叙述中错误的是（分数：2.00）A.向量是线性结构B.非空线性结构中只有一个结点没有前件C.非空线性结构中只有一个结点没有后件D.只有一个根结点和一个叶子结点的结构必定是线性结构 解析：解析：线性结构是 n个数据元素的有序(次
28、序)集合。 集合中必存在唯一的一个“第一个元素”；集合中必存在唯一的一个“最后的元素”； 除最后元素之外，其它数据元素均有唯一的“后件”； 除第一元素之外，其它数据元素均有唯一的“前件”。相对应于线性结构，非线性结构的逻辑特征是一个结点元素可能对应多个直接前驱和多个后继。向量符合线性结构特点。非线性结构也会存在只有一个根结点和叶子结点的情况。27.设顺序表的长度为 40，对该表进行冒泡排序。在最坏情况下需要的比较次数为（分数：2.00）A.780 B.820C.40D.41解析：解析：冒泡排序(Bubble Sort)，是一种计算机科学领域的较简单的排序算法。冒泡排序算法的运作如下：比较相邻的元素。如果第一个比第二个大，就交换它们两个；对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数；针对所有的元素重复以上的步骤，除了最后一个；持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。冒泡排序的最坏时间复杂度为(n*(n1)2=780。
