上海工程技术大学（电子电气工程学院）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. 顺序文件和索引文件
相关推荐：
loading