天津工业大学硕士研究生入学考试业务课考试大纲
　　科目编号：834                                          科目名称：数据结构

　　一、考试的总体要求
　　《数据结构》是计算机科学与技术专业、软件工程专业和网络工程专业等计算机技术领域专业的专业基础课。
　　该课程考试要求考生比较系统地理解数据结构的基本概念、基本原理和方法，掌握数据的逻辑结构、存储结构及其差异，以及各种基本操作的实现。能够运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题。能够对算法进行设计与分析，能够选择合适的数据结构和方法进行问题求解。
　　二、考试的内容及比例
　　（一）线性表
　　⒈ 线性表的定义和基本操作
　　⒉ 线性表的实现
　　（1）顺序存储结构
　　（2）链式存储结构
　　（3）线性表的应用
　　（二）栈、队列和数组
　　⒈ 栈和队列的基本概念
　　⒉ 栈和队列的顺序存储结构
　　⒊ 栈和队列的链式存储结构
　　⒋ 栈和队列的应用
　　⒌ 特殊矩阵的压缩存储
　　（三）树与二叉树
　　⒈ 树的基本概念
　　⒉ 二叉树
　　（1）二叉树的定义及其主要特征
　　（2）二叉树的顺序存储结构和链式存储结构
　　（3）二叉树的遍历
　　（4）线索二叉树的基本概念和构造
　　⒊ 树、森林
　　（1）书的存储结构
　　（2）森林与二叉树的转换
　　（3）树和森林的遍历
　　⒋ 树与二叉树的应用
　　（1）二叉排序树
　　（2）平衡二叉树
　　（3）哈夫曼树和哈夫曼编码
　　（四）图
　　⒈ 图的概念
　　⒉ 图的存储及基本操作
　　（1）邻接矩阵法
　　（2）邻接表法
　　⒊ 图的遍历
　　（1）深度优先搜索
　　（2）广度优先搜索
　　⒋ 图的基本应用及其复杂度分析
　　（1）最小（代价）生成树
　　（2）最短路径
　　（3）拓扑排序
　　（4）关键路径
　　（五）查找
　　⒈ 查找的基本概念
　　⒉ 顺序查找法
　　⒊ 有序表的查找方法
　　⒋ 二叉排序树和平衡二叉树
　　⒌ B-树
　　⒍ 哈希表及其查找
　　⒎ 查找算法的分析及应用
　　（六）内部排序
　　⒈ 排序的基本概念
　　⒉ 插入排序
　　（1）直接插入排序
　　（2）折半插入排序
　　⒊ 起泡排序
　　⒋ 简单选择排序
　　⒌ 希尔排序
　　⒍ 快速排序
　　⒎ 堆排序
　　⒏ 二路归并排序
　　⒐ 基数排序
　　10. 各种内部排序算法的比较
　　1⒈ 内部排序算法的应用
　　三、试卷的题型及比例 （待定）
　　考试题型包括填空题（20分）、选择题（40分）、判断题（16分）、综合应用题（74分），满分150分。
　　四、考试形式及时间
　　考试形式为笔试，时间为3个小时。
　　五、主要参考教材
　　严蔚敏， 吴伟民主编，《数据结构 （C语言版）》（第三版），清华大学出版社，2007年。