数据结构与算法
1.1 算法

 

考点一 算法的基本概念
算法是指解题方案的准确而完整的描述。
算法的基本特征：可行性、确定性、有穷性和拥有足够的情报
算法的两要素：一是对数据对象的运算和操作（算术、逻辑、关系运算等），二是算法的
控制结构。算法的主要特征是着重于算法的动态执行。算法的控制结构不仅决定了算法中
各操作的执行顺序，而且也直接反映了算法的设计是否符合结构化原则。
  描述算法的工具有传统的流程图、N-S 结构化流程图、算法描述语言等。
算法设计基本方法有列举法、归纳法、递推、递归、减半递推技术和回溯法。
*

 

考点二 算法的复杂度

（1）时间复杂度。是指执行算法所需要的计算工作量。而算法的工作量用算法所执行的基
本运算次数来度量，基本运算次数与问题的规模有关。
对于一个固定的规模，算法所执行的基本运算次数还与特定的输入有关。如果算法执行所
需的基本运算次数取决于某一特定输入时，可用平均性态分析和讨论算法在最坏情况下
的时间复杂度来分析。
（2）空间复杂度。指算法所需要的内存空间（算法程序、输入的初始数据所占的存储空间
等）。
1.2 数据结构的基本概念

 

考点三 什么是数据结构
数据结构是指相互关联的数据元素的集合。
数据的逻辑结构，反映数据元素之间逻辑关系的数据结构。
数据的存储结构，数据的逻辑结构在计算机存储空间中的存放形式。

 

考点四 数据结构的图形表示
数据结点。每一个数据元素用中间标有元素值的方框表示，称之为数据结点并简称结点。
为了进一步表示各数据元素之间的关系，用一条有向线段吧从前件结点指向后件结点。
没有前件的结点成为根结点；没有后件的结点称为终端结点（叶子结点）
*

 

考点五 线性结构和非线性结构

线性结构：
如果一个非空的数据结构满足下列两个条件：
有且只有一个根结点（有且只有一个终端结点）；
每一个结点最多有一个前件，也最多有一个后件。
则称该数据结构为线性结构。线性结构又称线性表。但特别需要说明的是，在一个线性结
构中插入或删除任何一个结点后还应该是线性结构。线性结构和非线性结构都可以是空的
数据结构。
矩阵、栈、队列都是线性表。（矩阵是较复杂的线性表，既可以把每一行看成一个数据元素，
也可以把每一列看成是一个数据元素）
*

 

考点七 线性表的顺序存储结构

线性表的顺序存储结构有以下两个基本特点：
线性表中所有元素所占的存储空间是连续的；
线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
在用一位数组存放线性表时，该一维数组的长度通常要定义得比线性表的实际长度大一
些。

 

考点八 顺序表的插入运算