训营，为学生引路，为学员服务！（四）树与二叉树1、二叉树（1）二叉树的定义及其主要特征：二叉树的五个性质及证明方法，并把这种方法推广到K叉树。（2）二叉树的顺序存储结构和链式存储结构：二叉树的顺序存储结构和二叉链表、三叉链表存储结构的各自优缺点及适用场合。（3）二叉树的遍历二叉树的先序，中序和后序遍历算法以及按层次遍历。遍历是基础，在基本遍历算法的基础上实现二叉树的其它算法。（4）线索二叉树的基本概念和构造线索化算法，线索化后二叉树的遍历算法，基本线索二叉树的其它算法问题（如：查找某一类线索二叉树中指定结点的前驱或后继结点）。（5）二叉排序树二叉排序树的建立、查找、插入和删除算法，以及判断某棵二叉树是否二叉排序树的算法。2、树、森林（1）树的概念和存储结构（2）森林与二叉树的转换（3）树和森林的遍历树与森林的遍历，有两种遍历算法：先根与后根（对于森林而言称作：先序与中序遍历）。二者的先根与后根遍历与二叉树中的遍历算法是有对应关系的：先根遍历对应二叉树的先序遍历，而后根遍历对应二叉树的中序遍历。（五）图1、图的概念、存储及基本操作（1）邻接矩阵法（2）邻接表法2、图的遍历深度优先搜索和广度优先搜索是图的两种基本的遍历算法以及基于这两种基本的遍历算法的程序设计。3、图的基本应用及其复杂度分析（1）最小（代价）生成树（2）最短路径（3）拓扑排序（4）关键路径（六）查找1、查找的基本概念2、顺序查找法、折半查找法3、散列（Hash）表及其查找4、查找算法的分析及应用（七）内部排序1、排序的基本概念2、插入排序3、冒泡排序
第2页共2页
f凯程考研集训营，为学生引路，为学员服务！4、简单选择排序5、希尔排序6、快速排序7、堆排序8、二路归并排序9、各种内部排序算法的比较各种排序方法的算法思想及程序设计、手工模拟排序过程、性能分析（包括时间复杂度、空间复杂度、稳定性）。10、内部排序算法的应用（八）进程管理1、进程概念、进程的状态与转换2、进程同步（1）进程同步的基本概念（2）实现临界区互斥的基本方法（3）信号量：PV原语的含义（4）经典同步问题：生产者消费者问题；读者写者问题；哲学家进餐问题。重点掌握PV操作的概念、流程，以及PV操作在同步与互斥问题中的应用。3、死锁的概念及处理策略三、考试的基本题型本试卷满分为150分。主要题型有：选择题、综合应用题、程序设计题等。四、考试的形式及时间笔试，r