数据结构A-考试复习指南.ppt

数据结构A 考试复习指南 计算机学院王海艳2 3 2020 前言 亲爱的同学 考试只是手段 不是最终目的 希望大家能踏踏实实根据教学大纲 教学要求展开复习 希望本指南对大家有所帮助 祝愿各位同学都能顺利通过考试 过一个愉快的暑假 王海艳 目录 考试题型 考试目标 主要内容 习题讲解 答疑时间安排 考试题型 数据结构A 执行考教分离制度 因而具体的考试题型不能肯定 建议采用的 常见的题型有 填空题 选择题 简答题 综合计算 程序填空题 算法设计 编程 题五大类 考试题型 填空题基本概念的掌握 理解 基本原理的考核 分值一般在20分左右 选择题易混淆的概念 知识点 易出错的一些基本结论 基本原理的考核 分值一般在10分左右 简答题基本方法 基本技能的考核 分值一般在50分左右 考试题型 综合计算 程序填空 题教学大纲中所涉及的一些能给出计算结果的基本知识点 教材中一些重要的算法的关键步的补充 分值一般在10 12分左右 算法设计 编程 题根据问题选用一些基本 常用的数据结构确立合理的存储结构来实现所需功能 或指定数据结构给出实现某种功能的算法 分值一般在8 10分左右 试题总体难度应该基本与习题相同 包括少量的个人发挥题 目录 考试题型 考试目标 主要内容 习题讲解 答疑时间安排 考试目标 促进学生学习的手段 学与不学不一样 认真学与不认真学不一样 听讲与不听讲不一样 完成作业与不完成作业不一样 课外习题与上机实验 评价教师教学水平的手段 是否能抓住基本知识点 是否能讲透重点和难点 是否能调动学生积极性共同完成教学任务 目录 考试题型 主要内容 习题讲解 答疑时间安排 考试目标 主要内容 第一章 基础知识数据结构的概念 四种常见的逻辑结构 数据的两种常用的存储表示方法 抽象数据类型的思想 算法分析的基本方法 时间 空间复杂度 主要内容 第二章 线性表线性表的顺序表示 ADT描述 插入 删除操作的实现及算法复杂度的分析 顺序表对象的应用 线性表的链接表示 单链表 查找 插入和删除运算的实现 主要内容 第二章 线性表线性表的链接表示 续 单链表带表头结点的单链表 查找 插入和删除运算的实现 单向循环链表 结构及基本运算的实现 双向链表 结构及基本运算的实现 线性表的应用 多项式的算术运算 主要内容 第三章 堆栈和队列堆栈 堆栈的概念 ADT描述 LIFO 顺序栈的基本操作 链式栈的基本操作 队列 队列的概念 ADT描述 FIFO 顺序队列的基本操作 重点是循环队列 解决 假溢出 现象 链式队列的基本操作 主要内容 第三章 堆栈和队列表达式计算 计算后缀表达式的值 中缀表达式转换为后缀表达式 主要内容 第四章 数组和字符串数组 数组的顺序表示ADT描述 顺序表示时存储地址的计算 特殊矩阵 对称矩阵的含义 对称矩阵中编号和行列对的计算对应关系 主要内容 第四章 数组和字符串稀疏矩阵 稀疏矩阵的ADT描述 三元组的表示法 行三元组 列三元组 稀疏矩阵的转置 辅助数组num k 的含义及计算 字符串 字符串的ADT描述 简单模式匹配算法 各趟匹配结果 主要内容 第四章 数组和字符串字符串 续 字符串的ADT描述 简单模式匹配算法 KMP算法 各趟匹配结果 失败函数和改进的失败函数值的计算 主要内容 第五章 树树 树的基本概念 度 二叉树的相关知识点 与树的区别 满二叉树 完全二叉树 扩充二叉树的概念及性质 二叉链表及二叉树的基本运算 二叉树的遍历 三种遍历方法的过程及执行结果 主要内容 第五章 树树和森林 树和森林的相互转换 左子右兄的原则 树和森林的遍历 堆和优先权队列 建堆运算 最大 最小堆AdjustDown 优先权队列的建立 Append和Serve运算的实现 主要内容 第五章 树哈夫曼树和哈夫曼编码 树的路径长度 加权路径长度WPL的计算 哈夫曼树的构造 哈夫曼树的编码和译码操作 主要内容 第五章 树并查集和等价关系 并查集的含义 函数Union和Find的算法实现 改进的函数Union2和Find2的算法实现 等价关系的分组 主要内容 第六章 集合和搜索集合和搜索的基本概念 动态集的含义 搜索的含义及分类 内搜索 外搜索 集合的表示 线性表 搜索树 散列表等 顺序搜索 无序表的顺序搜索 有序表的顺序搜索 算法性能分析 主要内容 第六章 集合和搜索二分搜索 二分搜索算法的含义 对半搜索算法的实现 对半搜索的二叉判定树 主要内容 第七章 搜索树二叉搜索树 二叉搜索树的含义 二叉搜索树的搜索 插入 删除操作的算法实现 二叉平衡树 AVL二叉搜索树的含义 四种平衡旋转的实现过程 二叉平衡树插入操作的算法实现 主要内容 第七章 搜索树B 树 m叉搜索树的含义 B 树的定义及有关性质 B 树的插入操作 B 树的删除操作 主要内容 第八章 散列表散列表 散列表 散列函数的含义 冲突的含义 解决冲突的方法 开散列法 拉链法 闭散列法 开地址法 线性探查法 二探查法 双散列法 主要内容 第九章 图图的基本概念 有向图 无向图 完全图 连通图 连通分量等的含义 图的两种存储结构 邻接矩阵表示法及实现 边的搜索 插入和删除操作 邻接表表示法及实现 边的搜索 插入和删除操作 主要内容 第九章 图图的遍历 DFS遍历算法执行过程及遍历结果 BFS遍历算法执行过程及遍历结果 深度优先搜索生成树和宽度优先搜索生成树 拓扑排序 AOV网的含义 TopoSort算法的实现及所有可能的执行结果 主要内容 第九章 图关键路径 AOE网的含义 关键活动及关键路径的含义 关键路径算法的实现过程 事件的可能最早发生时间和允许的最晚发生时间 活动可能的最早开始时间和允许的最晚开始时间 关键活动和关键路径长度 主要内容 第九章 图最小代价生成树 最小代价生成树的含义 Prim算法求最小代价生成树 Kruskal算法求最小代价生成树 单源最短路径 迪杰斯特拉算法求单源最短路径的过程 所有顶点之间的最短路径 Floyd算法求所有顶点之间的最短路径的过程 主要内容 第十章 内排序基本概念 稳定性 简单排序算法 简单选择排序 直接插入排序 冒泡排序 各趟排序结果及算法的性能分析 主要内容 第十章 内排序快速排序算法及性能分析 两路合并排序算法及性能分析 堆排序算法及性能分析 主要内容 第十一章 外排序文件文件的概念文件的四种基本组织方式 文件结构 文件的索引结构外排序外排序的基本过程 初始游程的生成 多路合并 竞赛树胜方树 败方树 主要内容 第十一章 外排序外排序 续 外排序的基本过程 初始游程的生成 多路合并 竞赛树胜方树 败方树 最佳合并树 最短的k叉树 目录 考试题型 考试目标 主要内容 习题讲解