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

1、全国计算机等级考试二级C+语言程序设计专用教材【考纲分析+考点精讲+真题演练+强化习最新资料，WORD式，可编辑修改！目录第一部分公共基础知识第1章数据结构与算法考纲分析考点精讲1.1 算法1.2 数据结构的基本概念1.3 线性表及其顺序存储结构1.4 栈和队列1.5 线性链表1.6 树与二叉树1.7 查找技术1.8 排序技术强化习题第2章程序设计基础考纲分析考点精讲2.1 程序设计方法与风格2.2 结构化程序设计2.3 面向对象的程序设计强化习题第3章软件工程基础考纲分析考点精讲3.1 软件工程基本概念3.2 结构化分析方法3.3 结构化设计方法3.4 软件测试3.5 程序的调试强化习题第4

2、章数据库设计基础考纲分析考点精讲4.1 数据库系统的基本概念4.2 数据模型:4.3 关系代数4.4 数据库设计与管理强化习题第二部分C+谣言程序设计第1章C+铺言人述考纲分析考点精讲1.1 C+铺言的发展1.2 C+铺言的特点1.3 面向对象程序设计1.4 C+铺言的基本符号1.5 C+铺言的词汇1.6 C+®序的基本框架1.7 C+®序的开发过程强化习题第2章数据类型、运算符和表达式考纲分析考点精讲2.1 C+铺言的数据类型2.2 常量2.3 变量2.4 运算符和表达式强化习题第3章基本控制结构考纲分析考点精讲3.1 C+铺句3.2 顺序结构3.3 选择结构3.4 循环

3、结构3.5 跳转语句强化习题第4章数组、指专f与引用考纲分析考点精讲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.5 this指针6.6 静态成员6.7 常成员6.8 友元6.9 对象数组6.10 成员对象强化习题第7章继承和派生考纲分析考点精讲7.1 继承与派生7.2 派生类对

4、基类成员的访问7.3 派生类的构造函数和析构函数7.4 多继承与虚基类7.5 子类型关系7.6 虚函数与多态性强化习题第8章运算符重载考纲分析考点精讲8.1 运算符函数与运算符重载8.2 典型运算符的重载.二8.3 运算符重载应注意的几个问题强化习题第9章模板考纲分析考点精讲9.1 函数模板9.2 类模板强化习题第10章C+毓考纲分析考点精讲10.1 C+喻的用既念10.2 输入输出的格式控制10.3 文件流强化习题第一部分公共基础知识第1章数据结构与算法考纲分析1 .算法的基本概念，算法复杂度的概念和意义（时间复杂度与空间复杂度）2 .数据结构的定义，数据的逻辑结构与存储结构；数据结构的图形

5、表示；线性结构与非线性结构的概念。3 .线性表的定义，线性表的顺序存储结构及其插入与删除运算。4 .栈和队列的定义，栈和队列的顺序存储结构及其基本运算。5 .线性单链表、双向链表与循环链表的结构及其基本运算。6 .树的基本概念，二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。7 .顺序查找与二分法查找算法，基本排序算法（交换类排序，选择类排序,插入类排序）。考点精讲1.1 算法考点1算法的基本概念（1）算法的定义算法是指解题方案的准确而完整的描述，即算法是对特定问题求解步骤的一种描述。它是一组严谨定义运算顺序的规则，且每个规则都是明确有效的，此顺序将在有限的次数下终止。需要注意的是：算

6、法不等于程序，也不等于计算方法。（2）算法的基本特征可行性a.算法中的每一步骤都必须能够实现；b.算法执行的结果要能够达到预期的目的。确定性确定性是指算法中的每一个步骤都必须有明确的定义，不允许有模棱两可的解释，也不允许有多义性。有穷性有穷性是指算法必须能在有限的时间内做完，即必须能在执行有限个步骤之后终止，且必须有合理的执行时间。拥有足够的情报算法是否有效，取决于为算法所提供的情报是否足够。一般而言，当算法有足够的情报时，此算法有效，而当提供的情报不够时，算法可能无效。【真题演练】算法的有穷性是指（）。2013年9月真题A.算法程序的运行时间是有限的B.算法程序所处理的数据量是有限的C.算法

7、程序的长度是有限的D.算法只能被有限的用户使用【答案】A【解析】算法设计有穷性要求操作步骤有限且必须在有限时间内完成，耗费太长时间得到的正确结果是没有意义的。考点2算法设计基本方法(1)列举法基本思想根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。常用于解决“是否存在”或“有多少种可能”等类型的问题。主要特点算法比较简单，但列举情况较多时，算法工作量很大。注意事项例举算法时，通过对实际问题进行详细分析，将与问题有关的知识条理化、完备化、系统化，并从中找出规律，或对所有可能的情况进行分类，从而引出一些有用的信息，减少列举量。(2)归纳法基本思想通过列举少

8、量的特殊情况，经过分析，最后找出一般的关系。主要特点a.比列举法更能反映问题的本质，可解决列举量为无限的问题；b.可操作性低，不易归纳出一个具体数学模型；c.归纳得出的结论只是一种猜测，须对这种猜测加以必要的证明。(3)递推基本思想从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。主要特点a.初始条件或问题本身已给定，或通过对问题的分析化简得到；b.递推本质上属于归纳法，递推关系式往往是归纳的结果；c.数值型递推算法计算过程中必须注意数值计算的稳定性问题。(4)递归基本思想将复杂问题逐层分解，归结为一些简单的问题，将简单问题解决掉，再沿着原来分解的逆过程逐步进行综合。主要特点a.递归

9、的基础是归纳，对问题逐层分解的过程实际上并没有对问题进行求解；b.在可计算性理论和算法设计中占有重要地位；c.递归算法比递推算法清晰易读，结构简练；d.设计递归算法比递推算法容易，但是其执行效率较低。分类a.直接递归。一个算法P显式地调用自己。b.间接递归。算法P调用另一个算法Q,而算法Q又调用算法P。递归与递推的区别递归与递推的区别主要在于二者实现方法的不同，表现为：a.递归是从算法本身到达递归的边界的；b.递推是从初始条件出发，逐次推出所需求的结果。(5)减半递推技术减半递推技术是工程上常用的分治法，其中，“减半”指将问题的规模减半，而问题的性质不变；“递推”指重复“减半”的过程。(6)回

10、溯法回溯法是指通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索逐步试探，若试探成功，则问题得到解决，若试探失败，则逐步回退换别的路线再进行试探。【真题演练】1.下列叙述中正确的是()。2013年9月真题A.所谓算法就是计算方法B.程序可以作为算法的一种描述方法C.算法设计只需考虑得到计算结果D.算法设计可以忽略算法的运算时间【答案】B【解析】程序可以作为算法的一种描述方法，算法在实现时需要用具体的程序设计语言描述。A项错误，算法并不等同于计算方法，是指对解题方案的准确而完整的描述；C项错误，算法设计需要考虑可行性、确定性、有穷性与足够的情报；D项错误，算法设计有穷性要求操作步骤有限且

11、必须在有限时间内完成，耗费太长时间得到的正确结果是没有意义的。2.下列关于算法的描述中错误的是()。2014年3月真题A.算法强调动态的执行过程，不同于静态的计算公式B.算法必须能在有限个步骤之后终止C.算法设计必须考虑算法的复杂度D.算法的优劣取决于运行算法程序的环境【答案】D【解析】算法是指对解题方案的准确而完整的描述。A项正确，算法强调实现，不同于数学上的计算方法；B项正确，算法的有穷性是指，算法中的操作步骤为有限个，且每个步骤都能在有限时间内完成；C项正确，算法设计必须考虑执行算法所需要的资源，即时间复杂度与空间复杂度；D项错误，算法的优劣取决于算法复杂度，只有当算法被编程实现运行时才

12、会受到运行环境影响。考点3算法复杂度(1)时间复杂度定义算法的时间复杂度是指执行算法所需要的计算工作量。算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数，即算法的工作量=f(n)其中，n是问题的规模。在同一问题规模下，若算法的基本运算次数取决于某一特定输入，可用以下两种方法来分析算法的工作量：a.平均性态平均性态分析是指用各种特定输入下的基本运算次数的加权平均值来度量算法的工作量。算法的平均性态定义为：其中，x是所有可能输入中的某个特定输入，p(x)是x出现的概率，即输入为x的概率，t(x)是算法在输入为x时所执行的基本运算次数，D表示当规模为n时，算法

13、执行时所有可能输入的集合。b.最坏情况复杂性最坏情况分析是指规模为n时，算法所执行的基本运算的最大次数。其定义为：(2)空间复杂度定义算法的空间复杂度一般是指执行这个算法所需要的内存空间。存储空间组成一个算法的存储空间包括以下几种：a.算法程序占用的空间；b.输入的初始数据占用的存储空间；c.算法执行过程中所需要的额外空间。额外空间包括算法程序执行过程中的工作单元以及某种数据结构所需要的附加存储空间，若额外空间相对于问题规模来说是常数，则称该算法是原地工作的。【真题演练】1 .下列叙述中正确的是()。2015年3月真题A.算法的效率只与问题的规模有关，而与数据的存储结构无关B.算法的时间复杂度

14、是指执行算法所需要的计算工作量C.数据的逻辑结构与存储结构是一一对应的D.算法的时间复杂度与空间复杂度一定相关【答案】B【解析】算法的时间复杂度是指算法在计算机内执行时所需时间的度量；与时间复杂度类似，空间复杂度是指算法在计算机内执行时所需存储空间的度量。2 .算法的空间复杂度是指()。2013年9月真题A.算法在执行过程中所需要的计算机存储空间B.算法所处理的数据量C.算法程序中的语句或指令条数D.算法在执行过程中所需要的临时工作单元数【答案】A【解析】空间复杂度是是对一个算法在运行过程中临时占用存储空间大小的量度。3 .算法空间复杂度的度量方法是()。2014年9月真题A.算法程序的长度B

15、.算法所处理的数据量C.执行算法所需要的工作单元D.执行算法所需要的存储空间【答案】D【解析】算法的空间复杂度包括：输入数据所占的存储空间；程序本身所占的存储空间；算法执行过程中所需要的额外空间，是指执行这个算法所需要的内存空间，4 .2数据结构的基本概念考点1概述(1)数据处理概述定义数据处理是指对数据集合中的各元素以各种方式进行运算，包括插入、删除、查找、更改等运算，也包括对数据元素进行分析。关键问题大量数据元素在计算机中如何组织，以便提高数据处理的效率，从而节省计算机的存储空间，这是进行数据结构处理的关键问题。(2)数据结构研究概述研究问题a.数据集合中各数据元素之间所固有的逻辑关系，即

16、数据的逻辑结构；b.在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；c.对各种数据结构进行的运算。研究目的数据结构研究和讨论上述3个问题的主要目的在于提高数据处理效率，包括：a.提高数据处理的速度；b.尽量节省在数据处理过程中所占用的计算机存储空间。考点2数据结构的概念(1)数据结构的定义数据结构是指相互有关联的数据元素的集合，即它是反映数据元素之间关系的数据元素集合的表示。简言之，数据结构是指带有结构的数据元素的集合，这里的“结构”指数据元素之间的前后件关系。一个数据结构应包含以下两方面内容：表述数据元素的信息；表示各数据元素之间的前后件关系。(2)数据的逻辑结构定义数

17、据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。要素：a.数据元素的集合，通常记为D;b.D上的关系，通常记为R,它反映了D中各数据元素之间的前后件关系。表示一个数据结构B可表示为：B=(D,R)为反映D中个数据元素之间的前后件关系，一般用二元组来表示。(3)数据的存储结构定义数据的存储结构，也称数据的物理结构，是指数据逻辑结构在计算机存储空间中的存放形式。在数据的存储结构中，不仅要存放各数据元素的信息，而且要存放各数据元素之间的前后件信息。常用的存储结构：a.顺序；b.链接；c.索引。采用不同的存储结构，数据处理的效率是不同的。【真题演练】下列叙述中正确的是()。2014年3月真题A.有

18、且只有一个根结点的数据结构一定是线性结构B.每一个结点最多有一个前件也最多有一个后件的数据结构一定是线性结构C.有且只有一个根结点的数据结构一定是非线性结构D.有且只有一个根结点的数据结构可能是线性结构，也可能是非线性结构【答案】D【解析】逻辑结构分为线性结构和非线性结构，线性结构的特征有：集合中必存在唯一的一个“第一个元素”；集合中必存在唯一的一个“最后的元素”；除第一元素之外，其它数据元素均有唯一的“前驱”；除最后元素之外，其它数据元素均有唯一的“后继”。D项正确，如树形结构只有一个根结点，为非线性结构。考点3数据结构的图形表示(1)在数据结构的图形表示中，数据集合D中每个元素用中间标有元

19、素值的方框表示，称为数据结点(简称结点)；对关系R中的每一个二元组，用一条有向线段从前件结点指向后件结点。(2)在数据结构中，没有前件的结点称为根结点，没有后件的结点称为终端结点(也称叶子结点)，其余结点都称为内部结点。(3)数据结构中的元素结点可能是在动态变化的，这种变化体现在结点数量的增减以及各结点之间的前后件关系的动态变化上。考点4线性结构与非线性结构根据数据结构中各数据元素之间的前后件关系的复杂程度，可将数据结构分为：(1)线性结构(线性表)一个非空的数据结构满足下列两个条件时，称其为线性结构：有且只有一个根结点；每个结点最多只有一个前件，也最多只有一个后件。线性结构中插入或删除任何一

20、个结点还应是线性结构，如果不满足这个条件就不能称之为线性结构。(2)非线性结构如果一个数据结构不是线性结构，则称之为非线性结构。注：线性结构与非线性结构都可以是空的数据结构。一个空的数据结构属于线性结构还是非线性结构，需要根据对该数据结构的运算是否按照线性结构的规则来处理进行判断。1.3线性表及其顺序存储结构考点1线性表的基本概念(1)线性表是一种最常见最简单的数据结构，由一组数据元素构成。数据元素在线性表中的位置值只取决于它们自己的序号，即数据元素之间的相对位置是线性的。(2)非空线性表的结构特征：有且只有一个根结点ai,它无前件；有且只有一个终端结点an,它无后件；除根结点与终端结点外，其

21、他所有结点有且只有一个前件，也有且只有*个后件。线性表中结点的个数n称为线性表的长度。当n=0时，称为空表。【真题演练】下列叙述中正确的是()。2014年9月真题A.结点中具有两个指针域的链表一定是二叉链表B.结点中具有两个指针域的链表可以是线性结构，也可以是非线性结构C.二叉树只能采用链式存储结构D.循环链表是非线性结构【答案】B【解析】A项错误，具有两个指针域的链表可能是双向链表；B项正确，如双向链表是线性结构，二叉树为非线性结构，两者结点中均有两个指针域；C项错误，二叉树通常采用链式存储结构，也可采用其他结构；D项错误，循环链表是线性结构，逻辑概念线性非线性与实际存储结构无关。考点2线性

22、表的顺序存储结构(1)概述顺序存储是一种最简单的在计算机中存放线性表的方法，也称顺序分配。(2)特点：线性表中所有元素所占的存储空间是连续的；线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。在线性表的顺序存储结构中，其前后件两个元素在存储空间中是紧邻的，且前件元素一定存储在后件元素的前面。(3)运算在线性表的顺序存储结构下，可对线性表进行以下运算：插入：在线性表的指定位置处加入一个新的元素；删除：在线性表中删除指定的元素；查找：在线性表中查找某个(或某些)特定的元素；排序：对线性表中的元素进行整序；分解：按要求将一个线性表分解成多个线性表；合并：按要求将多个线性表合并成一个线性表；复制：

23、复制一个线性表；逆转：逆转一个线性表等。【真题演练】在线性表的顺序存储结构中，其存储空间连续，各个元素所占的字节数()02014年3月真题A.相同，元素的存储顺序与逻辑顺序一致B.相同，但其元素的存储顺序可以与逻辑顺序不一致C.不同，但元素的存储顺序与逻辑顺序一致D.不同，且其元素的存储顺序可以与逻辑顺序不一致【答案】A【解析】在顺序表中，每个元素占有相同的存储单元。顺序表具有特征：线性表中所有元素所占的存储空间是连续的；线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。考点3顺序表的插入运算假设线性表的存储空间为V(1:m),线性表的长度为n(n<mj),插入的位置为i(表示在第i

24、个位置插入元素)，则顺序表插入新元素过程如下：(1)首先处理以下三种异常情况：当存储空间已满(即n=m)时为“上溢”错误，不能进行插入，算法结束；当i>n时，认为在最后一个元素之后(即第n+1个元素之前)插入；当i<1时，认为在第1个元素之前插入。(2)从最后一个元素开始，直到第i个元素，其中每一个元素均往后移动一，个位置。(3)最后将新元素插入到第i个位置，并且将线性表的长度增加1。考点4顺序表的删除运算假设线性表的存储空间为V(1:m),线性表的长度为n(n&m),删除的位置为i(表示删除第i个元素)，则顺序表删除元素的过程如下：(1)首先处理以下两种异常情况：当线性表

25、为空(即n=0)时为“上溢”错误，不能进行插入，算法结束；当i<1或i>n时，认为在最后一个元素之后(即第n+1个元素之前)插入。(2)然后从第i+1个元素开始，直到最后一个元素，其中每一个元素均依次往前移动一个位置。(3)最后将线性表的长度减小1。1.4栈和队列考点1栈及其基本运算(1)栈的定义栈是限定在一端进行插入与删除的线性表。（2）栈的特点：允许插入和删除的一端称为栈顶，不允许插入与删除的一端称为栈底。栈顶元素总是最后被插入的元素，也是最先被删除的元素；栈底元素总是最先被插入也是最后被删除的。栈遵循“先进后出”或“后进先出”的原则，具有记忆功能。通常用指针top来指示栈顶位

26、置，用指针bottom指向栈底，栈顶指针top动态反映了栈中元素的变化情况。（3）栈的顺序存储及其运算在栈的顺序存储空间S（1:m）中，top=0表示栈空；top=m表示栈满。栈的三种运算：入栈运算人栈运算是指在栈顶位置插入一个新元素。操作过程如下：a.首先判断栈顶指针是否已经指向存储空间的最后一个位置。如果是，则说明栈空间已满，不可能再进行入栈操作（这种情况称为栈“上溢”错误），算法结束。b.然后将栈顶指针进一（即top加1）。c.最后将新元素x插入栈顶指针指向的位置。退栈运算退栈运算是指取出栈顶元素并赋给一个指定的变量。操作过程如下：a.首先判断栈顶指针是否为00如果是，则说明栈空，不可能

27、进行退栈操作（这种情况称为栈“下溢”错误），算法结束。b.然后将栈顶元素（栈顶指针指向的元素）赋给一个指定的变量。c.最后将栈顶指针退一（即top减1）。读栈顶元素读栈顶元素是指将栈顶元素赋给一个指定的变量。操作过程如下：a.首先判断栈顶指针是否为00如果是，则说明栈空，读不到栈顶元素，算法结束。b.然后将栈顶元素赋给指定的变量y。这个运算不删除栈顶元素，只是将它的值赋给一个变量，栈顶指针不会变。【真题演练】1.支持子程序调用的数据结构是（）。2013年9月真题A.栈B.树C.队列D.二叉树【答案】A【解析】栈和队列都是受限的线性表，其中栈按照“先进后出”的原则组织数据，插入与删除操作被限制在

28、栈顶一端进行。栈支持子程序调用，在主程序调用子函数时，要首先保存主程序当前的状态，然后转去执行子程序，结束调用后返回到主程序中调用子程序的位置，继续执行，这种调用符合栈的特点。2.下列与栈结构有关联的是()。2013年3月真题A.数组的定义域使用B.操作系统的进程调度C.函数的递归调用D.选择结构的执行【答案】C【解析】递归调用的本质就是函数调用函数本身，直到满足特定条件时才停止，然后从最后被递归调用处返回。递归函数是通过栈来实现的，所以调用原则和栈的实现相一致。3.设栈的顺序存储空间为S(1:50),初始状态为top=0。现经过一系列入栈与退栈运算后，top=20,则当前栈中的元素个数为()

29、。2014年3月真题A. 30B. 29C. 20D. 19【答案】C【解析】栈按照“先进后出”的原则组织数据，插入与删除操作被限制在栈顶一端进行，入栈使栈顶位置进1,退栈使栈顶退1。top=0表示栈为空，在运算过程中，指针始终指向栈顶元素。top=20,说明当前栈中有20个元素。4. 一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是()。2013年9月真题1 .12345ABCDE8 .EDCBA543219 .ABCDE1234510 54321FDCBA【答案】B【解析】栈中数据的插入和删除都在栈顶按照“先进后出”的原则进行

30、操作。考点2队列及其基本运算(1)什么是队列队列(Queued是指允许在一端进行插入、而在另一端进行删除的线性表。(2)队列的特点允许插入的一端称为队尾，用队尾指针指向队尾元素；允许删除的一端称为队头，用排头指针指向排头元素的前一个位置。最先插入的元素最先被删除，最后插入的元素最后被删除，遵循“先进先出”或“后进后出”原则。队尾指针rear和排头指针front共同反映队列中元素变动情况。入队运算指只涉及队尾指针rear变化，退队运算只涉及排头指针front变化。(3)循环队列及其运算循环队列是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。在循环队列中，用队尾

31、指针rear指向队尾元素，用排头指针front指向排头元素的前一个位置，从排头指针front指向的后一个位置到队尾指针rear指向的位置均是队列中元素。队列空的条件是s=0;队列满的条件是s=1且front=rear。队列的两种运算假设循环队列的初始状态为空，即：s=0,且front=rear=mi入队运算入队运算是指在循环队列的队尾加入一个新元素。操作过程如下：a.首先判断循环队列是否满。当循环队列非空（S=1）且队尾指针等于排头指针时，说明循环队列已满，不能进行入队运算。这种情况称为“上溢”。此时算法结束。b.然后将队尾指针进一（即rear=rear+1）,并当rear=mi+1时置rea

32、r=1oc.最后将新元素x插入队尾指针指向的位置，并且置循环队列非空标志。退队运算退队运算是指在循环队列的排头位置退出一个元素并赋给指定的变量。操作过程如下：a.首先判断循环队列是否为空。当循环队列为空（s=0）时，不能进行退队运算。这种情况称为“下溢”。此时算法结束。b.然后将排头指针进一（即front=front+1）,并当front=mi+1时置front=1。c.再将排头指针指向的元素赋给指定的变量。d.最后判断退队后循环队列是否为空。当front=rear时置循环队列空标志（即s=0）o【真题演练】11 下列叙述中正确的是（）。2013年9月真题A.栈是“先进先出”的线性表B.队列是

33、“先进后出”的线性表C.循环队列是非线性结构D.有序线性表既可以采用顺序存储结构，也可以采用链式存储结构【答案】D【解析】栈和队列都是受限的线性表，其中栈按照“先进后出”的原则组织数据，插入与删除操作被限制在栈顶一端进行；队列采用“先进先出”的原则组织数据。循环队列是队列的一种特殊形式，是线性结构。12 下列叙述中正确的是（）。2014年3月真题A.循环队列是顺序存储结构B.循环队列是链式存储结构C.循环队列是非线性结构D.循环队列的插入运算不会发生溢出现象【答案】A【解析】B项错误，循环队列是一种顺序存储结构的队列；C项错误，线性结构是一个非空序列：除第一个元素外，每个元素，有且只有一个前件

34、；除最后一个元素外，每个元素有且只有一个后件，所以循环队列是线性结构；D项错误，当循环队列的元素个数等于存储长度后，入队会发生溢出现象，覆盖前面的数据。13 对于循环队列，下列叙述中正确的是()。2013年9月真题A.队头指针是固定不变的B.队头指针一定大于队尾指针C.队头指针一定小于队尾指针D.队头指针可以大于队尾指针，也可以小于队尾指针【答案】D【解析】循环队列的队头指针与队尾指针都不是固定的，每次入队操作队尾指针要%ma1,每次出队操作队头指针要谜1。因为存在mg算，所以队头指针与队尾指针大小关系不确定。14 下列叙述中正确的是()。2013年9月真题A.循环队列有队头和队尾两个指针，因

35、此，循环队列是非线性结构B.在循环队列中，只需要队头指针就能反映队列中元索的动态变化情况C.在循环队列中，只需要队尾指针就能反映队列中元素的动态变化情况D.循环队列中元素的个数是由队头指针和队尾指针共同决定【答案】D【解析】在循环队列中元素的个数是由队头指针和队尾指针共同决定的，入队使得队尾指针变化，出队使得队头指针变化。1.5线性链表考点1线性链表的基本概念(1)线性表的顺序存储结构存在的缺陷：在插入或删除元素时，为保证操作后的线性表仍然是顺序存储，需要大量移动数据元素，效率很低。在顺序存储结构下，线性表的存储空间不便于扩充，易产生上溢现象。线性表的顺序存储结构不便于对存储空间的动态分配。(

36、2)链式存储结点组成：数据域：用于存放数据元素值；指针域：用于存放指针。指针用于指向该结点的前一个或后一个结点，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。链式存储方式既可用于表示线性结构，也可用于表示非线性结构。在用链式结构表示较复杂的非线性结构时，其指针域的个数要多一些。(3)线性链表定义：线性链表是线性表的链式存储结构。特点a.各数据结点的存储序号是不连续的，各结点在存储空间中的位置关系与逻辑关系也不一致；b.各数据元素之间的前后件关系是由各结点的指针域来指示的；c.每一个结点只有一个指针域，由这个

37、指针只能找到后件结点，不能找到前件结点，只能顺指针向链尾进行扫描。为了弥补线性单链表的缺陷，在某些应用中为线性链表每个结点设置两个指针，左指针用以指向其前件结点，右指针指向其后件结点。(4)带链的栈带链的栈可以用来收集计算机存储空间中所有空闲的存储结点。与顺序栈一样，带链栈的基本操作有以下几个：栈的初始化：建立一个空栈的顺序存储空间；入栈运算：在栈顶位置插入一个新元素；退栈运算：取出栈顶元素并赋给一个指定的变量；读栈顶元素：将栈顶元素赋给一个指定的变量。(5)带链的队列与顺序队列一样，带链队列的基本操作有以下几个：队列的初始化：建立一个空队列的顺序存储空间；入队运算：在循环队列的队尾加入一个新

38、元素；退队运算：在循环队列的排头位置退出一个元素并赋给指定的变量。【真题演练】1.下列叙述中正确的是()。2014年9月真题A.所谓有序表是指在顺序存储空间内连续存放的元素序列B.有序表只能顺序存储在连续的存储空间内C.有序表可以用链式存储方式存储在不连续的存储空间内D.任何存储方式的有序表均能采用二分法进行查找【答案】C【解析】“有序”是指线性表中的元素按照升序或降序(允许相邻元素相同)的方式排列。有序是一个逻辑概念，与物理存储无关。二分法查找时涉及下标运算，要求有序表必须顺序存储。2.线性表的链式存储结构与顺序存储结构相比，链式存储结构的优点有()。2014年9月真题A.节省存储空间B.插

39、入与删除运算效率高C.便于查找D.排序时减少元素的比较次数【答案】B【解析】线性表的链式存储结构与顺序存储结构的优缺点比较如下：优点缺点顺序表方便随机存取无需额外的存储空间来表示结点间的逻辑关系插入和删除运算效率很低存储空间不便于扩充不便于对存储空间的动态分配在进行插入和删除操作时，只需要改变指针链表的存储空间易于扩充，容易实现空间的动态分配需要额外的空间来表示数据元素之间的逻辑关系，存储密度低3.下列叙述中正确的是()。2013年9月真题A顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的B.顺序存储结构只针对线性结构，链式存储结构只针对非线性结构C.顺序存储结构能存储有序

40、表，链式存储结构不能存储有序表D.链式存储结构比顺序存储结构节省存储空间【答案】A【解析】BC两项错误，逻辑概念上的线性非线性是否有序与存储结构为顺序还是链式没有直接关系；D项错误，链式存储结构比顺序存储结构更耗费存储空间，因为链式存储结构中除了要存储顺序结构中的数据外还要存储指针。考点2线性链表的基本运算(1)常见的线性表的运算线性链表的运算主要有以下几个：在线性链表中包含指定元素的结点之前插入一个新元素；在线性链表中删除包含指定元素的结点；将两个线性链表按要求合并成一个线性链表；将一个线性链表按要求进行分解；逆转线性链表；复制线性链表；线性链表的排序；线性链表的查找。(2)在线性链表中查找

41、指定元素非空线性链表中寻找包含指定元素值x的前一个结点p的基本方法：从头指针指向的结点开始往后沿指针进行扫描，直到后面已没有结点或下一个结点的数据域为x为止。因此，由这种方法找到的结点p有两种可能：当线性链表中存在包含元素x的结点时，则找到的p为第一次遇到的包含元素x的前一个结点序号；当线性链表中不存在包含元素x的结点时，则找到的p为线性链表中的最后一个结点号。(3)线性链表的插入定义：线性链表的插入是指在链式储存结构下的线性表中插入一个新元素。插入过程：在线性链表中包含元素x的结点之前插入一个新元素boa.从可利用栈取得一个结点，设该结点号为p,并置结点p的数据域为插入的元素值bob.在线性

42、链表中寻找包含元素x的前一个结点，设该结点的存储序号为q。c.最后将结点p插入到结点q之后。为了实现这一步，只要改变以下两个结点的指针域内容：第一，使结点P指向包含元素x的结点；第二，使结点q的指针域内容改为指向结点p。插入特点：a.不会发生上溢现象；b.可方便实现存储空间动态分配；c.不发生数据元素移动现象，只改变结点指针，提高插入效率。(4)线性链表的删除定义：线性链表的删除是指在链式储存结构下的线性表中删除包含指定元素的结点。删除过程：在线性链表中删除包含元素x的结点。a.在线性链表中寻找包含元素x的前一个结点，设该结点序号为q;b.将结点q后的结点p从线性链表中删除，即让结点q的指针指

43、向包含元素x的结点p的指针指向的结点；c.将包含元素x的结点p送回可利用栈。在线性链表中删除一个元素后，不需要移动表的数据元素，只需改变被删除元素所在结点的前一个结点的指针域即可。考点3循环链表(1)与线性链表相比，循环链表具有的特点：在循环链表中增加了一个表头结点，其数据域为任意或者根据需要来设置，指针域指向线性表的第一个元素的结点。循环链表的头指针指向表头结点。循环链表中最后一个结点的指针域不是空，而是指向表头结点。即在循环链表中，所有结点的指针构成了一个环状链。(2)与线性单链表相比，循环链表具有两方面优点：在循环链表中，只要指出表中任何一个结点的位置，就可以从它出发访问到表中其他所有的

44、结点。而线性单链表做不到这一点。由于在循环链表中设置了一个表头结点，因此，在任何情况下循环链表中至少有一个结点存在，从而使空表与非空表的运算统一。循环链表的插入与删除运算要比一般单链表简单，不用考虑在空链表和在第一个结点前插入以及空链表的删除等特殊情况，从而实现了空表与非空表运算的统一。【真题演练】下列叙述中错误的是()。2014年3月真题A.在双向链表中，可以从任何一个结点开始直接遍历到所有结点B.在循环链表中，可以从任何一个结点开始直接遍历到所有结点C.在线性单链表中，可以从任何一个结点开始直接遍历到所有结点D.在二叉链表中，可以从根结点开始遍历到所有结点【答案】C【解析】C项错误，在线性

45、表的单链式存储结构中，从一个结点出发只能遍历到其后的节点，不能遍历其前的结点。A项正确，双向链表的结点包含前驱和后继的两个指针；B项正确，循环链表的最后一个结点的指针指向头结点；D项正确，二叉链表中所有的结点都是根结点的分支。1.6树与二叉树考点1树的基本概念(1)树是一种简单的非线性结构，在这种结构中，所有数据元素之间的关系具有明显的层次特性。在树的图形表示中，上端结点是前件，下端结点是后件。(2)在树结构中，每个结点只有一个前件(父结点)，没有前件的结点只有一个，称为树的根结点。每个结点都可以有多个后件(子结点)，没有后件的结点称为叶子结点。(3)一个结点拥有的后件个数称为i结点的度。某结

46、点的度为n,表示该结点有n个分支，每个分支指向一个后件，除根结点外，每个结点都有一个唯一的分支指向它。树中的结点数为树中所有结点的度之和再加1。(4)根结点在第1层，同一层上所有结点的所有子结点都在下一层，树的最大层次称为树的深度(5)在树中，叶子结点没有子树。(6)用树来表示算术表达式的原则：表达式中的每一个运算符在树中对应一个结点，称为运算符结点；运算符的每一个运算对象在树中为该运算符结点的子树(在树中的顺序为从左到右)；运算对象中的单变量均为叶子结点。在树中，叶子结点没有子树。【真题演练】1.下列数据结构中，属于非线性结构的是()。2013年3月真题A.循环队列B.带链队列C.二叉树D.

47、带链栈【答案】C【解析】线性结构要求有唯一的根结点和叶子结点，且除了根结点任何一个元素只有唯一的前件，除了叶子结点任何一个元素只有唯一的后件。二叉树的后继结点可能不唯一，属于非线性结构。2.某二叉树的中序序列为DCBAEFG后序序列为DCBGFEA则该二叉树的深度(根节点在第1层)为()。2015年3月真题A. 5B. 4C. 3D. 2【答案】B【解析】题干中二叉树的后序序列为DCBGFEAA为根节点。中序序列为DCBAEFG可知DCB为左子树节点，EFG为右子树节点。同理B为C父节点，C为D父节点。根据分析，可画出左子树，同理E为F根节点，F为G根节点。根据分析，可画出右子树，观察得，树的

48、深度为4,故二叉树深度为4层。考点2二叉树及其基本性质(1)二叉树定义二叉树是一种很有用的非线性结构，与树结构很相似，树结构的所有术语都可以用到叉树这种数据结构上。(2)二叉树的两个特点非空二叉树只有一个根结点；每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。(3)二叉树的基本性质在二叉树的第k层上，最多有2k-1(k>1)个结点。深度为m的二叉树最多有2m-1个结点。在任意一棵二叉树中，度为0的结点(即叶子结点)总是比度为2的结点多一个。具有n个结点的二叉树，其深度至少为log2n十1,其中log2n表示取log2n的整数部分。(4)满二叉树与完全二叉树满二叉树与完全二叉树

49、是两种特殊形态的二叉树。满二叉树除最后一层外，每一层上的所有结点都有两个子结点。完全二叉树a.除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。b.更确切地说，如果从根结点起，对二叉树的结点自上而下、自左至右用自然数进行连续编号，则深度为m且有n个结点的二叉树，当且仅当其每一个结点都与深度为m的满二叉树中编号从1到n的结点一一对应时，称之为完全二叉树。对于完全二叉树来说，叶子结点只可能在层次最大的两层上出现；对于任何一个结点，若其右分支下的子孙结点的最大层次为P,则其左分支下的子孙结点的最大层次或为P,或为p+1oc.满二叉树也是完全二叉树，而完全二叉树一般不是满二

50、叉树。完全二叉树具有以下两个性质：a.具有n个结点的完全二叉树的深度为log2n+1。b.设完全二叉树共有n个结点。如果从根结点开始，按层序(每一层从左到右)用自然数1,2,，n给结点进行编号，则对于编号为k(k=1,2,n)的结点有以下结论：第一，若k=1,则该结点为根结点，它没有父结点；若k>1,则该结点的父结点编号为INT（k/2）。第二，若2k<n,则编号为k的结点的左子结点编号为2k;否则该结点无左子结点（显然也没有右子结点）。第三，若2k+1<n,则编号为k的结点的右子结点编号为2k+1;否则该结点无右子结点。根据完全二叉树的这个性质，如果按从上到下、从左到右顺序

51、存储完全二叉树的各结点，则很容易确定每一个结点的父结点、左子结点和右子结点的位置。【真题演练】1 .某二叉树共有13个结点，其中有4个度为1的结点，则叶子结点数为（）o2014年3月真题A. 5B. 4C. 3D. 2【答案】A【解析】对任何一棵二叉树来说，度为0的节点，即叶子节点，总是比度为2的节点多一个。所以可设叶子节点个数为n,则度为2的节点个数为n-1,13=n+4+n-1,得n=5。2 .某二叉树中有15个度为1的结点，16个度为2的结点，则该二叉树中总的结点数为（）。2014年9月真题A. 32B. 46C. 48D. 49【答案】C【解析】在树结构中，一个结点所拥有的后继个数称为

52、该结点的度。由二叉树的基本性质可得，对于任何的二叉树，叶子结点总是比度为2的结点多一个。因为度为2的结点有16个，所以叶子结点个数为17,因此结点总数为16+17+15=48o3 .某二叉树中共有935个结点，其中叶子结点有435个，则该二叉树中度为2的结点个数为（）。2014年3月真题A. 64B. 66C. 436D. 434【答案】D【解析】在树结构中，一个结点所拥有的后件个数称为该结点的度。对于任何一棵二叉树来说，度为0的结点总是比度为2的结点多一个。叶子结点有435个，则度为2的结点为434。4 .深度为7的完全二叉树中共有125个结点，则该完全二叉树中的叶子结点数为()。2014年

53、9月真题A. 62B. 63C. 64D. 65【答案】B【解析】定义一棵树的根结点所在的层次为1,其他结点所在的层次等于它的父结点所在的层次加1,树的最大层次称为树的深度。完全二叉树指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。本题中，前6层是满二叉树，结点个数为26-1=63,所以第7层有125-63=62个叶子结点，分别挂在第6层的左边62个结点上，所以第6层的最后1个结点为叶子结点，该完全二叉树共有62+1=63个叶子结点。考点3二叉树的存储结构(1)在计算机中，二叉树采用链式存储结构。(2)用于存储二叉树中各元素的存储结点由两部分组成：数据域指针域a

54、.左指针：用于指向该结点的左子结点的存储地址；b.右指针：指向该结点的右指结点的存储地址。【真题演练】下列叙述中正确的是()。2014年9月真题A.结点中具有两个指针域的链表一定是二叉链表B.结点中具有两个指针域的链表可以是线性结构，也可以是非线性结构C.二叉树只能采用链式存储结构D.循环链表是非线性结构【答案】B【解析】A项错误，具有两个指针域的链表可能是双向链表；B项正确，如双向链表是线性结构，二叉树为非线性结构，两者结点中均有两个指针域；C项错误，二叉树通常采用链式存储结构，也可采用其他结构；D项错误，循环链表是线性结构，逻辑概念线性非线性与实际存储结构无关。考点4二叉树的遍历二叉树的遍历是指不重复地访问二叉树中的所有结点。在遍历二叉树结点中遵循先左后右的原则。二叉树的遍历可分为三种：(1)前序遍历(DLR)在访问根结点、遍历左子树与遍历右子树这三者中，首先访问根结点，然后遍历左子树，最后遍历右子树；并且，在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。该过程是一个递归的过程。(2)中序遍历(LDR)在访问根结点、遍历左子树与遍