1、国家二级 MS Office高级应用机试（数据结构与算法）模拟试卷 11及答案与解析 一、选择题 1 某二叉树有 5个度为 2的结点，则该二叉树中的叶子结点数是 （ A） 10 （ B） 8 （ C） 6 （ D） 4 2 一个栈的初始状态为空。现将元素 1、 2、 3、 4、 5、 A、 B、 C、 D、 E依次入栈，然后再依次出栈，则元素出栈的顺序是 （ A） 12345ABCDE （ B） EDCBA54321 （ C） ABCDE12345 （ D） 54321EDCBA 3 下列叙述中正确的是 （ A）线性表的链式存储结构与顺 序存储结构所需要的存储空间是相同的 （ B）线性表的链式
2、存储结构所需要的存储空间一般要多于顺序存储结构 （ C）线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构 （ D）以上三项均正确 4 设循环队列存储空间为 Q(1： 50)，初始状态为 front=rear=50。经过一系列入队和退队操作后， front=rear=25，则该循环队列中元素个数为 （ A） 26 （ B） 25 （ C） 24 （ D） 0或 50 5 一棵二叉树共有 25个结点，其中 5个是叶子结点，则度为 1的结点数为 （ A） 16 （ B） 10 （ C） 6 （ D） 4 6 下列与队列结构有关联的是 （ A）函数的递归调用 （ B）数组元素的引用 （ C）
3、多重循环的执行 （ D）先到先服务的作业调度 7 下列叙述中正确的是 （ A）算法的效率只与问题的规模有关，而与数据的存储结构无关 （ B）算法的时间复杂度是指执行算法所需要的计算工作量 （ C）数据的逻辑结构与存储结构是一一对应的 （ D）算法的时间复杂度与空间复杂度一定相关 8 设栈的顺序存储空间为 S(1： 50)，初始状态为 top=0。现经过一系列入栈与退栈运算后， top=20，则当前栈中的元素个数为 （ A） 30 （ B） 29 （ C） 20 （ D） 19 9 算法时间复杂度的度量方法是 （ A）算法程序的长度 （ B）执行算法所需要的基本运算次数 （ C）执行算法所需要的
4、所有运算次数 （ D）执行算法所需要的时间 10 下列叙述中正确的是 （ A）循环队列属于队列的链式存储结构 （ B）双向链表是二叉树的链式存储结构 （ C）非线性结构只能采用链式存储结构 （ D）有的非线性结构也可以采用顺序存储结构 11 设循环队列为 Q(1： m)，其初始状态为 front=rear=m。经过一系列入队与退队运算后， front=20， rear=15。现要在该循环队列中寻找最小值的元素，最坏情况下需要比较的次数为 （ A） 5 （ B） 6 （ C） m-5 （ D） m-6 12 某二叉树的中序序列为 DCBAEFG，后序序列为 DCBGFEA，则该二叉树的深度 (根
5、结点在第 1层 )为 （ A） 5 （ B） 4 （ C） 3 （ D） 2 13 下列关于算法的描述中错误的是 （ A）算法强调动态的执行过程，不同于静态的计算公式 （ B）算法必须能在有限个步骤之后终止 （ C）算法设计必须考虑算法 的复杂度 （ D）算法的优劣取决于运行算法程序的环境 14 设某二叉树中共有 140个结点，其中有 40个度为 1的结点。则 （ A）该二叉树中有 51个叶子结点 （ B）该二叉树中有 50个叶子结点 （ C）该二叉树中有 51个度为 2的结点 （ D）不可能有这样的二叉树 15 下列叙述中错误的是 （ A）对于各种特定的输入，算法的时间复杂度是固定不变的 （
6、 B）算法的时间复杂度与使用的计算机系统无关 （ C）算法的时间复杂度与使用的程序设计语言无关 （ D）算法的时间复杂度与实现算法过程中的具体细节无关 16 循环队列的存储空间为 Q(1： 40)，初始状态为 front=rear=40。经过一系列正常的入队与退队操作后， front=rear=15，此后又退出一个元素，则循环队列中的元素个数为 （ A） 39，或 0且产生下溢错误 （ B） 14 （ C） 40 （ D） 15 17 设栈的存储空间为 s(1： 50)，初始状态为 top=0。现经过一系列正常的入栈与退栈操作后， top=51，则栈中的元素个数为 （ A）不可能 （ B） 5
7、0 （ C） 0 （ D） 1 18 设栈的顺序存储空间为 S(1： m)，初始状态为 top=m+1。现经过一系列正常的入栈与退栈操作后， top=0，则栈中的元素个数为 （ A）不可能 （ B） m+1 （ C） 1 （ D） m 19 设数据结构 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）线性结构 20 某二叉树的前序序列为 ABDFHCEG，中序序列为 HFDBACEG。该二叉树按层次输出 (同
8、一层从左到右 )的序列为 （ A） ABCDEFGH （ B） HFDBGECA （ C） HGFEDCBA （ D） ACEGBDFH 21 某带链栈的初始状态为 top=bottom=NULL，经过一系列正常的入栈与退栈操作后， top=bottom=20。该栈中的元素个数为 （ A） 1 （ B） 0 （ C） 20 （ D）不确定 22 下列叙述中错误的是 （ A）循环队列空的条件是队头指针与队尾指针相同 （ B）若二叉树没有叶子结点，则为空二叉树 （ C）带链栈的栈底指针是随栈的操作而动态变化的 （ D）若带链队列中只有一个元素，则队头指针与队尾 指针必定相同 23 设二叉树共有 5
9、00个结点，其中叶子结点有 250个。则度为 2的结点个数是 （ A） 0 （ B） 1 （ C） 249 （ D）不可能有这样的二叉树 24 下列叙述中错误的是 （ A）具有两个根结点的数据结构一定属于非线性结构 （ B）具有两个以上指针域的链式结构一定属于非线性结构 （ C）具有两个以上叶子结点的数据结构一定属于非线性结构 （ D）具有一个根结点且只有一个叶子结点的数据结构也可能是非线性结构 25 设二叉树的前序序列与中序序列均为 ABCDEFGH，则该二叉树的后序序列 为 （ A） HGFEDCBA （ B） ABCDEFGH （ C） ABCDHGFE （ D） DCBAHGFE 26
10、 在希尔排序法中，每经过一次数据交换后 （ A）能消除多个逆序 （ B）只能消除一个逆序 （ C）不会产生新的逆序 （ D）消除的逆序个数一定比新产生的逆序个数多 27 设表的长度为 n。在下列算法中，最坏情况下时间复杂度最高的是 （ A）堆排序 （ B）希尔排序 （ C）有序链表查找 （ D）循环链表中寻找最大项 国家二级 MS Office高级应用机试（数据结构与算法）模拟试卷 11答案 与解析 一、选择题 1 【正确答案】 C 【试题解析】 根据二叉树的性质，在任意二叉树中，度为 0的结点 (即叶子结点 )总是比度为 2的结点多一个。 【知识模块】 数据结构与算法 2 【正确答案】 B
11、【试题解析】 栈是按照 “先进后出 ”或 “后进先出 ”的原则组织数据的。所以出栈顺序是 EDCBA54321。 【知识模块】 数据结构与算法 3 【正确答案】 B 【试题解析】 线性表的存储分为顺序存储和链式存储。在顺序存储中，所有元素所占的存储空间是连续的。而在链式存储的方式中， 将存储空间的每一个存储结点分为两部分，一部分用于存储数据元素的值，称为数据域；另一部分用于存储下一个元素的存储序号，称为指针域。所以线性表的链式存储方式比顺序存储方式的存储空间要大一些。 【知识模块】 数据结构与算法 4 【正确答案】 D 【试题解析】 在循环队列中，用队尾指针 rear指向队列中的队尾元素，用排
12、头指针 front指向排头元素的前一个位置。因此，从排头指针 front指向的后一个位置直到队尾指针 rear指向的位置之间所有的元素为队列中的元素。 在循环队列动态变化过程 中，当循环队列满时有 front=rear，而当循环队列空时也有 front=rear。即在循环队列中，当 front=rear时，不能确定是队列满还是队列空。所以对于这个题目来说，当 front=rear=25，要么队列为空，队列中的元素个数为 0；要么队列为满，队列中的元素个数为 50，选项 D正确。 【知识模块】 数据结构与算法 5 【正确答案】 A 【试题解析】 根据二叉树的性质，在任意二叉树中，度为 0的结点
13、(即叶子结点 )总是比度为 2的结点多一个，故此度为 1的结点个数 =总结点数 -叶子节点数 -度为2的节点数 =25-5-4=16。 【知识模块】 数据结构与算法 6 【正确答案】 D 【试题解析】 队列中最先插入的元素将最先被删除，最后插入的元素将最后被删除。 【知识模块】 数据结构与算法 7 【正确答案】 B 【试题解析】 算法的时间复杂度是指执行算法所需要的计算工作量。算法的工作量用算法所执行的基本运算的次数来度量，而算法所执行的基本运算次数是问题规模的函数；算法的空间复杂度一般是指执行这个算法所需要的内存空间。 算法的时间复杂度与空间复杂度并不相关。数据的逻辑结构就是数据元素之间的逻
14、辑关系，它是从逻辑上描述数据元素之间的关系，是独立于计算机的：数据的存储结构是研究数据元素和数据元素之间的关系如何在计算机中表示，它们并非一一对应。算法的执行效率不仅与问题的规模有关，还与数据的存储结构有关。 【知识模块】 数据结构与算法 8 【正确答案】 C 【试题解析】 栈是允许在栈顶进行插入和删除的线性表，不允许在栈底进行插入与删除。通常用指针 top来指示栈顶的位置，用指针 bottom指向栈底。对栈的操作有 入栈和退栈两种。 入栈运算：首先将栈顶指针进一 (即 top加 1)，然后将新元素插入到栈顶指针指向的位置。 退栈运算：首先将栈顶元素 (栈顶指针指向的元素 )赋给一个指定的变量
15、，然后将栈顶指针退一 (即 top减 1)。 因为初始状态为 top=0，经过入栈和退栈操作后栈中的元素个数就是 top指针指向的位置。选项 C正确。 【知识模块】 数据结构与算法 9 【正确答案】 B 【试题解析】 算法的时间复杂度：分析算法时，语句总执行次数 T(n)是关于问题规模 n的函数，进而分析 T(n)随 n的变化情况并确定 T(n)。 算法的时间复杂度也就是算法的时间量度，记作 T(n)=O(f(n)。它表示问题输入规模 n的增大，算法执行时间的增长率和 f(n)的增长率相同，因此称作渐近时间复杂度，也称作时间复杂度。 f(n)是问题规模 n的某个函数。选项 B正确。 【知识模块
16、】 数据结构与算法 10 【正确答案】 D 【试题解析】 顺序存储方式不仅能用于存储线性结构，还可以用来存放非线性结构。例如，完全二叉树是属于非线性结构，但其最佳存储方式是顺序存储方式。 【知识模块】 数据结构与算法 11 【正确答案】 D 【试题解析】 在循环队列中元素的个数为 “(rear-front M) M”，式中 rear为队尾指针， front为队首指针， M为存储容量，为取余符号。对于找最小值的最坏情况下的比较次数，为循环队列中元素值个数减一。所以对于这个题目来说初始时元素个数为 0；运算后，元素个数为 m-5，找最小值的最坏情况下的比较次数为 m-5-1=m-6，选项 D正确。
17、 【知识模块】 数据结构与算法 12 【正确答案】 B 【试题解析】 该二叉树的中序序列为 DCBAEFG，后序序列为 DCBGFEA，可知 A为根 结点，结点 B、 C、 D位于根结点的左子树上，结点 E、 F、 G位于根结点的右子树上；并且结点 B、 C、 D在中序序列和后序序列中顺序未变，则说明这三个结点依次位于前一个结点的左子树上；结点 E、 F、 G顺序颠倒，则说明这三个结点依次位于前 _个结点的右子树上。根据以上分析，该二叉树的深度为 4，所以选项 B正确。 【知识模块】 数据结构与算法 13 【正确答案】 D 【试题解析】 算法的优劣取决自身的运行效率，时间和空间复杂度高低，并不
18、取决于运行算法程序的环境，故选项 D错误。 【知识模块】 数据结构与算法 14 【正确答案】 D 【试题解析】 140个结点除去 40个度为 1的结点，说明有 100个度为 2的结点，而根据二叉树性质，这个数值无法得出一棵二叉树，故本题答案选 D。 【知识模块】 数据结构与算法 15 【正确答案】 A 【试题解析】 一般情况下，算法的基本操作重复执行的次数，是模块 n的某一个函数 f(n)，因此，算法的时间复杂度记做 T(n)=O(f(n)。 随着模块 n的增大，算法执行的时间的增长率和 f(n)的增长率成正比，所以 f(n)越小，算法的时间复杂度越低，算法的效率 越高。因此算法会随着输入数据
19、的不同而有执行效率的不同，有时候会快点儿，有时候会慢点儿。因此选项 A正确。 【知识模块】 数据结构与算法 16 【正确答案】 A 【试题解析】 循环队列初始状态 front=rear=40，经过一系列入队和出队操作后，结束状态还是 front=rear=15，这说明入队元素个数和出队元素个数一样多。这样一来最后的元素个数就和原来的元素个数一样多，明显不是 0就是 40，即要么队列为空 (0个元素 )，要么队列为满队列 (40个元素 )。 这时进行出队操作，如果是队列满 (40个元素 )的情况，此时队列中的元素个数为 39，如果是队列空 (0个元素 )的情况，此时就会产生下溢错误。因此选项 A
20、正确。 【知识模块】 数据结构与算法 17 【正确答案】 A 【试题解析】 栈是向上增长的，每次压入一个元素，栈的 TOP指针向上移动一位，即 top-1。对于这个题目，由于 top初始值等于 0，此时入栈一个元素， top值减 1，即 0-1= 1，发生下溢错误，所以选项 A正确。 【知识模块】 数据结构与算法 18 【正确答案】 A 【试题解析】 栈是向上增长的，每次压入一个元素 ，栈的 TOP指针向上移动一位，即 top-1。对于这个题目，由于 top初始值等于 m+1，此时入栈一个元素， top值减 1，即 m+1-1=m，依次类推，当栈满时， top的值等于 1，不会出现 top的值
21、等于 0。 所以选项 A正确。 【知识模块】 数据结构与算法 19 【正确答案】 A 【试题解析】 该逻辑结构为非线性结构，在 R=(a,b)， (b,c)， (c,d)， (a,e)， (e，f)， (f， a)中，结构中的各结点之间形成一个循环链。 【知识模块】 数据结构与算法 20 【正确答案】 A 【试题解析】 由于二叉树的前序序列 ABDFHCEG，可以确定这个二叉树的根结点是 A。再由中序序列 HFDBACEG，可以得到， HFDB为 A的左子树， CEG为A的右子树。 同理依次对左子树 HFDB和右子树 CEG进行同样的推理，得到这个二叉树的结构如下，该二叉树按层次输出 (同一层
22、从左到右 )的序列为ABCDEFGH，所以选项 A正确。 【知识模块】 数据结构与算法 21 【正确答案】 D 【试题解析】 对于链栈而言，使用了链表来实现栈，链表中的元素存储在不连续的地址。所以当 top=bottom=20时，不能确定栈中的元素个数。所以选项 D正确。 【知识模块】 数据结构与算法 22 【正确答案】 A 【试题解析】 初始化建空队时，令 front=rear=0，当队空时： front=rear；当队满时： front=rear亦成立。因此，只凭等式 front=rear无法判断队空还是队满。有两种方法处理上述问题： 另设一个标志位以区别队列是空还是满； 少用一个元素空间
23、，约定以 “队列头指针 front在队尾指针 rear的下一个位置上作为队列 “满 ”状态的标志。即：队空时： front=rear；队 满时： (rear 1)maxsize=front。所以选项 A正确。 【知识模块】 数据结构与算法 23 【正确答案】 C 【试题解析】 二叉树的每个结点至多只有二棵子树 (不存在度大于 2的结点 )，二叉树的子树有左右之分，次序不能颠倒。二叉树的第 i层至多有 2i-1个结点；深度为 k的二叉树至多有 2k-1个结点；对任何一棵二叉树 T，如果其终端结点数为n0，度为 2的结点数为 n2，则 n0=n2+1。 本题中，叶子结点有 250个，度为 2的结点
24、数为 n2=n0-1=250-1=249。 【知识模块】 数据 结构与算法 24 【正确答案】 B 【试题解析】 非线性结构，数学用语，其逻辑特征是一个结点元素可能有多个直接前驱和多个直接后继。常见的非线性结构有：二维数组，多维数组，广义表，树 (二叉树等 )，图。 【知识模块】 数据结构与算法 25 【正确答案】 A 【试题解析】 前序遍历 (DLR)是二叉树遍历的一种，也叫做先根遍历、先序遍历、前序周游，可记做根左右；中序遍历 (LDR)是二叉树遍历的一种，也叫做中根遍历、中序周游，可记做左根右。 后序遍历 (LRD)是二叉树遍历的一种，也叫 做后根遍历、后序周游，可记做左右根。根据题中前
25、序和中序序列均为 ABCDEFGH，可画出二叉树，该二叉树是一个子结点全部在右侧二叉树，然后根据后序遍历方法，可得出后序遍历为HGFEDCBA。 【知识模块】 数据结构与算法 26 【正确答案】 A 【试题解析】 希尔排序法 (缩小增量法 )属于插入类排序，是将整个无序列分割成若干小的子序列分别进行插入排序的方法。插入排序能够消除多个逆序，也会产生新的逆序。消除的逆序与新产生的逆序有多有少。 【知识模块】 数据结构与算法 27 【正确答案】 B 【试题解析】 希尔排序 (Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。排序方法最坏时间复杂度直接插入为O(n2)、简单选择为 O(n2)、起泡排序为 O(n2)、快速排序为 O(n2)、堆排序为O(nlog2n)、归并排序为 O(nlog2n)。 【知识模块】 数据结构与算法
