文章目录
- 1.树相关应用大题
- 1.1 已知二叉树的中序序列和前序or中序,画出二叉树
- 1.2 二叉树的遍历、树的遍历、森林的遍历总结
- 1.3二叉树与森林之间的转换
- 1.3.1 已知树的先序序列和中序序列,画出森林
- 1.4 二叉树的线索化
- 1.5 二叉排序树
- 1.5.1 二叉排序树的删除(重点)
- 1.5.2 二叉排序树的ASL成功与ASL失败
- 1.6 平衡二叉树
- 1.6.1 平衡因子
- 1.6.2 平衡二叉树的构建(插入)
- 2.哈希函数
- 2.1 拉链法求平均成功查找长度与查找失败长度
- 2.2 开发地址法之线性探测法求平均成功查找长度与查找失败长度
- 2.3 开发地址法之平方探测法求平均成功查找长度
- 3.图的相关应用题
- 3.1 根据图画邻接矩阵与邻接表(根据邻接矩阵与邻接表)
- 3.1.1 画邻接矩阵
- 3.1.2 画邻接表
- 3.2 求图的强联通分量
- 3.3 深度优先生成树与广度优先生成树
- 3.4 哈夫曼树与哈夫曼编码
- 3.4.1 哈夫曼树WPL
- 3.4.2 构造哈夫曼树
- 3.5 最小生成树
- 3.5.1 prim算法
- 3.5.2 克鲁斯卡尔算法
- 3.6 最短路径
- 3.6.1 迪杰斯特拉算法
- 3.7 关键路径
- 4.排序
- 4.1 快速排序
- 4.2 堆排序
- 4.3 希尔排序
- 4.4 归并排序
- 4.5 基数排序
本篇文章的目的是,梳理一遍数据结构中容易出应用题的地方,整理成一个模版。
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 开发地址法之平方探测法求平均成功查找长度
根据题目给出的Hi函数,来具体进行平方探测法的计算,本质和线性探测是一回事
注意,线性探测平方法是,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|2),适用于边稠密图
例题:
3.5.2 克鲁斯卡尔算法
核心:加入边
每次选择代价最小的边,让这条边的两头连通(原本已经连通的不选),直到所有结点都连通。
时间复杂度:O(|E|log2|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年真题