兰州理工大学892数据结构（兰州理工大学考研真题854 百度网盘）

## 兰州理工大学 892 数据结构### 一、 简介“数据结构”是兰州理工大学计算机科学与技术、软件工程等专业硕士研究生入学考试的专业基础课，考试代码为 892。数据结构是计算机科学的核心课程之一，旨在考察学生对各种数据结构的理解、掌握和应用能力，以及利用数据结构解决实际问题的能力。### 二、 考试内容#### 2.1 线性结构

线性表的定义和基本操作

:

顺序存储结构和链式存储结构的特点、优缺点及适用场景

各种操作（插入、删除、查找等）的算法实现及时间复杂度分析

栈和队列

:

定义、特点及应用场景

顺序存储和链式存储结构的实现

基本操作（入栈、出栈、入队、出队等）的算法实现及时间复杂度分析

串

:

定义、特点及应用场景

顺序存储结构和链式存储结构的实现

模式匹配算法（如 KMP 算法）#### 2.2 树形结构

树的基本概念

:

树的定义、结点、度、深度、高度等基本概念

树的遍历方法（先序、中序、后序、层序）及其算法实现

二叉树

:

定义、性质及应用场景

顺序存储结构和链式存储结构的实现

二叉树的创建、遍历、查找、插入、删除等基本操作的算法实现及时间复杂度分析

线索二叉树

:

定义、特点及应用场景

线索化方法及算法实现

树和森林

:

树、森林和二叉树之间的转换关系

树和森林的遍历方法及算法实现

哈夫曼树

:

定义、构造方法及应用场景

哈夫曼编码的原理及实现#### 2.3 图结构

图的基本概念

:

图的定义、顶点、边、度、路径、连通性等基本概念

图的存储结构（邻接矩阵、邻接表）

图的遍历

:

深度优先搜索 (DFS) 和广度优先搜索 (BFS) 的算法实现及应用场景

最小生成树

:

Prim 算法和 Kruskal 算法的原理、步骤、算法实现及时间复杂度分析

最短路径

:

Dijkstra 算法和 Floyd 算法的原理、步骤、算法实现及时间复杂度分析

拓扑排序

:

定义、实现方法及应用场景#### 2.4 查找

顺序查找和二分查找

:

原理、算法实现及时间复杂度分析

适用场景

散列表

:

定义、构造方法（散列函数、冲突处理方法）及性能分析

常见散列表的实现

二叉排序树

:

定义、查找、插入、删除等操作的算法实现及时间复杂度分析

平衡二叉树

:

定义、特点及应用场景

AVL 树的旋转操作及实现#### 2.5 排序

插入排序

:

直接插入排序、折半插入排序、希尔排序的原理、算法实现及时间复杂度分析

交换排序

:

冒泡排序和快速排序的原理、算法实现及时间复杂度分析

选择排序

:

简单选择排序和堆排序的原理、算法实现及时间复杂度分析

归并排序

:

原理、算法实现及时间复杂度分析

基数排序

:

原理、算法实现及时间复杂度分析

各种排序算法的比较

:

时间复杂度、空间复杂度、稳定性等方面### 三、 备考建议

系统学习教材

: 选择一本数据结构教材，系统学习数据结构的基本概念、算法和应用。

重视代码实现

: 数据结构的学习不能只停留在理论层面，要注重代码实现，动手编写各种数据结构和算法的代码，加深理解和记忆。

刷题巩固

: 选择一本数据结构习题集，进行大量的刷题练习，巩固所学知识，提高解题能力。

关注真题

: 收集兰州理工大学 892 数据结构的历年真题，进行模拟考试，熟悉考试题型和难度。### 四、 参考书目

《数据结构（C语言版）》，严蔚敏，吴伟民 编著，清华大学出版社

《大话数据结构》，程杰 著，清华大学出版社

《算法导论》，Thomas H. Cormen 等 著，机械工业出版社### 五、 总结数据结构是计算机科学的基石，学习数据结构不仅可以为学习其他计算机课程打下坚实的基础，还可以提高解决实际问题的能力。希望考生认真备考，在考试中取得好成绩！

兰州理工大学 892 数据结构

一、 简介“数据结构”是兰州理工大学计算机科学与技术、软件工程等专业硕士研究生入学考试的专业基础课，考试代码为 892。数据结构是计算机科学的核心课程之一，旨在考察学生对各种数据结构的理解、掌握和应用能力，以及利用数据结构解决实际问题的能力。

二、 考试内容

2.1 线性结构* **线性表的定义和基本操作**:* 顺序存储结构和链式存储结构的特点、优缺点及适用场景* 各种操作（插入、删除、查找等）的算法实现及时间复杂度分析 * **栈和队列**:* 定义、特点及应用场景* 顺序存储和链式存储结构的实现* 基本操作（入栈、出栈、入队、出队等）的算法实现及时间复杂度分析 * **串**:* 定义、特点及应用场景* 顺序存储结构和链式存储结构的实现* 模式匹配算法（如 KMP 算法）

2.2 树形结构* **树的基本概念**: * 树的定义、结点、度、深度、高度等基本概念* 树的遍历方法（先序、中序、后序、层序）及其算法实现 * **二叉树**:* 定义、性质及应用场景* 顺序存储结构和链式存储结构的实现* 二叉树的创建、遍历、查找、插入、删除等基本操作的算法实现及时间复杂度分析 * **线索二叉树**:* 定义、特点及应用场景* 线索化方法及算法实现 * **树和森林**:* 树、森林和二叉树之间的转换关系* 树和森林的遍历方法及算法实现 * **哈夫曼树**:* 定义、构造方法及应用场景* 哈夫曼编码的原理及实现

2.3 图结构* **图的基本概念**:* 图的定义、顶点、边、度、路径、连通性等基本概念* 图的存储结构（邻接矩阵、邻接表） * **图的遍历**:* 深度优先搜索 (DFS) 和广度优先搜索 (BFS) 的算法实现及应用场景 * **最小生成树**:* Prim 算法和 Kruskal 算法的原理、步骤、算法实现及时间复杂度分析 * **最短路径**:* Dijkstra 算法和 Floyd 算法的原理、步骤、算法实现及时间复杂度分析 * **拓扑排序**:* 定义、实现方法及应用场景

2.4 查找* **顺序查找和二分查找**:* 原理、算法实现及时间复杂度分析* 适用场景 * **散列表**:* 定义、构造方法（散列函数、冲突处理方法）及性能分析* 常见散列表的实现 * **二叉排序树**:* 定义、查找、插入、删除等操作的算法实现及时间复杂度分析 * **平衡二叉树**:* 定义、特点及应用场景* AVL 树的旋转操作及实现

2.5 排序* **插入排序**:* 直接插入排序、折半插入排序、希尔排序的原理、算法实现及时间复杂度分析 * **交换排序**:* 冒泡排序和快速排序的原理、算法实现及时间复杂度分析 * **选择排序**:* 简单选择排序和堆排序的原理、算法实现及时间复杂度分析 * **归并排序**:* 原理、算法实现及时间复杂度分析 * **基数排序**:* 原理、算法实现及时间复杂度分析 * **各种排序算法的比较**:* 时间复杂度、空间复杂度、稳定性等方面

三、 备考建议* **系统学习教材**: 选择一本数据结构教材，系统学习数据结构的基本概念、算法和应用。 * **重视代码实现**: 数据结构的学习不能只停留在理论层面，要注重代码实现，动手编写各种数据结构和算法的代码，加深理解和记忆。 * **刷题巩固**: 选择一本数据结构习题集，进行大量的刷题练习，巩固所学知识，提高解题能力。 * **关注真题**: 收集兰州理工大学 892 数据结构的历年真题，进行模拟考试，熟悉考试题型和难度。

四、 参考书目* 《数据结构（C语言版）》，严蔚敏，吴伟民 编著，清华大学出版社 * 《大话数据结构》，程杰 著，清华大学出版社 * 《算法导论》，Thomas H. Cormen 等 著，机械工业出版社

五、 总结数据结构是计算机科学的基石，学习数据结构不仅可以为学习其他计算机课程打下坚实的基础，还可以提高解决实际问题的能力。希望考生认真备考，在考试中取得好成绩！