中国石油大学(华东)859数据结构考研大纲

2018 年硕士研究生入学考试大纲
考试科目名称：数据结构 考试时间：180 分钟，满分：150 分
一、考试要求
1．理解数据结构、存储结构、算法、数据类型、抽象数据类型(ADT)等基本概念及
它们之间的关系。
2．掌握线性表、树、图等基本数据结构的 ADT 定义以及基于不同存储方式（顺序、
链式等）的实现，并能对占用存储空间情况和算法的时间复杂度进行分析。
3．掌握典型的查找结构（静态表、搜索树、散列等）、查找算法的基本思想及性能
分析。
4．掌握内部排序（选择、插入、交换、归并等）的重要算法的基本思想、特点及性
能分析。
5．能够运用学习的数据结构及算法的知识和技能进行问题的分析与求解，即能对问
题进行抽象建模，能熟练使用高级语言（C 或 C++或 JAVA 等）进行模型的具体实
现（编程）。
二、考试内容
1．数据结构和算法的重要性
（1）基本概念及它们之间的关系
（2）各种存储结构的空间占用情况及映射逻辑关系的方式
（3）算法的评价及对算法渐近时间复杂性的理解
2．一般线性表
（1）一般线性表 ADT 的定义
（2）线性表 ADT 基于顺序存储的实现（存储方式、特点、重要操作的算法，下同）
（3）线性表 ADT 基于链式存储的实现（存储方式、特点、重要操作的算法，下同）
3．特殊线性表（栈、队列、字符串、数组）
（1）栈的特点及栈 ADT 的定义
（2）栈 ADT 基于顺序存储的实现
（3）栈 ADT 基于链式存储的实现
（4）栈 ADT 的应用（表达式求值、递归处理、迷宫问题）
（5）队列的特点及队列 ADT 的定义
（6）队列 ADT 基于顺序存储的实现
（7）队列 ADT 基于链式存储的实现
（8）队列 ADT 的应用（广度遍历、资源分配问题）
（9）字符串特点及串 ADT 的定义
（10）字符串 ADT 基于顺序存储的实现（重点掌握经典的模式匹配算法：BF，KMP）
（11）数组的特点及 ADT 定义
（12）数组 ADT 基于顺序存储的实现（重点掌握多维数组的存储结构）
（13）特殊矩阵的存储及操作实现（重点掌握分布有规律的特殊矩阵和分布无规律的
稀疏矩阵如何高效存储及矩阵典型操作的实现）
4．树与二叉树
（1）二叉树的特点及 ADT 定义
（2）二叉树的重要性质及证明
（3）二叉树基于顺序存储的实现
（4）二叉树基于链式存储的实现（重点掌握重要操作：建立、遍历、求深度、计算叶
子等等）
（5）线索二叉树的基本概念（为什么加线索？如何记录线索？如何使用线索？）
（6）建立（画）线索二叉树
（7）树、森林的定义及特点
（8）树的存储结构（重点掌握子女-兄弟表示）
（9）树、森林与二叉树的相互转换
（10）树和森林的遍历
（11）哈夫曼（Huffman）树和哈夫曼编码的构造过程
（12）二叉排序树的定义及建立（重点掌握结点的插入和删除的思想和过程）
（13）平衡二叉树的定义及建立（平衡的目的？如何达到平衡？）
（14）堆的定义及建立和调整（堆的构造和调整过程）
5．图
（1）图的基本概念及 ADT 定义
（2）图的 ADT 的实现（存储方式及基本操作实现）
①邻接矩阵存储（无向图、有向图、无向带权图、有向带权图）
②邻接表存储（无向图、有向图、无向带权图、有向带权图）
③各种存储方式下操作的算法实现（图的建立、遍历、插入边、删除边等）
（3）图的遍历及生成树
①深度优先遍历（思想、过程及算法实现）
②广度优先遍历（思想、过程及算法实现）
（4）图的基本应用（掌握算法的思想、过程）
①最小生成树问题
②最短路径问题
③有向图与工程问题（工程调度：AOV 网与拓扑排序，工期：AOE 网与关键路径）
6．查找
（1）查找的基本概念
（2）顺序查找法（监视哨法的思想和算法）
（3）折半查找法（思想和算法）
（4）树查找（二叉排序树）
（5）B 树及其基本操作、B+树的基本概念（思想和过程）
（6）散列（Hash）查找（Hash 函数和解决冲突的方法的思想和过程）
（6）各种查找表的组织及查找算法的时间复杂度、平均查找长度的分析
7．排序
（1）排序的基本概念
（2）基于“插入”思想的排序方法
①直接插入排序
②折半插入排序（思想和过程）
③希尔排序（思想和过程）
（3）基于“交换”思想的排序方法
①冒泡排序（思想、过程和算法）
②快速排序（思想、过程和算法）
（4）基于“选择”思想的排序方法
①简单选择排序（思想、过程和算法）
②堆排序（思想和过程）
（5）基于“归并”思想的排序方法
二路归并排序（思想、过程）
（6）各种常用内部排序算法的特点及应用
三、考试形式和试卷结构
1．考试形式：笔试，闭卷
2.试卷结构：
满分：150 分，其中：
a:选择题(50 分)
b:应用题(50 分)
c:算法分析与设计(50 分)
3.答题时间：180 分钟
四、参考书目
1. 数据结构（用面向对象方法与 C++语言描述）（第 2 版）.殷人昆主编. 北京：清华大
学出版社.2007.6
2. 数据结构（C 语言版）.严蔚敏、吴伟民编著. 北京：清华大学出版社. 2007