【万字总结】数据结构常考应用大题做法画法详解_树_哈希表_图_排序大总结

本篇文章的目的是，梳理一遍数据结构中容易出应用题的地方，整理成一个模版。

1.树相关应用大题

1.1 已知二叉树的中序序列和前序or中序，画出二叉树

1.2 二叉树的遍历、树的遍历、森林的遍历总结

• 二叉树的遍历，分三种，不再赘述。
• 树的遍历，分两种，先根遍历，后根遍历
  • 树的先根遍历序列=二叉树的先序遍历
  • 树的后根遍历序列=二叉树的中序遍历
• 森林的遍历，分两种，先序遍历森林，中序遍历森林
  • 先序遍历森林=对各个树进行先根遍历
  • 后序遍历森林=对各个树进行后根遍历

1.3二叉树与森林之间的转换

孩子兄弟表示法

1.3.1 已知树的先序序列和中序序列，画出森林

点睛：树是二叉树（孩子兄弟表示法）森林可不是二叉的，就是普通的

1.4 二叉树的线索化

主要是将二叉树线索化成前序线索二叉树和后序线索二叉树

做题思路:
1.写出二叉树的前序序列或后序序列
2.填充，根据第一步写出的序列，比较着，将空闲的左子树指向前驱。将空闲的右子树指向后继。

1.5 二叉排序树

1.5.1 二叉排序树的删除(重点)

二叉排序树根据删除结点的情况可分为三种情况：

先搜索找到目标结点：
1️⃣若被删除结点z是叶结点，则直接删除，不会破坏二叉排序树的性质。
2️⃣若被删除的结点只有左子树或右子树，直接让它的那个子树代替它的位置即可
3️⃣被删除的结点既有左子树又有右子树

• 从左子树找到最大的结点，代替它的位置(即左子树最右下的结点）
• 从右子树找到最小的结点，代替它的位置(即右子树最左下的结点）

1.5.2 二叉排序树的ASL成功与ASL失败

左图计算平均查找成功ASL，右图计算平均失败查找长度

查找成功：
(查询次数✖️同等查询次数结点数)➗结点总数
ASL=（1*1+2*2+3*4+4*1）/8=2.625

查找失败
(判断出是空子树需要的查找次数*这种情况的数量)/情况数
ASL=（3*7+4*2）/9=3.22

注意：空子树判断到它的父结点即可，意味着第四的空子树，判断次数是三。
注意ASL_成功每一个结点都要判断，ASL_失败每一个空子树都要判断。

1.6 平衡二叉树

平衡二叉树是一种特殊的二叉排序树

1.6.1 平衡因子

为了方便起见，给树上的每个结点附加一个数字，给出该结点左子树与右子树的高度差，这个数字称为结点的平衡因子（BF）

平衡因子=结点左子树的高度-结点右子树的高度。

因此平衡二叉树所有结点的平衡因子只能是-1、0、1，如下图，是一个平衡二叉树

1.6.2 平衡二叉树的构建(插入)

根据插入位置不同，分为四种类型

• LL(插入在左孩子的左子树）
• RR(插入在右孩子的右子树）
• LR(插入在左孩子的右子树）
• RL(插入在右孩子的左子树）

为什么假定所有子树的高度都是H

如何调整最小不平衡子树？(笔试过程中，如何调整平衡二叉树）
方法提炼:从下往上，寻找到不平衡的结点，然后以该结点出发，往下再找两个结点，这个就是它局部最小的不平衡，然后调整根节点，三个数，找中间的数，为新的根节点，把它调整，其他的结点按照二叉排序树的规则填好就行。

真题：
1.已知关键字序列22，12，13，8，9，20，33，42，44，38，24，48，60，画出对应的平衡二叉树

2.哈希函数

2.1 拉链法求平均成功查找长度与查找失败长度

ASL_成功要横着看，（一次查找到的结点数+2*两次的查到的结点数+…n*n次查到的结点数）/表中所有的结点数

ASL_失败=表中所有的结点数/mod的数

解释说明，上面给出的ASL_失败只是一种数值相等的公式，并不是理解。
拉链法中空指针算0次比较，所以拉链法在每一种查找失败的情况，就是该条链下结点的个数，mod的数，就是情况数，比如mod7，会得到0-6，7种情况。

例题如下:
【1999年 9分】

2.2 开发地址法之线性探测法求平均成功查找长度与查找失败长度

重点讲解：
1.当用哈希函数算完之后，使用线性探测的时候，要注意，分母变成了表长，不是哈希函数中的modx中的x，并且使用结果是上一步中哈希函数的结果，比如算完46%11=2，假设表长为13，线性探测就是（2+1）%13，而不是（46+1）%13，也不是（2+1）%11，这都是值得注意的。
2.在计算平均查找失败长度的过程中，每一次的情况是遇到空的时候就停止。
分母是映射空间，哈希函数是mod7，地址空间就是0-6，7种情况，从为0的情况出发一直加到6的情况
3.查找成功就是比较次数，这里不多说了

例题1:

例题2:

注意：计算ASL失败的时候，看的是映射空间 0-10 11种情况，地址为11的时候不计算ASL失败

例题3(手把手分析ASL失败和ASL成功)

分析：
ASL成功：分母是关键字的数目，分子就是插入过程中的比较次数
ASL失败：分母是情况数，mod取余13，那就是13种情况，即0-12地址。
分子：就是从当前地址出发(当前地址算比较一次)，找到下一个空白块的比较次数，假如地址到头没找到，就按照计算的hash函数，12没找到，就从0找，1…2…3

2.3 开发地址法之平方探测法求平均成功查找长度

根据题目给出的H_i函数，来具体进行平方探测法的计算，本质和线性探测是一回事

注意，线性探测平方法是，1，-1，4，-4，9，-9 别算错了

例题1:

3.图的相关应用题

3.1 根据图画邻接矩阵与邻接表(根据邻接矩阵与邻接表)

3.1.1 画邻接矩阵

3.1.2 画邻接表

不带权的情况：

带权的情况，规范的画法，是表结点中，权值在前，连接的序号在后

3.2 求图的强联通分量

如何写出一个图中的所有强连通分量？
写出一个图中的所有强连通分量

3.3 深度优先生成树与广度优先生成树

本质上就是去掉多余的边

3.4 哈夫曼树与哈夫曼编码

3.4.1 哈夫曼树WPL

带权路径长度（WPL）是指树中所有叶子结点的带权路径长度之和。具体来说，每个叶子结点的权值与其到根结点的路径长度（即经过的边数）的乘积，称为该叶子结点的带权路径长度。所有叶子结点的带权路径长度之和，即为该树的带权路径长度。

图一：4个2条边的叶子结点
图二：2个3条边的叶子结点，1个2条边的叶子结点，1个1条边的叶子结点
图三：2个3条边的叶子结点，1个2条边的叶子结点，1个1条边的叶子结点
图四：2个3条边的叶子结点，1个2条边的叶子结点，1个1条边的叶子结点
乘上对应的权值

3.4.2 构造哈夫曼树

构造步骤：
1️⃣ 找到当前权值最小的两个结点（包括两个结点构造出的新结点）
2️⃣ 将这两个结点通过一个构造出的父结点联系起来，父结点的权值是他俩权值之和。
3️⃣重复上面的步骤，直到没有结点可以添加

3.5 最小生成树

3.5.1 prim算法

核心：加入点，加入的点和之前加入的点看成一个整体
从某一个顶点出发，每次将代价(权值)最小的新顶点，加入到点集中，记录他们之间的连接边，从这个点集出发，循环上面的过程，将新结点加入，直到所有结点都加入进点集中。

时间复杂度：O（|v|²）,适用于边稠密图

例题：

3.5.2 克鲁斯卡尔算法

核心：加入边

每次选择代价最小的边，让这条边的两头连通(原本已经连通的不选)，直到所有结点都连通。
时间复杂度：O（|E|log₂|E|）,适用于边稀疏图

3.6 最短路径

3.6.1 迪杰斯特拉算法

理论方法学习:迪杰斯特拉算法求最短路径

例题1:给出一个无向图，从A出发用迪杰斯特拉算法写出到达每个顶点的最短路径

3.7 关键路径

解题思路：
拓扑排序决定了事件最早的发生的顺序
逆拓扑排序决定了事件最晚发生的顺序

起点和终点的事件最早发生时间和事件最晚发生时间相同。

做题逻辑顺序：
1.写出拓扑排序和逆拓扑排序
2.由拓扑排序写出事件的发生顺序，开始算事件最早发生时间。起点的最早发生时间是0，从这开始写。下一个事件的最早发生事件，看前面的事件+最长的活动时间(就是最晚)，到达下一个事件的时间就是算事件最早发生时间，以此类推。总结就是**，从前往后找最大**
3.从逆拓扑排序开始写，事件的最晚发生事件，由起点和终点的事件最晚发生时间相同，开写，看看前面最短的活动时间，前面事件的最早开始事件-最短的活动时间，总结就是从后往前找最小
4.活动最早的开始时间：就是活动弧尾指向事件的最早发生事件
5.活动最晚的开始时间：是活动弧头指向事件的最晚发生时间-活动时间

大总结，小口诀：

事件时间起手求，从前往后找最大，从后往前找最大
活动时间用箭头，最早弧尾，最晚弧头减活动。
注意：
终点事件的最晚发生时间就是关键路径长度
事件最早发生时间和最晚发生时间相同的事件就是关键事件
活动时间差值为0的活动就是关键路径，它的路径就是关键路径

多路径事件最早发生时间选最长的
多路径事件最晚发生时间选最短的
活动最早发生时间—弧尾顶点，最早发生时间
活动最晚发生时间----弧头顶点最迟发生时间-权值
弧头有箭头，弧尾没箭头
事件时间整体算，就是每次以起点或者终点找路径计算。

例题2:

4.排序

4.1 快速排序

真题1:


真题2:

4.2 堆排序

4.3 希尔排序

4.4 归并排序

算法思想：
把两个或多个已经有序的序列合并成一个序列，合并的过程，就是两个有序序列依次对比把更小(或更大的拿出来合并）。

算法流程：
以二路归并为例

从每一个元素都是一个队列开始都是一个独立的有序序列，相邻两个元素合并成一个，在排好序，以此类推，不断将相邻的两个有序序列合并并排好序，直到就剩一个有序序列为止。

4.5 基数排序

0到9写标号
升序，从左往右收集。将序，从右往左收集。
整体都是从上到下收集

题目来源:计算机2018年真题