科目代码：801 科目名称：数据结构
一、考试要求
主要考察考生是否掌握了数据结构的基本概念、基本原理和基本方法，包括线性表、栈、队列、串、树和二叉树、图等基本数据结构的逻辑结构、存储结构及基本操作；掌握各种查找、排序算法，能够对算法进行基本的时间复杂度与空间复杂度的分析；具备使用数据结构分析并求解问题的能力，能够采用C或C++语言设计与实现算法。
二、考试内容
1、数据结构与算法的基本概念
（1）理解数据、数据元素、数据项、数据对象、数据结构等基本概念，以及逻辑结构、存储结构、数据类型、抽象数据类型等术语的含义；
（2）掌握算法的定义、特性（有穷性、确定性、可行性、输入、输出），能够使用伪代码等方式描述算法。理解算法的时间复杂度和空间复杂度的概念，掌握分析算法复杂度的方法，能够对简单算法的复杂度进行分析。
（3）递归的定义、基本原理，递归算法的设计步骤，能够应用递归求解简单的问题。
2、线性表
（1）理解线性表的逻辑结构特征，掌握线性表的定义和基本操作（如插入、删除、查找、遍历等）；
（2）顺序存储结构：掌握顺序表的实现原理，包括元素的存储方式、地址计算方法等。能够分析顺序表基本操作的时间复杂度，理解顺序表的优缺点；
（3）链式存储结构：掌握单链表、双向链表、循环链表的结构特点和实现方法，理解链式存储结构中指针的作用，能够分析链表基本操作的时间复杂度，掌握链表的插入、删除、查找等操作的实现。
3、栈和队列
（1）栈和队列的概念：掌握栈和队列的逻辑结构特点，理解栈的后进先出（LIFO）和队列的先进先出（FIFO）特性；
（2）栈和队列的存储结构：掌握顺序栈和顺序队列的实现，理解栈满、栈空和队满、队空的判断条件及处理方法，掌握链栈和链队列的实现，能够分析链式存储结构下栈和队列操作的时间复杂度；
（3）栈和队列的应用：能够运用栈和队列求解问题，包括但不限于表达式求值、括号匹配、二叉树层序遍历、图的广度优先遍历等。
4、串
（1）掌握串的基本概念、串的存储结构（顺序存储与链式存储）；
（2）理解串的模式匹配算法（如朴素的模式匹配算法、KMP算法等）。
5、树和二叉树：
（1）树与二叉树的基本概念：掌握树的定义、基本术语（如节点、度、叶子节点、分支节点、树的深度、森林等），理解二叉树的定义和各种性质，能够根据性质进行简单的计算和推理。
（2）树与二叉树的存储结构：掌握树的存储结构（如孩子兄弟表示法等），掌握二叉树的顺序存储和链式存储结构；
（3）二叉树的遍历：熟练掌握二叉树的前序、中序、后序遍历的递归和非递归算法，理解遍历算法的执行过程和应用场景；
（4）哈夫曼树及其应用：掌握哈夫曼树的构造方法，理解哈夫曼编码的原理和实现过程，能够运用哈夫曼树和哈夫曼编码解决实际问题。
6、图
（1）图的基本概念：掌握图的定义、基本术语（如顶点、边、有向图、无向图、完全图、子图、连通图、强连通图等），理解图的度、入度、出度等概念。
（2）图的存储结构：掌握图的邻接矩阵和邻接表表示方法，理解两种存储结构的特点和适用场景，能够根据给定的图进行存储结构的转换。
（3）图的遍历：熟练掌握图的深度优先搜索和广度优先搜索算法，理解遍历算法的执行过程和应用场景，能够运用遍历算法解决简单的图的问题。
（4）图的基本应用：掌握最小生成树算法（如Prim算法和Kruskal算法）、最短路径算法（如Dijkstra算法和Floyd算法）、拓扑排序算法、关键路径算法的原理和实现，能够运用这些算法解决实际问题。
7、查找
（1）查找的基本概念：理解查找表、查找分类、查找结构等基本概念，掌握查找算法效率的评判标准（平均查找长度）；
（2）静态查找表：掌握顺序查找、折半查找等静态查找算法的原理和实现过程，能够分析算法的时间复杂度。
（3）动态查找表：掌握二叉排序树的定义、特点、创建、插入、删除等操作，理解平衡二叉树的定义和调整方法。
（4）哈希表：掌握哈希函数的确定方法、处理冲突的方法（如开放定址法、链地址法等），理解哈希查找的原理和实现过程，能够分析哈希表的性能。
8、排序
（1）排序的基本概念：理解排序的定义、稳定性等概念，掌握排序算法效率的评判标准（时间复杂度、空间复杂度、稳定性等）；
（2）常见的排序算法：掌握插入排序（如直接插入排序、希尔排序）、交换排序（如冒泡排序、快速排序）、选择排序（如简单选择排序、堆排序）、归并排序、基数排序等基本排序算法的原理、实现过程和时间复杂度分析，能够根据不同的问题选择合适的排序算法。
三、考试题型
本试卷满分为150分，答题方式为闭卷、笔试。其中：单项选择题/判断题占20%，简答题/填空题占20%，算法设计题占40%，综合应用题占20%。
四、参考教材
[1] 《数据结构（C语言版）》，严蔚敏、吴伟民，清华大学出版社，2018。
[2] 《数据结构教程（第6版）》，李春葆，清华大学出版社，2022。
