文档介绍：全国计算机等级考试二级教程
——二级公共基础知识
数据结构与算法
(2008年版)
赵国瑞
第1页
第1章数据结构与算法
算法是指解题方案的准确而完整的描述。
所谓算法,是一组严谨地定义运算顺序的规则,并且每一个规则都是有效的,且是明确的,此顺序将在有限的次数下终止。
算法
第2页
(1)可行性。针对实际问题而设计的算法,执行后能够得到满意的结果。
(2)确定性。每一条指令的含义明确,无二义性。并且在任何条件下,算法只有唯一的一条执行路径,即相同的输入只能得出相同的输出。
(3)有穷性。算法必须在有限的时间内完成。有两重含义,一是算法中的操作步骤为有限个,二是每个步骤都能在有限时间内完成。
(4)拥有足够的情报。一个算法执行的结果总是与输入的初始数据有关,不同的输入将会有不同的结果输出。当输入不够或输入错误时,算法将无法执行或执行有错。一般说来,当算法拥有足够的情报时,此算法才是有效的;而当提供的情报不够时,算法可能无效。
算法的基本特征
第3页
(1)算法中对数据的运算和操作
包括算术运算、逻辑运算、关系(比较)运算、数据传输(赋值、输入、输出等)
算法的设计一般是按解题要求选择适当的操作组成解题的操作序列。
(2)算法的控制结构
算法中各操作之间的执行顺序称为算法的控制结构。
算法可以用传统流程图、N-S结构化流程图、算法描述语言等描述。
一个算法可以用顺序、选择、循环三种基本控制结构组合而成。
算法的基本要素
第4页
计算机解题的过程实际上就是实施某种算法,这种算法称为计算机算法。它与人工算法不同。
算法设计就是对给定的问题设计出解决它的有效算法。
常用的算法设计方法有:穷举法、归纳法、递推法、递归法、减半递推技术、回溯法、迭代法、分治法等。
穷举法(列举法):
穷举法是对可能的情况按某种顺序逐一列举、检验,从中找出符合要求的解。经常用于解决“是否存在”或者“有多少种可能”等类型的问题。
例如,“百钱百鸡”问题,是我国古代数学家一道解不定方程的问题。设公鸡每只5元,母鸡每只3元,小鸡每3只1元。要用100元钱买100只鸡,问公鸡、母鸡和小鸡各买多少只。
在用穷举法设计算法时,要注意方案优化,减少列举量。
算法设计基本方法
第5页
归纳法:
归纳法是通过从少量简单而特殊的情况中找出一般关系。归纳是一种抽象。
归纳出的结论还只是一种猜测,必须通过证明才能知道是否正确或错误。但是,常有得不到证实对错的情况。
例如,等差数列求和公式的证明。
递推法:
递推法是利用问题本身所具有的某种递推关系求问题解的一种方法。
递推法从已知的初始条件出发,逐次推出所要求的各中间结果和最后结果。递推本质上属于归纳法。
例如,数学和工程中的递推关系。
数值型的递推算法必须注意其计算的稳定性。
第6页
递归法:
递归过程是将一个复杂的问题,归结为若干个较简单:的问题,然后再将这些较简单的问题归结为简单的问题,直到最简单的问题为止。
例如,计算n!可归结为n乘以(n-1)!,直到1!或者0!为止。1!或者0!都等于1。
递归分为直接递归和间接递归。
递归算法的执行效率较低。递推本质上也属于归纳法。
减半递推技术:
减半递推技术是一种分治法。分治法的基本思想是把一个大问题分解为一些较小的问题,然后由小问题的解方便地构造出大问题的解。在很多领域应用此方法。
“减半”是指将问题的规模减半而问题的性质不变。
“递推”是指重复“减半”的过程。
例如,二分法求方程的根。
第7页
二分法求方程的根。
设方程f(x) =0且f(a)与f(b)异号,则f(x)在区间[a,b]上必有实根。
(1)取区间的中点c←(a+b)/2;
(2)如果f(c)=0,则c即为所求,算法结束;
(3)如果f(a)f(c)<0,则b←c;
否则如果f(b)f(c)<0,则a←c;
(4)如果|a-b|<ε,则取(a+b)/2为根,算法结束;否则转步骤(1)。
第8页
回溯法:
回溯法也称为试探法,该方法首先放弃关于问题规模大小的限制,并将问题的候选解按某种顺序逐一枚举和检验。当发现当前候选解不可能是解时,就选择下一个候选解;如果当前候选解除了还不满足问题规模要求外,满足所有其它要求时,继续扩大当前候选解的规模,并继续试探。如果当前候选解满足包括问题规模在内的所有要求时,该当前候选解就是问题的一个解。在上述求解的描述中,放弃当前候选解,去寻找下一个候选解的过程称为回溯。扩大当前候选解的规模并继续求解的过程称为向前试探。
第9页
包括时间复杂度和空间复杂度。
1、算法时间复杂度是指执行算法所需要的计算工作量,可以用执行算法的过程中所需基本运算的执行次数来度量。如,矩阵相乘时的乘法运算次数,查找时的比较运算次