长春理工大学研究生入学考试《数据结构》考试大纲 一、考试科目:数据结构 二、适用专业:计算机科学技术学院所有专业 三、参考书目: 1.《数据结构》(C语言版)严蔚敏 吴伟民 编著,清华大学出版社, 2011.11. 四、 试卷结构: 总分150分,试题类型及试卷结构包括:选择题(40分);填空题(10分);问答题(40);综合应用题(60分). 五、考试内容:? (一)主要考查目标 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)各种排序方法比较及应用