2018年福州大学数据结构与程序设计考研大纲

福州大学
2018 年硕士研究生入学考试专业课课程（考试）大纲
一、考试科目名称: 《数据结构与程序设计》
二、招生学院：数学与计算机科学学院
基本内容:
1、数据结构与算法引论：算法的基本概念、表达算法的抽象机制以及算法的计算复杂性
概念和分析方法。
2、表：抽象数据类型表的基本概念及其逻辑特征。实现抽象数据类型表的一般步骤及常
用的实现表的方法。
3、栈：抽象数据类型栈的基本概念及其逻辑特征。实现抽象数据类型栈的一般步骤及常
用的实现方法。
4、队列：抽象数据类型队列的基本概念及其逻辑特征。实现抽象数据类型栈的一般步骤
及常用的实现方法。
5、排序与选择：简单排序算法（冒泡排序、插入排序和选择排序）及快速排序算法、合
并排序算法的的基本思想；掌计数排序算法和桶排序算法等典型的线性时间排序算法
的设计思想；选择问题及相应的算法。
6、树：常用的非线性层次结构树以及作为抽象数据类型的树的一般操作和一些常用的表
示树的数据结构。树的定义、树的遍历和树的三种常用表示法。ADT 二叉树的概念及
实现方法。
7、图：抽象数据类型的图的一般操作和图的表示法。图的遍历、图的最短路径及图的最
小支撑树算法。二分图的概念及其相关的图匹配问题，最大匹配问题的增广路径算法。
8、集合：集合和以集合为基础的抽象数据类型的基本概念及其逻辑特征。
9、符号表：符号表的概念以及用数组、开散列、闭散列三种实现符号表的方法。
10、字典：字典的概念，用数组和二叉搜索树实现字典的方法，AVL 树的概念及相关运算。
11、优先队列：以集合为基础的抽象数据类型优先队列，以及优先级树、堆的概念及堆排
序算法。
12、并查集：以不相交的集合为基础的抽象数据类型并查集概念，并查集的实现方法及其
合并策略。路径压缩技术及其实现方法。
13、面向对象程序设计：C++语言基本成分、数据描述与基本操作；C++语言流程设计和模
块化设计；C++语言程序设计中的类与对象、继承与派生、多态性等基本概念和基本方
法。
参考书目(须与专业目录一致)(包括作者、书目、出版社、出版时间、版次)：
参考书目：
《数据结构（C 语言描述）》（修订版）王晓东编著电子工业出版社 2011 年
《C++程序设计教程（第二版）》，钱能编，清华大学出版社 2005 年
说明：1、考试基本内容：一般包括基础理论、实际知识、综合分析和论证等几个方面的内容。有
些课程还应有基本运算和实验方法等方面的内容。字数一般在 300 字左右。
2、难易程度：根据大学本科的教学大纲和本学科、专业的基本要求，一般应使大学本科毕业生中优
秀学生在规定的三个小时内答完全部考题，略有一些时间进行检查和思考。排序从易到难。