1、国家二级公共基础知识（数据结构与算法）模拟试卷 17及答案解析(总分：56.00，做题时间：90 分钟)一、选择题(总题数：28，分数：56.00)1.选择题下列各题 A、B、C、D 四个选项中，只有一个选项是正确的，请将正确选项涂写在答题卡相应位置上。（分数：2.00）_2.算法的有穷性是指（分数：2.00）A.算法程序的运行时间是有限的B.算法程序所处理的数据量是有限的C.算法程序的长度是有限的D.算法只能被有限的用户使用3.下列叙述中正确的是（分数：2.00）A.算法就是程序B.设计算法时只需要考虑数据结构的设计C.设计算法时只需要考虑结果的可靠性D.以上三种说法都不对4.算法的空间复杂
2、度是指（分数：2.00）A.算法在执行过程中所需要的计算机存储空间B.算法所处理的数据量C.算法程序中的语句或指令条数D.算法在执行过程中所需要的临时工作单元数5.算法的时间复杂度是指（分数：2.00）A.算法的执行时间B.算法所处理的数据量C.算法程序中的语句或指令条数D.算法在执行过程中所需要的基本运算次数6.下列叙述中正确的是（分数：2.00）A.算法的效率只与问题的规模有关，而与数据的存储结构无关B.算法的时间复杂度是指执行算法所需要的计算工作量C.数据的逻辑结构与存储结构是一一对应的D.算法的时间复杂度与空间复杂度一定相关7.下列叙述中正确的是（分数：2.00）A.一个算法的空间复杂
3、度大，则其时间复杂度也必定大B.一个算法的空间复杂度大，则其时间复杂度必定小C.一个算法的时间复杂度大，则其空间复杂度必定小D.算法的时间复杂度与空间复杂度没有直接关系8.数据的存储结构是指（分数：2.00）A.存储在外存中的数据B.数据所占的存储空间量C.数据在计算机中的顺序存储方式D.数据的逻辑结构在计算机中的表示9.下列描述中正确的是（分数：2.00）A.一个逻辑数据结构只能有一种存储结构B.数据的逻辑结构属于线性结构，存储结构属于非线性结构C.一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率D.一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率1
4、0.下列描述中正确的是（分数：2.00）A.数据的逻辑结构与存储结构必定是一一对应的B.由于计算机存储空间是向量式的存储结构，因此，数据的存储结构一定是线性结构C.程序设计语言中的数据一般是顺序存储结构，因此，利用数组只能处理线性结构D.以上三种说法都不对11.下列叙述中正确的是（分数：2.00）A.有一个以上根结点的数据结构不一定是非线性结构B.只有一个根结点的数据结构不一定是线性结构C.循环链表是非线性结构D.双向链表是非线性结构12.下列数据结构中，属于非线性结构的是（分数：2.00）A.循环队列B.带链队列C.二叉树D.带链栈13.下列描述中正确的是（分数：2.00）A.线性链表是线性
5、表的链式存储结构B.栈与队列是非线性结构C.双向链表是非线性结构D.只有根结点的二叉树是线性结构14.下面叙述中正确的是（分数：2.00）A.线性表是线性结构B.栈与队列是非线性结构C.线性链表是非线性结构D.二叉树是线性结构15.下列关于栈的叙述正确的是（分数：2.00）A.栈按“先进先出”组织数据B.栈按“先进后出”组织数据C.只能在栈底插入数据D.不能删除数据16.支持子程序调用的数据结构是（分数：2.00）A.栈B.树C.队列D.二叉树17.下列数据结构中，能够按照“先进后出“原则存取数据的是（分数：2.00）A.循环队列B.栈C.队列D.二叉树18.下列关于栈叙述正确的是（分数：2.
6、00）A.栈顶元素能最先被删除B.栈顶元素最后才能被删除C.栈底元素永远不能被删除D.以上三种说法都不对19.下列关于栈的叙述中，正确的是（分数：2.00）A.栈底元素一定是最后入栈的元素B.栈顶元素一定是最先入栈的元素C.栈操作遵循先进后出的原则D.以上三种说法都不对20.下列叙述中正确的是（分数：2.00）A.在栈中，栈中元素随栈底指针与栈顶指针的变化而动态变化B.在栈中，栈顶指针不变，栈中元素随栈底指针的变化而动态变化C.在栈中，栈底指针不变，栈中元素随栈顶指针的变化而动态变化D.上述三种说法都不对21.一个栈的初始状态为空。现将元素 1、2、3、4、5、A、B、C、D、E 依次入栈，然
7、后再依次出栈，则元素出栈的顺序是（分数：2.00）A.12345ABCDEB.EDCBA54321C.ABCDE12345D.54321EDCBA22.栈的初始状态为空。现将元素 1，2，3，A，B，C 依次入栈，再依次出栈，则元素出栈的顺序是（分数：2.00）A.1，2，3，A，B，CB.C，B，A，1，2，3C.C，B，A，3，2，1D.1，2，3，C，B，A23.下列关于栈的描述中错误的是（分数：2.00）A.栈是先进后出的线性表B.栈只能顺序存储C.栈具有记忆作用D.对栈的插入与删除操作中，不需要改变栈底指针24.按照“后进先出“原则组织数据的数据结构是（分数：2.00）A.队列B.栈
8、C.双向链表D.二叉树25.下列对队列的描述中正确的是（分数：2.00）A.队列属于非线性表B.队列按“先进后出”原则组织数据C.队列在队尾删除数据D.队列按“先进先出”原则组织数据26.下列叙述中正确的是（分数：2.00）A.栈是一种先进先出的线性表B.队列是一种后进先出的线性表C.栈与队列都是非线性结构D.以上三种说法都不对27.下列叙述中正确的是（分数：2.00）A.栈是“先进先出”的线性表B.队列是“先进后出”的线性表C.循环队列是非线性结构D.有序线性表既可以采用顺序存储结构，也可以采用链式存储结构28.下列关于栈的描述中正确的是（分数：2.00）A.在栈中只能插入元素而不能删除元素
9、B.在栈中只能删除元素而不能插入元素C.栈是特殊的线性表，只能在一端插入或删除元素D.栈是特殊的线性表，只能在一端插入元素，而在另一端删除元素国家二级公共基础知识（数据结构与算法）模拟试卷 17答案解析(总分：56.00，做题时间：90 分钟)一、选择题(总题数：28，分数：56.00)1.选择题下列各题 A、B、C、D 四个选项中，只有一个选项是正确的，请将正确选项涂写在答题卡相应位置上。（分数：2.00）_解析：2.算法的有穷性是指（分数：2.00）A.算法程序的运行时间是有限的 B.算法程序所处理的数据量是有限的C.算法程序的长度是有限的D.算法只能被有限的用户使用解析：解析：算法的有穷
10、性，是指算法必须能在有限的时间内做完，即算法必须能在执行有限个步骤之后终止。3.下列叙述中正确的是（分数：2.00）A.算法就是程序B.设计算法时只需要考虑数据结构的设计C.设计算法时只需要考虑结果的可靠性D.以上三种说法都不对 解析：解析：所谓算法是指解题方案的准确而完整的描述。是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。算法不等于程序，也不等于计算方法。设计算法时不仅要考虑对数据对象的运算和操作，还要考虑算法的控制结构。4.算法的空间复杂度是指（分数：2.00）A.算法在执行过程中所需要的计算机存储空间 B.算法所处理的数据量C.算法程
11、序中的语句或指令条数D.算法在执行过程中所需要的临时工作单元数解析：解析：算法的空间复杂度是指执行这个算法所需要的内存空间。这个内存空间包括算法程序所占的空间，输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。5.算法的时间复杂度是指（分数：2.00）A.算法的执行时间B.算法所处理的数据量C.算法程序中的语句或指令条数D.算法在执行过程中所需要的基本运算次数 解析：解析：算法的时间复杂度，是指执行算法所需砭的计算工作量。算法的工作量可以用算法在执行过程中所需基本运算的执行次数来度量。6.下列叙述中正确的是（分数：2.00）A.算法的效率只与问题的规模有关，而与数据的存储结构无关
12、B.算法的时间复杂度是指执行算法所需要的计算工作量 C.数据的逻辑结构与存储结构是一一对应的D.算法的时间复杂度与空间复杂度一定相关解析：解析：算法的时间复杂度是指执行算法所需要的计算工作量。算法的工作量用算法所执行的基本运算的次数来度量，而算法所执行的基本运算次数是问题规模的函数；算法的空间复杂度一般是指执行这个算法所需要的内存空间。算法的时间复杂度与空间复杂度并不相关。数据的逻辑结构就是数据元素之间的逻辑关系，它是从逻辑上描述数据元素之间的关系，是独立于计算机的：数据的存储结构是研究数据元素和数据元素之间的关系如何在计算机中表示，它们并非一一对应。算法的执行效率不仅与问题的规模有关，还与数
13、据的存储结构有关。7.下列叙述中正确的是（分数：2.00）A.一个算法的空间复杂度大，则其时间复杂度也必定大B.一个算法的空间复杂度大，则其时间复杂度必定小C.一个算法的时间复杂度大，则其空间复杂度必定小D.算法的时间复杂度与空间复杂度没有直接关系 解析：解析：算法的复杂度主要包括时间复杂度和空问复杂度。算法的时间复杂度是指执行算法所需要的计算工作量，算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数，即算法的工作量=f(n)，其中 n是问题的规模：算法的空间复杂度，一般是指执行这个算法所需要的内存空间。一个算法所占用的存储空间包括算法程序所占用的空间、输
14、入的初始数据所占的仔储空间以及算法执行过程中所需要的额外空间。根据各自的定义可知，算法的时间复杂度与空间复杂度并不相关。8.数据的存储结构是指（分数：2.00）A.存储在外存中的数据B.数据所占的存储空间量C.数据在计算机中的顺序存储方式D.数据的逻辑结构在计算机中的表示 解析：解析：在对数据进行处理时，各数据元素在计算机中的存储关系，即为数据的存储结构。9.下列描述中正确的是（分数：2.00）A.一个逻辑数据结构只能有一种存储结构B.数据的逻辑结构属于线性结构，存储结构属于非线性结构C.一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率D.一个逻辑数据结构可以有多种存储结
15、构，且各种存储结构影响数据处理的效率 解析：解析：数据的逻辑结构是指数据集合中各数据元素之间所固有的逻辑关系；数据的存储结构是在对数据进行处理时，各数据元素在计算机中的存储关系。数据的存储结构是指数据的逻辑结构在计算机中的表示，一种逻辑结构可以表示成多种存储结构：而采用不同的存储结构，其数据处理的效率是不同的。10.下列描述中正确的是（分数：2.00）A.数据的逻辑结构与存储结构必定是一一对应的B.由于计算机存储空间是向量式的存储结构，因此，数据的存储结构一定是线性结构C.程序设计语言中的数据一般是顺序存储结构，因此，利用数组只能处理线性结构D.以上三种说法都不对 解析：解析：数据的逻辑结构是
16、指反映数据元素之间逻辑关系的数据结构。数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构(也称数据的物理结构)。一般来说，一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接、索引等。11.下列叙述中正确的是（分数：2.00）A.有一个以上根结点的数据结构不一定是非线性结构B.只有一个根结点的数据结构不一定是线性结构 C.循环链表是非线性结构D.双向链表是非线性结构解析：解析：在数据结构中，树这类的数据结构只有一个根结点，但它不是线性结构。12.下列数据结构中，属于非线性结构的是（分数：2.00）A.循环队列B.带链队列C.二叉树 D.带链栈解析：解析：根据数
17、据结构中各数据元素之间的前后性关系的复杂程度，一般将数据结构分为两大类：线性结构和非线性结构。循环队列、带链队列和带链栈都是线性结构，而二叉树是非线性结构。13.下列描述中正确的是（分数：2.00）A.线性链表是线性表的链式存储结构 B.栈与队列是非线性结构C.双向链表是非线性结构D.只有根结点的二叉树是线性结构解析：解析：线性表的链式存储结构称为线性链表。线性表链式存储结构的基本单位称为存储结点，每个存储结点包括数据域和指针域两个组成部分。各数据元素之间的前后件关系是由各结点的指针域来指示的，指向线性表中第结点的指针 HEAD称为头指针，当 HEAD=NULL时称为空表。栈、队列和双向链表是
18、线性结构，树是一种简单的非线性结构。在树这种数据结构中，所有数据元素的关系具有明显的层次特征。二叉树是仆线性结构。线性结构和非线性结构是从数据的逻辑结构角度来讲的，与该数据结构中有多少个元素没有关系，即使是空的二叉树也是非线性结构。14.下面叙述中正确的是（分数：2.00）A.线性表是线性结构 B.栈与队列是非线性结构C.线性链表是非线性结构D.二叉树是线性结构解析：解析：线性表是最简单的、最常用的一种线性结构。所谓线性链表指的是采用链式存储结构的线性表。栈和队列其实是一种特殊的线性表。树是一种简单的非线性结构，二叉树是树的一种。15.下列关于栈的叙述正确的是（分数：2.00）A.栈按“先进先
19、出”组织数据B.栈按“先进后出”组织数据 C.只能在栈底插入数据D.不能删除数据解析：解析：栈是限定在一端进行插入和删除的线性表，允许进行插入和删除元素的一端称为栈顶，另一端称为栈底。栈是按照“先进后出”的原则组织数据的。16.支持子程序调用的数据结构是（分数：2.00）A.栈 B.树C.队列D.二叉树解析：解析：栈是一种限定在一端进行插入与删除的线性表。在主函数调用子函数时，要首先保存主函数当前的状态，然后转去执行子函数，把子函数的运行结果返回到上函数调用子函数时的位置，主函数再接着往下执行，这种过程符合栈的特点。所以一般采用栈式存储方式。17.下列数据结构中，能够按照“先进后出“原则存取数
20、据的是（分数：2.00）A.循环队列B.栈 C.队列D.二叉树解析：解析：栈按照“先进后出”(FILO)或“后进先出”(LIFO)组织数据：队列是“先进先出”(FIFO)或“后进后出”(LILO)的线性表。18.下列关于栈叙述正确的是（分数：2.00）A.栈顶元素能最先被删除 B.栈顶元素最后才能被删除C.栈底元素永远不能被删除D.以上三种说法都不对解析：解析：栈是先进后出的线性表，栈顶的元素最先被删除，栈底的元素最后被删除。19.下列关于栈的叙述中，正确的是（分数：2.00）A.栈底元素一定是最后入栈的元素B.栈顶元素一定是最先入栈的元素C.栈操作遵循先进后出的原则 D.以上三种说法都不对解
21、析：解析：栈是限定只能在表的一端进行插入和删除操作的线性表，必须按“后进先出”的规则操作元素。20.下列叙述中正确的是（分数：2.00）A.在栈中，栈中元素随栈底指针与栈顶指针的变化而动态变化B.在栈中，栈顶指针不变，栈中元素随栈底指针的变化而动态变化C.在栈中，栈底指针不变，栈中元素随栈顶指针的变化而动态变化 D.上述三种说法都不对解析：解析：在栈中，允许插入与删除的一端称为栈顶，而不允许插入与删除的另一端称为栈底。栈跟队列不同，元素只能在栈项压入或弹出，栈底指针不变，栈中元素随栈顶指针的变化而动态变化，遵循后进先出的规则。21.一个栈的初始状态为空。现将元素 1、2、3、4、5、A、B、C
22、、D、E 依次入栈，然后再依次出栈，则元素出栈的顺序是（分数：2.00）A.12345ABCDEB.EDCBA54321 C.ABCDE12345D.54321EDCBA解析：解析：栈是按照“先进后出”或“后进先出”的原则组织数据的。所以出栈顺序是 EDCBA54321。22.栈的初始状态为空。现将元素 1，2，3，A，B，C 依次入栈，再依次出栈，则元素出栈的顺序是（分数：2.00）A.1，2，3，A，B，CB.C，B，A，1，2，3C.C，B，A，3，2，1 D.1，2，3，C，B，A解析：解析：栈是按照“先进后出”或“后进先出”的原则组织数据的。所以出栈顺序是 CBA321。23.下列关
23、于栈的描述中错误的是（分数：2.00）A.栈是先进后出的线性表B.栈只能顺序存储 C.栈具有记忆作用D.对栈的插入与删除操作中，不需要改变栈底指针解析：解析：栈是限定在一端进行插入与删除的线性表。栈顶(top)：插入数据(即入栈)的一端；栈底(bottom)：不能入栈也不能出栈的一端。栈存储数据的原则：“先进后出”或“后进先出”。栈的特性是具有记忆作用。24.按照“后进先出“原则组织数据的数据结构是（分数：2.00）A.队列B.栈 C.双向链表D.二叉树解析：解析：栈是限定在一端进行插入与删除的线性表。在栈中，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。栈顶元素总是最后被插
24、入的元素，也是最先被删除的元素：栈底元素总是最先被插入的元素，也是最后才能被删除的元素。即栈是按照“后进先出”(Last In First Out，简称LIFO)或“先进后出”(First In Last Out，简称 FILO)的原则组织数据的。因此，栈也称为“后进先出表”或“先进后出”表。25.下列对队列的描述中正确的是（分数：2.00）A.队列属于非线性表B.队列按“先进后出”原则组织数据C.队列在队尾删除数据D.队列按“先进先出”原则组织数据 解析：解析：队列 fqueue)是指允许在一端进行插入、而在另一端进行删除的线性表。允许插入的一端称为队尾；允许删除的一端称为队头。在队列这种数
25、据结构中，最先插入的元素将最先能够被删除；反之，最后插入的元素将最后才能被删除。因此，队列又称“先进先出”或“后进后出”的线性表。26.下列叙述中正确的是（分数：2.00）A.栈是一种先进先出的线性表B.队列是一种后进先出的线性表C.栈与队列都是非线性结构D.以上三种说法都不对 解析：解析：栈是先进后出的线性表，队列是先进先出的线性表，二者均为线性结构。27.下列叙述中正确的是（分数：2.00）A.栈是“先进先出”的线性表B.队列是“先进后出”的线性表C.循环队列是非线性结构D.有序线性表既可以采用顺序存储结构，也可以采用链式存储结构 解析：解析：本题主要考查了栈、队列、循环队列的概念，栈是先进后出的线性表，队列是先进先出的线性表。根据数据结构中各数据元素之间的前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。有序线性表既可以采用顺序存储结构，又可以采用链式存储结构。28.下列关于栈的描述中正确的是（分数：2.00）A.在栈中只能插入元素而不能删除元素B.在栈中只能删除元素而不能插入元素C.栈是特殊的线性表，只能在一端插入或删除元素 D.栈是特殊的线性表，只能在一端插入元素，而在另一端删除元素解析：解析：栈是限定在一端进行插入与删除的线性表，在栈中，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。
