2018年中国地质大学(北京)数据结构考研大纲

中国地质大学（北京）硕士研究生《数据结构》考试大纲
科目名称：数据结构
代码：858
一、考试性质
本课程在计算机科学中是程序设计（特别是非数值计算的
程序设计）的基础，而且是设计和实现大型应用程序的重要
基础。本课程需要掌握基本的数据结构、基本算法分析技术、
排序、检索和索引技术。对常用的基本数据结构，掌握相应
的存储实现技术和经典算法，并通过算法时间空间的效率分
析，理解时空权衡的原则。对常用的各种经典排序算法深入
讨论其时间和空间开销。了解文件管理和外排序技术，以及
常见的检索和索引技术。掌握数据结构和算法的设计分析技
术，提高程序设计的质量；根据所求解问题的性质选择合理
的数据结构并对时间空间复杂性进行必要的控制。
二、考试形式与试卷结构
1. 答卷方式：闭卷、笔试
2. 答卷时间：180 分钟
3. 题型比例：满分 75 分/150 分，概念题 5 题（占总分
20%－40%），其余题型全为操作题和计算题。
三、考查要点
1. 基本概念
数据结构定义（逻辑结构、存储结构、运算），抽象数据
类型，算法及其算法度量和评价。
2. 线性表
线性表的顺序存储结构、线性表的链式存储结构，掌握；
循环链表、多项式及其相加、双向链表。
3. 栈和队列
栈的存储结构及其基本操作、队列存储结构及其基本
操作，掌握；栈与递归的实现。
4. 串
字符串抽象数据类型，存储表示和类定义，掌握；字
符串的运算，了解；#字符串的模式匹配。
5. 数组和广义表
数组的定义、基本运算和存储结构，特殊矩阵的压缩
存储，了解；#广义表的定义、术语、存储结构、运算，
*递归算法设计。
6. 树
二叉树的概念及性质，二叉树的抽象数据类型，二叉树的
遍历，二叉树的存储实现，Huffman 编码树，树和二叉树
的转换掌握；线索二叉树（了解）；*非递归深度优先周
游二叉树和穿线二叉树。
7. 图
图的基本概念，图的抽象数据类型，图的存储结构，图的
周游，最小支撑树,拓扑排序，掌握；最短路径问题，关
键路径算法。
8. 动态存储管理
基本概念和算法
9. 查找
静态查找表及查找算法：顺序查找、折半查找，动态查找
表及查找算法，二叉排序树，哈希表及查找算法，掌握；
B_和 B+树、键树。
10.内排序
排序问题的基本概念，三种简单排序算法（插入排序、冒泡
排序、选择排序）；
Shell 排序，快速排序，归并排序，堆排序，了解；#基数
排序；#各种排序算法的理论和实验时间代价的讨论以及
排序问题的下限的研究。
11.外排序
外排序的特点掌握；二路外排序，置换选择排序，了解。
12.文件管理
文件的基本概念，常用的文件操作，文件的组织结构，
文件的不同组织方式的特点。
四、参考资料
严蔚敏、吴伟民，《数据结构》C 语言版，清华大学出版社，
第 1 版 (2009 年 3 月 1 日)