1、国家二级 MS Office高级应用机试（数据结构与算法）模拟试卷 17及答案与解析 一、选择题 1 算法的有穷性是指 ( )。 （ A）算法程序的长度是有限的 （ B）算法只能被有限的用户使用 （ C）算法程序的运行时间是有限的 （ D）算法程序所能处理的数据量是有限的 2 算法空间复杂度是指 ( )。 （ A）算法所处理的数据量 （ B）算法程序的代码指令条数 （ C）算法在执行过程中所需要的内存空间 （ D）算法在执行过程中需要的临时工作单元数 3 下列说法正确的是 ( )。 （ A）算法就是程序 （ B）设计算法只需要考虑数据结构的设计 （ C）设计算法只要考虑结果的可靠性 （ D）以
2、上说法都不对 4 算法的时间复杂度和空间复杂度的关系是 ( )。 （ A）时间复杂度大则空间复杂度也大 （ B）时间复杂度大则空间复杂度小 （ C）时间复杂度和空间复杂度都与问题规模无关 （ D）两者没有直接关系 5 算法的一条指令对应几个操作 ?( ) （ A）一个 （ B）多个 （ C）一个或多个 （ D）指令和操作没有关系 6 算法的基本特征不包含下列哪项 ?( ) （ A）有穷性 （ B）确定性 （ C）可行性 （ D）高效性 7 一般计算机系统指令系统包含的四类基本运算是 ( )。 （ A）算术运算、关系运算、逻辑运算、数据传输 （ B）算术运算、关系运算、逻辑运算、数据保存 （ C
3、）算术运算、逻辑运算、算法控制、数据传输 （ D）算术运算、逻辑运算、算法输入、算法输出 8 算法的控制结梅不包括 ( )。 （ A）顺序结构 （ B）选择结构 （ C）循环结构 （ D）归纳结构 9 支持子程序调用的数据结构是 ( )。 （ A）栈 （ B）树 （ C）队列 （ D）二叉树 10 数据的存储结构是指 ( )。 （ A）存储在外存中的数据 （ B）数据所占的存储空间量 （ C）数据在计算中的顺序存储方式 （ D）数据的逻辑结构在计算机中的表示 11 数据结构是 ( )。 （ A）数据元素的集合 （ B）反映数据元素之间关系的数据元素的集合 （ C）数据元素的存储方式 （ D）数
4、据元素在计算中的表示方式 12 下列叙述中正确的是 ( )。 （ A）有一个以上的根节点的数据结构不一定是非线性结构 （ B）只有一个根节点的数据结构不一 定是线性结构 （ C）循环链表是非线性结构 （ D）双向链表是非线性结构 13 一个栈的初始状态是空，现在 A、 B、 C、 1、 2、 3依次入栈，然后依次退栈，那么退栈顺序是 ( )。 （ A） ABC123 （ B） 123ABE （ C） 321CBA （ D） CBA321 14 下列关于栈的说法错误的是 ( )。 （ A）栈是线性表的一种 （ B）栈是 “先进后出 ” （ C）栈的两端都可以插入和删除 （ D）读取栈顶不是退栈
5、15 下列的叙述正确的是 ( )。 （ A）在栈中，栈中元素随栈底指 针与栈顶指针的变化而动态变化 （ B）在栈中，栈顶指针不变，栈中元素随栈底指针的变化而动态变化 （ C）在栈中，栈底指针不变，栈中元素随栈顶指针的变化而动态变化 （ D）在栈中，栈中元素不会随栈底指针与栈顶指针的变化而动态变化 16 下列关于栈的描述中错误的是 ( )。 （ A）栈是 “先进后出 ”的线性表 （ B）栈只能顺序存储 （ C）栈具有记忆作用 （ D）对栈的插入与删除操作中。不需要改变栈底指针 17 下列属于非线性结构的是 ( )。 （ A）栈 （ B）队列 （ C）链表 （ D）树 18 下列关于线性表的顺序存
6、储结构描述错误的是 ( )。 （ A）所有元素所占的存储空间必须是连续的 （ B）所有元素在存储空间的位置是按逻辑顺序存放的 （ C）只要确定了首地址，线性表中的所有元素的地址都可以方便地查找出来 （ D）所有元素都有一个指向后继节点 19 下列关于线性表的插入、删除操作描述错误的是 ( )。 （ A）当在线性表的尾部插入一个数据时，不需要移动线性表中的元素 （ B）当在线性表的头部插入一个数据时，需要移动表中的所有元素 （ C）当删除线性表尾部的元素时，不需要 移动线性表中的元素 （ D）当删除线性表头部的元素时，不需要移动线性表中的元素 20 下列数据结构中，能够按照 “先进后出 ”原则存
7、取数据的是 ( )。 （ A）循环队列 （ B）栈 （ C）队列 （ D）二叉树 21 对于循环队列，下列叙述正确的是 ( )。 （ A）循环队列有队头和队尾两个指针，因此循环队列是非线性结构 （ B）在循环队列中，只需要队头指针就能反映队列中元素的动态变化情况 （ C）在循环队列中，只需要队尾指针就能反映队列中元素的动态变化情况 （ D）循环队列中元素的个数由队头 指针和队尾指针共同决定 22 对于循环队列，下列叙述正确的是 ( )。 （ A）队头指针是固定不变的 （ B）队头指针一定大于队尾指针 （ C）队头指针一定小于队尾指针 （ D）队头指针既可以小于队尾指针，也可以大于队尾指针 23
8、 设循环队列的存储空间为 Q(1： 35)，初始状态为 front=rear=-35，现在经过一系列入队和退队操作后， front=rear=15，则此时循环队列中元素个数为 ( )。 （ A） 1 （ B） 15 （ C） 20 （ D） 0或者 35 24 下列数据结构按照 “先进先出 ”原则的是 ( )。 （ A）栈 （ B）队列 （ C）树 （ D）二叉树 25 下列与队列结构有关的是 ( )。 （ A）函数的递归调用 （ B）数组元素的引用 （ C）多重循环的执行 （ D）先到先服务的作业调度 26 下列关于线性链表叙述中正确的是 ( )。 （ A）各数据节点的存储空间可以不连续，但
9、它们的存储顺序与逻辑顺序必须一致 （ B）各数据节点的存储顺序与逻辑顺序不一致，但它们的存储顺序必须连续 （ C）进行插入与删除时，不需要移动表中的元素 （ D）以上都不正确 27 下列叙述正确的是 ( )。 （ A）循环队列是队列的一种链式存储结构 （ B）循环队列是队列的一种顺序存储结构 （ C）循环队列是非线性结构 （ D）循环队列是一种逻辑结构 28 下列叙述正确的是 ( )。 （ A）顺序存储结构的存储空间一定是连续的。链式存储结构的存储空间不一定是连续的 （ B）顺序存储结构只针对线性结构，链式存储结构只针对非线性结构 （ C）顺序存储结构能存储有序表，链式存储结构不能存储有序表
10、（ D）链式存储结构比顺序存储结构节省存储空间 国家二级 MS Office高级应用机试（数据结构与算法）模拟试卷 17答案与解析 一、选择题 1 【正确答案】 C 【试题解析】 算法有穷性指算法必须能在有限的时间内做完，即算法必须能在执行有限个步骤之后终止。 【知识模块】 数据结构与算法 2 【正确答案】 C 【试题解析】 算法的空间复杂度是指算法执行过程中所占用的内存空间，包括：算法程序所用空间、输入的初始数据所用存储空间以及执行过程中所需要的额外空间。 【知识模块】 数据结构与算法 3 【正确答案】 D 【试题解析】 算法是指问题 解决方案准确而完整的描述。算法从一个初始状态和初始输入开
11、始，经过一系列清晰和有效的运算后最终终止。算法不等于程序，也不等于计算方法。设计算法不仅要考虑数据对象的运算和操作，还要考虑算法的控制结构。 【知识模块】 数据结构与算法 4 【正确答案】 D 【试题解析】 算法时间复杂度指算法运行需要的时间，空间复杂度指算法运行需要的内存空间，两者都是问题规模的函数，但这两者之间没有直接关系。 【知识模块】 数据结构与算法 5 【正确答案】 C 【试题解析】 算法是指解决问题方案的准确 而完整的描述。它是指令的有限序列，每一条指令表示一个或多个操作。 【知识模块】 数据结构与算法 6 【正确答案】 D 【试题解析】 算法基本特征包括： 有穷性：算法要在有穷步
12、骤后结束； 确定性：算法中每条指令都有确切的含义，不存在多义性； 可行性：算法中的操作都可以通过已经实行的基本运算执行有限次来实现； 拥有足够的情报：有零个或多个输入，有一个或多个输出。 【知识模块】 数据结构与算法 7 【正确答案】 A 【试题解析】 指令系统是一个计算机系统能够执行的所有指令的集合。不同的计算机系统其指令系统是有差别的。但是一般都包含四类基本的运算：算术运算、逻辑运算、关系运算和数据传输。算术运算包括加减乘除等，逻辑运算包括与或非等，关系运算包括大于、小于、等于、不大于等，数据传输包括赋值、输入和输出等。 【知识模块】 数据结构与算法 8 【正确答案】 D 【试题解析】 算
13、法的控制结构是指算法中操作直接执行的顺序。算法的效果不仅取决于所选用的操作指令，还与各操作直接的执行顺序有关。基本的控制结构包括顺序 结构、选择结构和循环结构。 【知识模块】 数据结构与算法 9 【正确答案】 A 【试题解析】 栈支持子程序调用。栈是一种只能在一端进行插入或删除操作的线性表。在主程序调用子程序时要首先保存主程序当前的状态，然后转去执行子程序，最终把子程序的执行结果返回到主程序中调用子程序的位置，继续向下执行，这种调用符合栈的特点。 【知识模块】 数据结构与算法 10 【正确答案】 D 【试题解析】 数据的存储结构又称为物理结构，是指数据的逻辑结构在计算机存储空间中的存放方式。
14、【知识模 块】 数据结构与算法 11 【正确答案】 B 【试题解析】 数据结构是指反映数据元素之间关系的数据元素的集合。数据结构作为数据元素的集合，包括逻辑结构和存储结构两种。 【知识模块】 数据结构与算法 12 【正确答案】 B 【试题解析】 线性结构又称为线性表，线性表满足 2个条件： 有且只有一个根节点； 每个节点最多只有一个前件，也最多只有一个后件。 A选项有一个以上根节点的结构一定不是线性结构， B选项的只有一个根节点不一定是线性结构，如树。循环链表是一种特殊的链表，它的最后一个节点的指 针域指向头节点，整个链表形成一个环。双向链表也叫双链表，是链表的一种，它的每个数据节点中都有两个
15、指针，分别指向直接后继和直接前驱。 【知识模块】 数据结构与算法 13 【正确答案】 C 【试题解析】 栈是一种特殊的线性表，它的插入和删除运算都只在线性表的一端进行，另一端是封闭的，不能进行任何操作。允许进行插入和删除的一端称为栈顶，另一端称为栈底。栈遵循 “先进后出 ”或 “后进先出 ”的原则。入栈序列是ABC123，那么退栈序列就是入栈的逆序列，即 321CBA。 【知识模块】 数据结构与算法 14 【正确答案】 C 【试题解析】 栈是一种特殊的线性表，它的插入和删除运算都只在线性表的一端进行，另一端是封闭的，不能进行任何操作。允许进行插入和删除的一端称为栈顶，另一端称为栈底。栈遵循 “
16、先进后出 ”或 “后进先出 ”的原则。读取栈顶并不会做退栈操作。 【知识模块】 数据结构与算法 15 【正确答案】 C 【试题解析】 栈是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。当有新元素进栈时，栈顶指针向上移动；当有元素出栈时，栈顶指针向 下移动。在栈中栈底指针不变，栈中元素随栈顶指针的变化而动态变化。 【知识模块】 数据结构与算法 16 【正确答案】 B 【试题解析】 栈是线性表，具有先进后出 (First In Last Out简称 FILO)或者后进先出 (Last In First Out，简称 LIFO)原则。栈的记忆作用是
17、指 POP操作，可以与PUSH操作对应，还原 PUSH时的变量值。所以栈会通在函数调用时保存调用前的现场用于调用后恢复。栈的插入与删除只需改变栈顶指针。栈是一种逻辑结构。可以有多种存储结构。 【知识模块 】 数据结构与算法 17 【正确答案】 D 【试题解析】 根据数据结构中各数据元素之间前后关系的复杂稗度，数据结构分为线性结构和非线性结构。有且只有一个根节点，且每个节点最多只有一个前驱节点和最多一个后继节点，这种数据结构称为线性结构，否则称为非线性结构。树只有一个根节点，但是树的节点可以有超过一个后继节点。 【知识模块】 数据结构与算法 18 【正确答案】 D 【试题解析】 将线性表中的元素
18、在计算机中一段连续的存储区域中连续存储，称为线性表的顺序存储。由于是顺序存储，因此元素不需 要指针指向下一个元素。 【知识模块】 数据结构与算法 19 【正确答案】 D 【试题解析】 对线性表进行插入操作是，若在第 i(1 =i =n+1)个元素之前插入一个新元素，则完成需要 3个步骤： 原来第 i个节点至第 n个节点依次往后移动一个位置； 把新节点放在第 i个位置； 线性表的节点树加 l。对线性表删除第 i个节点时，需要 2个步骤： 把第 i个元素到第 n个元素依次前移一个位置； 线性表的节点数减 1。因此答案是 D。 【知识模块】 数据结构与算法 20 【正确答案】 B 【试题解析】 具有
19、 “先进后出 ”原则的是栈。队列的原则是 “先进先出 ”。 【知识模块】 数据结构与算法 21 【正确答案】 D 【试题解析】 循环队列就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间。循环队列是一种特殊的线性结构。元素个数由队头指针和队尾指针共同决定，元素总数是 (rear-front+线性表总长 )线性表总长，是取余运算。计算循环队列元素个数直接用 rear-front，如果结果是正数，结果就是元素个数；结果是负数，则再加上队列长度就是元素个数；如果结果是 0，那么有两种情况 ，要么个数是 0，要么个数是队列长度。 【知识模块】 数据结构与算法 22 【正确答案】 D
20、【试题解析】 循环队列是将顺序队列首尾相连形成的，随着插入或删除元素的进行，其队头指针及队尾指针是在不断变化的，有时可能会出现队头指针大于队尾指针的情况，也可能是队尾指针大于队头指针。如一个循环队列长度为 10，假定初始状态为 front=rear=0，在插入元素时， rear增加到 10，也可以认为 rear=0，此时队列已满，然后删除元素，假定删除 3个元素，此时 front=3，然后再插入 2个元素， rear=2，这个时候就是 front大于 rear。 【知识模块】 数据结构与算法 23 【正确答案】 D 【试题解析】 队头和队尾指针相等，可能有两种情况： 队列已满； 队列已空。当队
21、列已满。则元素个数为 35；为空，则元素个数是 0。 【知识模块】 数据结构与算法 24 【正确答案】 B 【试题解析】 采取 “先进先出 ”原则操作数据的是队列。栈的原则是 “先进后出 ”。 【知识模块】 数据结构与算法 25 【正确答案】 D 【试题解析】 队列的原则是 “先进先出 ”，因此可以用在先 到先服务的作业调度。 【知识模块】 数据结构与算法 26 【正确答案】 C 【试题解析】 线性表的链式存储结构称为线性链表。在链式存储结构中，存储数据结构的存储空间可以不连续，各数据节点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。 【知识模块】 数据结构与算法 27 【正确答案】 D 【试题解析】 循环队列是线性结构，是一种逻辑结构。循环队列既可以用顺序存储方式实现，也可以用链式存储方式实现。 【知识模块】 数据结构与算法 28 【正确答案】 A 【试题解析】 链式存储结构既可以存储线性结构，又可以存储有序表。链式存储结构需要额外的指针域，比顺序存储结构存储密度低，浪费空间。 【知识模块】 数据结构与算法
