中国石油大学（华东）859数据结构2023年硕士研究生初试自命题科目考试大纲

中国石油大学（华东）859数据结构2023年硕士研究生初试自命题科目考试大纲已出，理解数据结构、存储结构、算法、数据类型、抽象数据类型(ADT)等基本概念及它们之间的关系；掌握线性表、树、图等基本数据结构的 ADT 定义以及基于不同存储方式（顺序、链式等）的实现，并能对占用存储空间情况和算法的时间复杂度进行分析。

2023 年硕士研究生入学考试大纲

考试科目名称：数据结构 考试时间：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）特殊矩阵的存储及操作实现（重点掌握分布有规律的特殊矩阵和分布无规律的稀疏矩阵如何高效存储及矩阵典型操作的实现）

1 2 3