考研复习专业课#2021年中国石油大学华东<<数据结构>>考研大纲

考研复习>>专业课>>正文2021年中国石油大学华东<<数据结构>>考研大纲

更新时间：2020/11/2510:46:46

2021年中国石油大学华东硕士研究生入学考试大纲

考试科目名称：数据结构

一
、考试要求

考试时间：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.数据结构（用面向对象方法与C++语言描述）（第2版）.殷人昆主编.北京：清华大

学出版社.2007.6

2.数据结构（C语言版）.严蔚敏 、吴伟民编著.北京：清华大学出版社.2007