厦门理工学院2019年专业学位硕士研究生复试考试专业课课程考试大纲
一、考试科目名称:数据结构与算法
二、招生系部和专业：
考试要求：
要求考生能比较全面的理解与掌握数据结构的基本概念、基本原理和基本方法，掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度及空间复杂度的分析;能够根据数据结构基本原理和方法进行问题的分析与求解，具备采用C或C++语言设计与实现算法的能力。
考试题型及比例：
分析运算题+算法设计(100%)
基本内容及范围：
第一章引论
一、考核知识点
数据结构,数据类型,抽象数据类型基本概念;算法分析基本概念;算法复杂度基本概念;常见基本算法的时间复杂度分析;时间复杂度的几种表示法;
二、考核要求
1、了解数据、数据结构、抽象数据类型以及算法等概念的确切含义;
2、熟悉数据逻辑结构、存贮结构等概念;
3、掌握算法复杂度分析的基本概念及分析方法;
第二章线性表
一、考核知识点
线性表的逻辑结构定义、基本操作和在两种存储结构中基本操作的实现;链表;用线性表表示一元多项式及实现稀疏多项式的相加等运算。
二、考核要求
1、了解线性表的概念
2、掌握顺序表上各种运算的实现方法
3、掌握各种链表的存储结构及运算。
第三章栈和队列
一、考核知识点
栈和队列的结构特性、基本操作及在两种存储结构上基本操作的实现;栈和队列的应用、递归算法的设计。
二、考核要求
1、了解栈与队列的概念
2、掌握顺序栈、顺序队列，链栈、队列的各种运算的实现方法
3、掌握栈与递归的概念。
第四章串
一、考核知识点
串的逻辑结构定义、串的基本运算及其实现;串的匹配算法。
二、考核要求
1、了解串的概念
2、掌握串的存贮和基本运算方法。
第五章数组和广义表
一、考核知识点
数组的逻辑结构定义和存储方法;特殊矩阵和稀疏矩阵的压缩存储方法;广义表的逻辑结构和存储结构以及广义表运算的递归算法。
二、考核要求
1、了解数组的逻辑结构定义和存储方法
第六章树和二叉树
一、考核知识点
树的基本概念;二叉树的定义、性质、存储表示;二叉树的遍历;线索二叉树;森林和二叉树的相互转换;树的应用;哈夫曼树及哈夫曼编码。
二、考核要求
1、了解树和二叉树的概念
2、掌握树与二叉树的转换
3、掌握树、森林、二叉树遍历的方法及二叉树遍历的实现算法，线索化二叉树及其运算，哈夫曼树及哈夫曼编码等概念。
第七章图
一、考核知识点
图的基本概念、存储表示(邻接矩阵、邻接表、十字链表，邻接多重表);图的遍历、图的连通性问题;拓扑排序、关键路径;最短路径。
二、考核要求
1、了解图的概念
2、掌握图的存贮表示法，图的遍历及算法，生成树和最小生成树的概念
3、掌握最短路径，拓扑排序和关键路径等图的应用方法。
第九章查找
一、考核知识点
查找表是集合类型的数据结构，其操作借助静态查找表、动态查找表、哈希表实现;
二、考核要求
1、掌握查找的概念
2、掌握线性表的查找(顺序查找，二分法查找，分块查找)，树表的查找(二叉排序树、平衡二叉树)，散列表的查找及相应处理算法。
第十章排序
一、考核知识点
内部排序介绍插入排序、快速排序(交换排序)、选择排序、归并排序;排序的基本思想和算法分析。
外部排序介绍外存储器(磁带、磁盘)简介;多路平衡归并、置换选择排序、最佳归并树及磁带归并排序。
参考教材：
1、严蔚敏等著《数据结构(C语言版)》清华大学出版社
说明：1、考试基本内容：一般包括基础理论、实际知识、综合分析和论证等几个方面的内容。
2、难易程度：根据大学本科的教学大纲和本学科、专业的基本要求，一般应使大学本科毕业生中学生在规定的三个小时内答完全部考题，略有一些时间进行检查和思考。排序从易到难。
