2 2 2 2
log n 1 。
（5）满二叉树与完全二叉树 满二叉树是指这样的一种二叉树，除最后一层外，每一层上的所有结点都有两个子结点。 所谓完全二叉树是指这样的二叉树，除最后一层外，每一层上的结点数均达到最大值。在最 后一层上只缺少右边的若干结点。 （6）二叉树通常采用链式存储结构。 （7）二叉树的遍历： ①前序遍历（DLR）根结点-左子树-右子树； ②中序遍历（LDR）左子树-根结点-右子树； ③后序遍历（LRD）左子树-右子树-根结点。 9、查找技术有顺序查找、二分法查找。 （1）在下列两种情况下只能采用顺序查找法：①如果线性表为无序表；②即使是有序线性 表，如果采用链式存储结构，也只能用于顺序查找。 （2）二分法查找在最坏的情况下，只需要比较 10、排序技术 （1）交换排序法
2
log
2
n 次，而顺序查找需要比较 n 次。
By FangJun
A、冒泡排序法（需要比较次数为 n(n-1)/2、最好的情况下需要比较 0 次） ； B、快速排序法（比冒泡排序法快） 。 （2）插入排序法 A、简单插入排序法（最坏的情况下需要比较次数为 n(n-1)/2） ； B、希尔排序法（最坏的情况下需要比较
n
1 .5
次） ；
（3）选择类排序法包括简单选择排序法（最坏需要比较 n(n-1)/2 次） 、堆排序法（需要比较
n log
2
n 次） 。
注意：在序列基本有序的情况下，插入排序所用的时间最少。
3
By FangJun
第一章 数据结构与算法
1.1 算法的基本概念 1、算法是一系列解决问题的清晰指令（解决方案的准确而完整的描述） 。 2、算法的 4 个基本特征： 可行性、确定性、 有穷性、 拥有足够的情报（指的是输入和输出） 。 3、算法的两个基本元素： （1）数据的运算和操作（算术运算、逻辑运算、关系运算、数据运算（主要包括赋值、输 入、输出等操作） ） ； （2）算法的控制结构（顺序、选择、循环） 。 4、算法复杂度：衡量算法好坏的量度。 （1）算法的时间复杂度：是指执行算法所需要的计算工作量（即算法的运算次数） ； （2）算法的空间复杂度：是指执行这个算法所需要的存储空间（内存空间） 。 1.2 数据结构的基本概念 1、数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。 2、数据结构的内容： （1）逻辑结构：反映数据元素之间逻辑关系，从逻辑关系上描述数据与数据的存储无关， 独立于计算机； （2）数据的存储结构（物理结构） ：指数据的逻辑结构在计算机存储空间中的存放形式。 注意：①对于同一个逻辑结构，采用不同的存储结构，其数据处理的效率是不同的；②各数 据元素的计算机存储空间中的位置关系与它们的逻辑关系不一定相同。 （3）逻辑结构和存储结构的关系：①一种逻辑结构可以用不同的存储结构来实现；②存储 结构决定了算法的实现；③逻辑结构决定了算法的设计。 3、数据结构的分类：线性结构（线性表）与非线性结构。 （1）满足线性结构的两个条件：①有且只有一个根结点（没有前件的结点称为根结点） ；② 每一个结点最多有一个前件，也最多有一个后件。 （2）线性结构的操作：在一个线性结构中插入或删除任何一个结点后还应是线性结构。 4、线性表及其顺序存储结构 （1）线性表是最简单、最常用的一种线性数据结构； （2）线性表的长度是指星星表中结点的个数，当 n=0 时，称为空表； （3）通常定义一个一维数组来表示线性表的顺序存储空间； （4）顺序表的插入运算在最坏的情况下，N 个元素的线性表需要移动 N 次； （5）顺序表的删除运算在最坏的情况下，N 个元素的线性表需要移动 N-1 次。 5、栈（属于线性结构） （1）栈是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶，而不允 许插入与删除的另一端称为栈底； （2）栈特点是先进后出、后进先出（栈有记忆的功能） ； （3）栈有两种存储方法：一是顺序栈，二是链式栈； （4）栈的基本运算有三种：入栈、退栈和读栈。 6、队列及其基本运算 （1）队列是允许在一端进行插入、而在另一端进行删除的线性表； （2）允许插入的一端叫队尾（尾指针，rear） ，允许删除的一端叫队头（头指针，front） ； （3）队列的操作方法是：先进先出、后进后出； （4）确定循环队列中元素个数的方法如下：
1
By FangJun
设循环队列的容量为 M,如果 rear>front,则循环队列中的元素个数为 rear-front（负值）;如果 rear<front,则循环队列中的元素个数为 M+（rear-front） 。 注意：循环队列是一种顺序存储结构。 （5）线性表的顺序存储的缺点：①在插入和删除时需要移动元素（除栈和队列之外） ；②上 溢或下溢错误的出现，即存储空间不便于扩充；③不便于对存储空间的动态分配。 7、线性链表：是指线性表的链式存储结构 （1）在链式存储结构中，存储数据结构的存储空间可以是不连续的； （2）各结点的存储顺序与数据元素之间的逻辑关系可以不一致； （3）链式存储方式可以用于线性结构，也可用于非线性结构； （4）用链表表示线性表的优点是：便于插入和删除操作（不改变位置） 。 注意：顺序存储结构比链式存储空间更节省空间。 8、树与二叉树：树是结点的集合，非空二叉树的根结点数目是有且只有 1 个. （1）树是一种简单的非线性结构； （2）度：①在树结构中，一个结点所拥有的后件个数称为该结点的度；②在所有结点中的 最大的度称为树的度；③度为 0 的结点称为叶子结点；④树的最大层次称为树的深度。 （3）二叉树具有以下两个特点：①非空二叉树只有一个根节点；②每一个结点最多有两棵 子树，且分别称为该点的左子树和右子树。 （4）二叉树的性质： 性质 1：在二叉树的第 K 层上，最多有 2 K 1 性质 2：深度为 M 的二叉树最多有 2
M
（K≥个结点。
1 个结点。
性质 3：在任意一棵二叉树中，度为 0 的结点（即叶子结点）总是比度为 2 的结点多一个。 性质 4： 具有 n 个结点的二叉树， 其深度至少为 整数部分。 性质 5：具有 n 个结点的完全二叉树的深度为
log n 1 ,其中 log n表示取 log n 的