2015年国防科学技术大学0811控制科学与工程考研大纲

　　科目代码：852科目名称：数据结构
　　一、考试要求
　　数据结构主要考查学生对数据结构的基本概念、基本原理和基本方法的掌握；对数据的逻辑结构、存储结构及基本操作的掌握；运用数据结构基本原理和方法进行问题的分析与求解，设计与实现算法的能力。

　　二、考试内容
　　1．数据结构概述
　　数据结构的基本概念和术语，抽象数据类型的表示，算法时空复杂性的分析和度量方法。
　　2．线性表
　　线性表的概念，线性表的顺序表示和实现，线性表的链式表示和实现以及相应算法。
　　3．栈和队列
　　栈的定义、特点及栈的表示和实现，队列的定义、特点、队列的表示和实现，桟和队列的基本运算，桟和队列的应用。
　　4．串
　　串的基本概念、存储结构、基本运算，字符串的模式匹配算法。
　　5．数组和广义表
　　数组的逻辑结构定义和存储方法，特殊矩阵和稀疏矩阵的压缩存储，广义表的定义和存储结构。
　　6．树与二叉树
　　树、二叉树和森林的定义、基本术语和存储结构，树、二叉树以及森林的遍历，线索二叉树，森林与二叉树的转换，赫夫曼树和赫夫曼编码。
　　7．图
　　图的基本概念和图的存储表示，图的深度、广度优先搜索，图的连通性问题，有向无环图及其应用，最短路径。
　　8．查找
　　查找的基本概念，顺序查找、折半查找、分块查找，二叉排序树的表示、搜索、插入、删除算法及其性能分析方法，平衡二叉树的构造、性能分析方法，B-树、B+树的搜索和构造方法；散列法，包括散列函数的构造、解决冲突的方法。
　　9．排序
　　排序的基本概念，插入排序、交换排序、选择排序、归并排序、基数排序等排序方法及其性能分析方法。

　　三、考试形式
　　考试形式为闭卷、笔试，考试时间为3小时，满分150分。
　　题型包括：选择题、简答题、编写算法题、综合题等。

　　四、参考书目
　　1．《数据结构》（c语言版）．严蔚敏等编．清华大学出版社，2013.