第2章 数据结构和算法(同名27760)

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

1、第2章数据结构和算法本章主要考察的内容是：1.算法的基本概念(1)算法的定义(2)算法的特点(3)算法的复杂度2．数据结构的基本概念3.线性结构与非线性结构(1)线性表及其顺序存储结构(2)栈及其基本运算(3)队列及其基本运算(4)线性链表4.树的基本概念和特征(1)二叉树的基本概念及其特性(2)二叉树的遍历5.查找技术(1)顺序查找(2)二分法查找6.排序技术(1)交换类排序法(2)插入类排序法(3)选择类排序法历年的全国计算机等级考试的笔试中，数据结构和算法部分的分值约占10-15%，本章历年的考题分布情况如表2-1所示：表2-1程序设计基础部分历年考题分

2、数分布表考点内容2004.092005.042005.092006.042006.09小计算法的定义22算法的特点22算法复杂度242210栈、队列224210数据结构22228树的基本概念和特征22228查找技术424414排序技术2226合计101412101460由表2-1可知，在历年的笔试考试中，考试的关键点主要是算法、数据的存储结构、树和排序。2.1.1算法考点1:算法的基本概念所谓算法是指对解题方案准确而完整的描述。如果一个问题可以通过一个计算机程序，在有限的存储空间内运行有限长的时间而得到正确的结构，则称这个算法是可解的。算法既不是程序，也不是解

3、题方法。程序可以作为算法的一种描述，由于在编写程序时要受到计算机系统运行环境的限制，因而，程序的编制一般不会优于算法的设计。⑴　算法的基本特征包括以下几点。①　可行性。②确定性。算法中每一步骤都必须有明确定义，不允许有模棱两可的解释，不允许有多义性。在2005年4月的考试中以选择题的形式考查了该考点内容。今年针对该考点出题的几率较高，题型可能是选择题也可能是填空题，考生应重点掌握该考点的相关概念。③    有穷性。算法必须能在有限的时间内做完，能在执行有限个步骤后终止，这包括合理的执行时间的含义。④    足够的情报。(2)以下两个基本要素。①对数据的运算和操

4、作。算法实际上是按照解题要求从环境能进行的所有操作中选择合适的操作所组成的一组指令序列。一个计算机系统能执行的所有指令的集合称为该计算机系统的指令系统。在一般的计算机系统中，基本操作包括算术运算、逻辑运算、关系运算和数据传输。②算法的控制结构。算法中各操作之间的执行顺序称为算法的控制结构。算法的控制结构给出了算法的基本框架，它不仅决定了算法中各操作的执行顺序，而且也直接反映了算法的设计是否符合结构化原则。一个算法一般都可以及顺序、选择、循环3种基本控制结构组合而成。算法设计的基本方法包括列举法、归纳法、递推、递归、递推技术、回溯法。例2.1(2005年4月填空

5、题第5题)问题处理方案的正确而完整的描述称为_______。【解析】所谓算法是指对解题方案的准确而完整的描述。【答案】算法例2.2在计算机中，算法是指_______。（A）查询方法（B）加工方法（C）对解题方案的准确而完整的描述（D）排序方法【解析】请参照配音“考点破解1”说明。【答案】C例2.3算法一般都可以用哪几种控制结构组合而成_______。（A）循环、分支、递归（B）顺序、循环、嵌套（C）循环、递归、选择（D）顺序、选择、循环【解析】请参照本章“考点破解1”的说明。【答案】D例2.4在下列选项中，哪个不是一个算法应该具有的酝酿特征_______。（A

6、）确定性（B）可行性（C）无穷性（D）拥有足够的情报【解析】算法的基本特性能般包括了确定性、可行性、有穷性和拥有足够的情报。【答案】C例2.5下面关于递推和递推算法描述正确的是_______。（A） 不会出现既可以归纳为递推算法，又可以归纳为递归算法的实际问题（B） 递归算法和递推算法基本相同（C）  递归算法执行效率比递推算法低（D）  递推算法分为直接递推算法与间接递推算法【解析】从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果的算法称为递推算法，递推算法实际上属于归纳法。人们为了降低问题的复杂度，一般总是将问题逐层分解，最后归纳为一些简单的问题

7、，这个过程一直做下去，直到出现最简单的问题为止。有些实际问题，既可以归纳为递推算法，也可以归纳为递归算法，但递推和递归实现的方法大不一样。递推是从初始条件开始，逐次推出所要求的结果，而递归则是算法本身到达递归边界的。递归算法比递推简单，但递归算法执行效率较低。【答案】C自测题可用“2.2过知精练”中的选择题第1～2题以及填空题1～2题进行自测。考点2:算法复杂度算法的复杂度主要包括时间复杂度和窨复杂度。1.      算法的时间复杂该考点的命题重点是“算法复杂度”的概念，出题类型以填空题居多。在2004年9月、2005年4月和2005年9月的考点中都考核了本考

8、点的相关知识。考生必须掌握该考点的相关