计算机二级知识点

《计算机二级知识点》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、计算机二级知识点考点一，一．算法1.算法的基本特征：a，可行性；b，确定性；C，有穷性；d，拥有足够的情报；2.算法的基本要素：算法一般由两种基本要素构成a，对数据对象的运算和操作b，算法的控制结构；即运算和操作的时间顺序算法中对数据的运算和操作：算法就是按解题要求从指令系统中选择合适的指令组成的指令序列。因此计算机算法就是计算机能执行的操作所组成的指令序列，不同的计算机系统，其指令系统是有差异的，但一般的计算机系统中都包括的运算和操作有4类，即算法运算，逻辑运算，关系运算和数据传输。算法的控制结构：算法中各操作之间的执行顺序称为算法的控制结构。算法的功能不仅

2、取决于所选的操作；还与各操作之间的执行顺序有关。基本的控制结构包括顺序结构，选择结构和循环结构。3.算法设计的基本方法算法设计的基本方法有列举法，归纳法，递归法，递推法，减半递推技术和回溯法。二．算法复杂度（算法的复杂度主要包括时间复杂度和空间复杂度）1，算法的时间复杂度：所谓算法的时间复杂度，是指执行算法所需要的计算工作量。一般情况下，算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题的规模函数，即，算法的工作量=f（n）；其中n是问题的规模。这个表达式表示随着问题规模n的增大，算法执行时间的增长率和f（n）的增长率相同。在同一问

3、题规模下，如果算法执行所需的基本运算次数取决于某一特定输入时可以用两种方法来分析算法的工作量：平均性态分析和最坏情况分析。2.算法的空间复杂度。一个算法的空间复杂度；一般是指执行这个算法所需要的内存空间。算法执行期间所需要的存储空间包括3部分A，算法程序所占的空间B，输入的初始数据所占的存储空间C，算法执行过程中所需要的额外空间在许多实际问题中为了减少算法所占的存储空间，通常采用压缩存储技术。考点二数据结构的基本概念1.数据结构是指相互有关联的数据元素的集合，即数据的组织形式。（1）数据的逻辑结构。所谓数据的逻辑结构，是指反映数据元素之间逻辑关系（及前，后件关

4、系）的数据结构。它包括数据元素的集合和数据元素之间的关系。（1）数据的存储结构。数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称为数据的物理结构）。而采用不同的存储结构，其数据处理的效率是数据结构的存储方式有顺序存储方法，链式存储方法，索引存储方法和散列存储方法。不同的。因此，在进行数据处理时，选择合适的存储结构是很重要的。数据结构研究的内容主要包括3个方面：A数据集合中各数据元素之间的逻辑关系，即数据的逻辑结构；B在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；2.数据结构的图形表示数据元素之间的最基本的关系是前后件关

5、系，即每一个二元组，都可以用图形来表示。用中间标有元素值的方框表示数据元素，一般称之为数据结点，简称结点。对于每一个二元组，用一条有向线段从前件指向后件。用图形表示数据结构具有直观易懂的特点，在不引起歧义的情况下，前件结点到后件结点的连线上的箭头可以省去。例如，树形结构中，通常是用无向线段来表示前、后件关系的。3.线性结构和非线性结构根据数据结构中各数据元素之间前后关系的复杂程度，一般将数据结构分为两大类型，即线性结构和非线性结构。如果一个非空的数据结构满足有且只有一个根结点，并且每个结点最多有一个直接前驱或直接后继，则称该数据结构为线性结构，又称线性表。不满

6、足上述条件的数据结构称为非线性结构。小提示需要注意的是，在一个线性结构中插入或删除任何一个结点后还应该是线性结构，否则，不能称之为线性结构。考点三线性表及其顺序存储结构在数据结构中，线性表是最简单的也是最常用的一种数据结构。线性表是由n（n>=0)个数据a1，a2.....an组成的一个有限序列，除表中的第一个元素外，其他元素有且只有一个前件，除了最后一个元素外，其他元素有且只有一个后件。线性表要么是个空表，要么可以表示为（a1a2...an)其中ai（i=1,2，....，n）是线性表的数据元素，也称为线性表的一个结点。每个元素的具体含义，在不同的情况下各不

7、相同，它可以是一个数后或一个字符，也可以是一个具体的事物，甚至其他更复杂的信息。但需要注意的是同一线性表中的数据元素具有相同的特征，即属于同一数据对象。小提示非空线性表具有以下一些结构特征：A有且只有一个根结点，即头结点，它无前件；B有且只有一个终结点，即尾结点，它无后件；C除头结点和尾结点外，其他所有结点有且只有一个前件，也有且只有一个后件。结点的个数n称为线性表的长度，当n=0时，称为空表。2.线性表的顺序存储结构将线性表中的元素一个接一个地存储在一片相邻的存储区域中。这种顺序表示的线性表也称为顺序表。线性表的顺序存储结构具有以下两个基本特点A元素所占的存

8、储空间是连续的B元素在存储空间的位置是