北京邮电大学2012年软件工程专业综合考研大纲

　　软件工程专业综合(数据结构、操作系统、计算机网络)考研大纲

　　第一部分 数据结构(60/150)

　　一、考试要求

　　要求考生比较系统地理解数据结构的基本概念和基本理论，掌握各种数据结构的特点和基本方法，着重考察考生综合运用所学知识分析问题和解决问题的能力。要求考生能够用C或C++语言描述数据结构中的算法。

　　二、考试内容

　　(一)绪论

　　数据结构的基本概念，数据的逻辑结构、存储结构;

　　算法的定义，算法的基本特征及算法分析的基本概念。

　　(二)线性表

　　线性关系、线性表的定义，线性表的基本操作;

　　线性表的顺序存储结构的构造原理;

　　对线性表实施的比较主要的操作(包括三种链表的建立、插入和删除、检索等)的算法设计。

　　(三)链表

　　单链表、双向链表和循环链表三种链表形式的存储结构和特点以及基本操作;

　　稀疏矩阵的存储结构和特点以及基本操作。

　　(四)栈和队列

　　栈的定义、结构特点及其存储方式(顺序存储与链接存储)和基本操作的实现算法;

　　队列的结构、特点及其存储方式(顺序存储与链接存储)和基本操作的实现算法。

　　(五)数组和串

　　串的基本概念、串的存储结构和相关的操作算法;

　　数组的存储结构，在顺序存储的情况下，数组元素与存储单元的对应关系;

　　字符串比较的基本算法(包括KMP算法)。

　　(六)递归

　　递归的基本概念和实现原理以及用递归的思想描述问题和书写算法的方法;

　　汉诺塔、迷宫等问题的递归解法;

　　用栈实现递归问题的非递归解法。

　　(七)树和森林

　　树的结构和主要概念，各种二叉树的结构及其特点;

　　二叉树的三种遍历方法的实现原理和性质，能将二叉树的遍历方法应用于求解二叉树的叶子结点个数、二叉树计数等问题，遍历的非递归实现方法;

　　线索化二叉树的结构和基本操作;

　　堆的原理和基本操作的实现方法;

　　森林的定义和存储结构，森林的遍历等方法的实现;

　　基于霍夫曼树生成霍夫曼编码的方法。

　　(八)集合和搜索

　　集合的基本概念和各种存储方法;

　　等价类的生成算法;

　　针对有序顺序表的折半搜索、斐波那契等搜索方法;

　　AVL树的定义和特点以及AVL树调整操作的实现原理;

　　比较优二叉树的构造原理和相关算法。

　　(九)图

　　图的各种基本概念和各种存储方式;

　　图的两种搜索方法和连通分量的生成方法;

　　两种比较小生成树的生成方法;

　　各种求比较短路径的方法;

　　用顶点表示活动和用边表示活动的两种网络结构特点和相关操作的实现算法。

　　(十)排序

　　插入排序法(含折半插入排序法)、选择排序法、泡排序法、快速排序法、堆积排序法、归并排序、基数排序等排序方法排序的原理、规律和特点;

　　各种排序算法的时空复杂度简单分析。

　　(十一)索引结构与散列

　　线性索引结构、倒排表、静态搜索树的结构和特点;

　　B树的结构和各种操作的实现算法;

　　散列的实现原理和各种操作的实现算法。

　　三、试卷结构：

　　考试题型：填空题、选择题、简答题、编程题