第1章 数据结构与算法（13%）
重要考点提示： 1） 算法复杂度。
2） 栈、队列、线性链表的基本概念 3） 二叉树的存储结构
4） 线性表、树的结点计算和遍历 5） 冒泡排序的最坏次数计算
一、算法
考点1 算法的基本概念 记一些概念即可
1、算法：对解题方案的准确而完整的描述。重点
2、算法的基本特征 重点 ①可行性
针对实际问题设计的算法，人们总是希望能够得到满意的结果。但一个算法又总是在某个特定的计算工具上执行的，因此算法在执行过程中往往要受到计算工具的限制，使执行结果产生偏差。算法与计算公式是有差别的，在设计一个算法时，必须考虑它的可行性，否则将得不到满意的结果。 ②确定性
算法的确定性是指算法中的每一个步骤必须有明确的定义，不能产生歧义。这一性质也反映了算法与数学公式的明显差别。 ③有穷性
算法的有穷性，是指算法必须能在有限的时间内做完，即算法必须能在执行有限个步骤之后终止。算法的有穷性还包括合理的执行时间的含义，因为如果一个算法需要执行千万年，显然失去了价值。
④拥有足够的情报
一个算法是否有效，还取决为算法所提供的情报是否足够。通常，算法中的各种运算总是要施加到各个运算对象上，而这些运算对象又可能具有某种初始状态，这是算法执行的起点或是依据。因此，一个算法执行的结果总是与输入的初始数据有关，不
同的输入将会有不同的结果输出。当输入不够或输入错误时，算法本身也就无法执行或导致执行有错。一般来说，当算法拥有足够的情报时，此算法才是有效的，而当提供的情报不够时，算法可能无效。
有的认为是：可行性、确定性、有穷性、有输入、有输出。
3、算法的基本要素 重点 ①算法中对数据的运算和操作 ②算法的控制结构
可理解为：一个算法是由控制结构（顺序、分支和循环三种）和原操作（指固有数据类型的操作）构成的，则算法时间取决于两者的综合效果。
即：算法 = 控制结构 + 原操作 （固有数据类型的操作
解释：了解
①算法中对数据的运算和操作 每个算法实际上是按解题要求，从环境能进行的操作中选择合适的操作所组成的一组指令序列。因此，计算机算法就是计算机能处理的操作所组成的指令序列。
通常，计算机可以执行的基本操作以指令形式来描述，所有指令的集合构成计算机指令系统。
计算机程序就是按解题要求从计算机指令系统中选择合适的指令所组成的指令序列。
在一般的计算机系统中基本的运算和操作有以下4类： 算术运算、逻辑运算、关系运算、数据传输（如输入输出、赋值等）。
计算机程序也可以作为算法的一种描述，但由于在编制计算机程序时，通常要考虑很多与方法和分析无关的细节问题（如语法规则），因此，在设计算法的一开始，通常并不直接用计算机程序来描述算法，而是用别的描述工具（如流程图，专门的算法描述语言、自然语言）来描述算法。但不管用哪种工具来描述算
法，算法的设计一般都应从上述四种基本操作考虑，按解题要求从这些基本操作中选择合适的操作组成解题的操作序列。
②算法的控制结构
一个算法的功能不仅取决于所选用的操作，而且还与各操作之间的执行顺序有关。
算法中各个操作间的执行顺序称为算法的控制结构。
描述算法的工具通常有传统流程图、N-S结构化流程图、算法描述语言等。
一个算法一般都可以用顺序、选择（或称分支）、循环（也称重复）3种基本控制结构组合而成。
4、算法设计的基本方法 ①列举法 ②归纳法 ③递推 ④递归
⑤减半递推技术 ⑥回溯法
*考点2 算法的复杂度 重点
算法的复杂度主要包括：时间复杂度和空间复杂度。重点
1、算法的时间复杂度 重点
算法的时间复杂度：是指执行算法所需要的计算工作量。
解释：
为了能够比较客观地反映出一个算法的效率，在度量一个算法的工作量时，不仅应该与所使用的计算机、程序设计语言以及程序编制者无关，而且还应该与算法实现过程中的许多细节无关。因此，可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。 算法的工作量
基本运算反映了算法运算的主要特征，因此，用基本运算的次数来度量算法工作量是客观的也是实际可行的，有利于比较同一问题的几种算法的优劣。
如：在考虑两个矩阵相乘时，要以将两个实数之间的乘法运
算作为基本运算，而对于所用的加、减法运算可以忽略不计。
如：当需要在一个表中进行查找时，可以将两个元素之间的比较作为基本运算。
算法所执行的基本运算次数还与问题的规模有关。
如：两个20阶矩阵相乘与两个10阶矩阵相乘，所需要的基本运算（即两个实数的乘法）次数显然是不同的，前者所需要的运算次数更多。
例void mult(inta[], intb[], int&c[] ) {一// 以二维数组存储矩阵元素，c 为a 和b 的乘积两个矩阵相乘for(i=1; i<=n; ++i) { //此语句频度为：n+1for(j=1; j<=n; ++j) { //此语句频度为：n(n+1)c[i,j] = 0; //此语句频度为：nfor(k=1; k<=n; ++k) //此语句频度为：n(n+1)c[i,j] += a[i,k]*b[k,j]; //此语句频度为：n} //for基本操作:乘法操作} //mult223T(n)=2n3+3n2+2n+1=O(n3)时间复杂度为: n
3
因此，在分析算法的工作量时，还必须对问题的规模进行度量。
综上所述，算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数，即：
算法的工作量=O(n)
其中，n是问题的规模。
例如：两个n阶矩阵相乘所需要的基本运算（即两个实数的乘法）次数为n3，即计算工作量为n3，也就是时间复杂度为O(n3)。
在具体分析一个算法工作量时，还会存在这样的问题： 对于一个固定的规模，算法所执行的基本运算次数还可能与特定的输入有关，而实际上又不可能将所有情况下算法所执行的基本运算次数都列出来。
如：
在长度为n的一维数组中查找值为x的元素。 查找6，25，9 6 2 102 8 -3 0 23 25 若采用顺序搜索法，即从数组的第一个元素开始，逐个与被查值x进行比较。显然，如果第一个元素恰好为x，则只需要比较1次。但如果x为数组的最后一个元素，或者x不在数组中，则需要比较n次才能得到结果。因此，在这个问题的算法中，其基本运算（即比较）的次数与具体的被查值x有关。
在同一问题规模下，如果算法执行所需的基本运算次数取决于某一特定输入时，可以用以下两种方法来分析算法的工作量：
①平均性态 重点，记名词及概念即可 平均性态：用各种特定输入下的基本运算次数的加权平均值来度量算法的工作。
了解
设x是所有可能输入中的某个特定输入，p(x)是x出现的概率（即输入为x的概率），t(x)是算法在输入为x时所执行的基本运算次数，则算法的平均性态定义为：
A(n)=?p(x)t(x)
x?Dn其中Dn表示当规模为n时，算法执行时所有可能输入的集合。这个式子中的t(x)可以通过分析算法来加以确定；而p(x)必须由经验或用算法中有关的一些特定信息来确定，通常是不能解析地加以计算的。如果确定p(x)比较困难，则会给平均性态的分析带来困难。
②最坏情况复杂性 重点 最坏情况复杂性：在规模为n时，算法所执行的基本运算的最大次数。