计算机二级公共基础知识题库及答案分析

全国计算机等级考试二级公共基础学问考题库

第一章数据结构

一、选择题

（1）下列数据结构中，能用二分法进行查找的是

A）挨次存储的有序线性表B）线性链表

C）二叉链表D）有序线性链表

【答案】A

【解析】二分查找只适用于按次存储的有序表。在此所说的有序表是指线性表中的元素按值非递减排列（即从小到大.但允许相邻元素值相等）

的。选项A正确。

（2）下列关于栈的描述正确的是

A）在栈中只能插入元素而不能删除元素

B）在栈中只能删除元素而不能插入元素

C）栈是特殊的线性表，只能在一端插入或删除元素

D）栈是特殊的线性表，只能在一端插入元素，而在另一端删除元素

【答案】C

【解析】栈是一种特殊的线性表，其插入与删除运算都只在线性表的一端进行。由此可见，选项A、选项B和选项D错误，正确答案是选项

Co

（3）下列叙述中正确的是

A）一个规律数据结构只能有一种存储结构

B）数据的规律结构属于线性结构，存储结构属于非线性结构

C）一个规律数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率

D）一个规律数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率

【答案】D

【解析】一般来说，一种数据的规律结构依据需要可以表示成多种存储结构，常用的存储结构有挨次、链接、索引等存储结构。而接受不同

的存储结构，其数据处理的效率是不同的。由此可见，选项D的说法正确。

（4）算法执行过程中所需要的存储空间称为算法的

A）时间简单度B）计算工作量C）空间简单度D）工作空间

【答案】c

【解析】算法执行时所需要的存储空间，包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外

空间，其中额外空间还包括算法程序执行过程的工作单元以及某种数据结构所需要的附加存储空间。这些存储空间共称为算法的空后

（5）下列关于队列的叙述中正确的是

A）在队列中只能插入数据B）在队列中只能删除数据

C）队列是先进先出的线性表D）队列是先进后出的线性表

【答案】c

【解析】对队列可以进行插入和删除数据的操作，只是插入数据只能在队尾，删除数据只能在队头。所以队列是先进先出的线性表。

⑹设有下列二叉树：

O

/\

©。

\/\

©©O

对此二叉树后序遍历的结果为

A)ABCDEFB)BDAECFC)ABDCEFD)DBEFCA

【答案】D

【解析】二叉树的遍历分为先序、中序、后序三种不同方式。本题要求后序遍历。其遍历挨次应为：后序遍历左子树一〉后序遍历右子树一〉

访问根结点。依据定义，后序遍历序列是DBEFCA,故答案为D。

（7）下列叙述中正确的是（）

A）程序执行的效率与数据的存储结构亲密相关

B）程序执行的效率只取决于程序的掌握结构

C）程序执行的效率只取决于所处理的数据量

D）以上三种说法都不对

【答案】A

【解析】本题考查程序效率。程序效率是指程序运行速度和程序占用的存储空间。影响程序效率的因素是多方面的，包括程序的设计、使用

的算法、数据的存储结构等。在确定数据规律结构的基础上，选择一种合适的存储结构，可以使得数据操作所花费的时间少，占用的存储空

间少，即提高程序的效率。因此，本题选项A的说法是正确的。

（8）下列叙述中正确的是（）

A）数据的规律结构与存储结构必定是一一对应的

B）由于计算机存储空间是向量式的存储结构，因此，数据的存储结构肯定是线性结构

。程序设计语言中的数组一般是挨次存储结构，因此，采用数组只能处理线线结构

D）以上三种说法都不对

【答案】D

【解析1本题考查数据结构的基本学问。

数据之间的相互关系称为规律结构。通常分为四类基本规律结构，即集合、线性结构、树型结构、图状结构或网状结构。存储结构是规律结

构在存储器中的映象，它包含数据元素的映象和关系的映象。存储结构在计算机中有两种，即挨次存储结构和链式存储结构。挨次存储结构

是把数据元素存储在一块连续地址空间的内存中；链式存储结构是使用指针把相互直接关联的节点链接起来。因此，这两种存储结构都是线

性的。可见，规律结构和存储结构不是一一对应的。因此，选项A和选项B的说法都是错误的。

无论数据的规律结构是线性的还是非线性的，只能选择挨次存储结构或链式存储结构来实现存储。程序设计语言中，数组是内存中一段连续

的地址空间，可看作是挨次存储结构。可以用数组来实现树型规律结构的存储，比如二叉树。因此，选项c的说法是错误的

(9)冒泡排序在最坏状况下的比较次数是()

A)n(n+l)/2B)nbg2nC)n(n-l)/2D)n/2

【答案】C

【解析】冒泡排序的基本思想是：将相邻的两个元素进行比较，假如反序，则交换；对于一个待排序的序列，经一趟排序后，最大值的元素

移动到最终的位置，其他值较大的元素也向最终位置移动，此过程称为一趟冒泡。对于有n个数据的序列，共需n-1趟排序，第i趟对从1到

n-i个数据进行比较、交换。冒泡排序的最坏状况是待排序序列逆序，第1趟比较nJ次，第2趟比较n-2次。依此类推，最终趟比较1次，一

共进行n-1趟排序。因此，冒泡排序在最坏状况下的比较次数是(n-l)+(n-2)+…+1,结果为n(n-1)/2。本题的正确答案是选项c。

(10)一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为()

A)219B)221C)229D)231

【答案】A

【解析】本题考查数据结构中二叉树的性质。二叉树满意如下一条性质，即：对任意一棵二叉树，若终端结点(即叶子结点)数为口“而其度数

为2的结点数为出,则no=n2+l0

依据这条性质可知，若二叉树中有70个叶子结点，则其度为2的结点教为7()-1,即69个。二叉树的总结点数是度为2、度为1和叶子结点的

总和，因此，题目中的二叉树总结点数为69+80+70,即219。因此，本题的正确答案是选项A。

(11)下列叙述中正确的是()

A)算法的效率只与问题的规模有关，而与数据的存储结构无关

B)算法的时间简单度是指执行算法所需要的计算工作量

C)数据的规律结构与存储结构是一一对应的

D)算法的时间简单度与空间简单度肯定相关

【答案】B

【解析】本题考查数据结构中有关算法的息本学问和概念。数据的结构，直接影响算法的选择和效率。而数据结构包括两方面，即数据的规

律结构和数据的存储结构。因此，数据的规律结构和存储结构都影响算法的效率。选项A的说法是错误的。算法的时间简单度是指算法在计

算机内执行时所需时间的度量；与时间简单度类似，空间简单度是指算法在计算机内执行时所需存储空间的度量。因此，选项B的说法是正

确的。

数据之间的相互关系称为规律结构。通常分为四类基本规律结构，即集合、线性结构、树型结构、图状结构或网状结构。存储结构是规律结

构在存储器中的映象，它包含数据元素的映象和关系的映象。存储结构在计算机中有两种，即挨次存储结构和链式存储结构。可见，规律结

构和存储结构不是一一对应的。因此，选项c的说法是错误的。有时人们为了提高算法的时间简单度，而以牺牲空间简单度为代价。但是，

这两者之间没有必定的联系。因此，选项D的说法是错误的。

(12)下列关于算法的时间简单度陈述正确的是

A)算法的时间简单度是指执行算法程序所需要的时间

B)算法的时间简单度是指算法程序的长度

C)算法的时间简单度是指算法执行过程中所需要的基本运算次数

D)算法的时间简单度是指算法程序中的指令条数

【答案】C

【解析】算法的时间简单度是指执行算法所需要的计算工作量，也就是算法在执行过程中所执行的基本运算的次数，而不是指程序运行需要

的时间或是程序的长度。

(13)下列关于栈的叙述中正确的是

A)在栈中只能插入数据B)在栈中只能删除数据

C)栈是先进先出的线性表D)栈是先进后出的线性表

【答案】D

【解析】对栈可进行插入和删除数据的操作，但必需牢记插入和删除数据都只能是在栈顶，是一种特殊的线性表。所以栈是先进后出的线性

表O

(14)设有下列二叉树：

对此二叉树中序遍历的结果为

A)ABCDEFB)DAECFC)BDAECFD)DBEFCA

【答案】C

【解析】二叉树的遍历分为先序、中序、后序三种不同方式。本题要求中序遍历，其遍历挨次应为：中序遍历左子树-＞访问根结点-＞中序遍

历右子树。依据定义，中序遍历序列是BDAECF,故答案为B。

(15)依据“后进先出”原则组织数据的数据结构是

A)队列B)栈

C)双向链,表D)二叉树

【答案】B

【解析1"后进先出"表示最终被插入的元素敢先能被删除。选项A中，队列是指允许在一端进行插入、而在另一端进行删除的线性表，在队

列这种数据结构中，最先插入的元素将最先能够被删除，反之，靛终插入的元素将最终才能被删除，队列又称为"先进先出"的线性表，它

体现了“先来先服务”的原则：选项B中，栈顶元素总是最终被插入的元素，从而也是最先能被删除的元素，栈底元素总是最先被插入的元

素，从而也是最终才能被删除的元素。队列和栈都属于线性表，它们具有挨次存储的特点，所以才有“先进先出"和"后进先出”的数据组

织方式。双向链表使用链式存储方式.二叉树也通常接受链式存储方式，它们的存储数据的空间可以是不连续的，各个数据结点的存储挨次

与数据元素之间的规律关系可以不全都。所以选项c和选项D错。

(16)下列叙述中正确的是

A)线性链表是线性表的链式存储结构

B)栈与队列是非线性结构

C)双向链表是非线性结构

D)只有根结点的二叉树是线性结构

【答案】A

【解析1一个非空的数据结构假如满意下列两个条件：(1)有且只有一个根结点;(2)每一个结点最多有一个前件，也最多有一个后件。则称为线

性结构。线性链表是线性表的链式存储结构，选项A的说法是正确的。栈与队列是特殊的线性表，它们也是线性结构，选项B的说法是错误

的；双向链表是线性表的链式存储结构，其对应的规律结构也是线性结构，而不是非线性结构，选项c的说法是错误的；二叉树是非线性结

构，而不是线性结构，选项D的说法是错误的。因此，本题的正确答案为A

(17)对如下二叉树

进行后序遍历的结果为

A)ABCDEFB)DBEAFC

C)ABDECFD)DEBFCA

【答案】D

【解析】二叉树后序遍历的简洁描述如下：若二叉树为空，则结束返回。否则(1)后序遍历左子树；(2)后序遍历右子树；⑶访问根结点。也就

是说，后序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后遍历右子树，最终访问根结点，并且，在遍

历左、右子树时，仍旧先遍历左子树，然后遍历右子树，最终访问根结点。依据后序遍历的算法，后序遍历的结果为DEBFCA。

(18)下列对队列的叙述正确的是()

A)队列属于非线性表

B)队列按“先进后出”原则组织数据

C)队列在队尾删除数据

D)队列按"先进先出"原则组织数据

【答案】D

【解析】本题考查数据结构中队列的基本学问。队列是一种限定性的线性表，它只允许在表的一端插入元素，而在另一端删除元素，所以队

列具有先进先出的特性。在队列中，允许插入元素的一端叫做队尾，允许删除的一端则称为队头。这与日常生活中的排队是全都的，最早进

入队列的人最早离开，新来的人总是加入到队尾。因此，本题中只有选项D的说法是正确的。

(19)对下列二叉树进行前序遍历的结果为()

A)DYBEAFCZXB)YDEBFZXCAC)ABDYECFXZD)ABCDEFXYZ

【答案】C

I解析】本题考查数据结构中二叉树的遍历。依据对二叉树根的访问先后挨次不同，分别称为前序遍历、中序遍历和后序遍历。这三种遍历

都是递归定义的，即在其子树中也依据同样的规律进行遍历。下面就是前序遍历方法的递归定义。当二叉树的根不为空时，依次执行如下3

个操作：

⑴访问根结点

⑵按先序遍历左子树

(3)按先序遍历右子树

依据如上前序遍历规章，来遍历本题中的二叉树。首先访问根结点，即A,然后遍历A的左子树。遍历左子树同样依据相同的规章首先访问

根结点B,然后遍历B的左子树。遍历B的左子树，首先访问D,然后访问D的左子树，D的左子树为空，接下来访问D的右子树，即Y。

遍历完B的左子树后，再遍历B的右子树，即E。到此遍历完A的左子树，接下来遍历A的右子树。依据同样的规章，首先访问C,然后通

历C的左子树。即F。c的左子树遍历完，接着遍历C的右子树。首先访问右子树的根结点X,然后访问X的左子树，X的左子树，即Z,接

下来访问X的右子树，右子树为空。到此，把题目的二叉树进行了一次前序遍历。遍历的结果为ABDYECFXZ,故本题的正确答案为选项C。

(20)某二叉树中有n个度为2的结点，则该二叉树中的叶子结点数为()

A)n+1B)n-1C)2nD)n/2

【答案】A

【解析】本题考查数据结构中二叉树的性质。二叉树满意如下一条性质，即：对任意一棵二叉树，若终端结点(即叶子结点)数为n。，而其度

数为2的结点数为m,则n产m+L

依据这条性质可知，若二叉树中有n个度为2的结点，则该二叉树中的叶子结点数为n+1。因此，本题的正确答案是选项A。

(21)在深度为7的满二叉树中，叶子结点的个数为

A)32B)31C)64D)63

【答案】C

【解析】在二叉树的第k层上，最多有力'代/1)个结点。对于满二叉树来说，每一层上的结点数都达到最大值，即在满二叉树的第k层上有

2卜”个结点。因此，在深度为7的满二叉树中，全部叶子结点在第7层上.即其结点数为22=2"=64因此.本题的正确答案为c。

(22)下列叙述中正确的是

A)一个笄法的空间简单度大，则其时间简单度也必定大

B)一个算法的空间简单度大，则期时间简单度必定小

C)一个算法的时间简单度大，则其空间简单度必定小

D)上述三种说法都不对

【答案】D

【解析】时间简单度是指一个算法执行时间的相对度量；空间简单度是指算法在运行过程中临时占用所需存储空间大小的度量。人们都盼望

选择一个既省存储空间、又省执行时间的算法。然而，有时为了加快算法的运行速度，不得不增加空间开销；有时为了能有效地存储算法和

数据，又不得不牺牲运行时间。时间和空间的效率往往是一对冲突，很难做到两全。但是，这不适用于全部的状况，也就是说时间简单度和

空间简单度之间虽然常常冲突。但是二者不存在必定的联系。因此，选项A、B、c的说法都是错误的。故本题的正确答案是D。

(23)在长度为64的有序线性表中进行挨次查找，最坏状况下需要比较的次数为

A)63B)64C)6D)7

【答案】B

【解析1在长度为64的有序线性表中，其中的64个数据元素是依据从大到小或从小到大的挨次排列有序的。在这样的线性表中进行挨次查找,

最坏的状况就是查找的数据元素不在线性表中或位于线性表的最终。依据线性表的挨次查找笄法，首先用被查找的数据和线性表的第一个数

据元素进行比较。若相等，则查找胜利，否则，连续进行比较，即和线性表的其次个数据元素进行比较。同样，若相等，则查找胜利，否则，

连续进行比较。依次类推，直到在线性表中查找到该数据或查找到线性表的最终一个元素，算法才结束。因此，在长度为64的有序线性表中

进行挨次查找，最坏的状况下需要比较64次。因此，本题的正确答案为B。

(24)对下列二叉树

进行中序遍历的结果是

A)ACBDFEGB)ACBDFGE

C)ABDCGEFD)FCADBEG

【答案】A

【解析】二叉树的中序遍历递归算法为：假如根不空，则(1)按中序次序访问左子树；(2)访问根结点：(3)按中序次序访问右子树。否则返回。

本题中，依据中序遍历算法.应首先依据中序次序访问以c为根结点的左子树，然后再访问根结点F,最终才访问以E为根结点的右子树。遍

历以c为根结点的左子树同样要遵循中序遍历算法，因此中序遍历结果为ACBD;然后遍历根结点F;遍历以E为根结点的右子树，同样要遵

循中序遍历算法，因此中序遍历结果为EG。最终把这三部分的遍历结果按按次连接起来，中序遍历结果为ACBDFEG。因此，本题的正确答

案是A。

(25)数据的存储结构是指«

A)存储在外存中的数据B)数据所占的存储空间量

C)数据在计笄机中的挨次存储方式D)数据的规律结构在计算机中的表示

【答案】D

【解析】数据的规律结构在计算机存储空间中的存放形式称为数据的存储结构，也称数据的物理结构。所以选项D正确。

(26)下列关于栈的描述中错误的是。

A)栈是先进后出的线性表

B)栈只能挨次存储

C)栈具有记忆作用

D)对栈的插入与删除操作中，不需要转变栈底指针

【答案】B

【解析】本题考核栈的基本概念，我们可以通过排解法来确定本题的答案。栈是限定在一端进行插入与删除的线性表，栈顶元素总是最终被

插入的元素，从而也是最先能被删除的元素；栈底元素总是最先被插入的元素，从而也是最终才能被删除的元素，即栈是依据“先进后出”

或“后进先出”的原则组织数据的，这便是栈的记忆作用，所以选项A和选项C正确。对栈进行插入和删除操作时，栈顶位置是动态变化的，

栈底指针不变，选项D正确。由此可见，选项B的描述错误。

(27)对于长度为n的线性表，在最坏状况下，下列各排序法所对应的比较次数中正确的奥______。

A)冒泡排序为n/2B)冒泡排序为n

C)快速排序为nD)快速排序为n(n-l)/2

【答案】D

【解析1假设线性表的长度为n,在最坏状况下，冒泡排序和快速排序需要的比较次数为n(n—1)/2。由此可见，选项D正确。

(28)对长度为n的线性表进行挨次查找，在最坏状况下所需要的比较次数为。

A)log2nB)n/2C)nD)n+1

【答案】C

【解析】在长度为n的线性表中进行挨次查找，最坏状况下需要比较n次。选项C正确。

（29）下列对于线性链表的描述中正确的是______。

A）存储空间不肯定是连续，且各元素的存储挨次是任意的

B）存储空间不肯定是连续，且前件元素肯定存储在后件元素的前面

C）存储空间必需连续，且前件元素肯定存储在后件元素的前面

D）存储空间必需连续，且各元素的存储挨次是任意的

【答案】A

【解析】在姓式存储结构中，存储数据的存储空间可以不连续，各数据结点的存储挨次与数据元素之间的规律关系可以不全都，数据元素之

间的规律关系，是由指针域来确定的。由此可见，选项A的描述正确。

（30）某二叉树中度为2的结点有18个，则该二叉树中有个叶子结点。

【答案】19

【解析】二叉树具有如下性质：在任意一棵二叉树中，度为。的结点（即叶子结点）总是比度为2的结点多一个。依据题意，度为2的节点为

18个，那么，叶子结点就应是19个。

（1）线性表若接受链式存储结构时，要求内存中可用存储单元的地址

A）必需是连续的

B）部分地址必需是连续的

C）肯定是不连续的

D）连续不连续都可以

解析：在链式存储结构中，存储数据结构的存储空间可以是连续的，也可以是不连续的，各数据结点的存储挨次与数据元素之间的规律关系

可以不全郴。故本题答案应为选项D）

（2）在待排序的元素序列基本有序的前提下，效率最高的排序方法是

A）冒泡排序

B）选择排序

C）快速排序

D）归并排序

解析：从平均时间性能而言，快速排序最佳，其所需时间最少，但快速排序在敢坏状况下的时间性能不如堆排序和归并排序。当序列中的纪

录基本有序或元素个数较少时，冒泡排序和简洁选择排序为最佳排序方法，故本题答案应为选项A）。

（3）下列叙述中，错误的是

A）数据的存储结构与数据处理的效率亲密相关

B）数据的存储结构与数据处理的效率无关

C）数据的存储结构在计算机中所占的空间不肯定是连续的

D）一种数据的规律结构可以有多种存储结构

解析：一般来说，一种数据结构依据需要可以表示成多种存储结构。常用的存储结构有挨次、链接、索引等，而接受不同的存储结构，其数

据处理的效率是不同的；一个数据结构中的各数据元素在计算机存储空间中的位置关系与规律关系是有可能不同的。故本题答案应为选项B）o

（4）希尔排序属于

A）交换排序

B）归并排序

C）选择排序

D）插入排序

解析：希尔排序的基本思想是把纪录按下标的肯定增量分组，对每组纪录使用插入排序，随增量的渐渐减小，所分成的组包含的纪录越来越

多，到增量的值减小到1时，整个数据合成一组，构成一组有序纪录，故其属于插入排序方法。故本题答案应为选项D）。

（1）栈和队列的共同特点是

A）都是先进先出

B）都是先进后出

C）只允许在端点处插入和删除元素

D)没有共同点

解析：栈和队列都是一种特殊的操作受限的线性表，只允许在端点处进行插入和删除。二者的区分是：栈只允许在表的一端进行插入或删除

操作，是一种“后进先出”的线性表；而队列只允许在表的一端进行插入操作，在另一端进行删除操作，是一种“先进先出”的线性表。故

本题答案应为选项C)o

(2)已知二叉树后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是

A)ached

B)decab

C)deabc

D)cedba

解析：依据后序遍历序列可确定根结点为c；再依据中序遍历序列可知其左子树由deba构成，右子树为空；又由左子树的后序遍历序列可知

其根结点为e,由中序遍历序列可知其左子树为d,右子树由ba构成，如下图所示。求得该二叉树的前序遍历序列为选项D)。

(3)链表不具有的特点是

A)不必事先估量存储空间

B)可随机访问任一元素

C)插入删除不需要移动元素

D)所需空间与线性表长度成正比

解析：链表接受的是链式存储结构，它克服了挨次存储结构的缺点：它的结点空间可以动态申请和释放；它的数据元素的规律次序靠结点的

指针来指示，不需要移动数据元素。但是链式存储结构也有不足之处：①每个结点中的指针域需额外占用存储空间；②链式存储结构

是一种非随机存储结构。故本题答案应为选项D)。

(6)算法的时间简单度是指

A)执行算法程序所需要的时间

B)算法程序的长度

C)算法执行过程中所需要的基本运算次数

D)算法程序中的指令条数

解析：算法的简单度主要包括算法的时间简单度和算法的空间简单度。所谓算法的时间简单度是指执行算法所需要的计算工作量；算法的空

间简单度一般是指执行这个算法所需要的内存空间。故本题答案应为选项A)。

(1)已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF,则该二叉树的后序遍历为

A)GEDHFBCA

B)DGEBHFCA

C)ABCDEFGH

D)ACBFEDHG

解析：采用前序和中序遍历的方法可以确定二叉树的结构，具体步骤如下：①前序遍历的第一个结点A为树的根结点；②中序遍历中A的

左边的结点为A的左子树，A右边的结点为A的右子树；③再分别对A的左右子树进行上述两步处理，直到每个结点都找到正确的位置。

故本题答案应为选项B)o

(2)树是结点的集合，它的根结点数目是

A)有且只有1

B)1或多于1

C)0或1

D)至少2

解析：树是一个或多个结点组成的有限集合，其中一个特定的结点称为根，其余结点分为若干个不相交的集合。每个集合同时又是一棵树。

树有且只有1个根结点。故本题答案应为选项A)o

(3)假如进栈序列为el,e2,e3,e4,则可能的出栈序列是

A)e3,e1,e4,e2

B）e2,e4,e3,el

C）e3,e4,el,e2

D）任意挨次

解析：由栈”后进先出”的特点可知：A）中el不行能比e2先出，C）中e3不行能比e4先出，且el不行能比e2先出，D）中栈是先进后出的，

所以不行能是任意挨次。B）中出栈过程如图所示：

故本题答案应为选项B）o

（4）在设计程序时，应接受的原则之一是

A）不限制gpt。语句的使用

B）削减或取消注解行

C）程序越短越好

D）程序结构应有助于读者理解

解析：滥用goto语句将使程序流程无规律，可读性差，因此A）不选；注解行有利于对程序的理解，不应削减或取消，B）也不选；程序的

长短要依照实际状况而论，而不是越短越好，C）也不选。故本题答案应为选项D）。

（5）程序设计语言的基本成分是数据成分、运算成分、掌握成分和

A）对象成分

B）变量成分

C）语句成分

D）传输成分

解析：程序设计语言是用于书写计算机程序的语言，其息本成分有以下4种，数据成分：用来描述程序中的数据。运算成分：描述程序中所

需的运算。掌握成分：用来构造程序的规律掌握结构。传输成分：定义数据传输成分，如输入输出语言。故本题答案应为选项D）。

（1）循环链表的主要优点是

A)不再需要头指针了

B)从表中任一结点动身都能访问到整个链表

C)在进行插入、删除运算时，能更好的保证链表不断开

D)已知某个结点的位置后，能够简洁的找到它的直接前件

解析：循环链表就是将单向链表中最终一个结点的指针指向头结点，使整个链表构成一个环形，这样的结构使得从表中的任一结点动身都能

访问到整个链表。故本题答案应为选项B)。

(2)栈底至栈顶依次存放元素A、B、C、D,在第五个元素E入栈前，栈中元素可以出栈，则出栈序列可能是

A)ABCED

B)DCBEA

C)DBCEA

D)CDABE

解析：栈操作原则上“后进先出”，栈底至栈顶依次存放元素A、B、C、D,则表明这4个元素中D是最终进栈，B、C处于中间，A最早进

栈。所以出栈时肯定是先出D,再出C,最终出A。故本题答案应为选项B)。

(3)对长度为N的线性表进行挨次查找，在最坏状况下所需要的比较次数为o

A)N+1

B)N

Q(N+l)/2

D)N/2

解析：［答案］B,很简洁，我们的二级程序设计语言书中都有此算法，此外还要把握二分法查找，这也是我们二级中常考的。那么二分法最坏

的状况为多少次呢？log2"的最小整数值。比如n为4,最坏的状况要比较3次；n为18,最坏的状况要比较5次。

(1)下列叙述中正确的是

A)线性表是线性结构

B)栈与队列是非线性结构

C)线性链表是非线性结构

D)二叉树是线性结构

解析：线性表是一种线性结构，数据元素在线性表中的位置只取决于它们自己的序号，即数据元素之间的相对位更是线性的；栈、队列、线

性链表实际上也是线性表，故也是线性结构；树是一种简洁的非线性结构。故本题答案应为选项A)。

(2)非空的循环单链表head的尾结点(由p所指向)，满意

A)p->next==NULL

B)p二二NULL

C)p->next=head

D)p二head

解析：循环链表就是将链表的最终一个结点指向链表头结点(或第一个结点)，即p->next=head。故本题答案应为选项C)。

(3)已知数据表A中每个元素距其最终位置不远，为节约时间，应接受的算法是

A)堆排序

B)直接插入排序

C)快速排序

D)直接选择排序

解析：当数据表A中每个元素距其最终位置不远，说明数据表A按关键字值基本有序，在待排序序列基本有序的状况下，接受插入排序所用

时间最少，故答案为选项B)。

(1)假设线性表的长度为n,则在最坏状况下，冒泡排序需要的比较次数为

A)log2n

B)n2

C)()(nl.5)

D)n(n-1)/2

解析：假设线性表的长度为n,则在最坏状况下，冒泡排序要经过n/2遍的从前往后的扫描和n/2遍的从后往前的扫描，需要的比较次数为

n（n-1）/2o故本题答案应为选项D）。

（2）算法分析的目的是

A）找出数据结构的合理性

B）找出算法中输入和输出之间的关系

C）分析算法的易懂性和牢靠性

D）分析算法的效率以求改进

解析：算法分析是指对一个算法的运行时间和占用空间做定量的分析，一般计算出相应的数量级，常用时间简单度和空间简单度表示。分析

算法的目的就是要降低算法的时间简单度和空间简单度，提高算法的执行效率。故本题答案应为选项D）。

（3）线性表L=（al,a2,a3,--ai,--an）,下列说法正确的是

A）每个元素都有一个直接前件和直接后件

B）线性表中至少要有一个元素

C）表中诸元素的排列挨次必需是由小到大或由大到小

D）除第一个元素和最终一个元素外，其余每个元素都有一个且只有一个直接前件和直接后件

解析：线性表可以为空表；第一个元素没有直接前件，最终一个元素没有直接后件；线性表的定义中，元素的排列并没有规定大小挨次。故

本题答案应为选项D）o

（4）在单链表中，增加头结点的目的是

A）便利运算的实现

B）使单链表至少有一个结点

C）标识表结点中首结点的位置

D）说明单链表是线性表的链式存储实现

解析：头结点不仅标识了表中首结点的位置，而且依据单链表（包含头结点）的结构，只要把握了表头，就能够访问整个链表，因此增加头

结点目的是为了便于运算的实现。故本题答案应为选项A）o

（1）算法的空间简单度是指

A）算法程序的长度

B）算法程序中的指令条数

C）算法程序所占的存储空间

D）执行过程中所需要的存储空间

解析：算法的简单度主要包括算法的时间简单度和算法的空间简单度。所谓算法的时间简单度是指执行算法所需要的计算工作量；算法的空

间简单度一般是指执行这个算法所需要的内存空间。故本题答案应为选项D）。

（2）用链表表示线性表的优点是

A）便于随机存取

B）花费的存储空间较挨次存储少

C）便于插入和删除操作

D）数据元素的物理挨次与规律挨次相同

解析：链式存储结构克服了挨次存储结构的铁点：它的结点空间可以动态申请和释放；它的数据元素的规律次序靠结点的指针来指示，不需

要移动数据元素。故链式存储结构下的线性表便于插入和删除操作。故本题答案应为选项C）。

（3）数据结构中，与所使用的计算机无关的是数据的

A）存储结构

B）物理结构

C）规律结构

D）物理和存储结构

解析：数据结构概念一般包括3个方面的内容，数据的规律结构、存储结构及数据上的运算集合。数据的规律结构只抽象的反映数据元素之

间的规律关系，而不管它在计算机中的存储表示形式。故本职答案应为选项C）。

（1）由两个栈共享一个存储空间的好处是

A）削减存取时间，降低下溢发生的机率

B）节约存储空间，降低上溢发生的机率

C）削减存取时间，降低上滥发生的机率

D）节约存储空间，降低下溢发生的机率

解析：常常一个程序中要用到多个栈，为了不发生上溢错误，就必需给每个栈安排一个足够大的存储空间。但实际中，很难精确地

估量，若每个栈都安排过大的存储空间，势必造成系统空间紧急；若让多个栈共用一个足够大的连续存储空间，则可采用栈的动态特性使他

们的存储空间互补。故本题答案应为选项B）。

（2）设有两个串p和q,求q在p中首次消失位置的运算称作

A）连接

B）模式匹配

C）求子串

D）求串长

解析：子串的定位操作通常称作串的模式匹配，是各种串处理系统中最重要的操作之一，算法的基本思想是：从主串的开头字符起和模式的

第一个字符比较，若相等则连续比较后续字符，否则从主串的下一个字符起再重新和模式的字符比较，依次类推，直至模式中的每一个字符

依次和主串中的一个连续的字符序列相等，称匹配胜利，否则称匹配不胜利。

（3）下列关于队列的叙述中正确的盘______。

A.在队列中只能插入数据

B.在队列中只能删除数据

C.队列是先进先出的线性表

D.队列是先进后出的线性表

解析：C

队列是先进先出的，栈是先进后出的，2者的区分肯定要搞清晰。

⑴算法的空间简单度是指

A）算法程序的长度

B）算法程序中的指令条教

C）执行算法程序所占的存储空间

D）算法执行过程中所需要的存储空间

【答案】D

【解析】算法的空间简单度一般是指这个算法执行时所需要的内存空间，其中包括算法程序所占的空间、输入的初始数据所占的存储空间以

及算法执行过程中所需要的额外空间，其中额外空间还包括算法程序执行过程的工作单元以及某种数据结构所需要的附加存储空间。

（2）线性表的链式存储结构是一种

A）随机结构

B）挨次结构

C）索引结构

D）散列结构

【答案】B

【解析】线性表的链式存储结构中的每一个存储结点不仅含有一个数据元素，还包括指针，每一个指针指向一个与本结点有规律关系的结点。

此类存储方式属于挨次存储。

（3）设有下列二叉树：对此二叉树先序遍历的结果是

A）AB（：DEF

B）DBEAFC

QABDECF

D）DEBFCA

【答案】C

【解析】二叉树的遍历分为先序、中序、后序三种不同方式。本题要求先序遍历；遍历挨次应为：访问根结点-＞先序遍历左子树-＞先序遍历

右子树。依据定义，先序遍历序列是ABDECF。

（1）算法分析的目的是O

A）找出数据结构的合理性B）找出算法中输入和输出之间的关系

C）分析笄法的易懂性和牢靠性D）分析算法的效率以求改进

答案：D

评析：算法分析是指对一个算法的运行时间和占用空间做定量的分析，一般计笄出相应的数量级，常用时间简单度和空间简单度表示。分析

算法的目的就是要降低算法的时间简单度和空间简单度，提高算法的执行效率。

（3）已知数据表A中每个元素距其靛终位置,不远，为节约时间，应接受的算法兴。

A）堆排序B）直接插入排序

C）快速排序D）直接选择排序

答案：B

评析：当数据表A中每个元素距其最终位置不远，说明数据表A按关键字值基本有序，在待排序序列基本有序的状况下，接受插入排序所用

时间最少，故答案为选项B。

（4）用链表表示线性表的优点是______。

A）便于插入和删除操作B）数据元素的物理挨次与规律挨次相同

C）花费的存储空间较挨次存储少D）便于随机存取

答案：A

评析：链式存储结构克服了挨次存储结构的缺点：它的结点空间可以动态申请和释放；它的数据元素的规律次序靠结点的指针来指示，不需

要移动数据元素。故链式存储结构下的线性表便于插入和删除操作。

1.以下数据结构中不属于线性数据结构的是。

A、队列B、线性表