【公共基础知识】数据结构与算法（备考一）
文/南城以南hong
这是一个知识付费，知识共享的年代。我将我每天学习的内容进行总结，既是对自己的巩固，也是对你的帮助。
南城以南hong
考点一:算法
（1）定义:算法是指解题方案的准确而完整的描述。算法不等于程序，也不等于计算方法。通常程序的编制不可能优于算法的设计。
（2）特征:
①有穷性:算法要在执行有穷步骤之后结束，且每一步都在有穷时间内完成。
②确定性:算法中每一条指令都有确切的含义，不存在多义性。
③可行性:指算法中的操作都可以通过已经实现的基本运算执行有限次来实现。
④拥有足够的情报
（3）基本要素（了解）
①对数据对象的运算和操作
②算法的控制结构
（4）算法设计的基本方法（了解）
列举法、归纳法、递推法、递归法、减半递推技术和回溯法。
（5）算法的复杂程度
①时间复杂程度:指执行算法所需要的计算工作量。算法的计算工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数。
②空间复杂度:算法的空间复杂度是指执行此算法期间所需要占用的内存空间。包括三部分:算法程序所占的空间、输入的初始数据所占的储存空间、算法执行过程中所需要的额外空间。
考点二:数据结构
（1）定义:数据结构是指反映数据元素之间关系的数据元素的集合。学习数据结构的目的就是提高数据处理的效率。
（2）数据的逻辑结构
①它指只反映数据元素之间逻辑关系的数据结构。它包括数据元素的集合和数据元素之间前后关系两个要素。
②例如:家庭成员数据结构可表示成B=( D, R) D=｛父亲，儿子，女儿｝ R=｛（父亲，儿子），（父亲，女儿）｝
（3）数据的存储结构
数据的存储结构又称为数据的物理结构，是指数据的逻辑结构在计算机存储空间中的存放方式。不仅要存放数据的信息，还要存放数据间的前后件的信息。采用不同的存储结构，其处理数据的效率是不同的。
（4）数据的逻辑结构和数据的存储结构不一定相同。一般来说，一种数据的逻辑结构根据需要可以表示成多种存储结构。
（5）图形表示
【公共基础知识】数据结构与算法（备考一）
如图，在右边，d1, d2无前件，称为根结点。d5, d6, d7无后件，称为终端结点（叶子结点）。
（6）线性结构与非线性结构。
①有且只有一个根结点，它无前件。
②有且只有一个终端结点，它无后件。
③除根结点和终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。
满足上述三个条件为线性结构，反之，不满足上述三个条件则为非线性结构。
考点三:线性表及其顺序存储结构
（1）在数据结构中线性表是最基本也是最常用的一种数据结构。
（2）线性表的顺序存储结构的基本特点
①所有元素所占的存储空间必须是连续的。
②所有元素在存储空间的位置是按逻辑顺序存放的。
(3)线性表的插入运算(略)
(4)线性表的删除运算(略)
【敬请期待下次更文】
