北航软件学院考研大纲(2)

四、树与二叉树

1．树与二叉树的基本概念，基本特征、名词术语；

2．完全二叉树与满二叉树的基本概念，二叉树的基本性质；

3．二叉树与树、树林之间的转换；

4．二叉树的顺序存储结构与二叉链表存储结构；

5．二叉树的前序遍历、中序遍历、后序遍历和按层次遍历，以及在二叉链表基础上各种遍历算法(重点为非递归算法)的设计与应用；

6．二叉排序树的基本概念、建立(插入)、查找以及平均查找长度ASL的计算；

7．哈夫曼(Huffman)树的基本概念，哈夫曼树的构造与带权路径长度(WPL)的计算。

五、图

1．图的基本概念、名词术语；

2．图的邻接矩阵存储方法和邻接表(含逆邻接表)存储方法的构造原理及特点；

3．图的深度优先搜索与广度优先搜索；

4．最小(代价)生成树、最短路径、AOV网与拓扑排序以及AOE网与关键路径的基本概念与求

解过程。

六、文件及查找

1．顺序查找法以及平均查找长度(ASL)的计算；