华东交通大学2025年考研大纲：信息与软件工程学院-829数据结构(2)

（

一）基本内容

第一章

绪论

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

语言版）》，严蔚敏、吴伟民著，清华大学

出版社，2016；

《数据结构

（C

语言版）》（第二版

），

严蔚敏、李冬梅、吴伟民著，人民邮电出版社，

2021.

科目说明：不可携带计算器。