资源描述
陕西科技大学硕士研究生 招生 考试 902 数据结构 考试大纲 一、 考查要点 1、 基本概念：数据、数据对象、数据元素、数据结构、数据的逻辑结构与 存储 结构、抽象数据类型、算法及算法 分析 。 2、 线性表 的定义 和基本操作， 线性表 的抽象数据类型； 线性表的顺序表示和实现、线性表的链表表示和实现、链表运算（线性链表、循环链表、双向链表） 、 应用举例 。 3、 栈的 定义 和基本 操作 ； 栈 的抽象数据类型；栈的 特性 ；顺序 栈，链式 栈 ； 栈的应用（表达式计算、递归与栈）；队列 的 定义 和基本 操作 ； 队列 的抽象数据类型； 队列的特性 ；循环 队列 ， 链式队列； 双向 队列 的插入与删除算 法 ； 队列的应用。 4、 串的 定义、 串的基本运算、串的模式匹配算法（简单算法及改进算法）。 5、 数组的定义、数组的 按行顺序存储与按列顺序存储地址计算、矩阵的压缩存储；广义表定义 和 基本操作 ，广义表的存储结构，广义表的递归算法（包括复制、求深度、求长度等算法）。 6、 树的 基本概念和 基本 操作 ， 树 的抽象数据类型； 二叉树 的概念 和 性质 ，二叉树的存储结构 ； 二叉树的 遍历 ： 前序、中序、后序遍历的递归算法及 非递归 遍历算法 ， 二叉树遍历的应用； 树 的存储结构，树与二叉树之间的转换，森林与二叉树之间的转换，树 和森林的遍历； 哈夫曼树的 构造方法、哈夫曼编码、带权路径长度的 计算。 7、 图的 基本概念 和基本操作，图的抽象数据类型 ； 图的存储 结构 （邻接矩阵表示 ，邻接表 、 逆邻接表 、 十字链表 ）； 图 的遍历： 深度优先遍历 ， 广度优先遍历； 生成树、最小生成树的概念：克鲁斯卡尔 （ Kruskal） 算法、普里姆 （ Prim） 算法 ；最短路径（单源最短路径、任意顶点间的最短路径）； 拓扑排序 和 关键路径。 8、 查找 的 概念、 关键字 比较次数，平均查找长度； 线性表 的 查找 ： 顺序 查找 、 折半查找 、 分块 查找； 树 表的 查找： 二叉排序树 、 平衡二叉树 ；哈希 （ Hash） 表的 查 找 ：哈希表的 概念、哈希函数的构造 方法、冲突处理的方法、哈希表的查找算法及分析。 9、 排序的 概念 ；排序 的稳定性； 比较 关键字 次数 ， 数据移动次数； 内 部 排序 算法 ：交换 排序（ 冒泡 排序、快速排序） ， 插入排序（ 直接 插入排序、希尔排序） ， 选择排序（ 简单 选择排序、堆排序） ， 归并排序 ；上述 各种排序算法的 基本 原理、 评价 和应用。 二、 参考书目： 数据结构（ C 语言版 ） ， 严蔚敏 、 吴伟民 编著 ，清华大学出版社 ， 2012年
展开阅读全文