中科院863计算机学科综合 数据结构 考试大纲 考试范围及参考教材
作者：科大科院考研网 发表时间：2018-07-09 来源：学长经验
2019版中国科学院863计算机学科综合（专业）考研真题及答案解析 视频课程
中科院863计算机学科综合不是全国统考的，而是中科院自主命题。考察的内容包括了：数据结构、计算机组成原理、操作系统、计算机网络四门课程，每门课程各占25%。
以下为数据结构部分的考试大纲。
（一）考试大纲
1、绪论
（1）数据结构的基本概念，数据的逻辑结构、存储结构。
（2）算法的定义、算法的基本特性以及算法分析的基本概念。
2、线性表
（1）线性表的定义、基本操作。
（2）线性表的实现及应用，包括顺序存储结构、链式存储结构(单链表、循环链表和双向链表)的构造原理，在两种存储结构上对线性表实施的主要的操作(三种链表的建立、插入和删除、检索等)的算法设计与实现。
3、堆栈与队列
（1）堆栈与队列的基本概念、基本操作。
（2）堆栈与队列的顺序存储结构、链式存储结构的构造原理。
（3）在不同存储结构的基础上对堆栈、队列实施基本操作（插入与删除等）对应的算法设计与实现。
4、数组和广义表
（1）数组的概念、多维数组的实现。
（2）对称矩阵和稀疏矩阵的压缩存储。
（3）广义表的基本概念。
5、树与二叉树
（1）树的概念和性质。
（2）二叉树的概念、性质和实现。
（3）二叉树的顺序存储结构和链式存储结构。
（4）遍历二叉树。
（5）线索二叉树的基本概念和构造。
（6）树和森林的存储结构、遍历。
（7）二叉排序树。
（8）平衡二叉树。
（9）哈夫曼(Huffman)树和哈夫曼编码。
6、图
（1）图的基本概念。
（2）图的存储，包括邻接矩阵法、邻接表法。
（3）图的遍历操作，包括深度优先搜索、广度优先搜索。
（4）最小生成树，最短路径，关键路径、拓扑排序算法的原理与实现。
7、文件及查找
（1）数据文件的基本概念、基本操作。
（2）顺序查找法、分块查找法、折半查找方法的原理与实现。
（3）B树及其基本操作、B+树的基本概念。
（4）散列(Hash)表。
（5）字符串模式匹配的算法原理与实现。
8、排序
（1）排序的基本概念。
（2）直接插入排序、折半插入排序、气泡排序、简单选择排序、快速排序、堆排序、二路归并排序、基数排序、外部排序算法的原理、复杂度。
（3）排序算法的应用。
（二）考试要求
1.掌握数据结构的基本概念、基本原理和基本方法。
2.掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析。
3.能够运用数据结构基本原理和方法进行问题的分析与求解，具备采用C或C++语言设计与实现算法的能力。
（三）主要参考书目
1、数据结构（C语言版）. 严蔚敏，吴伟民 编著，北京：清华大学出版社，2007年。
