数据结构与算法.ppt

《数据结构与算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、李赛红2011-03全国计算机等级考试二级公共基础知识（一）河海大学文天学院教育培训中心1.数据结构与算法1.2数据结构的基本概念★★★★★1.3线性表的顺序存储1.4栈和队列★★★1.1算法基本概念及算法评价★★★★★第一章数据结构与算法1.6树与二叉树★★★★★1.7查找与排序★★1.5线性表的链式存储第一章数据结构与算法1.1算法基本概念及算法评价1.1.1算法考点1算法的定义算法是用来解决某个特定类型问题的有限运算序列。简单的说：算法就是解决问题的方法.eg.程序是用计算机语言表达的算法;流程图是图形化的算法第一章数据结构与算法算法特征：（1）有

2、穷性：一个算法（对任何合法的输入）在执行有穷步后能够结束，并且在有限的时间内完成。（2）确定性：算法中的每一步都有确切的含义。（3）可行性：算法中的操作能够用已经实现的基本运算执行有限次来实现。（4）输入：一个算法有零个或者多个输入，零个输入就是算法本身缺定了初始条件。（5）输出：一个算法有一个或者多个输出，以反映出数据加工的结果。（拥有足够的情报）第一章数据结构与算法例1.问题处理方案的正确而完整的描述称为______。[2005年4月填空第5题]例2.以下叙述中正确的是(A)用C语言实现的算法必须要有输入和输出操作(B)用C语言实现的算法可以没有输出

3、但必须要有输入(C)用C程序实现的算法可以没有输入但必须要有输出(D)用C程序实现的算法可以既没有输入也没有输出[2005年9月选择题第13题]例3.算法具有五个特性,以下选项中不属于算法特性的是(A)有穷性(B)简洁性(C)可行性(D)确定性[2005年4月选择题第11题]算法CB第一章数据结构与算法算法基本要素对数据的运算和操作算术运算逻辑运算关系运算输入输入运算算法的控制结构顺序结构选择结构循环结构第一章数据结构与算法算法设计的基本方法(1)列举法---根据提出的问题列举所有可能的情况，并用问题中给定的条件检验哪些是需要的而哪些是不需要的；(2)归

4、纳法---通过列举足够多的特殊情况发现其中一些规律，经过分析最终找出一般的关系；(3)递推法---从已知的初始条件出发，逐次地推出所要求的各中间结果和最后结果；(4)递归法---首先将问题逐层分解最后归结为一些最简单的问题，解决这些最简单问题后再沿着原来分解的逆过程逐步进行综合。(5)减半递推技术---工程上常用的分治法，即将问题的规模减半来解，最后重复“减半”的过程；(6)回溯法---在处理复杂数据结构时，通过对问题的分析找出一个解决问题的线索，然后沿着次线索逐步试探，若失败就逐步回退并换别的路线再进行试探；第一章数据结构与算法考点2算法的复杂度1.算

5、法设计的要求：（一个好的算法要达到的目标）(1)正确性(2)健壮性(3)可读性(4)效率与低存储量的要求2.算法效率的度量1)算法的时间复杂度算法的执行时间=每条语句执行时间之和；每条语句执行时间=语句执行（频度）次数*语句执行一次所需时间；独立于软硬件系统来分析算法的时间耗费可以设每条语句执行时间均为一个单位时间算法的执行时间=所有语句频度之和第一章数据结构与算法时间复杂度算法所执行的运算次数是问题规模的函数（f(n)）空间复杂度算法的空间复杂度是指执行这个算法所需要的内存空间算法复杂度第一章数据结构与算法例1.算法复杂度主要包括时间复杂度和【1】复杂

6、度。[2005年9月填空第2题]例2.对长度为N的线性表(一维数组)进行顺序查找,在最坏的情况下所需要的比较次数为[2005年4月选择第4题](A)log2n(B)n/2(C)n(D)n+1。空间复杂度C第二节数据结构基本概念1.2数据结构的基本概念1.2.1数据结构考点3数据结构的定义：数据结构(datastructure)是指相互之间存在一种或多种特定关系的数据元素的集合，即数据的组织形式。数据+关系数据结构学科，主要研究和讨论以下三个方面：(l)数据集合中个数据元素之间所固有的逻辑关系，即数据的逻辑结构；(2)在对数据元素进行处理时，各数据元素在计

7、算机中的存储关系，即数据的存储结构；(3)对各种数据结构进行的运算。第二节数据结构基本概念基本概念：（1）数据(data)：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。（2）数据元素(dataelement)：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。（3）数据对象(dataobject)：是性质相同的数据元素的集合。（数据元素是数据对象的一个实例）例如：所有书的书目信息为数据对象，每一条书目信息为数据元素。第二节数据结构基本概念（4）数据的逻辑结构：对数据元素之间逻辑关系的描述。一

8、个数据结构应该包含两方面的信息：数据元素的集合和定义在这个集合上的关系来表示.（