2019年广东技术师范学院813数据结构考试大纲.doc

广东技术师范学院2019 年研究生招生专业课考试大纲填报表一、 考试科目代码及名称：813 数据结构二、 招生学院（盖学院公章）：计算机科学学院基本内容:考查目标本课程主要考查学生对数据结构基础知识的理解和掌握程度、以及是否具备对经典数据结构和算法的应用能力，具体包括如下考查目标：（1）掌握数据结构的基本概念、基本原理和基本方法。（2）掌握数据的逻辑结构、存储结构及其基本操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析。（3）能够运用数据结构的基本原理和方法进行问题的分析和求解，具备采用 C、C+ 或 Java 语言设计与实现算法的能力。试卷题型与分值结构一、判断题 （10 分）二、选择题 （30 分）二、填空题 （40 分）三、解答题 （60 分）四、算法设计题 （10 分）考试内容一、数据结构基本概念1. 数据结构的定义2. 逻辑结构类型3. 存储结构类型4. 算法及其描述5. 算法分析：时间复杂度、空间复杂度二、线性表1. 线性表的定义和基本操作2. 线性表的顺序存储结构：顺序表及其基本运算3. 线性表的链式存储结构：单链表、双链表、循环链表及其基本运算4. 线性表的应用三、栈和队列1. 栈1）栈的基本概念2）栈的顺序存储结构及其基本运算3）栈的链式存储结构及其基本运算4）栈的应用2. 队列1）队列的基本概念2）队列的顺序存储结构及其基本运算3）队列的链式存储结构及其基本运算4）队列的应用四、串1. 串的基本概念2. 串的顺序存储结构及其基本运算3. 串的链式存储结构及其基本运算五、递归1. 递归的基本概念以及实现过程2. 递归算法的设计六、数组和广义表1. 数组的顺序存储结构2. 稀疏数组的概念和压缩存储方法3. 稀疏矩阵的三元组存储结构和基本操作4. 疏矩阵的十字链表存储结构5. 广义表的基本概念及其存储结构七、树和二叉树1. 树的基本概念2. 二叉树的基本概念3. 二叉树与树、森林之间的转换4. 二叉树的顺序存储结构和链式存储结构5. 二叉树的基本运算6. 二叉树的遍历7. 二叉树的构造8. 哈夫曼树八、图1. 图的基本概念2. 图的存储结构3. 图的遍历4. 最小生成树5. 最短路径6. 拓扑排序7. 关键路径九、查找1. 查找的基本概念及其效率的评价方法2. 线性表的查找：顺序查找、折半查找、分块查找3. 树表的查找：二叉排序树、B-树4. 哈希表的基本概念，哈希函数的构造和处理冲突的基本方法十、内排序1. 排序的基本概念2. 插入排序：直接插入排序、折半插入排序、希尔排序3. 交换排序：冒泡排序、快速排序4. 选择排序：直接选择排序、堆排序5. 归并排序6. 基数排序7. 各种内排序算法的比较参考书目(须与专业目录一致)(包括作者、书目、出版社、出版时间、版次)：1 数据结构教程 （第 4 版） ，李春葆 主编，清华大学出版社，2013 年。2同类型教材。