全国计算机等级考试笔试考试习题集答案（二级数据结构部分）1. 算法的基本概念1）算法的基本特征是可行性、确定性、__________和拥有足够的情报。

有穷性2）算法复杂度主要包括时间复杂度和__________复杂度。

空间3）一个算法通常由两种基本要素组成：一是对数据对象的运算和操作，二是_________。

算法的控制结构4）下列叙述中正确的是__________。

DA. 一个算法的空间复杂度大，则其时间复杂度也必定大B. 一个算法的空间复杂度大，则其时间复杂度必定小C. 一个算法的时间复杂度大，则其空间复杂度必定小D．上述三种说法都不对5）在长度为64的有序线性表中进行顺序查找，最坏情况下需要比较的次数为_________。

B A. 63 B. 64 C. 6 D. 76）算法的时间复杂度是指_________。

CA. 执行算法程序所需要的时间B. 算法程序的长度C. 算法执行过程中所需要的基本运算次数D．算法程序中的指令条数7）算法的空间复杂度是指_________。

DA. 算法程序的长度B. 算法程序中的指令条数C．算法程序所占的存储空间D. 算法执行过程中所需要的存储空间8）在算法的四个特性中，算法必须在执行有限个步骤之后终止指的是算法的_____。

有穷性9）算法分析的目的是_________。

DA. 找出数据结构的合理性B. 找出算法中输入和输出之间的关系C. 分析算法的易懂性和可靠性D. 分析算法的效率以求改进10）在程序设计阶段应该采取_________和逐步求精的方法，把一个模块的功能逐步分解，细化为一系列具体的步骤，继而用某种程序设计语言写成程序。

自顶向下2. 数据结构的基本概念1）下列叙述中正确的是__________。

DA. 一个逻辑数据结构只能有一种存储结构B. 数据的逻辑结构属于线性结构，存储结构属于非线性结构C. 一个逻辑结构可以有多种存储结构，且各种存储结构不影响数据处理的效率D. 一个逻辑数据结构可有多种存储结构，且各种存储结构影响数据处理的效率2）数据的存储结构是指__________。

DA. 存储在外存中的数据B. 数据所占的存储空间量C. 数据在计算机中的顺序存储方式D. 数据的逻辑结构在计算机中的表示3）下列叙述中正确的是_________。

AA. 线性表是线性结构B．栈与队列是非线性结构C. 线性链表是非线性结构D. 二叉树是线性结构4）以下关于数据的逻辑结构的叙述中，不正确的是_________。

BA. 数据的逻辑结构是数据间关系的描述B．数据的逻辑结构不仅反映数据间的逻辑关系，而且反映其在计算机中的存储方式C. 数据的逻辑结构分为线性结构和非线性结构D. 树形结构是典型的非线性结构5）在数据的存储结构中，不仅需要存储各数据元素的信息，还要存放各元素之间________的信息。

前后件关系3. 线性表及其顺序存储结构1）顺序表是一种____________的存储结构。

AA. 随机存取B.顺序存取2）表长为n的顺序存储的线性表，当在任何位置上插入或删除一个元素的概率相同时，插入一个元素所需移动元素的平均个数为________，删除一个元素所需移动元素的个数为__________。

n/2，（n-1）/23) 若要频繁地进行插入或删除操作，_________使用线性表的顺序存储结构。

BA. 适宜B. 不适宜4）下列叙述中错误的是_________。

CA. 线性表是由n个元素组成的一个有限序列B．线性表是一种线性结构C. 线性表的所有结点有且仅有一个前件和后件D．线性表可以是空表5）以下描述中，不是线性表顺序存储结构特征的是________。

DA. 不便于插入和删除B．需要连续的存储空间C. 可以随机访问D．需要另外开辟空间来保存元素之间的关系6）线性表常用的两种存储结构是_______和_______。

顺序存储和链式存储7）在包含1000个元素的线性表中实现如下运算，___________所需的执行时间最长。

A A．线性表按顺序方式存储，在线性表的第100个结点后面插入一个新结点B．线性表按链式方式存储，在线性表的第100个结点后面插入一个新结点C．线性表按顺序方式存储，删除线性表的第900个结点D．线性表按链式方式存储，删除指针p所指向的结点选项B、D中的运算无须移动结点，通过修改指针即可完成，选项A中的运算需要移动900个结点，选项C中的运算需要移动100个结点，故选项A中的运算最耗时。

答案A8）对长度为N的线性表进行顺序查找，在最坏情况下，需要的比较次数是________。

N4. 栈、队列、线性链表1）按“先进后出”原则组织数据的数据结构是_________。

栈或Stack2）数据结构分为逻辑结构和存储结构，循环队列属于_____结构。

存储或物理3）数据结构分为线性结构和非线性结构，带链的队列属于_________，栈属于_____。

均为线性结构4）在一个容量为15的循环队列中，若头指针front=6，尾指针rear=9，则该循环队列中共有_________个元素。

35）假设用一个长度为50的数组（数组元素的下标从0到49）作为栈的存储空间，栈底指针bottom指向栈底元素，栈顶指针top指向栈顶元素，若bottom=49，top=30，则栈中具有_________个元素。

206）下列对于线性链表的描述中正确的是__________。

AA.存储空间不一定是连续，且各元素的存储顺序是任意的B.存储空间不一定是连续，且前件元素一定存储在后件元素的前面C.存储空间必须连续，且前件元素一定存储在后件元素的前面D.存储空间必须连续，且各元素的存储顺序是任意的7）下列关于栈的描述中错误的是__________。

BA. 栈是先进后出的线性表B. 栈只能顺序存储C. 栈具有记忆作用D. 对栈的插入与删除操作中，不需要改变栈底指针8）下列关于栈的描述正确的是__________。

CA. 在栈中只能插入元素而不能删除元素B. 在栈中只能删除元素而不能插入元素C. 栈是特殊的线性表，只能在一端插入或删除元素D. 栈是特殊的线性表，只能在一端插入元素，而在另一端删除元素9）下列叙述中正确的是__________。

AA. 线性链表是线性表的链式存储结构B. 栈与队列是非线性结构C. 双向链表是非线性结构D. 只有根结点的二叉树是线性结构10）按照“后进先出”原则组织数据的数据结构是__________。

BA. 队列B. 栈C. 双向链表D. 二叉树11）下列关于队列的叙述中正确的是_________。

CA. 在队列中只能插入数据B. 在队列中只能删除数据C. 队列是先进先出的线性表D. 队列是先进后出的线性表12）下列关于栈的叙述中正确的是_________。

DA. 在栈中只能插入数据B. 在栈中只能删除数据C. 栈是先进先出的线性表D. 栈是先进后出的线性表13）下列关于栈的叙述中正确的是_________。

DA. 栈是非线性结构B. 栈是一种树状结构C. 栈具有先进先出的特征D. 栈具有后进先出的特征14）下列叙述中正确的是_________。

DA. 栈是先进先出的线性表B. 队列是先进后出的线性表C. 循环队列是非线性结构D. 有序线性表既可以采用顺序存储结构，也可以采用链式存储结构15）支持子程序调用的数据结构是_________。

AA. 栈B. 树C. 队列D. 二叉树16）下列关于线性表两种存储结构的叙述中，正确的是_________。

BA. 若存储相同数目的元素，则线性链表比顺序表要节省存储空间B. 对无序表的查找，顺序表和线性链表的效率基本上是一样的C. 顺序表适用于插入、删除等更新操作频繁的场合D. 线性链表适用于查询操作比较频繁的场合17）下列叙述中错误的是_________。

DA. 循环链表中，通过表中的任何一个结点可以访问到表中其他所有的结点B. 线性链表的插入和删除效率比顺序表的插入和删除效率高C. 线性链表与顺序表相比，它容易实现动态增长D. 在线性链表中查找一个元素要比在顺序表中查找一个元素快18）栈中允许进行插入和删除的一端叫做_________。

栈顶19）栈S最多能容纳4个元素。

现有6个元素按ABCDEF的顺序进栈，下列_________序列是可能的出栈序列。

CA. EDCBAFB. BCEFADC. CBEDAFD. ADFEBC20）队列是限定在表的一端进行插入和在另一端进行删除操作的线性表。

允许插入的一端称作________。

队尾21）在一个容量为24的循环队列中，若头指针front=8，尾指针rear=3，则该循环队列中共有_______个元素。

19 24+rear-front22）数据结构分为逻辑结构和存储结构，循环队列属于_______结构。

逻辑23）设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5、e6，依次通过栈S，一个元素出栈后即进入队列Q，若六个元素出队的顺序是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是_______。

CA. 6B. 4C. 3D. 2栈的特点是先进后出，由出栈顺序e2、e4、e3、e6、e5、e1可知：e2出栈前，栈里的元素为e2、e1，共2个元素；e4出栈前，栈里的元素为e4、e3、e1，共3个元素；e3出栈前，栈里的元素为e3、e1，共2个元素；e6出栈前，栈里的元素为e6、e5、e1，共3个元素；e5出栈前，栈里的元素为e5、e1，共2个元素；毫无疑问，栈的最小容量应为3。

本题答案为C。

24）若已知一个栈的输入序列为1，2，3，……，n；其输出序列为P1,P2,P3,…,Pn。

若P1=n，则Pi为________。

CA. iB. n-iC. n-i+1D. 不确定25）下列叙述中正确的是________。

CA. 在栈中，栈中元素随栈底指针与栈顶指针的变化而动态变化B. 在栈中，栈顶指针不变，栈中元素随栈底指针的变化而动态变化C. 在栈中，栈底指针不变，栈中元素随栈顶指针的变化而动态变化D. 上述三种说法都不对26）一个栈的初始状态为空，首先将元素5,4,3,2,1依次入栈，然后退栈一次，再将元素A,B,C,D依次入栈，之后将所有元素全部退栈。

则所有元素退栈的顺序为_______。

1DCBA234527）下列叙述中正确的是_______。

BA. 有一个以上根结点的数据结构不一定是非线性结构B．只有一个根结点的数据结构不一定是非线性结构C. 循环链表是非线性结构D. 双向链表是非线性结构5. 树与二叉树1）某二叉树中度为2的结点有18个，则该二叉树中有________个叶子结点。

192）一棵二叉树第六层（根结点为第一层）的结点数最多为__________个。