长春理工大学研究生入学考试《数据结构》考试大纲
一、考试科目：数据结构
二、适用专业：计算机科学技术学院所有专业
三、参考书目：
1.《数据结构》(C语言版)严蔚敏 吴伟民 编著，清华大学出版社， 2011.11。
2.考试难度和形式可以参考计算机科学技术学院的《数据结构》课程考试：
(http://cs.cust.edu.cn/ArticleShow.asp?ArticleID=2880)。
四、考试内容：
(一)主要考查目标
1. 理解数据结构的基本概念，掌握数据的逻辑结构、存储结构及其差异，以及基本操作及实现。
2. 掌握基本的数据处理原理和方法，能够对算法进行设计和分析。
3. 能够选择合适的数据结构和方法进行问题求解。
(二) 知识点
1、线性表
1) 线性链表的顺序存储结构;线性链表的链式存储结构;线性表的插入与删除
2) 线性表的应用
2、栈和队列
1) 栈的基本概念;栈的顺序存储结构;栈的链式存储结构;栈的基本操作及应用
2) 队列的基本概念;队列的顺序存储结构;队列的链式存储结构;队列的基本操作及应用
3、串
1) 字符串的基本操作及应用
2)字符串的模式匹配
4、数组与广义表
1) 特殊矩阵的压缩存储
2) 广义表的概念和表示;广义表存储结构
3)数组及广义表的基本操作和应用
5、树与二叉树
1) 树的概念
2) 二叉树的定义;二叉树的性质;二叉树的顺序存储结构和链式存储结构
3) 二叉树遍历
4) 线索化二叉树的构造
5) 树的存储结构;森林与二叉树的转换;树与森林的遍历
6) 哈夫曼(Huffman)树和哈夫曼编码;树的基本应用
6、图
1) 图的基本概念
2) 图的邻接矩阵;邻接表
3) 图的深度优先搜索;广度优先搜索
4) 最小生成树
5) 拓扑排序
6)最短路径;关键路径;图的基本应用
7、查找
1)查找的基本概念
2)顺序查找法
3)折半查找法
4)散列(Hash)表及其查找;散列表与散列方法
5)各种查找方法的比较和应用
8、内部排序
1) 直接插入排序;折半插入排序
2) 起泡排序
3)简单选择排序
4)希尔排序
5)快速排序
6) 堆排序
7) 归并排序
8)各种排序方法比较及应用
