软件学院2011年工程硕士考试大纲

　　工程领域：软件工程
　　考试科目：数据结构
　　参考教材：
　　《数据结构》（第二版），严蔚敏等编著，清华大学出版社出版
　　基本内容：
　　1.线性表
　　（1）线性表的定义和基本操作
　　（2）线性表的实现
　　①顺序存储
　　②链式存储
　　③线性表的应用 
　　2.栈、队列和数组
　　（1）栈和队列的基本概念
　　（2）栈和队列的顺序存储结构
　　（3）栈和队列的链式存储结构
　　（4）栈和队列的应用
　　（5）特殊矩阵的压缩存储 
　　3.树与二叉树
　　（1）树的概念
　　（2）二叉树
　　①二叉树的定义及其主要特征
　　②二叉树的顺序存储结构和链式存储结构
　　③二叉树的遍历
　　④线索二叉树的基本概念和构造
　　（3）树、森林
　　①树的存储结构
　　②森林与二叉树的转换
　　③树和森林的遍历
　　（4）树与二叉树的应用
　　①二叉排序树
　　②平衡二叉树
　　③哈夫曼（Huffman）树和哈夫曼编码 
　　4.图
　　（1）图的基本概念
　　（2）图的存储及基本操作
　　① 邻接矩阵法
　　②  邻接表法
　　（3）图的遍历
　　① 深度优先搜索
　　②广度优先搜索
　　（4）图的基本应用
　　 ① 最小（代价）生成树
　　② 最短路径
　　③ 拓扑排序
　　④  关键路径 
　　5.查找
　　（1）查找的基本概念
　　（2）顺序查找法
　　（3）折半查找法
　　（4）B树及其基本操作、B+树的基本概念
　　（5）散列（Hash）表
　　（6）查找算法的分析及应用 
　　6.排序
　　（1）排序的基本概念
　　（2）插入排序
　　  ①直接插入排序
　　  ② 折半插入排序
　　（3）气泡排序（bubble sort）
　　（4）简单选择排序
　　（5） 希尔排序（shell sort）
　　（6） 快速排序
　　（7）堆排序
　　（8）二路归并排序（merge sort）
　　（9）基数排序
　　（10）各种内部排序算法的比较
　　题目类型： 
　　1.选择题
　　2.简答题