资源描述
2020 年硕士研究生入学考试专业课考试大纲考试科目代码：823 考试科目名称：数据结构一、考试要求数据结构研究生入学考试是为所招收计算机应用技术专业硕士研究生而实施的具有选拔功能的水平考试。它的主要目的是测试学生对数据结构的基本概念、基本原理和基本方法的掌握程序。要求学生掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析。能够运用数据结构基本原理和方法进行问题的分析与求解，具备采用 C 或 C+语言设计与实现算法的能力。二、考试内容一、线性表(一) 线性表的定义和基本操作(二) 线性表的实现1. 顺序存储结构2. 链式存储结构3. 线性表的应用二、栈、队列和数组(一) 栈和队列的基本概念(二) 栈和队列的顺序存储结构(三) 栈和队列的链式存储结构(四) 栈和队列的应用(五) 特殊矩阵和稀疏矩阵的压缩存储三、树与二叉树(一) 树的基本概念(二) 二叉树1. 二叉树的定义及其主要特征2. 二叉树的顺序存储结构和链式存储结构3. 二叉树的遍历4. 线索二叉树的基本概念和构造(三) 树、森林1. 树的存储结构2. 森林与二叉树的转换3. 树和森林的遍历(四) 树和二叉树的应用1. 二叉排序树2. 平衡二叉树3. 哈夫曼(Huffman)树和哈夫曼编码四、图(一) 图的概念(二) 图的存储及基本操作1. 邻接矩阵法2. 邻接表法(三) 图的遍历1. 深度优先搜索2. 广度优先搜索(四) 图的基本应用1. 最小(代价)生成树2. 最短路径3. 拓扑排序4. 关键路径五、查找(一) 查找的基本概念(二) 顺序查找法(三) 折半查找法(四) B-树及其基本操作、B+树的基本概念(五) 散列(Hash)表(六) 查找算法的分析及应用六、排序(一) 排序的基本概念(二) 插入排序1. 直接插入排序2. 折半插入排序(三) 气泡排序(bubble sort)(四) 简单选择排序(五) 希尔排序(shell sort)(六) 快速排序(七) 堆排序(八) 二路归并排序(merge sort) (九) 基数排序(十) 各种内部排序算法的比较(十一) 排序算法的应用三、题型结构1、单项选择题 (共 20 题，每题 2 分，共 40 分)2、填空题（每空 1 分，共 40 分）3、应用题(共 5 题，每题 8 分，共 40 分)4、算法设计与分析题(共 2 题，每题 15 分，共 30 分)四、参考书目1.数据结构（C 语言版） ，严蔚敏、吴伟民，清华大学出版社，2011 年。
展开阅读全文