2018年中国传媒大学硕士研究生考试程序设计树与二叉树

1、二叉树

（1）二叉树的定义及其主要特征：二叉树的五个性质及证明方法，并把这种方法推广到K叉树。

（2）二叉树的顺序存储结构和链式存储结构：二叉树的顺序存储结构和二叉链表、三叉链表存储结构的各自优缺点及适用场合。

（3）二叉树的遍历

二叉树的先序，中序和后序遍历算法以及按层次遍历。遍历是基础，在基本遍历算法的基础上实现二叉树的其它算法。

（4）线索二叉树的基本概念和构造

线索化算法，线索化后二叉树的遍历算法，基本线索二叉树的其它算法问题（如：查找某一类线索二叉树中指定结点的前驱或后继结点）。

（5）二叉排序树

二叉排序树的建立、查找、插入和删除算法，以及判断某棵二叉树是否二叉排序树的算法。

（1）树的概念和存储结构

（2）森林与二叉树的转换

（3）树和森林的遍历

树与森林的遍历，有两种遍历算法：先根与后根（对于森林而言称作：先序与中序遍历）。二者的先根与后根遍历与二叉树中的遍历算法是有对应关系的：先根遍历对应二叉树的先序遍历，而后根遍历对应二叉树的中序遍历。

1、图的概念、存储及基本操作

（1）邻接矩阵法

（2）邻接表法

2、图的遍历

深度优先搜索和广度优先搜索是图的两种基本的遍历算法以及基于这两种基本的遍历算法的程序设计。

3、图的基本应用及其复杂度分析

三、考试的基本题型

本试卷满分为150分。

主要题型有：选择题、综合应用题、程序设计题等。

本试卷满分为150分。

主要题型有：选择题、综合应用题、程序设计题等。

四、考试的形式及时间

笔试，不需要任何辅助工具。考试时间为三小时。

笔试，不需要任何辅助工具。考试时间为三小时。

2、树、森林