文档介绍：李赛红 2011-03
全国计算机等级考试 二级公共基础知识(一)
河海大学文天学院教育培训中心
数据结构的基本概念★★★★★
线性表的顺序存储
栈和队列★★★
算法基本概念及算法评价★★★★★
第一章数据结构与算法
树与二叉树★★★★★
查找与排序★★
线性表的链式存储
第一章数据结构与算法
算法基本概念及算法评价
算法 考点1 算法的定义
 算法是用来解决某个特定类型问题的有限运算序列。简单的说:算法就是解决问题的方法.
;
流程图是图形化的算法
第一章数据结构与算法
算法特征:
(1)有穷性:一个算法(对任何合法的输入)在执行有穷步后能够结束,并且在有限的时间内完成。
    (2)确定性:算法中的每一步都有确切的含义。
    (3)可行性:算法中的操作能够用已经实现的基本运算执行有限次来实现。
    (4)输入:一个算法有零个或者多个输入,零个输入就是算法本身缺定了初始条件。
    (5)输出:一个算法有一个或者多个输出,以反映出数据加工的结果。(拥有足够的情报)
第一章数据结构与算法
例1. 问题处理方案的正确而完整的描述称为______。
[2005年4月填空第5题]
例2. 以下叙述中正确的是  (A)用C语言实现的算法必须要有输入和输出操作  (B)用C语言实现的算法可以没有输出但必须要有输入  (C)用C程序实现的算法可以没有输入但必须要有输出  (D)用C程序实现的算法可以既没有输入也没有输出
[2005年9月选择题第13题]
例3. 算法具有五个特性,以下选项中不属于算法特性的是   (A)有穷性 (B)简洁性 (C)可行性 (D)确定性 
[2005年4月选择题第11题]
算法
C
B
第一章数据结构与算法
算法基本要素
对数据的运算和操作
算术运算
逻辑运算
关系运算
输入输入运算
算法的控制结构
顺序结构
选择结构
循环结构
第一章数据结构与算法
算法设计的基本方法
(1)列举法--- 根据提出的问题列举所有可能的情况,并用问题中给定的条件检验哪些是需要的而哪些是不需要的;
(2)归纳法--- 通过列举足够多的特殊情况发现其中一些规律,经过分析最终找出一般的关系;
(3)递推法--- 从已知的初始条件出发,逐次地推出所要求的各中间结果和最后结果;
(4)递归法--- 首先将问题逐层分解最后归结为一些最简单的问题,解决这些最简单问题后再沿着原来分解的逆过程逐步进行综合。
(5)减半递推技术--- 工程上常用的分治法,即将问题的规模减半来解,最后重复“减半”的过程;
(6)回溯法--- 在处理复杂数据结构时,通过对问题的分析找出一个解决问题的线索,然后沿着次线索逐步试探,若失败就逐步回退并换别的路线再进行试探;
第一章数据结构与算法
考点2 算法的复杂度
:(一个好的算法要达到的目标)
(1)正确性
(2)健壮性
(3)可读性
(4)效率与低存储量的要求
1)算法的时间复杂度
算法的执行时间=每条语句执行时间之和;
每条语句执行时间=语句执行(频度)次数* 语句执行一次所需时间;
独立于软硬件系统来分析算法的时间耗费
可以设每条语句执行时间均为一个单位时间
算法的执行时间=所有语句频度之和
第一章数据结构与算法
时间复杂度
算法所执行的运算次数是问题规模的函数(f(n))
空间复杂度
算法的空间复杂度是指执行这个算法所需要的内存空间
算
法
复
杂
度