计算机等级考试二级公共基础知识
第1章数据结构与算法
11算法111算法的基本概念
算法是指对解题方案的准确而完整的描述。简单地说，就是解决问题的操作步骤。值得注意的是，算法不等于数学上的计算方法，也不等于程序。在用计算机解决实际问题时，往往先设计算法，用某种表达方式（如流程图）描述，然后再用具体的程序设计语言描述此算法（即编程）。在编程时由于要受到计算机系统运行环境的限制，因此，程序的编制通常不可能优于算法的设计。1111算法的基本特征一般来说，一个算法应具有以下4个基本特征。（1）可行性（Effective
ess）：算法在特定的执行环境中执行，应当能够得出满意的结果，即必须有一个或多个输出。（2）确定性（Defi
ite
ess）：算法中的每一个步骤都必须有明确的定义，不允许有模棱两可的解释和多义性。（3）有穷性（Fi
ite
ess）：算法必需在有限时间内做完，即算法必需能在执行有限个步骤之后终止。（4）拥有足够的情报：要使算法有效必需为算法提供足够的情报。当算法拥有足够的情报时，此算法才是有效的；而当提供的情报不够时，算法可能无效。1112算法的基本要素通常，一个算法由两种基本要素组成。对数据对象的运算和操作；算法的控制结构，即运算或操作时间的顺序。（1）算法中对数据的运算和操作在一般的计算机系统中，基本的运算和操作有以下4类，如表11所示。表114类基本的运算和操作运算类操作实例型算术运算＋、－、×、÷a＋b、3－1逻辑运算与（）或（‖）（！！1、1‖0、11、、非）关系运算＞＜＝≠ab、ac、b≠c数据传输赋值、输入、输出a0、b3（2）算法的控制结构一个算法的功能不仅仅取决于所选用的操作，而且还与各操作之间的执行顺序有关。算法中各操作之间的执行顺序称为算法的控制结构。算法的控制结构给出了算法的基本框架，它不仅决定了算法中各操作的执行顺序，而且也直接反映了算法的设计是否符合结构化原则。描述算法的工具通常有传统流程图、NS结构化流程图、算法描述语言等。一个算法一般都可以用顺序、选择、循环3种基本控制结构组合而成。1113算法设计的基本方法虽然设计算法是一件非常困难的工作，但是算法设计也不是无章可循，人们经过实践，总结和积累了许多行之有效的方法。常用的几种算法设计方法有列举法、归纳法、递推法、递归法、减半递推技术和回溯法。1114算法设计的要求通常一个好的算法应达到如下目标：（1）正确性（Correct
ess）
f正确性大r