长春理工大学研究生入学考试《数据结构》考试大纲

一、考试科目：数据结构

二、适用专业：计算机科学技术学院所有专业

三、参考书目：

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)各种排序方法比较及应用