数据结构应用题解构思维导图
数据结构应用题解构详解
树图思维导图提供 数据结构应用题解构 在线思维导图免费制作，点击“编辑”按钮，可对 数据结构应用题解构 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：aa5e150ae76e3f6221d3e36b5fe6da76
思维导图大纲
数据结构应用题解构思维导图模板大纲
上节课的任务
1. 根据数据结构考试大纲，筛选出你认为有可能出“应用题”的考点，并在纸上罗列一个清单
2. 复习上述考点
3. 跟着数据结构强化课第二场直播，训练应用题
哪里可能考大题？
一、线性表
(一)线性表的基本概念
(二)线性表的实现
1.顺序存储
2.链式存储
(三)线性表的应用
通常考算法
二、栈、队列和数组
(一)栈和队列的基本概念
(二)栈和队列的顺序存储结构
(三)栈和队列的链式存储结构
(四)多维数组的存储
(五)特殊矩阵的压缩存储
(六)栈、队列和数组的应用
栈的应用
队列的应用
数组的应用
三、树与二叉树
(一)树的基本概念
(二)二叉树
1.二叉树的定义及其主要特征
2.二叉树的顺序存储结构和链式存储结构
3.二叉树的遍历
4.线索二叉树的基本概念和构造
(三)树、森林
1.树的存储结构
2.森林与二叉树的转换
3.树和森林的遍历
(四)树与二叉树的应用
1.哈夫曼(Huffman)树和哈夫曼编码
2.并查集及其应用
四、图
(一)图的基本概念
(二)图的存储及基本操作
1.邻接矩阵
2.邻接表
3.邻接多重表、十字链表
(三)图的遍历
1.深度优先搜索
2.广度优先搜索
(四)图的基本应用
1.最小(代价)生成树
2.最短路径
3.拓扑排序
4.关键路径
五、查找
(一)查找的基本概念
(二)顺序查找法
(三)分块查找法
(四)折半查找法
(五)树型查找
1.二叉树搜索树
2.平衡二叉树
3.红黑树
(六)B 树及其基本操作、B+树的基本概念
(七)散列(Hash)表
(八)字符串模式匹配
(九)查找算法的分析及应用
六、排序
(一)排序的基本概念
(二)直接插入排序
(三)折半插入排序
(四)起泡排序(bubble sort)
(五)简单选择排序
(六)希尔排序(shell sort)
(七)快速排序
(八)堆排序
(九)二路归并排序(merge sort)
(十)基数排序
(十一)外部排序
(十二)排序算法的分析和应用
怎么考？
“数组”的应用题命题角度
矩阵压缩存储
对称矩阵
上/下三角矩阵
三对角矩阵
“栈、队列”的应用题命题角度
数据结构定义
顺序存储
链式存储
用单向链表实现
用双向链表实现
用循环链表实现
手绘数据结构
给一个初始状态，在此基础上进行插入、删除一个元素，手绘画出来
基本操作代码实现
插入、删除、判空、判满
“树”的应用题命题角度
关于性质的计算、推导
结点数、边数、度数、树高等
数据结构 Struct 定义
二叉树
顺序存储
链式存储
多叉树、森林
顺序存储
双亲表示法
链式存储
孩子表示法
孩子兄弟表示法
树的应用
哈夫曼树
手绘、文字描述：建立哈夫曼树的过程
手绘、文字描述：查找哈夫曼树（译码）的过程
并查集
数据结构定义（树的双亲表示法）
基本操作
Union 并
代码实现
手绘示意图
find 查
代码实现
路径压缩 手绘示意图
二叉查找树、平衡二叉树
数据结构定义
手绘：插入元素
手绘：删除元素（平衡二叉树考删除的概率较低）
查找长度分析（关键字对比次数）
“图”的应用题命题角度
关于性质的计算、推导
结点数、边数、度数、连通性、强连通性等
图基础考察
数据结构定义
领接矩阵
邻接表
低优先级：多重邻接表、十字链表
手绘
给出邻接矩阵，要求手绘图的样子
给出邻接表，要求手绘图的样子
给出图，要求手绘邻接矩阵的样子
给出图，要求手绘邻接表的样子
图的特别应用
最小生成树MST
Prim
手绘：算法执行过程
文字描述：算法执行过程
Kruskal
手绘：算法执行过程
文字描述：算法执行过程
若需要判断MST是否唯一、是否有多种形态，可优先考虑使用Kruskal
最短路径
Dj
文字描述：给一个图，描述算法每一轮的执行过程
Floyd
大题考察概率低，主要准备小题
有精力的同学手动模拟一遍
拓扑排序
文字描述：给一个图，描述每一轮拓扑排序过程
应用：结点代表动作、有向边代表各个动作的先后顺序
关键路径
文字描述训练：略，太难描述
快速解题技巧训练：怎么快速得出路径？
起点到终点的最长路径
“查找”的应用题命题角度
分析
ASL
成功
失败
时间、空间复杂度
直接给全新的查找代码，让你分析
应用
手绘算法过程
文字描述算法过程
根据题目条件应用某种查找算法
“排序”的应用题命题角度
分析
比较次数
稳定性
时间、空间复杂度
应用
手绘算法过程
注意代码难写的算法，更容易考应用题手绘
代码简单的算法，更可能在算法题考察
文字描述算法过程
根据题目条件应用某种排序算法
做题技巧
过程需要详细说明吗？
题目不说就不用
省时间
eg：对比
不用写过程：2011年 41 题
必须写过程：2016年 42 题
直接写答案的坏处是什么？
坏处
只写答案不写过程，那么，一旦答案错误，分会全部扣完
建议
如果有数字计算，或矩阵等容易算错的东西，则可以写计算过程，防止结果错误，还能得到过程分
如果时间不够，可以直接写计算结果
如果对自己的答案很有信心，可以不写过程，节省时间
eg：2010年 41 题
第二小问，计算平均查找长度
如果只写答案不写计算式，且答案正确，得满分
如果只写答案不写计算式，且答案错误，得0分
如果写了答案也写了计算式，且答案错误，则只要计算式正确，可得一半分
给分规则是什么？
踩点给分
能给尽给
不会做的、不确定的题尽量别空着，写上就有希望得分
沪公网安备 31011502019485号
上海工商