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