上海工程技术大学809数据结构2020年考研专业课初试大纲.pdfVIP

上海工程技术大学（电子电气工程学院）

2020年硕士研究生入学考试《数据结构考试大纲

参考教材：《数据结构及应用算法教程（修订版）严蔚敏，陈文

博北京：清华大学出版社，2011.5

成绩总分：150分

考试时间：3小时

答题方式：闭卷、笔试

一．数据结构基本知识：

1.数据结构的基本概念

2.算法的时间复杂度和空间复杂度分析

二．线性表

1.线性表的基本概念和类型定义

2.线性表的顺序存储结构表示和基本操作实现

3.顺序表其他算法举例

4.线性表的链式存储结构表示和基本操作实现

5.单链表其他操作举例

6.循环链表和双向链表

三．栈和队列

1.栈的特点和类型定义

2.栈的表示和基本操作的实现

3.栈的应用举例

4.队列的表示和基本操作的实现

5.队列应用举例

四．串和数组

1.串的基本概念、表示和实现

2.串操作应用举例

3.数组的顺序表示和实现

4.矩阵的压缩存储

5.稀疏矩阵

五．树和二叉树

1.树的定义、术语和表示方法

2.树的存储结构、遍历方法和实现

3.二叉树的定义、性质和存储结构

4.二叉树遍历方法、实现和应用举例

5.树、森林和二叉树的相互转换

6.线索二叉树

7.哈夫曼树的定义、构造及其应用(哈夫曼编码)

六．图

1.图的定义和术语

2.图的存储结构：邻接矩阵和邻接表

3.图的遍历：深度优先有哪些信誉好的足球投注网站遍历和广度优先有哪些信誉好的足球投注网站遍历

4.连通网的最小生成树

5.单源最短路径

6.拓扑排序和关键路径

七．查找

1.静态查找表：顺序查找、折半查找和分块查找；性能分析

2.动态查找表：二叉排序树和平衡二叉树，性能分析，键树基本概

念；

3.哈希表、哈希查找和性能分析

4.哈希冲突的解决方法：闭散列法和开散列法

八．内部排序

1.内部排序的基本概念

2.插入排序：直接插入排序和希尔排序

3.交换排序：冒泡排序和快速排序

4.选择排序：直接选择排序和堆排序

5.归并排序和基数排序

九．文件

1.文件的基本概念

2.顺序文件和索引文件