二年级M y S Q L数据库程序设计专用教材
Company Document number：WTUT-WT88Y-W8BBGB-BWYTT-19998
目录
第一部分公共基础知识
第1章数据结构与算法
考纲分析
1．算法的基本概念，算法复杂度的概念和意义（时间复杂度与空间复杂度）。
2．数据结构的定义，数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。
3．线性表的定义，线性表的顺序存储结构及其插入与删除运算。
4．栈和队列的定义，栈和队列的顺序存储结构及其基本运算。
5．线性单链表、双向链表与循环链表的结构及其基本运算。
6．树的基本概念，二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。
7．顺序查找与二分法查找算法，基本排序算法（交换类排序，选择类排序，插入类排序）。
考点精讲
算法
考点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．设计递归算法比递推算法容易，但是其执行效率较低。
③分类
b．间接递归。算法P调用另一个算法Q，而算法Q又调用算法P。
④递归与递推的区别
递归与递推的区别主要在于二者实现方法的不同，表现为：
a．递归是从算法本身到达递归的边界的；
b．递推是从初始条件出发，逐次推出所需求的结果。
（5）减半递推技术
减半递推技术是工程上常用的分治法，其中，“减半”指将问题的规模减半，而问题的性质不变；“递推”指重复“减半”的过程。
（6）回溯法
回溯法是指通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索逐步试探，若试探成功，则问题得到解决，若试探失败，则逐步回退换别的路线再进行试探。
【真题演练】
1．下列叙述中正确的是（）。[2013年9月真题]
A．所谓算法就是计算方法
B．程序可以作为算法的一种描述方法
C．算法设计只需考虑得到计算结果
D．算法设计可以忽略算法的运算时间
【答案】B
【解析】程序可以作为算法的一种描述方法,算法在实现时需要用具体的程序设计语言描述。A项错误，算法并不等同于计算方法，是指对解题方案的准确而完整的描述；C项错误，算法设计需要考虑可行性、确定性、有穷性与足够的情报；D项错误，算法设计有穷性要求操作步骤有限且必须在有限时间内完成，耗费太长时间得到的正确结果是没有意义的。
2．下列关于算法的描述中错误的是（）。[2014年3月真题]
B ．算法必须能在有限个步骤之后终止
C ．算法设计必须考虑算法的复杂度
D ．算法的优劣取决于运行算法程序的环境
【答案】D
【解析】算法是指对解题方案的准确而完整的描述。A 项正确，算法强调实现，不同于数学上的计算方法；B 项正确，算法的有穷性是指，算法中的操作步骤为有限个，且每个步骤都能在有限时间内完成；C 项正确，算法设计必须考虑执行算法所需要的资源，即时间复杂度与空间复杂度；D 项错误，算法的优劣取决于算法复杂度，只有当算法被编程实现运行时才会受到运行环境影响。
考点3 算法复杂度
（1）时间复杂度
①定义
算法的时间复杂度是指执行算法所需要的计算工作量。
算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数，即
算法的工作量＝f （n ）
其中，n 是问题的规模。
②在同一问题规模下，若算法的基本运算次数取决于某一特定输入，可用以下两种方法来分析算法的工作量：
a ．平均性态
平均性态分析是指用各种特定输入下的基本运算次数的加权平均值来度量算法的工作量。算法的平均性态定义为：
n x D A(n)=
p(x)t(x)∈∑
其中，x 是所有可能输入中的某个特定输入，p （x ）是x 出现的概率，即输入为x 的概率，t （x ）是算法在输入为x 时所执行的基本运算次数，D n 表示当规模为n 时，算法执行时所有可能输入的集合。
b ．最坏情况复杂性
最坏情况分析是指规模为n 时，算法所执行的基本运算的最大次数。其定义为：
{}x D n W(n)=t(x)max ∈
（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概述
（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线性表的基本概念
（1）线性表是一种最常见最简单的数据结构，由一组数据元素构成。数据元素在线性表中的位置值只取决于它们自己的序号，即数据元素之间的相对位置是线性的。
①有且只有一个根结点a1
，它无前件；
②有且只有一个终端结点a n，它无后件；
③除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。
线性表中结点的个数n称为线性表的长度。当n＝0时，称为空表。
【真题演练】
下列叙述中正确的是（）。[2014年9月真题]
A．结点中具有两个指针域的链表一定是二叉链表
B．结点中具有两个指针域的链表可以是线性结构，也可以是非线性结构
C．二叉树只能采用链式存储结构
D．循环链表是非线性结构
【答案】B
【解析】A项错误，具有两个指针域的链表可能是双向链表；B项正确，如双向链表是线性结构，二叉树为非线性结构，两者结点中均有两个指针域；C项错误，二叉树通常采用链式存储结构，也可采用其他结构；D项错误，循环链表是线性结构，逻辑概念线性非线性与实际存储结构无关。
考点2线性表的顺序存储结构
（1）概述
顺序存储是一种最简单的在计算机中存放线性表的方法，也称顺序分配。
（2）特点：
①线性表中所有元素所占的存储空间是连续的；
②线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
在线性表的顺序存储结构中，其前后件两个元素在存储空间中是紧邻的，且前件元素一定存储在后件元素的前面。
在线性表的顺序存储结构下，可对线性表进行以下运算：
①插入：在线性表的指定位置处加入一个新的元素；
②删除：在线性表中删除指定的元素；
③查找：在线性表中查找某个（或某些）特定的元素；
④排序：对线性表中的元素进行整序；
⑤分解：按要求将一个线性表分解成多个线性表；
⑥合并：按要求将多个线性表合并成一个线性表；
⑦复制：复制一个线性表；
⑧逆转：逆转一个线性表等。
【真题演练】
在线性表的顺序存储结构中，其存储空间连续，各个元素所占的字节数（）。[2014年3月真题]
A．相同，元素的存储顺序与逻辑顺序一致
B．相同，但其元素的存储顺序可以与逻辑顺序不一致
C．不同，但元素的存储顺序与逻辑顺序一致
D．不同，且其元素的存储顺序可以与逻辑顺序不一致
【答案】A
【解析】在顺序表中，每个元素占有相同的存储单元。顺序表具有特征：①线性表中所有元素所占的存储空间是连续的；②线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
考点3顺序表的插入运算
假设线性表的存储空间为V（1：m），线性表的长度为n（n≤m），插入的位置为i（表示在第i个位置插入元素），则顺序表插入新元素过程如下：
（1）首先处理以下三种异常情况：
②当i>n时，认为在最后一个元素之后（即第n＋1个元素之前）插入；
③当i<1时，认为在第1个元素之前插入。
（2）从最后一个元素开始，直到第i个元素，其中每一个元素均往后移动一个位置。
（3）最后将新元素插入到第i个位置，并且将线性表的长度增加1。
考点4顺序表的删除运算
假设线性表的存储空间为V（1：m），线性表的长度为n（n≤m），删除的位置为i（表示删除第i个元素），则顺序表删除元素的过程如下：
（1）首先处理以下两种异常情况：
①当线性表为空（即n＝0）时为“上溢”错误，不能进行插入，算法结束；
②当i<1或i>n时，认为在最后一个元素之后（即第n＋1个元素之前）插入。
（2）然后从第i＋1个元素开始，直到最后一个元素，其中每一个元素均依次往前移动一个位置。
（3）最后将线性表的长度减小1。
栈和队列
考点1栈及其基本运算
（1）栈的定义
栈是限定在一端进行插入与删除的线性表。
（2）栈的特点：
①允许插入和删除的一端称为栈顶，不允许插入与删除的一端称为栈底。栈顶元素总是最后被插入的元素，也是最先被删除的元素；栈底元素总是最先被插入也是最后被删除的。
②栈遵循“先进后出”或“后进先出”的原则，具有记忆功能。
③通常用指针top来指示栈顶位置，用指针bottom指向栈底，栈顶指针top动态反映了栈中元素的变化情况。