《数据结构与程序设计》由会员分享，可在线阅读，更多相关《数据结构与程序设计（3页珍藏版）》请在金锄头文库上搜索。
1、福 州 大 学2012 年硕士研究生入学考试自命题科目考试大纲一、 考试科目名称: 数据结构与程序设计二、 招生学院和专业：数学与计算机科学学院 基本内容(可续页):1、 数据结构与算法概论：算法的基本概念、表达算法的抽象机制以及算法的计算复杂性概念和分析方法。数据类型、数据结构和抽象数据类型的基本概念以及这 3 个重要概念的区别和内在联系。采用 C/C+与自然语言相结合的方式描述算法的方法。2、 线性表：抽象数据类型表的基本概念及其逻辑特征。实现抽象数据类型的一般步骤。按照抽象数据类型设计和实现的一般性原则，常用的实现表的方法，如用数组实现表的方法、用指针实现表的方法、用间接寻址技术实现表的
2、方法、用游标实现表的方法、单循环链表和双链表以及表的搜索游标的实现方法和步骤。3、 栈：抽象数据类型栈的基本概念及其逻辑特征。按照抽象数据类型设计和实现的一般性原则，常用的用数组实现栈的方法和用指针实现栈的方法。以集合的等价类划分等问题为例讨论栈的应用方法。4、 队列：抽象数据类型队列的基本概念及其逻辑特征。按照抽象数据类型设计和实现的一般性原则，常用的用指针实现队列的方法和用循环数组实现队列的方法。以电路布线等问题为例讨论队列的应用方法。5、 集合：集合和以集合为基础的抽象数据类型的基本概念及其逻辑特征。如何用位向量和链表两种方式实现集合。6、 排序与选择：排序问题的提法及其实质，常用的简单
3、排序算法，如冒泡排序算法、插入排序算法和选择排序算法的设计思想与分析方法。快速排序算法的基本设计思想及其多方面的改进。合并排序算法的基本设计思想与分析方法。计数排序算法和桶排序算法等典型的线性时间排序算法的设计思想与分析方法，线性时间排序算法与基于比较的排序算法的主要差别和适用范围。与排序问题类似的选择问题及相应的算法。从平均情况和最坏情况 2 个不同侧面研究算法的设计思想及实现方法。7、 树：常用的非线性层次结构树以及作为抽象数据类型的树的一般操作和一些常用的表示树的数据结构。树的定义，树的前序遍历、中序遍历和后序遍历方法。常用的树的父结点数组表示法、树的儿子链表表示法和树的左儿子右兄弟表示
4、法。二叉树和 ADT二叉树的概念。二叉树的顺序存储结构、二叉树的结点度表示法和用指针实现二叉树的方法。线索二叉树结构。以信号传输网络中最优信号增强装置布局等问题为例讨论树结构在实际问题中的应用方法。8、 二叉搜索树：字典的概念，用数组和二叉搜索树实现字典的方法， AVL 树的概念及相关运算。9、 堆与优先队列：以集合为基础的抽象数据类型优先队列，以及优先级树、堆、左偏树和可并优先队列等概念。堆排序算法。10、 散列：符号表的概念以及用数组、开散列、闭散列三种实现符号表的方法。常用的散列函数构造方法，如：除余法、数乘法、平方取中法等以及主要的几种解决冲突的方法，如：线性探测法、二次探测法等。11
5、、 并查集：以不相交的集合为基础的抽象数据类型并查集概念，并查集的实现方法及其合并策略。路径压缩技术及其实现方法。12、 图：常用的表示复杂非线性关系的数据结构图，以及作为抽象数据类型的图的一般操作和表示图的数据结构。图的邻接矩阵表示及其实现方法、图的邻接表表示及其实现方法以及图的紧缩邻接表表示方法。遍历一个图的 2 个重要方法，即图的深度优先搜索和广度优先搜索算法。单源最短路径问题的 Dijkstra 算法和 Bellman-Ford 算法以及所有顶点对之间最短路径问题的 Floyd 算法。构造最小支撑树的 Prim 算法和 Kruskal算法。无圈有向图 DAG 的拓扑排序及其最短路径和最
6、长路径的求法。二分图的概念及其相关的图匹配问题，最大匹配问题的增广路径算法。13、 用 C+语言实现算法与数据结构 ：C+语言基本成分、数据描述与基本操作； C+语言流程设计和模块化设计；算法的基本控制结构（顺序、选择、循环结构设计）；函数的定义与使用；数组、指针与字符串的综合使用；结构体的定义和使用；面向对象程序设计中的类与对象、继承与派生、多态性等基本概念和基本方法。熟练掌握面向对象程序设计方法，利用线性表、栈、队列、集合、排序算法、树及二叉树、二叉搜索树、优先队列、散列、并查集、图解决实际问题。参考书目(须与专业目录一致)(包括作者、书目、出版社、出版时间、版次)：教材： 数据结构（ STL 框架 ） ，王晓东编，清华大学出版社C+程序设计教程，钱能编，清华大学出版社教学参考书：数据结构（C+版），王晓东编著，科学出版社数据结构严蔚敏编著 清华大学出版社。说明：1、考试基本内容：一般包括基础理论、实际知识、综合分析和论证等几个方面的内容。有些课程还应有基本运算和实验方法等方面的内容。2、难易程度：根据大学本科的教学大纲和本学科、专业的基本要求，一般应使大学本科毕业生中优秀学生在规定的三个小时内答完全部考题，略有一些时间进行检查和思考。
