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

目录第卷分公共亶出知识6第1章 数据结构与算法6皿分析6考点修井61.1 算法61.2 数据结构的基本概念121.3 线性表及其顺序存储结构141.4 栈和队列171.5 线性链表221.6 树与二叉树271.7 查找技术341.8 排序技术35强化习题39第2章 不辨设计基础44考纲分析44考点播井442.1 程序设计方法与风格442.2 结构彳储序设计462.3 面向对象的出削48强化习题54第3章 软件工程基础58考纲分析58考点播井583.1 软件工程基本峥583.2 结构化分析方法653.3 结构化设计方法713.4 软件测试823.5 程序的调试92强化习题95第4章 数据库设计基础100考纲分析100考点播井1004.1 数据库系统的基本概念1004.2 数据模型1104.3 关系代数1204.4 蝇库蚓与W3127强化习题134第二部分C + +语言程序蜘139第1章C+语言概述139考纲分析139考点篙井1394.5 C+语言的发展1394.6 C+语言的特点1404.7 面向对象程序蚓1414.8 C+语言的基本符号1424.9 C+语言的词汇1434.10 C+程序的基本框架1454.11 C+程序的开发过程146强化习题148第2章 数据类型、运算符和表达式150匏分析150考点mi井1504.12 C+语言的数据类型1504.13 常量1534.14 变量1564.15 算符和表达式160强化习题167第3章 基本控制结构169匏分析169考点播井1694.16 C+语句1694.17 序结构1694.18 择结构1734.19 环结构1764.20 转语句180强化习题182第4章 数组、指针与引用185皿分析185考点mi井1854.21 数组1854.22 指针1894.23 弓 | 用1924.24 态存储分配193强化习题194第5章函数197考纲分析197考点mi井1975.1 函级义1975.2 函数调用1985.3 函雕型1995.4 函搬回类型1995.5 函数参数2015.6 函数重载2025.7 内联函数2035.8 递归函数2035.9 变量的生存周期203强化习题204第6章 类和对象207考纲分析207考点播井2076.1 类的定义2076.2 对象的定义2126.3 构造函数和析构函数2126.4 自由存储又搀2176.5 this 指针2176.6 静态成员2196.7 常成员2216.8 友元2236.9 对象数组2256.10 成员四225强化习题225第7章 继翦口派生232考纲分析232考点播井2327.1 继承与派生2327.2 派生类对基类成员的访问2347.3 派生类的构造函数和析构函数2367.4 多继承与虚基类2397.5 子类型关系2417.6 虚函数与多态性242强化习题246第8章运算符重载252匏分析252考点mi井2528.1 运算符函数与运算符重载2528.2 典型运算符的重载2538.3 运算符重载应注意的几个问题259强化习题261第9章模板265粗分析265考点播井2659.1 函数模板2659.2 类模板266强化习题268第10章 C + +流272物分析272考点mi井27210.1 C+流的概念27210.2 输入输出的格式控制27610.3 文件流282强化习题287第一部分公共基础知识 第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又调用算法Po递归与递推的区别递归与递推的区别主要在于二者实现方法的不同，表现为：a.递归是从算法本身到达递归的边界的；b.递推是从初始条件出发，逐次推出所需求的结果。(5)减半递推技术减半递推技术是工程上常用的分治法，其中，"减半"指将问题的规模减半, 而问题的性质不变；"递推"指重复"减半”的过程。（6）回溯法回溯法是指通过对问题的分析，找出一个解决问题的线索，然后沿着这个线 索逐步试探，若试探成功,则问题得到解决，若试探失败，则逐步回退换别的路 线再进行试探。【真题演练】1 .下列叙述中正确的是（）.2013年9月真题A.所谓算法就是计算方法B.程序可以作为算法的一种描述方法C.算法设计只需考虑得到计算结果D.算法设计可以忽略算法的运算时间【答案】B【解析】程序可以作为算法的一种描述方法，算法在实现时需要用具体的程序 设计语言描述。A项错误，算法并不等同于计算方法，是指对解题方案的准确而 完整的描述；C项错误，算法设计需要考虑可行性、确定性、有穷性与足够的情 报；D项错误，算法设计有穷性要求操作步骤有限且必须在有限时间内完成，耗 费太长时间得到的正确结果是没有意义的。2 .下列关于算法的描述中错误的是（）o 2014年3月真题A.算法强调动态的执行过程，不同于静态的计算公式B.算法必须能在有限个步骤之后终止C.算法设计必须考虑算法的复杂度D.算法的优劣取决于运行算法程序的环境【答案】D【解析】算法是指对解题方案的准确而完整的描述。A项正确，算法强调实 现，不同于数学上的计算方法；B项正确，算法的有穷性是指，算法中的操作步骤 为有限个，且每个步骤都能在有限时间内完成；C项正确，算法设计必须考虑执 行算法所需要的资源，即时间复杂度与空间复杂度；D项错误，算法的优劣取决 于算法复杂度，只有当算法被编程实现运行时才会受到运行环境影响。考点3算法复杂度(1)时间复杂度定义算法的时间复杂度是指执行算法所需要的计算工作量。算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运 算次数是问题规模的函数，即算法的工作量= f(n)其中，n是问题的规模。在同一问题规模下，若算法的基本运算次数取决于某一特定输入，可用以 下两种方法来分析算法的工作量：a.平均性态平均性态分析是指用各种特定输入下的基本运算次数的加权平均值来度量算 法的工作量。算法的平均性态定义为：A(n) = £ p(x)t(x)xeD其中，X是所有可能输入中的某个特定输入，P ( X )是X出现的概率，即输 入为X的概率,t(x)是算法在输入为X时所执行的基本运算次数，Dn表示当规 模为n时，算法执行时所有可能输入的集合。b.最坏情况复杂性最坏情况分析是指规模为n时，算法所执行的基本运算的最大次数。其定义 为：W(n) = maxt(x)(2 )空间复杂度定义算法的空间复杂度一般是指执行这个算法所需要的内存空间。存储空间组成一个算法的存储空间包括以下几种：a.算法程序占用的空间；b.输入的初始数据占用的存储空间；c .算法执行过程中所需要的额外空间。额外空间包括算法程序执行过程中的工作单元以及某种数据结构所需要的附 加存储空间，若额外空间相对于问题规模来说是常数，则称该算法是原地工作的。【真题演练】1 .下列叙述中正确的是（）.2015年3月真题A.算法的效率只与问题的规模有关，而与数据的存储结构无关B,算法的时间复杂度是指执行算法所需要的计算工作量C.数据的逻辑结构与存储结构是对应的D.算法的时间复杂度与空间复杂度一定相关【答案】B【解析】算法的时间复杂度是指算法在计算机内执行时所需时间的度量；与 时间复杂度类似，空间复杂度是指算法在计算机内执行时所需存储空间的度量。2 .算法的空间复杂度是指（）0 2013年9月真题A.算法在执行过程中所需要的计算机存储空间8 .算法所处理的数据量C.算法程序中的语句或指令条数D.算法在执行过程中所需要的临时工作单元数【答案】A【解析】空间复杂度是是对一个算法在运行过程中临时占用存储空间大小的 量度。3 .算法空间复杂度的度量方法是（）。2014年9月真题A.算法程序的长度1.1 法所处理的数据量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中个数据元素之间的前后件关系，T殳用二元组来表示。(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)非空线性表的结构特征：有且只有一个根结点ai,它无前件；有且只有一个终端结点an,它无后件；除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一 个后件。线性表中结点的个数n称为线性表的长度。当n = 0时，称为空表。【真题演练】下列叙述中正确的是().2014年9月真题A.结点中具有两个指针域的链表一定是二叉链表B.结点中具有两个指针域的链表可以是线性结构,也可以是非线性结构C.二叉树只能采用链式存储结构D.循环链表是非线性结构【答案】B【解析】A项错误，具有两个指针域的链表可能是双向链表；B项正确，如双 向链表是线性结构，二叉树为非线性结构，两者结点中均有两个指针域；C项错 误，二叉树通常采用链式存储结构，也可采用其他结构；D项错误，循环链表是 线性结构，逻辑概念线性非线性与实际存储结构无关。考点2线性表的顺序存储结构(1)概述顺序存储是一种最简单的在计算机中存放线性表的方法，也称顺序分配。(2)特点：线性表中所有元素所占的存储空间是连续的；线性表中各数据元素在存储空间中是按逻辑JI顺序依次存放的。在线性表的顺序存储结构中，其前后件两个元素在存储空间中是紧邻的，且 前件元素一定存储在后件元素的前面。(3)运算在线性表的顺序存储结构下，可对线性表进行以下运算：插入：在线性表的指定位置处加入一个新的元素；删除：在线性表中删除指定的元素；查找：在线性表中查找某个(或某些)特定的元素；排序：对线性表中的元素进行整序；分解：按要求将一个线性表分解成多个线性表；合并：按要求将多个线性表合并成一个线性表;复制：复制一个线性表；逆转：逆转一个线性表等。【真题演练】在线性表的顺序存储结构中，其存储空间连续，各个元素所占的字节数().2014年3月真题A .相同，元素的存储JI喷序与逻辑顺序一致B.相同，但其元素的存储顺序可以与逻辑顺序不一致C.不同，但元素的存储顺序与逻辑顺序一致D.不同，且其元素的存储顺序可以与逻辑顺序不一致【答案】A【解析】在)顺序表中，每个元素占有相同的存储单元。顺序表具有特征： 线性表中所有元素所占的存储空间是连续的；线性表中各数据元素在存储空间 中是按逻辑顺序依次存放的。考点3顺序表的插入运算假设线性表的存储空间为V(l:m),线性表的长度为n(n<m),插入的 位置为i(表示在第i个位置插入元素)，则顺序表插入新元素过程如下：(1)首先处理以下三种异常情况：当存储空间已满(即n = m )时为“上溢”错误，不能进行插入，算法结束;当i>n时，认为在最后一个元素之后(即第n +1个元素之前)插入；当i<l时，认为在第1个元素之前插入。(2 )从最后一个元素开始，直到第i个元素，其中每一个元素均往后移动一 个位置。(3 )最后将新元素插入到第i个位置，并且将线性表的长度增加lo考点4顺序表的删除运算假设线性表的存储空间为V(l:m),线性表的长度为n(n<m),删除的 位置为i(表示删除第i个元素)，贝”I圆序表删除元素的过程如下：(1)首先处理以下两种异常情况：当线性表为空(即n = 0 )时为“上溢”错误，不能进行插入，算法结束; 当i<l或i>n时，认为在最后一个元素之后(即第n +1个元素之前)插入。(2 )然后从第i + 1个元素开始，直到最后一个元素，其中每一个元素均依 次往前移动一个位置。(3 )最后将线性表的长度减小1.1.4栈和队列考点1栈及其基本运算(1)栈的定义栈是限定在一端进行插入与删除的线性表。(2 )栈的特点：允许插入和删除的一端称为栈顶，不允许插入与删除的一端称为栈底。栈 顶元素总是最后被插入的元素，也是最先被删除的元素；栈底元素总是最先被插 入也是最后被删除的。栈遵循"先进后出"或"后进先出"的原则，具有记忆功能。通常用指针top来指示栈顶位置，用指针bottom指向栈底，栈顶指针top 动态反映了栈中元素的变化情况。(3)栈的顺序存储及其运算在栈的M页序存储空间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 .下列与栈结构有关联的是（）0 2013年3月真题A.数组的定义域使用B.操作系统的进程调度C.函数的递归调用D.选择结构的执行【答案】C【解析】递归调用的本质就是函数调用函数本身，直到满足特定条件时才停止, 然后从最后被递归调用处返回。递归函数是通过栈来实现的，所以调用原则和栈 的实现相一致。3 .设栈的顺序存储空间为S ( 1 : 50 ),初始状态为top=0o现经过一系列 入栈与退栈运算后，top=20 ,则当前栈中的元素个数为( ).2014年3月 真题A . 30B . 29C . 20D . 19【答案】C【解析】栈按照“先进后出”的原则组织数据，插入与删除操作被限制在栈 顶一端进行，入栈使栈顶位置进1 ,退栈使栈顶退lo top=0表示栈为空，在运算 过程中，指针始终指向栈顶元素。top=20 ,说明当前栈中有20个元素。4 .一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依 次入栈，然后再依次出栈，则元素出栈的顺序是()» 2013年9月真题A . 12345ABCDEB . EDCBA54321C . ABCDE12345D. 54321FDCBA【答案】B【解析】栈中数据的插入和删除都在栈顶按照“先进后出"的原则进行操作。考点2队列及其基本运算(1)什么是队列队列(Queue )是指允许在一端进行插入、而在另一端进行删除的线性表。(2 )队列的特点允许插入的一端称为队尾，用队尾指针指向队尾元素；允许删除的一端称 为队头，用排头指针指向排头元素的前一个位置。最先插入的元素最先被删除，最后插入的元素最后被删除，遵循"先进先 出"或"后进后出"原则。队尾指针rear和排头指针front共同反映队列中元素变动情况。入队运算指只涉及队尾指针rear变化，退队运算只涉及WE头指针front变 化。（3）循环队列及其运算循环队列是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的 环状空间，供队列循环使用。在循环队列中，用队尾指针rear指向队尾元素，用 排头指针front指向排头元素的前一个位置，从排头指针front指向的后一个位置 到队尾指针rear指向的位置均是队列中元素。队列空的条件是s = 0;队列满的条 件是 s = 1 且 front = rear0队列的两种运算假设循环队列的初始状态为空，即：s = 0 ,且front = rear=mo入队运算入队运算是指在循环队列的队尾加入一个新元素。操作过程如下：a .首先判断循环队列是否满。当循环队列非空（S = l）且队尾指针等于排头 指针时，说明循环队列已满，不能进行入队运算。这种情况称为“上溢”。此时 算法结束。b .然后将队尾指针进一（即rear = rear +1）,并当rear = m + l时置rear =loc.最后将新元素x插入队尾指针指向的位置，并且置循环队列非空标志。退队运算退队运算是指在循环队列的排头位置退出一个元素并赋给指定的变量。操作 过程如下:a .首先判断循环队列是否为空。当循环队列为空（s = 0 ）时，不能进行退队 运算。这种情况称为“下溢”。此时算法结束。b .然后将HE头指针进一（即front = front +1），并当front = m +1时置front =loc.再将头指针指向的元素赋给指定的变量。d .最后判断退队后循环队列是否为空。当front = rear时置循环队列空标志 （即 s = 0）。【真题演练】1 .下列叙述中正确的是（）。2013年9月真题A.栈是“先进先出”的线性表B.队列是“先进后出”的线性表C.循环队列是非线性结构D.有序线性表既可以采用顺序存储结构，也可以采用链式存储结构【答案】D【解析】栈和队列都是受限的线性表，其中栈按照“先进后出”的原则组织数 据，插入与删除操作被限制在栈顶一端进行；队列采用“先进先出”的原则组织 数据。循环队列是队列的一种特殊形式，是线性结构。2 .下列叙述中正确的是（）。2014年3月真题A.循环队列是顺序存储结构B.循环队列是链式存储结构C.循环队列是非线性结构D.循环队列的插入运算不会发生溢出现象【答案】A【解析】B项错误，循环队列是一种II质序存储结构的队列；C项错误，线性结 构是一个非空序列：除第一个元素外，每个元素，有且只有一个前件；除最后一 个元素外，每个元素有且只有一个后件，所以循环队列是线性结构；D项错误， 当循环队列的元素个数等于存储长度后，入队会发生溢出现象，覆盖前面的数据。3 .对于循环队列，下列叙述中正确的是（）.2013年9月真题A.队头指针是固定不变的B.队头指针一定大于队尾指针C.队头指针一定小于队尾指针D.队头指针可以大于队尾指针，也可以小于队尾指针【答案】D【解析】循环队列的队头指针与队尾指针都不是固定的，每次入队操作队尾 指针要m进1 ,每次出队操作队头指针要m进10因为存在m运算，所以队 头指针与队尾指针大小关系不确定。4 .下列叙述中正确的是()。2013年9月真题A.循环队列有队头和队尾两个指针，因此，循环队列是非线性结构B.在循环队列中，只需要队头指针就能反映队列中元索的动态变化情况C.在循环队列中，只需要队尾指针就能反映队列中元素的动态变化情况D.循环队列中元素的个数是由队头指针和队尾指针共同决定【答案】D【解析】在循环队列中元素的个数是由队头指针和队尾指针共同决定的，入 队使得队尾指针变化，出队使得队头指针变化。1.5线性链表考点1线性链表的基本概念(1)线性表的顺序存储结构存在的缺陷：在插入或删除元素时，为保证操作后的线性表仍然是顺序存储，需要大量 移动数据元素，效率很低。在J顺序存储结构下，线性表的存储空间不便于扩充，易产生上溢现象。线性表的顺序存储结构不便于对存储空间的动态分配。(2 )链式存解点侬:数据域：用于存放数据元素值；指针域：用于存放指针。指针用于指向该结点的前一个或后一个结点，存储数据结构的存储空间可以 不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据 元素之间的逻辑关系是由指针域来确定的。链式存储方式既可用于表示线性结构，也可用于表示非线性结构。在用链式 结构表示较复杂的非线性结构时，其指针域的个数要多一些。(3)线性链表定义：线性链表是线性表的链式存储结构。特点a.各数据结点的存储序号是不连续的，各结点在存储空间中的位置关系与逻 辑关系也不一致；b.各数据元素之间的前后件关系是由各结点的指针域来指示的；c.每一个结点只有一个指针域，由这个指针只能找到后件结点，不能找到前 件结点，只能顺指针向链尾进行扫描。为了弥补线性单链表的缺陷，在某些应用中为线性链表每个结点设置两个指 针，左指针用以指向其前件结点，右指针指向其后件结点。(4)带链的栈带链的栈可以用来收集计算机存储空间中所有空闲的存储结点。与"质序栈一样，带链栈的基本操作有以下几个：栈的初始化：建立一个空栈的顺序存储空间；入栈运算：在栈顶位置插入一个新元素；退栈运算：取出栈顶元素并赋给一个指定的变量；读栈顶元素：阴戋顶元素赋给一个指定的变量。(5)带链的队列与顺序队列一样，带链队列的基本操作有以下几个：队列的初始化：建立一个空队列的顺序存储空间；入队运算：在循环队列的队尾加入一个新元素；退队运算：在循环队列的排头位置退出一个元素并赋给指定的变量。【真题演练】1 .下列叙述中正确的是()。2014年9月真题A .所谓有序表是指在II质序存储空间内连续存放的元素序列B.有序表只能顺序存储在连续的存储空间内C.有序表可以用链式存储方式存储在不连续的存储空间内D .任彳可存储方式的有序表均能采用二分法进行查找【答案】C【解析】“有序”是指线性表中的元素按照升序或降序(允许相邻元素相同) 的方式排列。有序是一个逻辑概念，与物理存储无关。二分法查找时涉及下标运 算，要求有序表必须顺序存储。2.线性表的链式存储结构与顺序存储结构相比，链式存储结构的优点有 ).2014年9月真题A.节省存储空间B.插入与删除运算效率高C.便于查找D,排序时减少元素的b匕较次数【答案】B【解析】线性表的链式存储结构与质序存储结构的优缺点比较如下：类型优点缺点顺序 表方便随机存取无需额外的存储空间来表示结 点间的逻辑关系插入和删除运算效率很低存储空间不便于扩充不便于对存储空间的动态分配链表在进行插入和删除操作时，只需 要改变指针链表的存储空间易于扩充，容易 实现空间的动态分配需要额外的空间来表示数据元素之 间的逻辑关系，存储密度低3 .下列叙述中正确的是()o 2013年9月真题A J顺序存储结构的存储一定是连续的,链式存储结构的存储空间不一定是连 续的B.顺序存储结构只针对线性结构，链式存储结构只针对非线性结构C.顺序存储结构能存储有序表，链式存储结构不能存储有序表D.链式存储结构比顺序存储结构节省存储空间【答案】A【解析】BC两项错误，逻辑概念上的线性非线性是否有序与存储结构为顺序 还是链式没有直接关系；D项错误，链式存储结构比JI质序存储结构更耗费存储空 间，因为链式存储结构中除了要存储顺序结构中的数据外还要存储指针。考点2线性链表的基本运算(1)常见的线性表的运算线性链表的运算主要有以下几个：在线性链表中包含指定元素的结点之前插入一个新元素；在线性链表中删除包含指定元素的结点；将两个线性链表按要求合并成一个线性链表；将一个线性链表按要求进行分解；逆转线性链表；复制线性链表；线性链表的排序；线性链表的查找。(2)在线性链表中查找指定元素非空线性链表中寻找包含指定元素值x的前一个结点p的基本方法：从头指针指向的结点开始往后沿指针进行扫描，直到后面已没有结点或下一 个结点的数据域为x为止。因此，由这种方法找到的结点p有两种可能：当线性 链表中存在包含元素x的结点时，则找到的p为第一次遇到的包含元素x的前一 个结点序号；当线性链表中不存在包含元素X的结点时，则找到的p为线性链表 中的最后一个结点号。(3)线性链表的插入定义：线性链表的插入是指在链式储存结构下的线性表中插入一个新元素。插入过程：在线性链表中包含元素x的结点之前插入一个新元素boa.从可利用栈取得一个结点，设该结点号为p,并置结点p的数据域为插入 的元素值bo b .在线性链表中寻找包含元素x的前一个结点，设该结点的存储序 号为q。c.最后将结点p插入到结点q之后。为了实现这一步，只要改变以下两个结 点的指针域内容：第一，使结点P指向包含元素x的结点；第二，使结点q的指针域内容改为指向结点po插入特点：a.不会发生上溢现象；b.可方便实现存储空间动态分配；c.不发生数据元素移动现象，只改变结点指针，提高插入效率。(4)线性链表的删除定义：线性链表的删除是指在链式储耨构下的线性表中删除包含指定元 素的结点。删除过程：在线性链表中删除包含元素X的结点。a.在线性链表中寻找包含元素x的前一个结点，设该结点序号为q;b .将结点q后的结点p从线性链表中删除，即让结点q的指针指向包含元 素x的结点p的指针指向的结点；c.将包含元素x的结点p送回可利用栈。在线性链表中删除一个元素后，不需要移动表的数据元素，只需改变被删除 元素所在结点的前一个结点的指针域即可。考点3循环链表(1)与线性链表相比，循环链表具有的特点：在循环链表中增加了一个表头结点，其数据域为任意或者根据需要来设置, 指针域指向线性表的第一个元素的结点。循环链表的头指针指向表头结点。循环链表中最后一个结点的指针域不是空，而是指向表头结点。即在循环 链表中，所有结点的指针构成了一个环状链。(2)与线性单链表相比，循环链表具有两方面优点：在循环链表中，只要指出表中任何一个结点的位置，就可以从它出