全国计算机等级考试《二级c 语言程序设计》专用教材【考纲分析 考点精讲 真题演练 强化习题】

全国计算机等级考试《二级C++语言程序设计》专

用教材【考纲分析+考点精讲+真题演练+强化习

题】

目录

第一部分公共基础知识......................................................

第1章数据结构与算法..................................................

考纲分析............................................................

考点精讲............................................................

1.1算法.....................................................

1.2数据结构的基本概念.........................................

1.3线性表及其顺序存储结构.....................................

1.4栈和队列...................................................

1.5线性链表..................................................

L6树与二叉树.................................................

1.7♦找技术..................................................

1.8排序技术..................................................

强化习题............................................................

第2章程序设计基础....................................................

考纲分析............................................................

考点精讲............................................................

2.1程序设计方法与风格.........................................

2.2结构化程序设计.............................................

2.3面向对象的程序设计.........................................

强化习题............................................................

第3章软件工程基础....................................................

考纲分析............................................................

考点精讲............................................................

3.1软件工程基本概念...........................................

3.2结构化分析方法.............................................

3.3结构化设计方法.............................................

3.4软件测试...................................................

3.5程序的调试.................................................

强化习题............................................................

第4章数据库设计基础..................................................

考纲分析............................................................

考点精讲............................................................

4.1数据库系统的基本概念.......................................

4.2数据模型...................................................

43关系代数

4：4数［库设计与管理.二二二二二二二二二二二二二二二

强化习题............................................................

第二部分C++语言程序设计...................................................

第1章C++语言概述.....................................................

考纲分析............................................................

考点精讲............................................................

1.1C++语言的发展..............................................

1.2C++语言的特点..............................................

1.3面向对象程序设计...........................................

L4C++语言的基本符号..........................................

1.5C++语言的词汇..............................................

1.6C++程序的基本框架..........................................

L7C++程序的开发过程..........................................

强化习题............................................................

第2章数据类型、运算符和表达式........................................

考纲分析............................................................

考点精讲............................................................

2.1C++语言的数据类型.........................................

2.2常量....................................................

2.3变量....................................................

2.4运算符和表达式.............................................

强化习题............................................................

第3章基本控制结构....................................................

考纲分析............................................................

考点精讲............................................................

3.1C++语句...................................................

3.2顺序结构...................................................

3.3选择结构...................................................

3.4循环结构..................................................

3.5跳转语句..................................................

强化习题............................................................

第4章数组、指针与引用................................................

考纲分析............................................................

考点精讲............................................................

4.1数组.....................................................

4.2指针.....................................................

4.3引用.....................................................

4.4动态存储分配...............................................

强化习题............................................................

第5章函数..........................................................

考纲分析............................................................

考点精讲............................................................

5.1函数定义...................................................

5.2函数调用...................................................

5.3函数原型...................................................

5.4函数返回类型...............................................

5.5函数参数...................................................

5.6函数重载...................................................

5.7内联函数...................................................

5.8递归函数...................................................

5.9变量的生存周期.............................................

强化习题............................................................

第6章类和对象........................................................

考纲分析............................................................

考点精讲............................................................

6.1类的定义...................................................

6.2对象的定义.................................................

6.3构造函数和析构函数.........................................

6.4自由存储对象...............................................

6.5this指针..................................................

6.6静态成员...................................................

6.7常成J..........................................................

6.8友元.....................................................

6.9对象数组...................................................

6.10成员对象..................................................

强化习题............................................................

第7章继承和派生......................................................

考纲分析............................................................

考点精讲............................................................

7.1继承与派生.................................................

7.2派生类对基类成员的访问.....................................

7.3派生类的构造函数和析构函数.................................

7.4多继承与虚基类.............................................

7.5子类型关系.................................................

7.6虚函数与多态性.............................................

强化习题............................................................

第8章运算符重载......................................................

考纲分析............................................................

考点精讲............................................................

8.1运算符函数与运算符重载.....................................

8.2典型运算符的重载...........................................

8.3运算符重载应注意的几个问题.................................

强化习题............................................................

第9章模板..........................................................

考纲分析............................................................

考点精讲............................................................

9.1函数模板..................................................

9.2类模板.....................................................

强化习题............................................................

第10章C++流..........................................................

考纲分析............................................................

考点精讲............................................................

10.1C++流的概念..............................................

10.2输入输出的格式控制........................................

10.3文件流....................................................

强化习题............................................................

第一部分公共基础知识

第1章数据结构与算法

考纲分析

1.算法的基本概念，算法复杂度的概念和意义（时间复杂度与空间复杂度）。

2.数据结构的定义，数据的逻辑结构与存储结构；数据结构的图形表示；

线性结构与非线性结构的概念。

3.线性表的定义，线性表的顺序存储结构及其插入与删除运算。

4.栈和队列的定义，栈和队列的顺序存储结构及其基本运算。

5.线性单链表、双向链表与循环链表的结构及其基本运算。

6.树的基本概念，二叉树的定义及其存储结构；二叉树的前序、中序和后

序遍历。

7.顺序查找与二分法查找算法，基本排序算法（交换类排序，选择类排序,

插入类排序）。

考点精讲

1.1算法

考点1算法的基本概念

（1）算法的定义

算法是指解题方案的准确而完整的描述，即算法是对特定问题求解步骤的

一种描述。它是一组严谨定义运算顺序的规则，且每个规则都是明确有效的，

此顺序将在有限的次数下终止。需要注意的是：算法不等于程序，也不等于计

算方法。

（2）算法的基本特征

①可行性

a.算法中的每一步骤都必须能够实现；

b.算法执行的结果要能够达到预期的目的。

②确定性

确定性是指算法中的每一个步骤都必须有明确的定义，不允许有模棱两可

的解释，也不允许有多义性。

③有穷性

有穷性是指算法必须能在有限的时间内做完，即必须能在执行有限个步骤

之后终止，且必须有合理的执行时间。

④拥有足够的情报

算法是否有效，取决于为算法所提供的情报是否足够。一般而言，当算法

有足够的情报时，此算法有效，而当提供的情报不够时，算法可能无效。

【真题演练】

算法的有穷性是指（）。［2013年9月真题］

A.算法程序的运行时间是有限的

B.算法程序所处理的数据量是有限的

C.算法程序的长度是有限的

D.算法只能被有限的用户使用

【答案】A

【解析】算法设计有穷性要求操作步骤有限且必须在有限时间内完成，耗

费太长时间得到的正确结果是没有意义的。

考点2算法设计基本方法

(1)列举法

①基本思想

根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些

是需要的，哪些是不需要的。常用于解决“是否存在”或“有多少种可能”等

类型的问题。

②主要特点

算法比较简单，但列举情况较多时，算法工作量很大。

③注意事项

例举算法时，通过对实际问题进行详细分析，将与问题有关的知识条理化、

完备化、系统化，并从中找出规律，或对所有可能的情况进行分类，从而引出

一些有用的信息，减少列举量。

(2)归纳法

①基本思想

通过列举少量的特殊情况，经过分析，最后找出一般的关系。

②主要特点

a.比列举法更能反映问题的本质，可解决列举量为无限的问题；

b.可操作性低，不易归纳出一个具体数学模型；

c.归纳得出的结论只是一种猜测，须对这种猜测加以必要的证明。

(3)递推

①基本思想

从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。

②主要特点

a.初始条件或问题本身已给定，或通过对问题的分析化简得到；

b.递推本质上属于归纳法，递推关系式往往是归纳的结果；

c.数值型递推算法计算过程中必须注意数值计算的稳定性问题。

(4)递归

①基本思想

将复杂问题逐层分解，归结为一些简单的问题，将简单问题解决掉，再沿

着原来分解的逆过程逐步进行综合。

②主要特点

a.递归的基础是归纳，对问题逐层分解的过程实际上并没有对问题进行求

解；

b.在可计算性理论和算法设计中占有重要地位；

c.递归算法比递推算法清晰易读，结构简练；

d.设计递归算法比递推算法容易，但是其执行效率较低。

③分类

a.直接递归。一个算法P显式地调用自己。

b.间接递归。算法P调用另一个算法Q,而算法Q又调用算法P。

④递归与递推的区别

递归与递推的区别主要在于二者实现方法的不同，表现为：

a.递归是从算法本身到达递归的边界的；

b.递推是从初始条件出发，逐次推出所需求的结果。

（5）减半递推技术

减半递推技术是工程上常用的分治法，其中，“减半”指将问题的规模减

半，而问题的性质不变；“递推”指重复“减半”的过程。

（6）回溯法

回溯法是指通过对问题的分析，找出一个解决问题的线索，然后沿着这个

线索逐步试探，若试探成功，则问题得到解决，若试探失败，则逐步回退换别

的路线再进行试探。

【真题演练】

1.下列叙述中正确的是（）。［2013年9月真题］

A.所谓算法就是计算方法

B.程序可以作为算法的一种描述方法

C.算法设计只需考虑得到计算结果

D.算法设计可以忽略算法的运算时间

【答案】B

【解析】程序可以作为算法的一种描述方法,算法在实现时需要用具体的程

序设计语言描述。A项错误，算法并不等同于计算方法，是指对解题方案的准确

而完整的描述；C项错误，算法设计需要考虑可行性、确定性、有穷性与足够的

情报；D项错误，算法设计有穷性要求操作步骤有限且必须在有限时间内完成，

耗费太长时间得到的正确结果是没有意义的。

2.下列关于算法的描述中错误的是（）。［2014年3月真题］

A.算法强调动态的执行过程，不同于静态的计算公式

B.算法必须能在有限个步骤之后终止

C.算法设计必须考虑算法的复杂度

D.算法的优劣取决于运行算法程序的环境

［答案］D

【解析】算法是指对解题方案的准确而完整的描述。A项正确，算法强调实

现，不同于数学上的计算方法；B项正确，算法的有穷性是指，算法中的操作步

骤为有限个，且每个步骤都能在有限时间内完成；C项正确，算法设计必须考虑

执行算法所需要的资源，即时间复杂度与空间复杂度；D项错误，算法的优劣取

决于算法复杂度，只有当算法被编程实现运行时才会受到运行环境影响。

考点3算法复杂度

（1）时间复杂度

①定义

算法的时间复杂度是指执行算法所需要的计算工作量。

算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本

运算次数是问题规模的函数，即

算法的工作量=f（n）

其中，n是问题的规模。

②在同一问题规模下，若算法的基本运算次数取决于某一特定输入，可用

以下两种方法来分析算法的工作量：

a.平均性态

平均性态分析是指用各种特定输入下的基本运算次数的加权平均值来度量

算法的工作量。算法的平均性态定义为：

其中，x是所有可能输入中的某个特定输入，p（x）是x出现的概率，即输

入为x的概率，t（x）是算法在输入为x时所执行的基本运算次数，D”表示当规

模为n时，算法执行时所有可能输入的集合。

b.最坏情况复杂性

最坏情况分析是指规模为n时，算法所执行的基本运算的最大次数。其定

义为：

（2）空间复杂度

①定义

算法的空间复杂度一般是指执行这个算法所需要的内存空间。

②存储空间组成

一个算法的存储空间包括以下几种：

a.算法程序占用的空间；

b.输入的初始数据占用的存储空间；

c.算法执行过程中所需要的额外空间。

额外空间包括算法程序执行过程中的工作单元以及某种数据结构所需要的

附加存储空间，若额外空间相对于问题规模来说是常数，则称该算法是原地工

作的。

【真题演练】

1.下列叙述中正确的是（）。［2015年3月真题］

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

B.算法的时间复杂度是指执行算法所需要的计算工作量

C.数据的逻辑结构与存储结构是一一对应的

D.算法的时间复杂度与空间复杂度一定相关

［答案］B

【品析•】算法的时间复杂度是指算法在计算机内执行时所需时间的度量；

与时间复杂度类似，空间复杂度是指算法在计算机内执行时所需存储空间的度

量。

2.算法的空间复杂度是指（）。［2013年9月真题］

A.算法在执行过程中所需要的计算机存储空间

B.算法所处理的数据量

C.算法程序中的语句或指令条数

D.算法在执行过程中所需要的临时工作单元数

【答案】A

【解析】空间复杂度是是对一个算法在运行过程中临时占用存储空间大小

的量度。

3.算法空间复杂度的度量方法是()。［2014年9月真题］

A.算法程序的长度

B.算法所处理的数据量

C.执行算法所需要的工作单元

D.执行算法所需要的存储空间

【答案】D

【解析】算法的空间复杂度包括：①输入数据所占的存储空间；②程序本

身所占的存储空间；③算法执行过程中所需要的额外空间，是指执行这个算法

所需要的内存空间，

1.2数据结构的基本概念

考点1概述

(1)数据处理概述

①定义

数据处理是指对数据集合中的各元素以各种方式进行运算，包括插入、删

除、查找、更改等运算，也包括对数据元素进行分析。

②关键问题

大量数据元素在计算机中如何组织，以便提高数据处理的效率，从而节省

计算机的存储空间，这是进行数据结构处理的关键问题。

(2)数据结构研究概述

①研究问题

a.数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；

b.在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存

储结构；

c.对各种数据结构进行的运算。

②研究目的

数据结构研究和讨论上述3个问题的主要目的在于提高数据处理效率，包

括：a.提高数据处理的速度；b,尽量节省在数据处理过程中所占用的计算机

存储空间。

考点2数据结构的概念

(1)数据结构的定义

数据结构是指相互有关联的数据元素的集合，即它是反映数据元素之间关

系的数据元素集合的表示。简言之，数据结构是指带有结构的数据元素的集合,

这里的“结构”指数据元素之间的前后件关系。一个数据结构应包含以下两方

面内容：

①表述数据元素的信息；

②表示各数据元素之间的前后件关系。

(2)数据的逻辑结构

①定义

数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。

②要素：

a.数据元素的集合，通常记为D；

b.D上的关系，通常记为R,它反映了D中各数据元素之间的前后件关系。

③表示

一个数据结构B可表示为：

B=（D,R）

为反映D中个数据元素之间的前后件关系，一般用二元组来表示。

（3）数据的存储结构

①定义

数据的存储结构，也称数据的物理结构，是指数据逻辑结构在计算机存储

空间中的存放形式。在数据的存储结构中，不仅要存放各数据元素的信息，而

且要存放各数据元素之间的前后件信息。

②常用的存储结构：a.顺序；b.链接；c.索引。

采用不同的存储结构，数据处理的效率是不同的。

【真题演练】

下列叙述中正确的是（）。［2014年3月真题］

A.有且只有一个根结点的数据结构一定是线性结构

B.每一个结点最多有一个前件也最多有一个后件的数据结构一定是线性结

构

C.有且只有一个根结点的数据结构一定是非线性结构

D.有且只有一个根结点的数据结构可能是线性结构，也可能是非线性结构

［答案］D

【前析】逻辑结构分为线性结构和非线性结构，线性结构的特征有：①集

合中必存在唯一的一个“第一个元素”；②集合中必存在唯一的一个“最后的

元素”；③除第一元素之外，其它数据元素均有唯一的“前驱”；④除最后元

素之外，其它数据元素均有唯一的“后继”。D项正确，如树形结构只有一个根

结点，为非线性结构。

考点3数据结构的图形表示

（1）在数据结构的图形表示中，数据集合D中每个元素用中间标有元素值

的方框表示，称为数据结点（简称结点）；对关系R中的每一个二元组，用一

条有向线段从前件结点指向后件结点。

（2）在数据结构中，没有前件的结点称为根结点，没有后件的结点称为终

端结点（也称叶子结点），其余结点都称为内部结点。

（3）数据结构中的元素结点可能是在动态变化的，这种变化体现在结点数

量的增减以及各结点之间的前后件关系的动态变化上。

考点4线性结构与非线性结构

根据数据结构中各数据元素之间的前后件关系的复杂程度，可将数据结构

分为：

（1）线性结构（线性表）

一个非空的数据结构满足下列两个条件时.，称其为线性结构：

①有且只有一个根结占,

②每个结点最多只有二个前件，也最多只有一个后件。

线性结构中插入或删除任何一个结点还应是线性结构，如果不满足这个条

件就不能称之为线性结构。

(2)非线性结构

如果一个数据结构不是线性结构，则称之为非线性结构。

注：线性结构与非线性结构都可以是空的数据结构。一个空的数据结构属

于线性结构还是非线性结构，需要根据对该数据结构的运算是否按照线性结构

的规则来处理进行判断。

1.3线性表及其顺序存储结构

考点1线性表的基本概念

(1)线性表是一种最常见最简单的数据结构，由一组数据元素构成。数据

元素在线性表中的位置值只取决于它们自己的序号，即数据元素之间的相对位

置是线性的。

(2)非空线性表的结构特征：

①有且只有一个根结点a.,它无前件；

②有且只有一个终端结点4,它无后件；

③除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有

一个后件。

线性表中结点的个数n称为线性表的长度。当n=0时，称为空表。

【真题演练】

下列叙述中正确的是()。［2014年9月真题］

A.结点中具有两个指针域的链表一定是二叉链表

B.结点中具有两个指针域的链表可以是线性结构，也可以是非线性结构

C.二叉树只能采用链式存储结构

D.循环链表是非线性结构

【答案】B

【解析】A项错误，具有两个指针域的链表可能是双向链表；B项正确，如

双向链表是线性结构，二叉树为非线性结构，两者结点中均有两个指针域；C项

错误，二叉树通常采用链式存储结构，也可采用其他结构；D项错误，循环链表

是线性结构，逻辑概念线性非线性与实际存储结构无关。

考点2线性表的顺序存储结构

(1)概述

顺序存储是一种最简单的在计算机中存放线性表的方法，也称顺序分配。

(2)特点：

①线性算中所有元素所占的存储空间是连续的；

②线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。

在线性表的顺序存储结构中，其前后件两个元素在存储空间中是紧邻的，

且前件元素一定存储在后件元素的前面。

(3)运算

在线性表的顺序存储结构下，可对线性表进行以下运算：

①插入：在线性表的指定位置处加入一个新的元素；

②删除：在线性表中删除指定的元素；

③查找：在线性表中查找某个（或某些）特定的元素；

④排序：对线性表中的元素进行整序；

⑤分解：按要求将一个线性表分解成多个线性表；

⑥合并：按要求将多个线性表合并成一个线性表；

⑦复制：复制一个线性表；

⑧逆转：逆转一个线性表等。

【真题演练】

在线性表的顺序存储结构中，其存储空间连续，各个元素所占的字节数

（）。［2014年3月真题］

A.相同，元素的存储顺序与逻辑顺序一致

B.相同，但其元素的存储顺序可以与逻辑顺序不一致

C.不同，但元素的存储顺序与逻辑顺序一致

D.不同，且其元素的存储顺序可以与逻辑顺序不一致

【答案】A

【解析】在顺序表中，每个元素占有相同的存储单元。顺序表具有特征：

①线性表中所有元素所占的存储空间是连续的；②线性表中各数据元素在存储

空间中是按逻辑顺序依次存放的。

考点3顺序表的插入运算

假设线性表的存储空间为V（1：m）,线性表的长度为n（nWm）,插入的

位置为i（表示在第i个位置插入元素），则顺序表插入新元素过程如下：

（1）首先处理以下三种异常情况：

①当存储空间已满（即n=m）时为“上溢”错误，不能进行插入，算法结

束；

②当i>n时，认为在最后一个元素之后（即第n+1个元素之前）插入；

③当i<l时，认为在第1个元素之前插入。

（2）从最后一个元素开始，直到第i个元素，其中每一个元素均往后移动

一个位置。

（3）最后将新元素插入到第i个位置，并且将线性表的长度增加1。

考点4顺序表的删除运算

假设线性表的存储空间为V（1：m）,线性表的长度为n（nWm）,删除的

位置为i（表示删除第i个元素），则顺序表删除元素的过程如下：

（1）首先处理以下两种异常情况：

①当线性表为空（即n=0）时为“上溢”错误，不能进行插入，算法结束;

②当i<l或i>n时，认为在最后一个元素之后（即第n+1个元素之前）插

入。

（2）然后从第i+1个元素开始，直到最后一个元素，其中每一个元素均

依次往前移动一个位置。

（3）最后将线性表的长度减小lo

1.4栈和队列

考点1栈及其基本运算

（1）栈的定义

栈是限定在一端进行插入与删除的线性表。

（2）栈的特点：

①允许插入和删除的一端称为栈顶，不允许插入与删除的一端称为栈底。

栈顶元素总是最后被插入的元素，也是最先被删除的元素；栈底元素总是最先

被插入也是最后被删除的。

②栈遵循“先进后出”或“后进先出”的原则，具有记忆功能。

③通常用指针top来指示栈顶位置，用指针bottom指向栈底，栈顶指针top

动态反映了栈中元素的变化情况。

（3）栈的顺序存储及其运算

在栈的顺序存储空间S（l:m）中，top=0表示栈空；top=m表示栈满。

栈的三种运算：

①入栈运算

人栈运算是指在栈顶位置插入一个新元素。操作过程如下：

a.首先判断栈顶指针是否已经指向存储空间的最后一个位置。如果是，则

说明栈空间已满，不可能再进行入栈操作（这种情况称为栈“上溢”错误），

算法结束。

b.然后将栈顶指针进一（即top加1）。

c.最后将新元素x插入栈顶指针指向的位置。

②退栈运算

退栈运算是指取出栈顶元素并赋给一个指定的变量。操作过程如下：

a.首先判断栈顶指针是否为0。如果是，则说明栈空，不可能进行退栈操

作（这种情况称为栈“下溢”错误），算法结束。

b.然后将栈顶元素（栈顶指针指向的元素）赋给一个指定的变量。

c.最后将栈顶指针退一（即top减1）。

③读栈顶元素

读栈顶元素是指将栈顶元素赋给一个指定的变量。操作过程如下：

a.首先判断栈顶指针是否为0。如果是，则说明栈空，读不到栈顶元素，

算法结束。

b.然后将栈顶元素赋给指定的变量y。

这个运算不删除栈顶元素，只是将它的值赋给一个变量，栈顶指针不会变。

【真题演练】

1.支持子程序调用的数据结构是（）。［2013年9月真题］

A.栈

B.树

C.队列

D.二叉树

【答案】A

【解析】栈和队列都是受限的线性表，其中栈按照“先进后出”的原则组

织数据，插入与删除操作被限制在栈顶一端进行。栈支持子程序调用，在主程

序调用子函数时，要首先保存主程序当前的状态，然后转去执行子程序，结束

调用后返回到主程序中调用子程序的位置，继续执行，这种调用符合栈的特点。

2.下列与栈结构有关联的是（）。［2013年3月真题］

A.数组的定义域使用

B.操作系统的进程调度

C.函数的递归调用

D.选择结构的执行

【答案】C

【解析】递归调用的本质就是函数调用函数本身，直到满足特定条件时才停

止，然后从最后被递归调用处返回。递归函数是通过栈来实现的，所以调用原

则和栈的实现相一致。

3.设栈的顺序存储空间为S（1：50）,初始状态为top=0。现经过一系列

入栈与退栈运算后，top=20,则当前栈中的元素个数为（）。［2014年3月

真题］

A.30

B.29

C.20

D.19

【答案】c

【解析】栈按照“先进后出”的原则组织数据，插入与删除操作被限制在

栈顶一端进行，入栈使栈顶位置进1,退栈使栈顶退1。top=0表示栈为空，在

运算过程中，指针始终指向栈顶元素。top=20,说明当前栈中有20个元素。

4.一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次

入栈，然后再依次出栈，则元素出栈的顺序是（）。［2013年9月真题］

A.12345ABCDE

B.EDCBA54321

C.ABCDE12345

D.54321FDCBA

【答案】B

【解后】栈中数据的插入和删除都在栈顶按照“先进后出”的原则进行操

作。

考点2队列及其基本运算

（1）什么是队列

队列（Queue）是指允许在一端进行插入、而在另一端进行删除的线性表。

（2）队列的特点

①允许插入的一端称为队尾，用队尾指针指向队尾元素；允许删除的一端

称为队头，用排头指针指向排头元素的前一个位置。

②最先插入的元素最先被删除，最后插入的元素最后被删除，遵循“先进

先出”或“后进后出”原则。

③队尾指针rear和排头指针front共同反映队列中元素变动情况。

④入队运算指只涉及队尾指针rear变化，退队运算只涉及排头指针front

变化。

（3）循环队列及其运算

循环队列是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上

的环状空间，供队列循环使用。在循环队列中，用队尾指针rear指向队尾元素,

用排头指针front指向排头元素的前一个位置，从排头指针front指向的后一

个位置到队尾指针rear指向的位置均是队列中元素。队列空的条件是s=0；队

列满的条件是s=l且front=rearo

队列的两种运算

假设循环队列的初始状态为空，即：s=0,且front=rear=m。

①入队运算

入队运算是指在循环队列的队尾加入一个新元素。操作过程如下：

a.首先判断循环队列是否满。当循环队列非空（S=l）且队尾指针等于排

头指针时，说明循环队列已满，不能进行入队运算。这种情况称为“上溢”。

此时算法结束。

b.然后将队尾指针进一（即rear=rear+l）,并当rear=m+l时置rear

——1O

c.最后将新元素x插入队尾指针指向的位置，并且置循环队列非空标志。

②退队运算

退队运算是指在循环队列的排头位置退出一个元素并赋给指定的变量。操

作过程如下：

a.首先判断循环队列是否为空。当循环队列为空（s=0）时，不能进行退

队运算。这种情况称为“下溢”。此时算法结束。

b.然后将排头指针进一（即front=front+l）,并当front=m+l时置

front=lo

c.再将排头指针指向的元素赋给指定的变量。

d.最后判断退队后循环队列是否为空。当front=rear时置循环队列空标

志（即s=0）。

【真题演练】

1.下列叙述中正确的是（）。［2013年9月真题］

A.栈是“先进先出”的线性表

B.队列是“先进后出”的线性表

C.循环队列是非线性结构

D.有序线性表既可以采用顺序存储结构，也可以采用链式存储结构

【答案】D

【解析】栈和队列都是受限的线性表，其中栈按照“先进后出”的原则组织

数据，插入与删除操作被限制在栈顶一端进行；队列采用“先进先出”的原则

组织数据。循环队列是队列的一种特殊形式，是线性结构。

2.下列叙述中正确的是（）。［2014年3月真题］

A.循环队列是顺序存储结构

B.循环队列是链式存储结构

C.循环队列是非线性结构

D.循环队列的插入运算不会发生溢出现象

【答案】A

【解析】B项错误，循环队列是一种顺序存储结构的队列；C项错误，线性

结构是一个非空序列：除第一个元素外，每个元素，有且只有一个前件；除最

后一个元素外，每个元素有且只有一个后件，所以循环队列是线性结构；D项错

误，当循环队列的元素个数等于存储长度后，入队会发生溢出现象，覆盖前面

的数据。

3.对于循环队列，下列叙述中正确的是()。［2013年9月真题］

A.队头指针是固定不变的

B.队头指针一定大于队尾指针

C.队头指针一定小于队尾指针

D.队头指针可以大于队尾指针，也可以小于队尾指针

［答案］D

【力析】循环队列的队头指针与队尾指针都不是固定的，每次入队操作队

尾指针要加进1,每次出队操作队头指针要%m进1。因为存在如运算，所以队

头指针与队尾指针大小关系不确定。

4.下列叙述中正确的是()。［2013年9月真题］

A.循环队列有队头和队尾两个指针，因此，循环队列是非线性结构

B.在循环队列中，只需要队头指针就能反映队列中元索的动态变化情况

C.在循环队列中，只需要队尾指针就能反映队列中元素的动态变化情况

D.循环队列中元素的个数是由队头指针和队尾指针共同决定

［答案］D

【漏焦】在循环队列中元素的个数是由队头指针和队尾指针共同决定的，

入队使得队尾指针变化，出队使得队头指针变化。

1.5线性链表

考点1线性链表的基本概念

(1)线性表的顺序存储结构存在的缺陷：

①在插入或删除元素时，为保证操作后的线性表仍然是顺序存储，需要大

量移动数据元素，效率很低。

②在顺序存储结构下，线性表的存储空间不便于扩充，易产生上溢现象。

③线性表的顺序存储结构不便于对存储空间的动态分配。

(2)链式存储结点组成：

①数据域：用于存放数据元素值；

②指针域：用于存放指针。

指针用于指向该结点的前一个或后一个结点，存储数据结构的存储空间可

以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而

数据元素之间的逻辑关系是由指针域来确定的。

链式存储方式既可用于表示线性结构，也可用于表示非线性结构。在用链

式结构表示较复杂的非线性结构时，其指针域的个数要多一些。

(3)线性链表

①定义：线性链表是线性表的链式存储结构。

②特点

a.各数据结点的存储序号是不连续的，各结点在存储空间中的位置关系与

逻辑关系也不一致；

b.各数据元素之间的前后件关系是由各结点的指针域来指示的；

c.每一个结点只有一个指针域，由这个指针只能找到后件结点，不能找到

前件结点，只能顺指针向链尾进行扫描。

为了弥补线性单链表的缺陷，在某些应用中为线性链表每个结点设置两个

指针，左指针用以指向其前件结点，右指针指向其后件结点。

(4)带链的栈

带链的栈可以用来收集计算机存储空间中所有空闲的存储结点。

与顺序栈一样，带链栈的基本操作有以下几个：

①栈的初始化：建立一个空栈的顺序存储空间；

②入栈运算：在栈顶位置插入一个新元素；

③退栈运算：取出栈顶元素并赋给一个指定的变量；

④读栈顶元素：将栈顶元素赋给一个指定的变量。

(5)带链的队列

与顺序队列一样，带链队列的基本操作有以下几个：

①队列的初始化：建立一个空队列的顺序存储空间；

②入队运算：在循环队列的队尾加入一个新元素；

③退队运算：在循环队列的排头位置退出一个元素并赋给指定的变量。

【真题演练】

1.下列叙述中正确的是()。［2014年9月真题］

A.所谓有序表是指在顺序存储空间内连续存放的元素序列

B.有序表只能顺序存储在连续的存储空间内

C.有序表可以用链式存储方式存储在不连续的存储空间内

D.任何存储方式的有序表均能采用二分法进行查找

【答案】C

【解析】“有序”是指线性表中的元素按照升序或降序(允许相邻元素相同)

的方式排列。有序是一个逻辑概念，与物理存储无关。二分法查找时涉及下标

运算，要求有序表必须顺序存储。

2.线性表的链式存储结构与顺序存储结构相比，链式存储结构的优点有

()o［2014年9月真题］

A.节省存储空间

B.插入与删除运算效率高

C.便于查找

D.排序时减少元素的比较次数

【答案】B

【解析】线性表的链式存储结构与顺序存储结构的优缺点比较如下：

类型|优点|缺点

①插入和删除运算效率很低

①方便随机存取

顺序②存储空间不便于扩充

②无需额外的存储空间来表示

表③不便于对存储空间的动态分

结点间的逻辑关系

配

①在进行插入和删除操作时，只

需要改变指针需要额外的空间来表示数据元

链表

②链表的存储空间易于扩充，容素之间的逻辑关系，存储密度低

易实现空间的动态分配

3.下列叙述中正确的是()。［2013年9月真题］

A.顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是

连续的

B.顺序存储结构只针对线性结构，链式存储结构只针对非线性结构

C.顺序存储结构能存储有序表，链式存储结构不能存储有序表

D.链式存储结构比顺序存储结构节省存储空间

【答案】A

【蓝析】BC两项错误，逻辑概念上的线性非线性是否有序与存储结构为顺序

还是链式没有直接关系；D项错误，链式存储结构比顺序存储结构更耗费存储空

间，因为链式存储结构中除了要存储顺序结构中的数据外还要存储指针。

考点2线性链表的基本运算

(1)常见的线性表的运算

线性链表的运算主要有以下几个：

①在线性链表中包含指定元素的结点之前插入一个新元素；

②在线性链表中删除包含指定元素的结点；

③将两个线性链表按要求合并成一个线性链表；

④将一个线性链表按要求进行分解；

⑤逆转线性链表；

⑥复制线性链表；

⑦线性链表的排序；

⑧线性链表的查找。

(2)在线性链表中查找指定元素

非空线性链表中寻找包含指定元素值x的前一个结点p的基本方法：

从头指针指向的结点开始往后沿指针进行扫描，直到后面已没有结点或下

一个结点的数据域为x为止。因此，由这种方法找到的结点p有两种可能：当

线性链表中存在包含元素x的结点时，则找到的p为第一次遇到的包含元素x

的前一个结点序号；当线性链表中不存在包含元素x的结点时，则找到的p为

线性链表中的最后一个结点号。

(3)线性链表的插入

①定义：线性链表的插入是指在链式储存结构下的线性表中插入一个新元

素。

②插入过程：

在线性链表中包含元素x的结点之前插入一个新元素bo

a.从可利用栈取得一个结点，设该结点号为p,并置结点p的数据域为插

入的元素值b。b.在线性链表中寻找包含元素x的前一个结点，设该结点的

存储序号为q。

c.最后将结点p插入到结点q之后。为了实现这一步，只要改变以下两个

结点的指针域内容：

第一，使结点P指向包含元素x的结点；

第二，使结点q的指针域内容改为指向结点P。

③插入特点：

a.不会发生上溢现象；

b.可方便实现存储空间动态分配；

c.不发生数据元素移动现象，只改变结点指针，提高插入效率。

(