906《数据结构》
一、考试性质
《数据结构》是硕士研究生招生院校招收电子信息专业硕士研究生而设置的具有选拔性质的考试科目。本考试大纲的制定力求反映招生类型的特点，科学、公平、准确、规范地测评考生的相关基础知识掌握水平，考生分析问题和解决问题及综合知识运用能力。考生应根据本大纲的内容和要求自行组织学习内容和掌握有关知识。
二、考试的总体要求
要求考生通过《数据结构》课程的学习，掌握数据结构的基本概念、基本原理和基本方法；掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析；能够运用数据结构基本原理和方法进行问题的分析与求解，具备采用C或C++语言设计与实现算法的能力。
三、考试内容
第1章 概论
1、考试内容：
（1）数据结构的基本概念
（2）算法的定义
1.算法复杂度
2.渐进表示法
2、考试要求
（1）掌握数据结构的基本概念；
（2）了解数据的逻辑结构、存储结构以及二者之间的关系；
（3）掌握算法分析方法；
（4）掌握大O记号的表示。
第2章 数据结构实现基础
（略）本章内容将在算法分析、设计中涉及，不做具体考点要求。
第3章 线性表
1、考试内容：
（1）线性表的定义和基本操作
（2）线性表的实现
1.顺序存储
2.链式存储
3.线性表的应用
4.广义表与多重链表
（3）堆栈和队列的基本概念
（4）堆栈和队列的顺序存储结构
（5）堆栈和队列的链式存储结构
（6）堆栈和队列的应用
2、考试要求
（1）了解顺序存储结构和链接存储结构的基本思想；
（2）掌握顺序表和单链表的基本算法；
（3）了解顺序表和单链表基本操作的时间性能；
（4）了解堆栈和队列的操作特性；
（5）掌握堆栈和队列基本操作的实现；
（6）了解循环队列的存储方法；
（7）掌握循环队列中队空和队满的判定条件；
（8）熟练掌握各种线性表的应用。
第4章 树与二叉树
1、考试内容：
（1）树的基本概念
（2）二叉树
1.二叉树的定义及其主要特征
2.二叉树的顺序存储结构和链式存储结构
3.二叉树的操作
（3）二叉树的应用
1.二叉搜索树
2.平衡二叉树
3.堆及其操作
4.哈夫曼树和哈夫曼编码
5.集合及其运算
2、考试要求
（1）掌握树和二叉树的性质；
（2）掌握树和二叉树的存储表示；
（3）掌握二叉树的遍历及递归/非递归算法实现；
（4）了解树与二叉树的转换关系；
（5）熟练掌握二叉树的几种应用。
第5章 散列查找
1、考试内容：
（1）查找及散列查找的基本概念
（2）散列函数的构造方法
（3）处理冲突的方法
（4）散列表的性能分析
（5）散列查找的应用
2、考试要求
（1）了解散列函数的设计方法和原则
（2）了解处理冲突的常用方法；
（3）掌握平均成功/失败查找长度的计算；
（4）了解各种查找技术的时间性能及对比。
第6章 图
1、考试内容：
（1）图的基本概念
（2）图的存储结构及基本操作
1.邻接矩阵
2.邻接表
（3）图的遍历
1.深度优先搜索
2.广度优先搜索
（4）图的基本应用
1.最小生成树的概念及两种构造算法
2.单源/多源最短路径
3.拓扑排序
4.关键路径计算
2、考试要求
（1）了解图的基本术语；
（2）了解图的各种存储表示：
（3）掌握图的两种遍历的思想及算法，能运用图的遍历算法解决图的其他相关问题；
（4）熟练掌握图的各种应用：最小生成树算法、最短路径算法、拓扑排序算法、关键路径算法。
第7章 排序
1、考试内容：
（1）排序的基本概念
（2）选择排序
1.简单选择排序
2.堆排序
（3）插入排序
1.直接插入排序
2.希尔排序
（4）交换排序
1.冒泡排序
2.快速排序
（5）归并排序
（6）基数排序
（7）各种内部排序算法的比较
2、考试要求
（1）了解各种排序算法的基本思想；
（2）掌握各种排序算法的执行过程；
（3）了解各种排序算法的设计；
（4）掌握各种排序算法时间复杂度；
（5）了解各种排序算法之间的比较。
第8章 综合应用案例分析
1、考试内容：
（1）银行排队问题
（2）畅通工程问题
2、考试要求
深刻理解各种数据结构及算法的设计思想，并能应用相应数据结构和算法的设计思想解决实际问题；对改进的算法，分析其改进的着眼点是什么，自己能否从某一个方面改进一个算法，从而提高算法设计能力；对各类相似算法方法进行综合对比，从而得出一般性结论，在实际应用中可以根据情况选取合适的算法。
四、考试形式与试卷结构
1、考试形式：闭卷、笔试。
2、试卷分值：150分。
3、考试时间：180分钟。
4、题型结构（包括但不限于）：填空题、选择题、判断题、算法分析/设计题。
5、其他要求：无。
五、参考教材
1、陈越主编，《数据结构》（第二版），高等教育出版社，2016.6
