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