2016计算机二级公共基础

《2016计算机二级公共基础》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第1章数据结构与算法1.算法1.1算法1.1.1什么是算法算法是指对解题方案准确而完整的描述。简单地说，算法就是解决问题的操作步骤。计算机程序本质上就是一个算法，它告诉计算机确切的步骤来执行一个指定的任务。但是，算法不等于程序，也不等于数学上的计算方法。在用计算机解决实际问题时，往往先设计算法，用某种表达方式（如流程图）描述，然后再用具体的程序设计语言描述此算法（即编程）。但在编程时由于要受到计算机系统运行环境等的限制，所以程序的编制不可能优于算法的设计。1.算法的基本特征一个算法一般应具有以下几个基本特征。（1）可行性可行性是指算法在特定的执行环境中执行应当能够

2、得出满意的结果，保证每一个步骤必须能够实现，保证结果要能够达到预期的目的。一个算法，即使在数学理论上是正确的，但如果在实际的计算工具上不能执行，则该算法也是不具有可行性的。例如，一栋楼地上有10层，地下有负1层，该建筑的电梯只设有1到10层的而没有到负1层的电梯，我们乘电梯从1楼到5楼是可行的，从1楼到负1楼则是不可行的。（2）确定性算法的确定性表现在对算法中每一步的描述都是明确的，不允许有模棱两可的解释，也不允许有多义性，只要输入相同，初始状态相同，则无论执行多少遍，所得的结果都应该相同。如果算法的某个步骤有多义性，则该算法将无法执行。例如，开车到了十字路口需要

3、转弯时就要明确给出“左转”或“右转”的指令，而不是“转弯”这种没有明确方向的指令。（3）有穷性算法的有穷性是指算法能够在有限时间内完成，即执行有限步骤后能够终止。这其中也包括了合理的执行时间，如果一个算法执行需要耗费千万年，那么即使最终得出了正确结果，也失去了实际意义。例如，数学中的无穷级数，其表示只是一个计算公式，当n趋向于无穷大时，这将会是是无终止的过程，这样的算法是没有意义的。（4）拥有足够的情报一般来说，算法在拥有足够的输入信息和初始化信息时，才是有效的；当提供的情报不够时，算法可能无效。例如，a=3，b=5，求a+b+c的值，显然由于对c没有进行初始化，

4、无法计算出正确的答案。在特殊情况下，算法也可以没有输入。因此，一个算法有零个或多个输入。综上所述，算法是一个动态的概念，是一组严谨地定义运算顺序或操作步骤的规则，并且每一个规则都是有效的、明确的、能够在有限次执行后终止的。2.算法的基本要素一个算法通常由两种基本要素组成：一是对数据对象的运算和操作；二是算法的控制结构，即运算或操作间的顺序。（1）算法中对数据对象的运算和操作算法主要是指计算机算法。计算机算法就是计算机能执行的操作所组成的指令序列。不同的计算机系统，指令系统是有差异的，但一般的计算机系统中，都包括包括4类基本运算和操作：算术运算、逻辑运算、关系运算和

5、数据传输，如表1-1所示。（2）算法的控制结构一个算法所实现的功能不仅与其选用的操作有关，还与各个操作步骤之间的执行顺序有关。算法中各操作步骤之间的执行顺序称为算法的控制结构。算法一般是由顺序、选择（又称分支）和循环（又称重复）3种基本结构组合而成。描述算的的工具有传统流程图、N-S结构化流程图和算法描述语言等。3.算法设计的基本方法算法设计的基本方法有列举法、归纳法、递推法、递归法、减半递推技术和回溯法等。（1）列举法列举法是指针对待解决的问题，列举所有可能的情况，并用问题中给定的条件来检验哪些是必须的，哪些是不需要的。其特点是原理比较简单，只能适用于存在的可能

6、比较少的问题。例如，汽车行经十字路口，只有左拐、右拐、直行或调头4种可能情况。（2）归纳法归纳法是从特殊到一般的抽象过程。通过分析少量的特殊情况，从而找出一般的关系。归纳法比列举法更能反映问题的本质，并且可以解决无限列举量的情况，但是归纳法不容易实现。（3）递推法递推法本质上也属于归纳法，不过它是指从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果，就是一步一步的归纳。（4）减半递推法“减半”是指在不改变问题性质的前提下，将问题的规模减半；而“递推”则是不断重复减半的过程。（5）递归法递归法就是将一个复杂的问题逐层分解成若干个简单的问题，直接解决这些简单问

7、题后，再按原来分解的层次逐层向上，把简单的问题综合以解决复杂的问题。（6）回溯法回溯法就是把一个问题逐层分析，从上到下逐步去“试”，若成功，则得到问题的解；若失败，就逐步退回，换个路线再行试探，直到彻底解决问题。1.1.2算法复杂度一个算法的复杂度高低体现在运行该算法所需要的计算机资源的多少，所需的资源越多，就说明该算法的复杂度越高；反之，所需的资源越少，则该算法的复杂度越低。算法复杂度包括算法的时间复杂度和算法的空间复杂度。1.算法的时间复杂度算法的时间复杂度是指执行算法所需要的计算工作量。值得注意的是：算法程序执行的具体时间和算法的时间复杂度并不是一致的。算法

8、程序执行的