公共基础知识总结--二级考试必看

《公共基础知识总结--二级考试必看》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章数据结构与算法1.1算法1．1．1算法：是指解题方案的准确而完整的描述。规定了解决某类问题所需的操作语句以及执行顺序使其能通过有限的指令语句，在一定时间内解决问题算法是一个操作序列，有限长度，目的是解决某类问题算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。1．算法特征包括：（1）可行性；（2）确定性，算法中每一步骤都必须有明确定义，不允许有模棱两可的解释，不允许有多

2、义性；（3）有穷性，算法必须能在有限的时间内做完，即能在执行有限的步骤后终止，包括合理的执行时间的含义；（4）拥有足够的情报。在设计一个算法时，必须要考虑算法的执行过程保证结果的可靠性。2．算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构通常，计算机可以以执行的基本操作是以指令的形式描述的。一个计算机系统能执行的所有指令的集合，称为计算机系统的指令系统。（1）计算机系统中的基本运算和操作包括：算术运算+-*/逻辑运算notandor关系运算<>!=数据传输赋值输入与输出（2）算法的控

3、制结构：顺序结构、选择结构、循环结构。3．算法基本设计方法：（计算机解题的过程实际上是在实施某种算法）1、列举法（列举所有解决方案）2、归纳法（特殊à一般）适合于列举量为无限的情况，通过列举少量的特殊情况，经过分析，最后找出一般的关系。3、递推（已知à未知）阶乘从已经的初始条件出发，逐次推出所要求的各中间结果和最后结果。4、递归（逐层分解）将一个复杂的问题归结为若干个较简单的问题，然后将这些较简单的每一个问题再归结为更简单的问题5、减半递推“减半”是指将问题的规模减半，而问题的性质不为，所谓“递推

4、”是指重复“减半”的过程6、回溯法找出一个解决问题的线索，然后沿着这个线索逐步多次“探、试”1．1．2算法复杂度算法的复杂度：一个算法所要付出的代价算法时间复杂度和算法空间复杂度是衡理算法好坏的。1．算法时间复杂度概念：算法时间复杂度是指执行算法所需要的计算工作量。（既算法的运算次数）含义：算法执行过程中所需要的基本运算次数影响计算工作量的主要因素：一、基本运算次数二、问题与规模二、时间复杂度的具体度量方法：在同一问题规模下，如果算法执行所需的基本运算次数取决于某一特定输入时，可以用以下两种方法分

5、析算法的工作量：（1）平均性态分析（2）最坏情况复杂性分析2．算法空间复杂度是指执行这个算法所需要的内存空间。一个算法所用的内存空间包括：1、算法程序所占的空间2、输入的初始数据所占的存储空间3、算法执行过程中的额外空间算法概念基本特征基本要索算法设计基本方法算法复杂度数据的运算和操作控制结构时间复杂度空间复杂度算法小结：1.2数据结构的基本基本概念张华男浙江汉数据：在计算机科学中指所有能输入到计算机中的并被计算机程序处理的符号的总称数据元素：数据的基本单位，在计算机程序中通常作为一个整体进行考虑

6、和处理。数据结构：是相互之间存在一种或多种特定关系的数据元素的集合数据结构研究的三个方面：（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。逻辑结构：春à夏à秋à冬父亲à儿子à女儿P7倒数第二段逻辑结构：数据元素之间的逻辑关系，从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。存储结构即物理结构：是指数据元素及其关系在计算机内存中的表示，即数据的逻辑结构在计算机放形

7、式存储空间中的存。在顺序存储时逻辑顺序与物理顺序是一致的链式存储是每一个数据项都有编号，例如表中的记录，每个记录都有记录号，可方便定位到每条记录，也可对表中的记录进行排序数据结构是指相互有关联的数据元素的集合。注意：对于同一个逻辑结构来说，采用不同的存储结构，其数据处理的效率是不同的。因此，在数据即：一般来说，人们不会同时处理特征完全不同且互相之间没有任何关系的各类数据元素，对于具有不同特征的数据元素总是分别进行处理。1．数据的逻辑结构包含：（1）表示数据元素的信息；（2）表示各数据元素之间的前后

8、件关系。其中数据元素之间的前后件关系是指它们的逻辑关系，与它们在计算机中的存储位置无关。2．数据的存储结构：P12一个数据结构中的各数据元素在计算机存储空间中的位置关系与逻辑关系不一定相同由于数据元素在计算机存储空间中的位置关系可能与逻辑关系不同，因此，为了表示存放在计算机存储空间中的各元素之间的逻辑关系（即前后件关系），在数据存储结构中，不仅要存储各数据元素的信息，还需要存放各数据元素之间的前后件关系的信息。逻辑结构与物理结构的关系A．一种逻辑结构可以用不同的物理结构来实现D1C