「计算机等级考试--二级公共基础知识汇总」

1、计算机等级考试二级公共基础知识计算机等级考试二级公共基础知识第第1 1章章 数据结构与算法数据结构与算法1.1.算法算法1.11.11 1 算法的基本概念算法的基本概念算法是指对解题方案的准确而完整的描述。简单地说,就是解决问题的操作步骤。值得注意的是，算法不等于数学上的计算方法，也不等于程序。在用计算机解决实际问题时，往往先设计算法,用某种表达方式（如流程图)描述，然后再用具体的程序设计语言描述此算法(即编程)。在编程时由于要受到计算机系统运行环境的限制,因此,程序的编制通常不可能优于算法的设计。1.1.1.11.1.1.1 算法的基本特征算法的基本特征一般来说,一个算法应具有以下个基本特征

2、。(1)可行性（effetees)：算法在特定的执行环境中执行，应当能够得出满意的结果，即必须有一个或多个输出。(2）确定性（efinnss):算法中的每一个步骤都必须有明确的定义,不允许有模棱两可的解释和多义性。（3)有穷性(finieness）:算法必需在有限时间内做完，即算法必需能在执行有限个步骤之后终止。（）拥有足够的情报:要使算法有效必需为算法提供足够的情报。当算法拥有足够的情报时,此算法才是有效的；而当提供的情报不够时，算法可能无效。.1.11.21.2 算法的基本要素算法的基本要素通常,一个算法由两种基本要素组成。对数据对象的运算和操作；算法的控制结构，即运算或操作时间的顺序。（

3、）算法中对数据的运算和操作在一般的计算机系统中，基本的运算和操作有以下4类,如表1-所示。表表1 14 4类基本的运算和操作类基本的运算和操作运算类操作实例型算术运算、a+、1逻辑运算与（&)、或()、非 （!)!、10、1&关系运算b、a= 、数据传输赋值、输入、输出a=0、b=3（2)算法的控制结构一个算法的功能不仅仅取决于所选用的操作,而且还与各操作之间的执行顺序有关。 算法中各操作之间的执行顺序称为算法的控制结构。算法的控制结构给出了算法的基本框架,它不仅决定了算法中各操作的执行顺序,而且也直接反映了算法的设计是否符合结构化原则。 描述算法的工具通常有传统流程图、 n-

4、s结构化流程图、算法描述语言等。一个算法一般都可以用顺序、选择、循环种基本控制结构组合而成。1 11.1.1.1. 算法设计的基本方法算法设计的基本方法虽然设计算法是一件非常困难的工作,但是算法设计也不是无章可循,人们经过实践，总结和积累了许多行之有效的方法。常用的几种算法设计方法有列举法、归纳法、递推法、递归法、减半递推技术和回溯法。1 11.41.4 算法设计的要求算法设计的要求通常一个好的算法应达到如下目标:(1）正确性(orretnes）正确性大体可以分为以下个层次：程序不含语法错误；程序对于几组输入数据能够得出满足规格说明要求的结果；程序对于精心选择的典型、苛刻而带有刁难性的几组输入

5、数据能够得出满足规格说明要求的结果；程序对于一切合法的输入数据都能产生满足规格说明要求的结果。(2)可读性（raablity）算法主要是为了方便人的阅读与交流，其次才是其执行。可读性好有助于用户对算法的理解;晦涩难懂的程序易于隐藏较多错误，难以调试和修改。()健壮性（rbunes)当输入数据非法时,算法也能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果。()效率与低存储量需求效率指的是程序执行时,对于同一个问题如果有多个算法可以解决， 执行时间短的算法效率高;存储量需求指算法执行过程中所需要的最大存储空间。1.11.12 2 算法的复杂度算法的复杂度算法的复杂度是算法效率的度量，是评价

6、算法优劣的重要依据。算法复杂度包括算法的时间复杂度和算法的空间复杂的。1.1.2.1.1.2. 算法的时间复杂度算法的时间复杂度算法的时间复杂度是指执行算法所需要的计算工作量。为了能够比较客观地反映出一个算法的效率， 在度量一个算法的工作量时,不仅应该与所使用的计算机、程序设计语言以及程序编制者无关 ,而且还应该与算法实现过程中的许多细节无关。算法的计算工作量是用算法所执行的基本运算次数来度量的，而算法所执行的基本运算次数是问题规模（通常用整数n表示)的函数。即算法的工作量（n)例如,在nn矩阵相乘的算法中， 整个算法的执行时间与该基本操作 （乘法)重复执行的次3数n 成正比,也就是时间复杂度

7、为n3，即f(n）（n3）在有的情况下，算法中的基本操作重复执行的次数还随问题的输入数据集不同而不同。例如在起泡排序的算法中，当要排序的数组初始序列为自小至大有序时，基本操作的执行次数为0；当初始序列为自大至小有序时,基本操作的执行次数为n（n-)/2。对这类算法,可以采用平均性态和最坏情况复杂性两种方法来分析。.1.2.2.1.2.2算法的空间复杂度算法的空间复杂度算法的空间复杂度是指执行这个算法所需要的内存空间。一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。其中额外空间包括算法程序执行过程中的工作单元以及某种数据结构所需要的

8、附加存储空间。如果额外空间量相对于问题规模来说是常数，则称该算法是原地（inplace）工作的。在许多实际问题中,为了减少算法所占的存储空间,通常采用压缩存储技术,以便尽量减少不必要的额外空间。1 12.12.1 数据结构的定义数据结构的定义数据结构是计算机科学与技术领域广泛使用的一个基本术语,用来反映数据的内部构成。 在给出数据结构的定义之前，我们先弄清楚几个概念。数据(data） ：是对客观事物的符号表示,在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素(dt lemen):是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。数据对象（dtaobe

9、ct):是性质相同的数据元素的集合，是数据的一个子集。简单地说, 数据结构是指相互关联的数据元素的集合,即数据的组织形式。所谓结构,就是指数据元素之间的前后件关系（或称直接前驱与直接后继关系） 。例如，在考虑一日三餐的时间顺序关系时,早餐是午餐的前件（或直接前驱),而午餐是早餐的后件 （或直接后继);同样,午餐是晚餐的前件， 晚餐是午餐的后件。又例如,在考虑学历的顺序关系时，小学是初中的前件，而初中是小学的后件。同样，初中是高中的前件，高中是初中的后件。前后件关系是数据元素之间的一个基本关系 ,但前后件关系所表示的实际意义随具体对象的不同而不同。一般来说,数据元素之间的任何关系都可以用前后件关

10、系来描述。数据结构的两个要素-数据和结构是紧密联系在一起的,数据是有结构的数据， 而不是无关联的、松散的;而结构就是数据元素间的关系,是由数据的特性所决定的。数据结构作为计算机的一门学科,主要研究和讨论以下三个方面:(1）数据集合中个数据元素之间所固有的逻辑关系，即数据的逻辑结构;(2）在对数据元素进行处理时，各数据元素在计算机中的存储关系,即数据的存储结构;（3）对各种数据结构进行的运算。讨论以上问题的目的是为了提高数据处理的效率，即提高数据处理的速度以及尽量节省在数据处理过程中所占用的计算机存储空间。1 1.1.1.1.1 数据的逻辑结构数据的逻辑结构由数据结构的定义可知,一个数据结构应包

11、含以下两方面信息:(）表示数据元素的信息；()表示各数据元素之间的前后件关系。在此定义中，并没有考虑数据元素的存储,所以上述的数据结构实际上是数据的逻辑结构。数据的逻辑结构是对数据元素之间的逻辑关系的描述，它可以用一个数据元素的集合和定义在此集合中的若干关系来表示。数据的逻辑结构有两个要素：一是数据元素的集合,通常记为d;二是上的关系，它反映了数据元素之间的前后件关系,通常记为r。一个数据结构可以表示成（,r)其中b表示数据结构。为了反映d中各数据元素之间的前后件关系,一般用二元组来表示。例如，如果把一日三餐看作一个数据结构,则可表示成b=(d，r)=早餐,午餐,晚餐=（早餐，午餐）,(午餐，晚餐）数据的逻辑结构包括线性结构、树型结构图、网状结构图和集合图4种。1.21.21.21.2 数据的存储结构数据的存储结构数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称数据的物理结构)。在进行数据处理时，被处理的各数据元素总是被存放在计算机的存储空间中,而且各数据元素在计算机存储空间中的位置关系与它们的逻辑关系可能不同。由于数据元素在计算机存储空间中的位置关系可能与逻辑关系不同， 因此,为了表示存放在计算机存储空间中的各数据元素之间的逻辑关系 （即前后件关系）,在数据的存储结构中，不仅要存放各数据元素的信息，还需要