二级公共基础知识考试要点：数据结构与算法

1.1算法

算法:是指对问题解决方案的准确完整的描述。
算法不等于程序，也不等于计算机方法。程序的编程不可能比算法的设计更好。
算法的基本特征:它是一组严格定义运算顺序的规则。每一条规则都是有效且明确的，这个序列将在有限的次数内终止。
特点包括:
(1)可行性；
(2)确定性，算法中的每一步都必须定义清楚，不允许有模棱两可的解释或歧义；
(3)作为有限性，算法必须在有限的时间内完成，算法可以在有限的步数后终止，包括合理执行时间的含义；
(4)掌握足够的信息。
算法的基本要素:一、数据对象的运算和操作；二是算法的控制结构。
指令系统:计算机系统可以执行的所有指令的集合。
基本运算和操作包括:算术运算、逻辑运算、关系运算和数据传输。
算法的控制结构:枚举法、归纳法、递归、递归、桶归约递归技术、回溯法。
算法复杂度:算法时间复杂度和算法空复杂度。
算法的时间复杂度是指执行算法所需的计算量。
算法间的复杂度空是指执行这个算法所需的内存空。

1.2数据结构的基本概念

数据结构研究的三个方面:
(1)数据集中数字元素之间的内在逻辑关系，即数据的逻辑结构；
(2)处理数据时，计算机中各数据元素的存储关系，即数据的存储结构；
(3)对各种数据结构的操作。
数据结构是指相互关联的数据元素的集合。
数据的逻辑结构包括:
(1)表示数据元素的信息；
(2)表示数据元素之间的上下文关系。
数据的存储结构包括顺序、链接、索引等。
线性结构条件:
(1)只有一个根节点；
(2)每个节点最多有一个前部，最多有一个后部。
非线性结构:不满足线性结构条件的数据结构。