二年级公共基础知识专用教材考纲分析完整版.pdf

《二年级公共基础知识专用教材考纲分析完整版.pdf》由会员分享，可在线阅读，更多相关《二年级公共基础知识专用教材考纲分析完整版.pdf（239页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 二年级公共基础知识专用教材考纲分析 HUA system office room【HUA16H-TTMS2A-HUAS8Q8-HUAH1688】目 录 第 1 章 数据结构与算法.考纲分析.考点精讲.1.1 算 法.考点 1 算法的基本概念.考点 2 算法设计基本方法.考点 3 算法复杂度.1.2 数据结构的基本概念.考点 1 概 述.考点 2 数据结构的概念.2018 年 9 月全国计算机等级考试 二级公共基础知识专用教材【考纲分析考点精讲真题演练强化习题】最新资料，WORD 格式，可编辑修改！考点 3 数据结构的图形表示.考点 4 线性结构与非线性结构.1.3 线性表及其顺序存储结构.考

2、点 1 线性表的基本概念.考点 2 线性表的顺序存储结构.考点 3 顺序表的插入运算.考点 4 顺序表的删除运算.1.4 栈和队列.考点 1 栈及其基本运算.考点 2 队列及其基本运算.1.5 线性链表.考点 1 线性链表的基本概念.考点 2 线性链表的基本运算.考点 3 循环链表.1.6 树与二叉树.考点 1 树的基本概念.考点 2 二叉树及其基本性质.考点 3 二叉树的存储结构.考点 4 二叉树的遍历.1.7 查找技术.考点 1 顺序查找（顺序搜索）.考点 2 二分法查找（对分查找）.1.8 排序技术.考点 1 交换类排序法.考点 2 插入类排序法.考点 3 选择类排序法.强化习题.第 2

3、 章 程序设计基础.考纲分析.考点精讲.2.1 程序设计方法与风格.考点 1 程序设计发展阶段.考点 2 程序设计风格.考点 3 良好的程序设计风格应考虑的因素.2.2 结构化程序设计.考点 1 结构化程序设计的原则.考点 2 结构化程序的基本结构与特点.考点 3 结构化程序设计原则和方法的应用.2.3 面向对象的程序设计.考点 1 关于面向对象方法.考点 2 面向对象方法的基本概念.强化习题.第 3 章 软件工程基础.考纲分析.考点精讲.3.1 软件工程基本概念.考点 1 软件定义与软件特点.考点 2 软件危机与软件工程.考点 3 软件过程与软件生命周期.考点 4 软件工程的目标与原则.考点

4、 5 软件开发工具与软件开发环境.3.2 结构化分析方法.考点 1 需求分析与需求分析方法.考点 2 结构化分析方法.考点 3 软件需求规格说明书.3.3 结构化设计方法.考点 1 软件设计的基本概念.考点 2 概要设计.考点 3 详细设计.3.4 软件测试.考点 1 软件测试的目的和定义.考点 2 软件测试的准则.考点 3 软件测试方法与技术综述.考点 4 软件测试的策略.3.5 程序的调试.考点 1 基本概念.考点 2 软件调试方法.强化习题.第 4 章 数据库设计基础.考纲分析.考点精讲.4.1 数据库系统的基本概念.考点 1 数据、数据库、数据库管理系统.考点 2 数据库系统的发展.考

5、点 3 数据库系统的基本特点.考点 4 数据库系统的内部结构体系.4.2 数据模型.考点 1 数据模型的基本概念.考点 2 E-R 模型.考点 3 层次模型.考点 4 网状模型.考点 5 关系模型.4.3 关系代数.考点 1 关系模型的基本操作.考点 2 关系模型的基本运算.考点 3 关系代数中的扩充运算.4.4 数据库设计与管理.考点 1 数据库设计概述.考点 2 数据库设计的需求分析.考点 3 数据库概念设计.考点 4 数据库的逻辑设计.考点 5 数据库的物理设计.考点 6 数据库管理.强化习题.附 录 全国计算机等级考试二级公共基础知识考试大纲（2013 年版）.第 1 章 数据结构与算

6、法 考纲分析 1算法的基本概念，算法复杂度的概念和意义（时间复杂度与空间复杂度）。2数据结构的定义，数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。3线性表的定义，线性表的顺序存储结构及其插入与删除运算。4栈和队列的定义，栈和队列的顺序存储结构及其基本运算。5线性单链表、双向链表与循环链表的结构及其基本运算。6树的基本概念，二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。7顺序查找与二分法查找算法，基本排序算法（交换类排序，选择类排序，插入类排序）。考点精讲 1.1 算 法 考点 1 算法的基本概念（1）算法的定义 算法是指解题方案的准确而完整的描述，即算法是

7、对特定问题求解步骤的一种描述。它是一组严谨定义运算顺序的规则，且每个规则都是明确有效的，此顺序将在有限的次数下终止。需要注意的是：算法不等于程序，也不等于计算方法。（2）算法的基本特征 可行性 a算法中的每一步骤都必须能够实现；b算法执行的结果要能够达到预期的目的。确定性 确定性是指算法中的每一个步骤都必须有明确的定义，不允许有模棱两可的解释，也不允许有多义性。有穷性 有穷性是指算法必须能在有限的时间内做完，即必须能在执行有限个步骤之后终止，且必须有合理的执行时间。拥有足够的情报 算法是否有效，取决于为算法所提供的情报是否足够。一般而言，当算法有足够的情报时，此算法有效，而当提供的情报不够时，

8、算法可能无效。【真题演练】算法的有穷性是指（）。2013 年 9 月真题 A算法程序的运行时间是有限的 B算法程序所处理的数据量是有限的 C算法程序的长度是有限的 D算法只能被有限的用户使用【答案】A【解析】算法设计有穷性要求操作步骤有限且必须在有限时间内完成，耗费太长时间得到的正确结果是没有意义的。考点 2 算法设计基本方法（1）列举法 基本思想 根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。常用于解决“是否存在”或“有多少种可能”等类型的问题。主要特点 算法比较简单，但列举情况较多时，算法工作量很大。注意事项 例举算法时，通过对实际问题进行详细分

9、析，将与问题有关的知识条理化、完备化、系统化，并从中找出规律，或对所有可能的情况进行分类，从而引出一些有用的信息，减少列举量。（2）归纳法 基本思想 通过列举少量的特殊情况，经过分析，最后找出一般的关系。主要特点 a比列举法更能反映问题的本质，可解决列举量为无限的问题；b可操作性低，不易归纳出一个具体数学模型；c归纳得出的结论只是一种猜测，须对这种猜测加以必要的证明。（3）递推 基本思想 从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。主要特点 a初始条件或问题本身已给定，或通过对问题的分析化简得到；b递推本质上属于归纳法，递推关系式往往是归纳的结果；c数值型递推算法计算过程中必须

10、注意数值计算的稳定性问题。（4）递归 基本思想 将复杂问题逐层分解，归结为一些简单的问题，将简单问题解决掉，再沿着原来分解的逆过程逐步进行综合。主要特点 a递归的基础是归纳，对问题逐层分解的过程实际上并没有对问题进行求解；b在可计算性理论和算法设计中占有重要地位；c递归算法比递推算法清晰易读，结构简练；d设计递归算法比递推算法容易，但是其执行效率较低。分类 a直接递归。一个算法 P 显式地调用自己。b间接递归。算法 P 调用另一个算法 Q，而算法 Q 又调用算法 P。递归与递推的区别 递归与递推的区别主要在于二者实现方法的不同，表现为：a递归是从算法本身到达递归的边界的；b递推是从初始条件出发

11、，逐次推出所需求的结果。（5）减半递推技术 减半递推技术是工程上常用的分治法，其中，“减半”指将问题的规模减半，而问题的性质不变；“递推”指重复“减半”的过程。（6）回溯法 回溯法是指通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索逐步试探，若试探成功，则问题得到解决，若试探失败，则逐步回退换别的路线再进行试探。【真题演练】1下列叙述中正确的是（）。2013 年 9 月真题 A所谓算法就是计算方法 B程序可以作为算法的一种描述方法 C算法设计只需考虑得到计算结果 D算法设计可以忽略算法的运算时间【答案】B【解析】程序可以作为算法的一种描述方法,算法在实现时需要用具体的程序设计语言描述

12、。A 项错误，算法并不等同于计算方法，是指对解题方案的准确而完整的描述；C 项错误，算法设计需要考虑可行性、确定性、有穷性与足够的情报；D 项错误，算法设计有穷性要求操作步骤有限且必须在有限时间内完成，耗费太长时间得到的正确结果是没有意义的。2下列关于算法的描述中错误的是（）。2014 年 3 月真题 A算法强调动态的执行过程，不同于静态的计算公式 B算法必须能在有限个步骤之后终止 C算法设计必须考虑算法的复杂度 D算法的优劣取决于运行算法程序的环境【答案】D【解析】算法是指对解题方案的准确而完整的描述。A 项正确，算法强调实现，不同于数学上的计算方法；B 项正确，算法的有穷性是指，算法中的操

13、作步骤为有限个，且每个步骤都能在有限时间内完成；C 项正确，算法设计必须考虑执行算法所需要的资源，即时间复 杂度与空间复杂度；D 项错误，算法的优劣取决于算法复杂度，只有当算法被编程实现运行时才会受到运行环境影响。考点 3 算法复杂度（1）时间复杂度 定义 算法的时间复杂度是指执行算法所需要的计算工作量。算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数，即 算法的工作量f（n）其中，n 是问题的规模。在同一问题规模下，若算法的基本运算次数取决于某一特定输入，可用以下两种方法来分析算法的工作量：a平均性态 平均性态分析是指用各种特定输入下的基本运算次数的加

14、权平均值来度量算法的工作量。算法的平均性态定义为：其中，x 是所有可能输入中的某个特定输入，p（x）是 x 出现的概率，即输入为 x 的概率，t（x）是算法在输入为 x 时所执行的基本运算次数，Dn表示当规模为 n 时，算法执行时所有可能输入的集合。b最坏情况复杂性 最坏情况分析是指规模为 n 时，算法所执行的基本运算的最大次数。其定义为：（2）空间复杂度 定义 算法的空间复杂度一般是指执行这个算法所需要的内存空间。存储空间组成 一个算法的存储空间包括以下几种：a算法程序占用的空间；b输入的初始数据占用的存储空间；c算法执行过程中所需要的额外空间。额外空间包括算法程序执行过程中的工作单元以及某

15、种数据结构所需要的附加存储空间，若额外空间相对于问题规模来说是常数，则称该算法是原地工作的。【真题演练】1下列叙述中正确的是（）。2015 年 3 月真题 A算法的效率只与问题的规模有关，而与数据的存储结构无关 B算法的时间复杂度是指执行算法所需要的计算工作量 C数据的逻辑结构与存储结构是一一对应的 D算法的时间复杂度与空间复杂度一定相关【答案】B【解析】算法的时间复杂度是指算法在计算机内执行时所需时间的度量；与时间复杂度类似，空间复杂度是指算法在计算机内执行时所需存储空间的度量。2算法的空间复杂度是指（）。2013 年 9 月真题 A算法在执行过程中所需要的计算机存储空间 B算法所处理的数据

16、量 C算法程序中的语句或指令条数 D算法在执行过程中所需要的临时工作单元数【答案】A 【解析】空间复杂度是是对一个算法在运行过程中临时占用存储空间大小的量度。3算法空间复杂度的度量方法是（）。2014 年 9 月真题 A算法程序的长度 B算法所处理的数据量 C执行算法所需要的工作单元 D执行算法所需要的存储空间【答案】D【解析】算法的空间复杂度包括：输入数据所占的存储空间；程序本身所占的存储空间；算法执行过程中所需要的额外空间，是指执行这个算法所需要的内存空间，1.2 数据结构的基本概念 考点 1 概 述（1）数据处理概述 定义 数据处理是指对数据集合中的各元素以各种方式进行运算，包括插入、删

17、除、查找、更改等运算，也包括对数据元素进行分析。关键问题 大量数据元素在计算机中如何组织，以便提高数据处理的效率，从而节省计算机的存储空间，这是进行数据结构处理的关键问题。（2）数据结构研究概述 研究问题 a数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；b在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；c对各种数据结构进行的运算。研究目的 数据结构研究和讨论上述 3 个问题的主要目的在于提高数据处理效率，包括：a提高数据处理的速度；b尽量节省在数据处理过程中所占用的计算机存储空间。考点 2 数据结构的概念（1）数据结构的定义 数据结构是指相互有关联的数据元素

18、的集合，即它是反映数据元素之间关系的数据元素集合的表示。简言之，数据结构是指带有结构的数据元素的集合，这里的“结构”指数据元素之间的前后件关系。一个数据结构应包含以下两方面内容：表述数据元素的信息；表示各数据元素之间的前后件关系。（2）数据的逻辑结构 定义 数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。要素：a数据元素的集合，通常记为 D；bD 上的关系，通常记为 R，它反映了 D 中各数据元素之间的前后件关系。表示 一个数据结构 B 可表示为：B（D，R）为反映 D 中个数据元素之间的前后件关系，一般用二元组来表示。（3）数据的存储结构 定义 数据的存储结构，也称数据的物理结构，是指

19、数据逻辑结构在计算机存储空间中的存放形式。在数据的存储结构中，不仅要存放各数据元素的信息，而且要存放各数据元素之间的前后件信息。常用的存储结构：a顺序；b链接；c索引。采用不同的存储结构，数据处理的效率是不同的。【真题演练】下列叙述中正确的是（）。2014 年 3 月真题 A有且只有一个根结点的数据结构一定是线性结构 B每一个结点最多有一个前件也最多有一个后件的数据结构一定是线性结构 C有且只有一个根结点的数据结构一定是非线性结构 D有且只有一个根结点的数据结构可能是线性结构，也可能是非线性结构【答案】D【解析】逻辑结构分为线性结构和非线性结构，线性结构的特征有：集合中必存在唯一的一个“第一个

20、元素”；集合中必存在唯一的一个“最后的元素”；除第一元素之外，其它数据元素均有唯一的“前驱”；除最后元素之外，其它数据元素均有唯一的“后继”。D 项正确，如树形结构只有一个根结点，为非线性结构。考点 3 数据结构的图形表示（1）在数据结构的图形表示中，数据集合D 中每个元素用中间标有元素值的方框表示，称为数据结点（简称结点）；对关系 R 中的每一个二元组，用一条有向线段从前件结点指向后件结点。（2）在数据结构中，没有前件的结点称为根结点，没有后件的结点称为终端结点（也称叶子结点），其余结点都称为内部结点。（3）数据结构中的元素结点可能是在动态变化的，这种变化体现在结点数量的增减以及各结点之间的

21、前后件关系的动态变化上。考点 4 线性结构与非线性结构 根据数据结构中各数据元素之间的前后件关系的复杂程度，可将数据结构分为：（1）线性结构（线性表）一个非空的数据结构满足下列两个条件时，称其为线性结构：有且只有一个根结点；每个结点最多只有一个前件，也最多只有一个后件。线性结构中插入或删除任何一个结点还应是线性结构，如果不满足这个条件就不能称之为线性结构。（2）非线性结构 如果一个数据结构不是线性结构，则称之为非线性结构。注：线性结构与非线性结构都可以是空的数据结构。一个空的数据结构属于线性结构还是非线性结构，需要根据对该数据结构的运算是否按照线性结构的规则来处理进行判断。1.3 线性表及其顺

22、序存储结构 考点 1 线性表的基本概念（1）线性表是一种最常见最简单的数据结构，由一组数据元素构成。数据元素在线性表中的位置值只取决于它们自己的序号，即数据元素之间的相对位置是线性的。（2）非空线性表的结构特征：有且只有一个根结点 a1，它无前件；有且只有一个终端结点 an，它无后件；除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。线性表中结点的个数 n 称为线性表的长度。当 n0 时，称为空表。【真题演练】下列叙述中正确的是（）。2014 年 9 月真题 A结点中具有两个指针域的链表一定是二叉链表 B结点中具有两个指针域的链表可以是线性结构，也可以是非线性结构 C二叉

23、树只能采用链式存储结构 D循环链表是非线性结构【答案】B【解析】A 项错误，具有两个指针域的链表可能是双向链表；B 项正确，如双向链表是线性结构，二叉树为非线性结构，两者结点中均有两个指针域；C 项错误，二叉树通常采用链式存储结构，也可采用其他结构；D 项错误，循环链表是线性结构，逻辑概念线性非线性与实际存储结构无关。考点 2 线性表的顺序存储结构（1）概述 顺序存储是一种最简单的在计算机中存放线性表的方法，也称顺序分配。（2）特点：线性表中所有元素所占的存储空间是连续的；线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。在线性表的顺序存储结构中，其前后件两个元素在存储空间中是紧邻的，且前

24、件元素一定存储在后件元素的前面。（3）运算 在线性表的顺序存储结构下，可对线性表进行以下运算：插入：在线性表的指定位置处加入一个新的元素；删除：在线性表中删除指定的元素；查找：在线性表中查找某个（或某些）特定的元素；排序：对线性表中的元素进行整序；分解：按要求将一个线性表分解成多个线性表；合并：按要求将多个线性表合并成一个线性表；复制：复制一个线性表；逆转：逆转一个线性表等。【真题演练】在线性表的顺序存储结构中，其存储空间连续，各个元素所占的字节数（）。2014年 3 月真题 A相同，元素的存储顺序与逻辑顺序一致 B相同，但其元素的存储顺序可以与逻辑顺序不一致 C不同，但元素的存储顺序与逻辑顺

25、序一致 D不同，且其元素的存储顺序可以与逻辑顺序不一致【答案】A【解析】在顺序表中，每个元素占有相同的存储单元。顺序表具有特征：线性表中所有元素所占的存储空间是连续的；线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。考点 3 顺序表的插入运算 假设线性表的存储空间为 V（1：m），线性表的长度为 n（nm），插入的位置为 i（表示在第 i 个位置插入元素），则顺序表插入新元素过程如下：（1）首先处理以下三种异常情况：当存储空间已满（即 nm）时为“上溢”错误，不能进行插入，算法结束；当 in 时，认为在最后一个元素之后（即第n1 个元素之前）插入；当 i1 时，认为在第 1 个元素之前插

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

27、小 1。1.4 栈和队列 考点 1 栈及其基本运算（1）栈的定义 栈是限定在一端进行插入与删除的线性表。（2）栈的特点：允许插入和删除的一端称为栈顶，不允许插入与删除的一端称为栈底。栈顶元素总是最后被插入的元素，也是最先被删除的元素；栈底元素总是最先被插入也是最后被删除的。栈遵循“先进后出”或“后进先出”的原则，具有记忆功能。通常用指针 top 来指示栈顶位置，用指针 bottom 指向栈底，栈顶指针 top 动态反映了栈中元素的变化情况。（3）栈的顺序存储及其运算 在栈的顺序存储空间 S（1:m）中，top0 表示栈空；topm 表示栈满。栈的三种运算：入栈运算 人栈运算是指在栈顶位置插入一

28、个新元素。操作过程如下：a首先判断栈顶指针是否已经指向存储空间的最后一个位置。如果是，则说明栈空间已满，不可能再进行入栈操作（这种情况称为栈“上溢”错误），算法结束。b然后将栈顶指针进一（即 top 加 1）。c最后将新元素 x 插入栈顶指针指向的位置。退栈运算 退栈运算是指取出栈顶元素并赋给一个指定的变量。操作过程如下：a首先判断栈顶指针是否为 0。如果是，则说明栈空，不可能进行退栈操作（这种情况称为栈“下溢”错误），算法结束。b然后将栈顶元素（栈顶指针指向的元素）赋给一个指定的变量。c最后将栈顶指针退一（即 top 减 1）。读栈顶元素 读栈顶元素是指将栈顶元素赋给一个指定的变量。操作过程

29、如下：a首先判断栈顶指针是否为 0。如果是，则说明栈空，读不到栈顶元素，算法结束。b然后将栈顶元素赋给指定的变量 y。这个运算不删除栈顶元素，只是将它的值赋给一个变量，栈顶指针不会变。【真题演练】1支持子程序调用的数据结构是（）。2013 年 9 月真题 A栈 B树 C队列 D二叉树【答案】A【解析】栈和队列都是受限的线性表，其中栈按照“先进后出”的原则组织数据，插入与删除操作被限制在栈顶一端进行。栈支持子程序调用，在主程序调用子函数时，要首先保存主程序当前的状态，然后转去执行子程序，结束调用后返回到主程序中调用子程序的位置，继续执行，这种调用符合栈的特点。2下列与栈结构有关联的是（）。201

30、3 年 3 月真题 A数组的定义域使用 B操作系统的进程调度 C函数的递归调用 D选择结构的执行【答案】C【解析】递归调用的本质就是函数调用函数本身，直到满足特定条件时才停止，然后从最后被递归调用处返回。递归函数是通过栈来实现的，所以调用原则和栈的实现相一致。3设栈的顺序存储空间为 S（1：50），初始状态为 top=0。现经过一系列入栈与退栈运算后，top=20，则当前栈中的元素个数为（）。2014 年 3 月真题 A30 B29 C20 D19【答案】C【解析】栈按照“先进后出”的原则组织数据，插入与删除操作被限制在栈顶一端进行，入栈使栈顶位置进 1，退栈使栈顶退 1。top=0 表示栈为

31、空，在运算过程中，指针始终指向栈顶元素。top=20，说明当前栈中有 20 个元素。4一个栈的初始状态为空。现将元素 1、2、3、4、5、A、B、C、D、E 依次入栈，然后再依次出栈，则元素出栈的顺序是（）。2013 年 9 月真题 A12345ABCDE BEDCBA54321 CABCDE12345 D54321FDCBA 【答案】B【解析】栈中数据的插入和删除都在栈顶按照“先进后出”的原则进行操作。考点 2 队列及其基本运算（1）什么是队列 队列（Queue）是指允许在一端进行插入、而在另一端进行删除的线性表。（2）队列的特点 允许插入的一端称为队尾，用队尾指针指向队尾元素；允许删除的一

32、端称为队头，用排头指针指向排头元素的前一个位置。最先插入的元素最先被删除，最后插入的元素最后被删除，遵循“先进先出”或“后进后出”原则。队尾指针 rear 和排头指针 front 共同反映队列中元素变动情况。入队运算指只涉及队尾指针 rear 变化，退队运算只涉及排头指针 front 变化。（3）循环队列及其运算 循环队列是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。在循环队列中，用队尾指针rear 指向队尾元素，用排头指针 front 指向排 头元素的前一个位置，从排头指针 front 指向的后一个位置到队尾指针 rear 指向的位置均是队列中元素。队列

33、空的条件是 s0；队列满的条件是 s1 且 frontrear。队列的两种运算 假设循环队列的初始状态为空，即：s0，且 frontrearm。入队运算 入队运算是指在循环队列的队尾加入一个新元素。操作过程如下：a首先判断循环队列是否满。当循环队列非空（S1）且队尾指针等于排头指针时，说明循环队列已满，不能进行入队运算。这种情况称为“上溢”。此时算法结束。b然后将队尾指针进一（即 rearrear1），并当 rearm1 时置 rear1。c最后将新元素 x 插入队尾指针指向的位置，并且置循环队列非空标志。退队运算 退队运算是指在循环队列的排头位置退出一个元素并赋给指定的变量。操作过程如下：a

34、首先判断循环队列是否为空。当循环队列为空（s0）时，不能进行退队运算。这种情况称为“下溢”。此时算法结束。b然后将排头指针进一（即 frontfront1），并当 frontm1 时置 front1。c再将排头指针指向的元素赋给指定的变量。d最后判断退队后循环队列是否为空。当 frontrear 时置循环队列空标志（即 s0）。【真题演练】1下列叙述中正确的是（）。2013 年 9 月真题 A栈是“先进先出”的线性表 B队列是“先进后出”的线性表 C循环队列是非线性结构 D有序线性表既可以采用顺序存储结构，也可以采用链式存储结构【答案】D【解析】栈和队列都是受限的线性表，其中栈按照“先进后出”

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

36、队列，下列叙述中正确的是（）。2013 年 9 月真题 A队头指针是固定不变的 B队头指针一定大于队尾指针 C队头指针一定小于队尾指针 D队头指针可以大于队尾指针，也可以小于队尾指针【答案】D 【解析】循环队列的队头指针与队尾指针都不是固定的，每次入队操作队尾指针要%m 进1，每次出队操作队头指针要%m 进 1。因为存在%m 运算，所以队头指针与队尾指针大小关系不确定。4下列叙述中正确的是（）。2013 年 9 月真题 A循环队列有队头和队尾两个指针，因此，循环队列是非线性结构 B在循环队列中，只需要队头指针就能反映队列中元索的动态变化情况 C在循环队列中，只需要队尾指针就能反映队列中元素的动

37、态变化情况 D循环队列中元素的个数是由队头指针和队尾指针共同决定【答案】D【解析】在循环队列中元素的个数是由队头指针和队尾指针共同决定的，入队使得队尾指针变化，出队使得队头指针变化。1.5 线性链表 考点 1 线性链表的基本概念（1）线性表的顺序存储结构存在的缺陷：在插入或删除元素时，为保证操作后的线性表仍然是顺序存储，需要大量移动数据元素，效率很低。在顺序存储结构下，线性表的存储空间不便于扩充，易产生上溢现象。线性表的顺序存储结构不便于对存储空间的动态分配。（2）链式存储结点组成：数据域：用于存放数据元素值；指针域：用于存放指针。指针用于指向该结点的前一个或后一个结点，存储数据结构的存储空间

38、可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。链式存储方式既可用于表示线性结构，也可用于表示非线性结构。在用链式结构表示较复杂的非线性结构时，其指针域的个数要多一些。（3）线性链表 定义：线性链表是线性表的链式存储结构。特点 a各数据结点的存储序号是不连续的，各结点在存储空间中的位置关系与逻辑关系也不一致；b各数据元素之间的前后件关系是由各结点的指针域来指示的；c每一个结点只有一个指针域，由这个指针只能找到后件结点，不能找到前件结点，只能顺指针向链尾进行扫描。为了弥补线性单链表的缺陷，在某些应用中为线性链表每个结点设置两个指针，

39、左指针用以指向其前件结点，右指针指向其后件结点。（4）带链的栈 带链的栈可以用来收集计算机存储空间中所有空闲的存储结点。与顺序栈一样，带链栈的基本操作有以下几个：栈的初始化：建立一个空栈的顺序存储空间；入栈运算：在栈顶位置插入一个新元素；退栈运算：取出栈顶元素并赋给一个指定的变量；读栈顶元素：将栈顶元素赋给一个指定的变量。（5）带链的队列 与顺序队列一样，带链队列的基本操作有以下几个：队列的初始化：建立一个空队列的顺序存储空间；入队运算：在循环队列的队尾加入一个新元素；退队运算：在循环队列的排头位置退出一个元素并赋给指定的变量。【真题演练】1下列叙述中正确的是（）。2014 年 9 月真题 A

40、所谓有序表是指在顺序存储空间内连续存放的元素序列 B有序表只能顺序存储在连续的存储空间内 C有序表可以用链式存储方式存储在不连续的存储空间内 D任何存储方式的有序表均能采用二分法进行查找【答案】C【解析】“有序”是指线性表中的元素按照升序或降序（允许相邻元素相同）的方式排列。有序是一个逻辑概念，与物理存储无关。二分法查找时涉及下标运算，要求有序表必须顺序存储。2线性表的链式存储结构与顺序存储结构相比，链式存储结构的优点有（）。2014 年 9 月真题 A节省存储空间 B插入与删除运算效率高 C便于查找 D排序时减少元素的比较次数【答案】B【解析】线性表的链式存储结构与顺序存储结构的优缺点比较如

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

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

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

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

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

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

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

48、。（3）一个结点拥有的后件个数称为该结点的度。某结点的度为 n，表示该结点有 n 个分支，每个分支指向一个后件，除根结点外，每个结点都有一个唯一的分支指向它。树中的结点数为树中所有结点的度之和再加 1。（4）根结点在第 1 层，同一层上所有结点的所有子结点都在下一层，树的最大层次称为树的深度（5）在树中，叶子结点没有子树。（6）用树来表示算术表达式的原则：表达式中的每一个运算符在树中对应一个结点，称为运算符结点；运算符的每一个运算对象在树中为该运算符结点的子树（在树中的顺序为从左到右）；运算对象中的单变量均为叶子结点。在树中，叶子结点没有子树。【真题演练】1下列数据结构中，属于非线性结构的是（

49、）。2013 年 3 月真题 A循环队列 B带链队列 C二叉树 D带链栈【答案】C【解析】线性结构要求有唯一的根结点和叶子结点，且除了根结点任何一个元素只有唯一的前件，除了叶子结点任何一个元素只有唯一的后件。二叉树的后继结点可能不唯一，属于非线性结构。2某二叉树的中序序列为 DCBAEFG，后序序列为 DCBGFEA，则该二叉树的深度（根节点在第 1 层）为（）。2015 年 3 月真题 A5 B4 C3 D2【答案】B 【解析】题干中二叉树的后序序列为 DCBGFEA，A 为根节点。中序序列为 DCBAEFG，可知DCB 为左子树节点，EFG 为右子树节点。同理 B 为 C 父节点，C 为

50、D 父节点。根据分析，可画出左子树，同理 E 为 F 根节点，F 为 G 根节点。根据分析，可画出右子树，观察得，树的深度为 4，故二叉树深度为 4 层。考点 2 二叉树及其基本性质（1）二叉树定义 二叉树是一种很有用的非线性结构，与树结构很相似，树结构的所有术语都可以用到叉树这种数据结构上。（2）二叉树的两个特点 非空二叉树只有一个根结点；每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。（3）二叉树的基本性质 在二叉树的第 k 层上，最多有 2k-1（k1）个结点。深度为 m 的二叉树最多有 2m-1 个结点。在任意一棵二叉树中，度为 0 的结点（即叶子结点）总是比度为 2 的结