计算机二级公共基础知识(全).docx

《计算机二级公共基础知识(全).docx》由会员分享，可在线阅读，更多相关《计算机二级公共基础知识(全).docx（35页珍藏版）》请在第一文库网上搜索。

1、1.1算法考点1算法的基本概念计算机解题的过程事实上是在实施某种算法，这种算法称为计算机算法。算法(a1gorihm)是一组严谨地定义运算依次的规则，并且每一个规则都是有效的，同时是明确的；此依次将在有限的次数后终止。算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。1算法的基本特征可行性(effectiveness)：针对实际问题而设计的算法,执行后能够得到满足的结果。(2)确定性(definiteness)：算法中的每一个步骤都必需有明确的定义，不允许有模棱两可的说明和多义性。(3)有穷性(finiteness)：算法必需在有限时间内做完，即算法必需

2、能在执行有限个步骤之后终止。(4)拥有足够的情报：要使算法有效必需为算法供应足够的情报当算法拥有足够的情报时，此算法才最有效的；而当供应的情报不够时，算法可能无效。2算法的基本要素(1)算法中对数据的运算和操作：每个算法事实上是按解题要求从环境能进行的全部操作中选择合适的操作所组成的一组指令序列。计算机可以执行的基本操作是以指令的形式描述的。一个计算机系统能执行的全部指令的集合，称为该计算机系统的指令系统。计算机程序就是按解题要求从计算机指令系统中选择合适的指令所组成的指令序列在一般的计算机系统中，基本的运算和操作有以下4类：算术运算：主要包括加，减，乘，除等运算；逻辑运算：主要包括“及”，“

3、或”，“非”等运算；关系运算：主要包括“大于”，“小于”，“等于”，“不等于”等运算；数据传输：主要包括赋值，输入，输出等操作。(2)算法的限制结构：一个算法的功能不仅仅取决于所选用的操作，而且还及各操作之间的执行依次有关。算法中各操作之间的执行依次称为算法的限制结构。算法的限制结构给出了算法的基本框架，它不仅确定了算法中各操作的执行依次，而且也直接反映了算法的设计是否符合结构化原则。描述算法的工具通常有传统流程图，N-S结构化流程图，算法描述语言等。一个算法一般都可以用依次，选择，循环3种基本限制结构组合而成。(3)算法设计的基本方法计算机算法不同于人工处理的方法,下面是工程上常用的几种算法

4、设计,在实际应用时,各种方法之间往往存在着确定的联系。列举法列举法是计算机算法中的一个基础算法。列举法的基本思想是，依据提出的问题，列举全部可能的状况，并用问题中给定的条件检验哪些是须要的，哪些是不须要的。列举法的特点是算法比较简单。但当列举的可能状况较多时，执行列举算法的工作量将会很大。因此，在用列举法设计算法时，使方案优化，尽量削减运算工作量，是应当重点留意的。(2)归纳法归纳法的基本思想是，通过列举少量的特殊状况，经过分析，最终找出一般的关系。从本质上讲，归纳就是通过视察一些简单而特殊的状况，最终总结出一般性的结论。(3)递推递推是指从已知的初始条件动身，逐次推出所要求的各中间结果和最终

5、结果。其中初始条件或是问题本身已经给定，或是通过对问题的分析及化简而确定。递推木质上也属于归纳法，工程上很多递推关系式事实上是通过对实际问题的分析及归纳而得到的，因此，递推关系式往往是归纳的结果。对于数值型的递推算法必须要留意数值计算的稳定性问题。(4)递归人们在解决一些困难问题时，为了降低问题的困难程度(如问题的规模等)，一般总是将问题逐层分解，最终归结为一些最简单的问题。这种将问题逐层分解的过程，事实上并没有对问题进行求解，而只是当解决了最终那些最简单的问题后，再沿着原来分解的逆过程逐步进行综合，这就是递归的基本思想。递归分为直接递归及间接递归两种。(5)减半递推技术实际问题的困难程度往往

6、及问题的规模有着亲密的联系。因此，利用分治法解决这类实际问题是有效的。工程上常用的分治法是减半递推技术。所谓“减半”，是指将问题的规模减半，而问题的性质不变；所谓“递推”，是指重复“减半”的过程。(6)回溯法在工程上，有些实际问题很难归纳出一组简单的递推公式或直观的求解步骤，并且也不能进行无限的列举。对于这类问题，一种有效的方法是“试通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索逐步摸索，若摸索胜利，就得到问题的解，若摸索失败，就逐步回退，换别的路线再逐步摸索。4算法设计的要求通常一个好的算法应达到如下目标：(1)正确性(CorreCIneSS)正确性大体可以分为以下4个层次：程序

7、不含语法错误；程序对于几组输入数据能够得出满足规格说明要求的结果；程序对于细心选择的典型，苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果；程序对于一切合法的输入数据都能产生满足规格说明要求的结果。(2)可读性(readabi1ity)算法主要是为了使利入的阅读及沟通，其次才是其执行。可读性好有助于用户对算法的理解；晦涩难懂的程序易于隐藏较多错误，难以调试和修改。(3)健壮性(ro健StneSS)当输入数据非法时，算法也能适当地做出反应或进行处理，而不会产生稀里糊涂的输出结果。(4)效率及低存储量需求效率指的是程序执行时，对于同一个问题假如有多个算法可以解决，执行时间短的算法效率高

8、；存储量需求指算法执行过程中所须要的最大存储空间考点2算法的困难度1算法的时间困难度算法的时间困难度，是指执行算法所须要的计算工作量。同一个算法用不同的语言实现，或者用不同的编译程序进行编译，或者在不同的计算机上运行，效率均不同。这表明运用确定的时间单位衡量算法的效率是不合适的。撇开这些及计算机硬件，软件有关的因素，可以认为一个特定算法“运行工作量”的大小，只依靠于问题的规模(通常用整数n表示)，它是问题的规模函数。即算法的工作量=f(n)例如，在NXN矩阵相乘的算法中，整个算法的执行时间及该基本操作(乘法)重复执行的次数n3成正比，也就是时间困难度为n3,即f(n)=0(n3)在有的状况下，

9、算法中的基本操作重复执行的次数还随问题的输入数据集不同而不同0例如在起泡排序的算法中，当要排序的数组a初始序列为自小至大有序时，基本操作的执行次数为氏当时始序列为自大至小有序时，基本操作的执行次数为n(n-1)2o对这类算法的分析，可以接受以下两种方法来分析。(1)平均性态(AVerageBehavior)所谓平均性态是指各种特定输入下的基本运算次数的加权平均值来度量算法的工作量。设X是全部可能输入中的某个特定输入，p(x)是X出现的概率(即输入为X的概率)，t(x)是算法在输入为X时所执行的基本运算次数，则算法的平均性态定义为其中Dn表示当规模为n时，算法执行的全部可能输入的集合。最坏状况困

10、难性(WOrS1YaSeComp1exity)所谓最坏状况分析，是指在规模为n时，算法所执行的基本运算的最大次数。2算法的空间困难度算法的空间困难度是指执行这个算法所须要的内存空间。一个算法所占用的存储空间包括算法程序所占的空间，输入的初始数据所占的存储空间以及算法执行中所须要的额外空间。其中额外空间包括算法程序执行过程中的工作单元以及某种数据结构所须要的附加存储空间。假如额外空间量相对于问题规模来说是常数，则称该算法是原地(inp1ace)工作的。在很多实际问题中，为了削减算法所占的存储空间，通常接受压缩存储技术，以使尽量削减不必要的额外空间。考点3数据结构的定义数据结构(da1aStrUC

11、1Ure)是指相互之间存在一种或多种特定关系的数据元素的集合，即数据的组织形式。数据结构作为计算机的一门学科，主要探讨和探讨以下三个方面：数据集合中个数据元素之间所固有的逻辑关系，即数据的逻辑结构；(2)在对数据元素进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；(3)对各种数据结构进行的运算。探讨以上问题的日的是为了提高数据处理的效率,所谓提高数据处理的效率有两个方面：提高数据处理的速度；(2)尽量节约在数据处理过程中所占用的计算机存储空间。数据(data)：是对客观事物的符号表示，在计算机科学中是指全部能输入到计算机中并被计算机程序处理的符号的总称。数据元素(datae1em

12、ent)：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据对象(dataObjeCt)：是性质相同的数据元素的集合，是数据的一个子集。在一般状况下，在具有相同特征的数据元素集合中，各个数据元素之间存在有某种关系(即连续)，这种关系反映了该集合中的数据元素所固有的一种结构。在数据处理领域中，通常把数据元素之间这种固有的关系简单地用前后件关系（或直接前驱及直接后继关系）来描述。前后件关系是数据元素之间的一个基本关系,但前后件关系所表示的实际意义随具体对象的不同而不同。一般来说，数据元素之间的任何关系都可以用前后件关系来描述。1数据的逻辑结构数据结构是指反映数据元素之间的关系的数

13、据元素集合的表示。更通俗地说，数据结构是指带有结构的数据元素的集合。所谓结构事实上就是指数据元素之间的前后件关系。一个数据结构应包含以下两方面信息：（1）表示数据元素的信息；（2）表示各数据元素之间的前后件关系。数据的逻辑结果是对数据元素之间的逻辑关系的描述。它可以用一嘎数据元素的集合和定义在此集合中的若干关系来表示。数据的逻辑结构包括集合，线性结构，树型结构和图形结构四种。线性结构:数据元素之间构成一种依次的线性关系。树型结构：数据元素之间形成一种树型的关系数据的逻辑结构有两个要素：一是数据元素的集合，通常记为D;二是D上的关系，它反映了数据元素之间的前后件关系，通常记为R。一个数据结构可以

14、表示成B=（C,R）其中B表示数据结构。为了反映D中各元素之间的前后件关系，一般用二元组来表示。例如I,复数是一种数据结构，在计算机科学中，复数可取如下定义：B=（C,R）其中，C是含有两个实数的集合c1,c2;R是定义在集合C上的一种关系,其中有序偶表示CI是复数的实部，c2是复数的虚部。2数据的存储结构数据的逻辑结构在计算机存储空间中的存放形式，称为数据的存储结构（也称为数据的物理结构）。由于数据元素在计算机存储空间中的位置关系可能及逻辑关系不同，因此，为了表示存放在计算机存储空间中的各数据元素之间的逻辑关系（即前后件关系），在数据的存储结构中，不仅要存放各数据元素的信息，还须要存放各数据

15、元素之间的前后件关系的信息。一种数据的逻辑结构依据须要可以表示成多种存储结构，常用的结构有依次，链接,索引等存储结构而接受不同的存储结构，其数据处理的效率是不同的。因此，在进行数据处理是，选择合适的存储结构是很重要的。考点4数据结构的图形表示数据结构除了用二元关系表示外，还可以直观地用图形表示。在数据结构的图形表示中，对于数据集合D中的每一个数据元素用中间标有元素值的方框表示，一般称之为数据结点，并简称为结点；为了进一步表示各数据元素之间的前后件关系，对于关系R中的每一个二元组，用一条有向线段从前件结点指向后件结点。在数据结构中，没有前件的结点称为根结点；没有后件的结点称为终端结点（也称为叶子结点）。一个数据结构中的结点可能是在动态变化的。依据须要或在处理过程中，可以在一个数据结构中增加一个新结点（称为插入运算），也可以删除数据结构中的某个结点（称为删除运算）。插入及删除是对数据结构的两种基本运算。除此之外，对数据结构的运算还有查找，分类，合并，分解，复制和修改等。考点5线性结构及非线性结构假如在一个数据结构中一个数据元素都没有，则称该数据结构为空的数据结构。依据数据结构中各数据元素之间前后件关系的困难程度，一般将数据结构分为两大类型：线性结构及非线性结构。非空数据结构满足：有且只有一个根结点；(2