科目名称：数据结构                       科目代码：810

本考试大纲适用于南阳师范学院电子信息专业学位硕士研究生2024年入学考试。数据结构是电子信息、计算机科学与技术、数据科学与大数据技术及相关学科的重要基础。要求考生对电子信息、计算机科学与技术、数据科学与大数据技术及相关学科的基本概念有较深入、系统的理解，掌握各种数据结构的定义和实现算法，能够利用C/C++语言的基本知识进行各种数据结构的逻辑设计与存储实现，并具有综合运用所学知识分析问题和解决问题的能力。

一、考试内容

1、绪论

（1）数据结构的基本概念，数据的逻辑结构、存储结构。

（2）算法的定义、算法的基本特性以及算法分析的基本概念、标准及方法，对算法的时空复杂度进行分析。

2、线性表

（1）线性关系、线性表的定义，线性表的基本操作。

（2）线性表的顺序存储结构与链式存储结构(包括单链表、循环链表)的构造原理。在以上两种存储结构上对线性表实施的最主要的操作(包括建立、插入和删除、检索等)的算法设计。

3、栈和队列

（1）栈与队列的基本概念、基本操作。

（2）栈与队列的顺序存储结构与链式存储结构的构造原理。

（3）在不同存储结构的基础上对栈与队列实施插入与删除等基本操作对应的算法设计。

4、串、数组和广义表

（1）串的基本概念、串的基本操作和存储结构。

（2）串的模式匹配算法（包括BF算法和KMP算法）。

（3）数组的概念、多维数组的实现。

（4）特殊矩阵和随机稀疏的压缩存储。

（5）广义表的基本概念。

5、树与二叉树

（1）树的定义和性质。

（2）二叉树的概念、性质和实现。

（3）遍历二叉树和线索二叉树。

（4）树和森林。

（5）赫夫曼树及其应用。

（6）树的叶子结点个数、深度等的计数方法。

6、图

（1）图的定义，基本概念，图的分类，常用名词术语。

（2）图的邻接矩阵存储方法、邻接表存储方法的构造原理。

（3）图的遍历操作。

（4）最小生成树，最短路径，关键路径与拓扑排序。

7、查找

（1）查找的基本概念和基本术语。

（2）线性表的查找。

（3）树表的查找。

（4）散列表的查找。

8、排序

（1）排序的基本概念，排序方法的分类。

（2）插入排序（含折半插入排序）选择排序、冒泡排序、快速排序、堆排序、归并排序、基数排序等排序方法的原理、规律、特点和实现，以及时空复杂度的简单分析。

二、考试要求

1、掌握有关数据结构的基本概念，包括数据的逻辑结构、存储结构。

2、掌握算法的基本概念以及算法分析的基本方法。

3、掌握线性表的基本概念，在两种存储结构下的构造原理及相应的操作。

4、掌握栈和队列的基本概念与特征以及在两种存储结构下如何对栈和队列进行插入和删除等操作，具备使用栈与队列解决实际问题的能力。

5、掌握串的基本概念以及串的存储结构和相关的算法。

6、掌握数组、广义表和稀疏矩阵的基本概念以及基本操作。

7、掌握树型结构的逻辑特征以及各种存储结构的构造原理，能够熟练使用基于树的三种遍历方法。

8、掌握二叉排序树的逻辑特征、建立过程，具备使用其解决实际问题的能力。

9、了解图的逻辑结构的特点以及常用的两种存储方法，了解最小生成树(Prim算法和Kruskal算法)、最短路径、拓扑排序的求解过程。

10、掌握查找表的结构与相应的查找方法以及各种查找算法之间时空效率的差异；了解散列表的创建、散列函数的选择(构造)原则、处理散列冲突的方法以及基于散列的查找。

11、掌握各种排序方法的排序特点和排序过程，能够对每一种排序方法在时间、空间、排序的稳定性等方面进行简单分析。

三、主要参考书目

1、数据结构（C语言版 第2版），严蔚敏、李冬梅、吴伟民，人民邮电出版社，2015年；

2、数据结构教程（第5版），李春葆，清华大学出版社，2017年。

人工智能与软件工程学院

2023年10月24日