第章数据结构和算法.docVIP

第2章 数据结构和算法 本章主要考察的内容是： 1 .算法的基本概念 算法的定义 算法的特点 算法的复杂度 2．数据结构的基本概念 3. 线性结构与非线性结构 (1) 线性表及其顺序存储结构 (2) 栈及其基本运算 (3) 队列及其基本运算 (4) 线性链表 4. 树的基本概念和特征 二叉树的基本概念及其特性 二叉树的遍历 5. 查找技术 (1) 顺序查找 (2) 二分法查找 6. 排序技术 (1)交换类排序法 (2)插入类排序法 (3)选择类排序法 历年的全国计算机等级考试的笔试中，数据结构和算法部分的分值约占10-15%，本章历年的考题分布情况如表2-1所示： 表2-1 程序设计基础部分历年考题分数分布表 考点内容 2004.09 2005.04 2005.09 2006.04 2006.09 小计 算法的定义 2 2 算法的特点 2 2 算法复杂度 2 4 2 2 10 栈、队列 2 2 4 2 10 数据结构 2 2 2 2 8 树的基本概念和特征 2 2 2 2 8 查找技术 4 2 4 4 14 排序技术 2 2 2 6 合计 10 14 12 10 14 60 由表2-1可知，在历年的笔试考试中，考试的关键点主要是算法、数据的存储结构、树和排序。 2.1.1算法 考点1:算法的基本概念 所谓算法是指对解题方案准确而完整的描述。 如果一个问题可以通过一个计算机程序，在有限的存储空间内运行有限长的时间而得到正确的结构，则称这个算法是可解的。算法既不是程序，也不是解题方法。程序可以作为算法的一种描述，由于在编写程序时要受到计算机系统运行环境的限制，因而，程序的编制一般不会优于算法的设计。 ⑴　算法的基本特征包括以下几点。 ①　可行性。 ②确定性。算法中每一步骤都必须有明确定义，不允许有模棱两可的解释，不允许有多义性。 ③???? 有穷性。算法必须能在有限的时间内做完，能在执行有限个步骤后终止，这包括合理的执行时间的含义。 ④???? 足够的情报。 (2)以下两个基本要素。 ①对数据的运算和操作。算法实际上是按照解题要求从环境能进行的所有操作中选择合适的操作所组成的一组指令序列。一个计算机系统能执行的所有指令的集合称为该计算机系统的指令系统。在一般的计算机系统中，基本操作包括算术运算、逻辑运算、关系运算和数据传输。 ②算法的控制结构。算法中各操作之间的执行顺序称为算法的控制结构。算法的控制结构给出了算法的基本框架，它不仅决定了算法中各操作的执行顺序，而且也直接反映了算法的设计是否符合结构化原则。一个算法一般都可以及顺序、选择、循环3种基本控制结构组合而成。算法设计的基本方法包括列举法、归纳法、递推、递归、递推技术、回溯法。 例2.1 (2005年4月填空题第5题) 问题处理方案的正确而完整的描述称为_______。 【答案】 算法 例2.2 在计算机中，算法是指_______。 A）查询方法 （B）加工方法 C）对解题方案的准确而完整的描述（D）排序方法 1” 说明。 C 例2.3 算法一般都可以用哪几种控制结构组合而成_______。 A） （B） （C） （D） 【解析】请参照本章“考点破解1”的说明。 D 例2.4 在下列选项中，哪个不是一个算法应该具有的酝酿特征_______。 A） （B） （C） （D） 【解析】算法的基本特性能般包括了确定性、可行性、有穷性和拥有足够的情报。 【答案】C 例2.5 下面关于递推和递推算法描述正确的是_______。 A）? （B）?递归算法和递推算法基本相同 （C）??递归算法执行效率比递推算法低 （D）??递推算法分为直接递推算法与间接递推算法 【解析】从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果的算法称为递推算法，递推算法实际上属于归纳法。人们为了降低问题的复杂度，一般总是将问题逐层分解，最后归纳为一些简单的问题，这个过程一直做下去，直到出现最简单的问题为止。有些实际问题，既可以归纳为递推算法，也可以归纳为递归算法，但递推和递归实现的方法大不一样。递推是从初始条件开始，逐次推出所要求的结果，而递归则是算法本身到达递归边界的。递归算法比递推简单，但递归算法执行效率较低。 【答案】C 自测题 可用“2.2过知精练”中的选择题第1～2题以及填空题1～2题进行自测。 考点2 :算法复杂度 算法的复杂度主要包括时间复杂度和窨复杂度。 1.?????? 算法的时间复杂 所谓算法的时间复杂度，是指执行算法所需要的计算工作量。 算法的工作量用算法所执行的基本运算次数来试题，而算