考研复习专业课#2021年山东工商学院807数据结构考研大纲

考研复习>>专业课>>正文2021年山东工商学院807数据结构考研大纲

更新时间：2020/11/313:21:06

2021年山东工商学院招收硕士研究生入学考试

招收硕士研究生入学考试

807数据结构考试大纲

一 、考试总体要求

《数据结构》是一门专业基础课 ，要求考生理解数据结构的基本概念
，掌握数据的逻辑结构
、存储结构及其差异，以及各种基本操作的实现；在掌握基本的数据处理原理和方法的基础上 ，能够对算法进行时间复杂度和空间复杂度分析；能够选择合适的数据结构和方法进行问题求解。具备采用C、C++设计与实现算法的能力 。

二 、考试内容

本课程主要考试主要包括的内容：基本概念和算法分析
、线性表、栈和队列 、串
、数组和广义表、树和二叉树 、图、查找
、排序
。

1.基本概念和算法分析

本部分主要介绍数据结构的基本概念和常用术语
，算法和算法分析方法。重点要求理解数据结构的基本概念、理解抽象数据结构的定义 、算法的基本要素和算法分析方法，掌握算法的时间复杂度和空间复杂度分析方法 。

2.线性表

本部分主要介绍线性表的逻辑结构和各种存储表示方法 ，以及运算的实现
。重点要求掌握线性表的定义
、特点和基本操作
，熟练掌握线性表的存储表示，包括顺序存储和链式存储 ，以及在这两种存储结构上的插入、删除 、查找等运算的实现，理解其异同点和优缺点。掌握特殊链表的定义和基本运算的实现
，包括循环链表和双向链表，掌握线性表的应用 ，包括一元多项式的组织和操作以及其它应用等 。

3.栈和队列

本部分主要介绍栈和队列的逻辑结构定义
，以及在两种存储结构上基本运算的实现
。重点要求熟练掌握栈和队列的基本概念，以及栈和队列的两种实现方法（顺序存储结构实现和链式存储结构实现）及其操作的实现。能够掌握栈和队列的基本应用 。

4.串

本部分主要介绍串的基本概念
、存储结构和运算。重点要求掌握串的基本概念 ，掌握串模式匹配KMP及改进算法
。

5.数组和广义表

本部分主要介绍数组和广义表的定义、存储及运算。重点要求掌握数组的特点及存储表示方法 。掌握特殊矩阵的存储表示方法
，包括对称矩阵 、对角线矩阵
、稀疏矩阵
。掌握广义表的定义、存储表示方法以及对广义表的分解操作。

6.树和二叉树

本部分主要介绍二叉树的定义 、性质
、存储结构、遍历 、线索化；树的定义、存储结构
、遍历、树和森林的转换，赫夫曼树及其赫夫曼编码等内容 。要求掌握树与二叉树的定义 、性质 ，掌握二叉树的存储表示
，包括顺序存储和链式存储
。掌握二叉树的遍历及其应用，包括先序
、中序、后序和层次序遍历。理解线索二叉树的定义 、存储表示和寻找前驱
、后继 。掌握树和森林的存储表示、树 、森林与二叉树的转换
、树和森林的遍历
。掌握赫夫曼树和赫夫曼编码及其应用。

7.图

本部分主要介绍介绍图的基本概念、两种常用的存储结构 、两种遍历方法以及图的应用算法 。重点要求掌握图的基本概念 ，基本性质
。掌握图的存储方法
，重点掌握邻接矩阵法和邻接表法。掌握图的两种遍历方法：深度优先遍历和广度优先遍历算法及实现，掌握拓扑排序算法及算法实现 。理解基于图的最小(代价)生成树算法
、最短路径算法、关键路径算法。

8.查找

本部分主要介绍线性表 、树和哈希表的查找方法、算法实现以及各种查找方法的时间性能（平均查找长度）分析
。重点要求掌握顺序查找
、折半查找、二叉排序树和哈希表查找的基本思想和算法实现。掌握平衡二叉树的基本操作 ，理解B-树和B+树的基本概念 。能够理解各种不同查找算法的特点及其适用情况，分析不同查找算法的性能
。

9.内部排序

本部分主要介绍几种内部排序方法的基本思想 、排序过程
、算法实现、时间和空间性能的分析；并且对各种排序方法进行比较。重点要求掌握直接插入排序 、折半插入排序
、起泡排序、快速排序 、直接选择排序
、堆排序、归并排序 、基数排序的基本思想和排序过程 。掌握各类排序方法的时间/空间复杂度
，以及稳定性
。