2024年华东交通大学非全日制研究生招生考试《数据结构》考试大纲

　　(一)基本内容

　　第一章绪论

　　1.数据结构的基本概念;

　　2.算法的基本概念;

　　3.算法描述和算法分析的方法。

　　第二章线性表

　　1.线性表的定义及逻辑结构;

　　2.线性表的顺序表示及实现;

　　3.线性表的链式表示及实现;

　　4.顺序表和链表上的平均时间性能分析。

　　第三章栈和队列

　　1.栈和队列的定义;

　　2.栈的存储结构及实现;

　　3.队列的存储结构及实现;

　　4.线性表、栈、队列三种结构的区别。

　　第四章串

　　1.串类型的定义;

　　2.串的表示和实现;

　　3.串操作应用举例;

　　4.模式匹配算法及其时间性能分析。

　　第五章数组

　　1.数组的存储结构及基本操作实现;

　　2.二维数组基本操作;

　　3.稀疏矩阵的压缩存储、转置算法。

　　第六章树

　　1.树及二叉树的逻辑结构定义;

　　2.二叉树的性质与存储结构;

　　3.遍历二叉树的方法;

　　4.线索二叉树的构造;

　　5.森林与二叉树的转换;

　　6.最优二叉树及哈夫曼编码。

　　第七章图

　　1.图的定义和术语;

　　2.图的存储结构;

　　3.图的遍历算法;

　　4.图的最小生成树;

　　5.拓扑排序;

　　6.关键路径;

　　7.最短路径。

　　第八章查找

　　1.查找(顺序查找、二分查找、哈希查找、分块查找及动态查找等)的基本概念;

　　2.二叉排序树和平衡二叉树;

　　3.查找的算法实现;

　　4.哈希函数的构造方法和处理冲突的方法。

　　第九章排序

　　1.排序(直接插入排序、希尔排序、快速排序、简单选择排序、堆排序、归并排序和

　　基数排序)的基本思想;

　　2.对比分析个排序算法的时间复杂度与稳定性。

　　(二)满分分值

　　试卷满分为150 分。

　　(三)参考书目

　　《数据结构(C 语言版)》(第二版)，严蔚敏、李冬梅、吴伟民著，人民邮电出版社，2021。

　　科目说明：可携带无记忆、存储功能的计算器。