众所周知，考研大纲是全国硕士研究生考试命题的重要依据，也是考生复习备考必不可少的工具书。今天，小编为大家整理了“2024考研大纲：中国石油大学2024年考研自命题科目 859 数据结构 考试大纲”的相关内容，请持续关注！
以下为《859 数据结构》文档文字版，内容仅供参考,详情请下载文末附件查看：
202 4 年 硕士研究生入学考试大纲
考试科目名称：数据结构 考试时间： 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
以上就是小编整理的“2024考研大纲：中国石油大学2024年考研自命题科目 859 数据结构 考试大纲”的全部内容，更多关于中国石油大学2024年考研大纲的信息，尽在“考研大纲”栏目，下面我们一起来看看吧！
