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

福州大学

一、考试科目名称:数据结构与程序设计

二、招生学院：数学与计算机科学（软件）学院

基本内容:

1、数据结构与算法引论：算法的基本概念、表达算法的抽象机制以及算法的计算复杂性概念和分析方法。

2、表：抽象数据类型表的基本概念及其逻辑特征。实现抽象数据类型表的一般步骤及常用的实现表的方法。

3、栈：抽象数据类型栈的基本概念及其逻辑特征。实现抽象数据类型栈的一般步骤及常用的实现方法。

4、队列：抽象数据类型队列的基本概念及其逻辑特征。实现抽象数据类型栈的一般步骤及常用的实现方法。

5、排序与选择：简单排序算法（冒泡排序、插入排序和选择排序）及快速排序算法、合并排序算法的的基本思想；掌计数排序算法和桶排序算法等典型的线性时间排序算法的设计思想；选择问题及相应的算法。

6、树：常用的非线性层次结构树以及作为抽象数据类型的树的一般操作和一些常用的表示树的数据结构。树的定义、树的遍历和树的三种常用表示法。ADT二叉树的概念及实现方法。

7、图：抽象数据类型的图的一般操作和图的表示法。图的遍历、图的最短路径及图的最小支撑树算法。二分图的概念及其相关的图匹配问题，最大匹配问题的增广路径算法。

8、集合：集合和以集合为基础的抽象数据类型的基本概念及其逻辑特征。

9、符号表：符号表的概念以及用数组、开散列、闭散列三种实现符号表的方法。

10、字典：字典的概念，用数组和二叉搜索树实现字典的方法，AVL树的概念及相关运算。

11、优先队列：以集合为基础的抽象数据类型优先队列，以及优先级树、堆的概念及堆排序算法。

12、并查集：以不相交的集合为基础的抽象数据类型并查集概念，并查集的实现方法及其合并策略。路径压缩技术及其实现方法。

13、面向对象程序设计：C++语言基本成分、数据描述与基本操作；C++语言流程设计和模块化设计；C++语言程序设计中的类与对象、继承与派生、多态性等基本概念和基本方法。

参考书目(须与专业目录一致)(包括作者、书目、出版社、出版时间、版次)：

参考书目：
《数据结构（C语言描述）》（修订版）王晓东编著电子工业出版社 2011年

《C++程序设计教程（第二版）》，钱能编，清华大学出版社 2005年