《数据结构》考试大纲
一、课程简介
《数据结构》是计算机各专业的专业基础课。它是操作系统、数据库、编译原理等所有软件专业基础课和专业课的重要基础 它还是进行程序设计，尤其是进行高水平的应用程序和系统程序必不可少的基础。通过本课程的学习，使学生掌握数据组织、存储和运算的基本原理和方法，培养学生对各类数据结构和相关算法的分析和设计的能力，使学生能够编写出正确、清晰和较高质量的算法和程序。
二、考查目标与要求
《数据结构》是为选拔全日制课程与教学论（计算机）专业硕士研究生而设置的复试考试科目。考试内容主要包括基本数据结构、 排序、 索引、 检索、高级数据结构等内容， 从逻辑结构的角度包括线性表、 栈、 队列、 二叉树、 树和图等各种基本数据结构； 从算法的角度包括各类排序、 检索和索引算法。 要求考生对其中的基本概念有很深入的理解， 掌握数据结构与算法的基本概念、合理组织数据的基本方法、 高效处理数据的基本算法、 并具备面对实际问题选择恰当数据结构与相应算法的能力。
三、考试内容
（一）数据结构和算法
1.了解数据结构、逻辑结构、存储结构和抽象数据类型的基本概念。
2.了解数据结构的发展和地位。
3.了解各种算法描述方法和算法设计的基本要求。
4.掌握对算法的评价标准和算法效率的度量方法。
（二） 线性表
1.理解线性表的概念、定义、逻辑结构和存储结构。
2.熟练掌握线性表的顺序结构及其各种基本运算。
3.熟练掌握单链表、循环链表、双向链表的存储结构及其各种基本运算。
4.理解链表的应用——稀疏多项式存储和运算。
（三）栈和队列
1.掌握栈的定义、表示、实现和应用。
2.掌握递归的概念和递归的实现过程。
3.掌握队列的定义以及顺序(循环队列)和链式存储结构的实现。
（四）串
1.了解串的基本概念及顺序和链式存储结构。
2.掌握串的各种基本运算。
3.了解串的模式匹配算法。
（五）数组和广义表
1.掌握数组的顺序存储结构。
2.理解稀疏数组的概念和压缩存储的方法。
3.理解稀疏矩阵的三元组存储结构和基本运算。
4.了解稀疏矩阵的十字链表存储结构。
5.理解广义表的基本概念，掌握广义表的存储结构。
（六）树
1.理解树的基本概念及其存储结构。
2.熟练掌握二叉树的定义、性质以及各种存储结构和遍历算法。
3.掌握线索二叉树的概念、存储结构及线索化算法。
4.掌握树和森林与二叉树间的转换，掌握树和森林的遍历算法。
5.掌握哈夫曼树的概念、存储结构和应用。
（七） 图
1.理解图的基本概念，掌握图的邻接矩阵和邻接表的存储结构。
2.了解十字链表，邻接多重表等存储结构。
3.熟练掌握图的深度优先和广度优先遍历算法。
4.理解图的连通性、小生成树的概念。
5.掌握求小生成树算法。
6.理解有向无环图的概念，掌握拓扑排序和关键路径算法。
7.理解带权短路径的概念，掌握求短路径的算法。
（八）查找
1.理解查找的概念及其效率的评价方法。
2.理解静态查找表的概念，熟练掌握顺序、折半和分块查找算法。
3.理解动态查找表和二叉排序树的概念。
4.了解平衡二叉树的概念。
5.理解哈希表的含义，掌握哈希函数的构造和处理冲突的基本方法。
（九）内部排序
1.掌握插入类排序的算法：直接插入排序、希尔排序。
2.掌握交换类排序的算法：冒泡排序、快速排序。
3.掌握选择类排序的算法：简单选择排序、堆排序。
4.了解归并排序、基数排序的思想，了解外排序的概念。
四、试卷结构
1.试卷满分为100分，考试时间为180分钟。
2.试卷题型结构
名称解释 20分 （共4题，每题5分）。
应用题 40分 （共4题，每题10分）。
设计题 40分 （共2题，每题20分）。
五、参考书目
《数据结构》（C语言版）严蔚敏，吴伟民编著。清华大学出版社，1997.4（2018.6重印）
原标题：2019年沈阳师范大学教师专业发展学院硕士研究生招生考试加试大纲-数据结构
