第1章 数据结构与算法

《第1章 数据结构与算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第1章数据结构与算法（13%）重要考点提示：1）算法复杂度。2）栈、队列、线性链表的基本概念3）二叉树的存储结构4）线性表、树的结点计算和遍历5）冒泡排序的最坏次数计算一、算法考点1算法的基本概念记一些概念即可1、算法：对解题方案的准确而完整的描述。重点2、算法的基本特征重点①可行性针对实际问题设计的算法，人们总是希望能够得到满意的结果。但一个算法又总是在某个特定的计算工具上执行的，因此算法在执行过程中往往要受到计算工具的限制，使执行结果产生偏差。算法与计算公式是有差别的，在设计一个算法时，必须考虑它的可行性，否则将得不到满意的结果。

2、②确定性算法的确定性是指算法中的每一个步骤必须有明确的定义，不能产生歧义。这一性质也反映了算法与数学公式的明显差别。③有穷性算法的有穷性，是指算法必须能在有限的时间内做完，即算法必须能在执行有限个步骤之后终止。算法的有穷性还包括合理的执行时间的含义，因为如果一个算法需要执行千万年，显然失去了价值。④拥有足够的情报一个算法是否有效，还取决为算法所提供的情报是否足够。通常，算法中的各种运算总是要施加到各个运算对象上，而这些运算对象又可能具有某种初始状态，这是算法执行的起点或是依据。因此，一个算法执行的结果总是与输入的初始数据有关，不同的输

3、入将会有不同的结果输出。当输入不够或输入错误时，算法本身也就无法执行或导致执行有错。一般来说，当算法拥有足够的情报时，此算法才是有效的，而当提供的情报不够时，算法可能无效。有的认为是：可行性、确定性、有穷性、有输入、有输出。3、算法的基本要素重点①算法中对数据的运算和操作②算法的控制结构可理解为：一个算法是由控制结构（顺序、分支和循环三种）和原操作（指固有数据类型的操作）构成的，则算法时间取决于两者的综合效果。即：算法=控制结构+原操作（固有数据类型的操作解释：了解①算法中对数据的运算和操作每个算法实际上是按解题要求，从环境能进行的操

4、作中选择合适的操作所组成的一组指令序列。因此，计算机算法就是计算机能处理的操作所组成的指令序列。通常，计算机可以执行的基本操作以指令形式来描述，所有指令的集合构成计算机指令系统。计算机程序就是按解题要求从计算机指令系统中选择合适的指令所组成的指令序列。在一般的计算机系统中基本的运算和操作有以下4类：算术运算、逻辑运算、关系运算、数据传输（如输入输出、赋值等）。计算机程序也可以作为算法的一种描述，但由于在编制计算机程序时，通常要考虑很多与方法和分析无关的细节问题（如语法规则），因此，在设计算法的一开始，通常并不直接用计算机程序来描述算法

5、，而是用别的描述工具（如流程图，专门的算法描述语言、自然语言）来描述算法。但不管用哪种工具来描述算法，算法的设计一般都应从上述四种基本操作考虑，按解题要求从这些基本操作中选择合适的操作组成解题的操作序列。②算法的控制结构一个算法的功能不仅取决于所选用的操作，而且还与各操作之间的执行顺序有关。算法中各个操作间的执行顺序称为算法的控制结构。描述算法的工具通常有传统流程图、N-S结构化流程图、算法描述语言等。一个算法一般都可以用顺序、选择（或称分支）、循环（也称重复）3种基本控制结构组合而成。4、算法设计的基本方法①列举法②归纳法③递推④递

6、归⑤减半递推技术⑥回溯法*考点2算法的复杂度重点算法的复杂度主要包括：时间复杂度和空间复杂度。重点1、算法的时间复杂度重点算法的时间复杂度：是指执行算法所需要的计算工作量。解释：为了能够比较客观地反映出一个算法的效率，在度量一个算法的工作量时，不仅应该与所使用的计算机、程序设计语言以及程序编制者无关，而且还应该与算法实现过程中的许多细节无关。因此，可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。算法的工作量基本运算反映了算法运算的主要特征，因此，用基本运算的次数来度量算法工作量是客观的也是实际可行的，有利于比较同一问题

7、的几种算法的优劣。如：在考虑两个矩阵相乘时，要以将两个实数之间的乘法运算作为基本运算，而对于所用的加、减法运算可以忽略不计。如：当需要在一个表中进行查找时，可以将两个元素之间的比较作为基本运算。算法所执行的基本运算次数还与问题的规模有关。如：两个20阶矩阵相乘与两个10阶矩阵相乘，所需要的基本运算（即两个实数的乘法）次数显然是不同的，前者所需要的运算次数更多。时间复杂度为:n3因此，在分析算法的工作量时，还必须对问题的规模进行度量。综上所述，算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数，即：

8、算法的工作量=O(n)其中，n是问题的规模。例如：两个n阶矩阵相乘所需要的基本运算（即两个实数的乘法）次数为n3，即计算工作量为n3，也就是时间复杂度为O(n3)。在具体分析一个算法工作量时，还会存在这样的问题：对于一个