2024年湖南大学非全日制研究生招生考试《数据结构》考试大纲

　　【考查目标】

　　1、掌握数据结构的基本概念、基本原理和基本方法。

　　2、掌握数据的逻辑结构、存储结构及基本操作的实现，了解各种典型数据结构的应用，能够对算法进行基本的时间复杂度与空间复杂度的分析。

　　3、能够选择并设计合适的数据结构及相应的算法对问题进行分析与求解，具备采用C或C++或JAVA语言设计与实现算法的能力。

　　【考查内容】

　　1、数据结构与算法分析的基本概念

　　(1)数据结构的基本概念

　　(2)渐近算法分析方法

　　(3)时间复杂度

　　(4)空间复杂度

　　2、线性表、栈和队列

　　(1)线性表的基本概念

　　(2)线性表的顺序存储结构和链式存储结构

　　(3)线性表的应用

　　(4)栈和队列的基本概念

　　(5)栈和队列的顺序存储结构和链式存储结构

　　(6)栈和队列的应用

　　3、二叉树与树

　　(1)二叉树

　　① 二叉树的基本概念

　　② 二叉树的顺序存储结构和链式存储结构

　　③ 二叉树的遍历及应用

　　④ 二叉排序(查找、检索)树

　　⑤ 堆与优先队列

　　⑥ 哈夫曼(Huffman)树及哈夫曼编码

　　(2)树

　　① 树的基本概念

　　② 树的顺序存储结构和链式存储结构

　　③ 树的遍历

　　4、图

　　(1)图的基本概念

　　(2)图的存储及基本操作

　　① 邻接矩阵

　　② 邻接表

　　(3)图的遍历

　　① 深度优先搜索

　　② 广度优先搜索

　　(4)图的基本应用

　　① 拓扑排序

　　② 关键路径

　　③ 最短路径

　　④ 最小(代价)生成树

　　5、查找

　　(1)查找的基本概念

　　(2)顺序查找法

　　(3)折半查找法

　　(4)查找树

　　① 二叉排序(查找、检索)树

　　② 平衡的二叉检索树- AVL树

　　(5)散列(Hash)表及查找

　　(6)查找算法的分析及应用

　　6、内排序

　　(1)排序的基本概念

　　(2)直接插入排序

　　(3)冒泡排序

　　(4)简单选择排序

　　(5)希尔排序(shell sort)

　　(6)快速排序

　　(7)堆排序

　　(8)归并排序

　　(9)基数排序

　　(10)各种内排序算法的分析及应用

　　【参考书籍】

　　1、Clifford A. Shaffer著，张铭、刘晓丹等译，《数据结构与算法分析(C++版)(第三版)》，电子工业出版社，2016年。

　　2、严蔚敏、吴伟民著，《数据结构(C语言版)》，清华大学出版社，2020年。