国家计算机公共基础知识(B).docVIP

公共基础知识 第一章 数据结构与算法 1.1 算法 1. 算法：所谓算法是指解题方案的准确而完整的描述。 对于一个问题，如果可以通过一个计算机程序．在有限的存储空间内运行有限长的时间而得到正确的结果，则称这个问题是算法可解的。但算法不等于程序，也不等于计算方法。当然，程序也可以作为算法的一种描述，但程序通常还需考虑很多与方法和分析无关的细节问题，这是因为在编写程序时要受到计算机系统运行环境的限制。 算法实际上是一种抽象的解题方法，它具有动态性。作为一个算法．一般应具有以下几个基本特征。 (1) 可行性 算法的可行性主要包括两个方面。一是算法中的每一个步骤必须是能实现的。一是算法执行的结果要能达到预期的目的。 (2) 确定性 算法的确定性，是指算法中的每一个步骤都必须是有明确定义的，不允许有模棱两可的解释，也不允许有多义性。 (3) 有穷性 算法的有穷性，是指算法必须能在有限的时问内做完．即算法必须能在执行有限个步骤之后终止。 算法的有穷性还应包括合理的执行时间的含义。因为，如果一个算法需要执行千万年，也失去了实用价值。 (4) 拥有足够的情报 一个算法是否有效，还取决于为算法所提供的情报是否足够。通常，算法中的各种运算总是要施加到各个运算对象，而这些运算对象又可能具有某种初始状态，这是算法执行的起点或是依据。因此，一个算法执行的结果总是与输入的初始数据有关，不同的输入将会有不同的结果输出。当输入不够或输入错误时，算法本身也就无法执行或导致执行有错。一般来说，当算法拥有足够的情报时，此算法才是有效的，而当提供的情报不够时，算法并不有效。 综上所述，所谓算法，是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的．且是明确的，此顺序将在有限的次数下终止。 2. 算法复杂度：算法的复杂度主要包括时间复杂度和空间复杂度。 (1) 算法的时间复杂度 算法的时间复杂度是指执行算法所需要的计算工作量。 算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数，即： 算法的工作量= 其中n是问题的规模。 在同一问题规模下，如果算法执行所需的基本运算次数取决于某特定输入时，可以用以下两种方法来分析算法的工作量。 平均性态分析，是指用各种特定输入下的基本运算次数的带权平均值来度量算法的工作量。算法的平均性态定义为： 其中：x是所有可能输入中的某个特定输入，p(x)是x出现的概率(即输入为x的概率)，t(x)是算法在输入为x时所执行的基本运算次数，Dn表示当规模为n时，算法执行时所有可能输入的集合。 最坏情况分析，是指在规模为n时，算法所执行的基本运算的最大次数。它定义为： 显然，W(n)的计算要比A(n)的计算方便得多。由于W(n)实际上是给出了算法工作量的一个上界，因此，它比A(n)更具有实用价值。 (2)算法的空间复杂度 一个算法的空间复杂度．一般是指执行这个算法所需要的内存空间。 一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。其中额外空间包括算法程序执行过程中的工作单元以及某种数据结构所需要的附加存储空间。如果额外空间量相对于问题规模来说是常数，则称该算法是原地(in place)工作的。存许多实际问题中，为了减少算法所占的存储空间，通常采用压缩存储技术，以便尽量减少不必要的额外空间。 1.2 数据结构 1. 数据结构的基本概念 数据结构是指反映数据元素之间关系的数据元素集合的表示。通俗地说，数据结构是指带有结构的数据元素的集合。 (1) 数据的逻辑结构：一般情况下，在具有相同特征的数据元素集合中，各个数据元素之间存在有某种关系，这种关系反映了该集合中的数据元素所固有的种结构。在数据处理领域中，通常把数据之间的这种固有的关系简单地用前后关系（或直接前驱与直接后继关系）来描述。 所谓数据的逻辑结构，是指反映数据元素之间逻辑关系的数据结构。 数据的逻辑结构有两个要素：一是数据元素的集合，通常记为D；二是D上的关系，它反映了D中各数据元素之间的前后件关系，通常记为R。即一个数据结构可以表示成 B=（R，D） 其中B表示数据结构。为了反映D中各数据元素之间的前后件关系，一般用二元组来表示。例如，假设a与b是D中的两个数据，则二元组(a，b)表示a是b的前件，b是a的后件。这样，在D中的每两个元素之间的关系都可以用这种二元组来表示。 例如，一年四季的数据结构可以表示成 B=（R，D） D={春，夏，秋，冬} R={（春，夏），（夏，秋），（秋，冬）} 家庭成员数据结构可以表示成 B=（R，D） D={父亲，儿子，女儿} R={（父亲，儿子），（父亲，女儿