当前位置: 首页 > article >正文

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

文章目录

  • 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年真题


http://www.kler.cn/a/384467.html

相关文章:

  • 【Spring】Spring Web MVC基础入门~(含大量例子)
  • 【网络原理】关于HTTP状态码以及请求的构造的哪些事
  • 【Java SE语法】抽象类(abstract class)和接口(interface)有什么异同?
  • 分布式和微服务的区别
  • xrc的比赛
  • 揭秘全向轮运动学:机动艺术与上下位机通信的智慧桥梁
  • 【金融风控】相关业务介绍及代码详解
  • (vue3)在Pinia Store中正确使用Vue I18n
  • 掌握Rust模式匹配:从基础语法到实际应用
  • HarmonyOS NEXT 应用开发实战(九、知乎日报项目详情页实现详细介绍)
  • 【MATLAB源码-第210期】基于matlab的OFDM电力线系统仿真,不同梳状导频间隔对比。三种信道估计,三种插值误码率对比
  • 市场营销应该怎么学?
  • SW - 将step中的输入实体转成零件
  • wpf 制作丝滑Flyout浮出侧边栏Demo (Mahapps UI框架)
  • Springboot 整合 Java DL4J 打造自然语言处理之语音识别系统
  • TypeScript完整学习 --【比降价金还值!】
  • 计算机毕业设计Python+图神经网络手机推荐系统 手机价格预测 手机可视化 手机数据分析 手机爬虫 Django Flask Spark 知识图谱
  • vue3 ref对象的width改变了,并不会直接去更新视图,但是触发obj.width++是可以正常更新视图的简单处理方法
  • springBoot动态加载jar,将类注册到IOC
  • MongoDB笔记01-概念与安装
  • <网络> 协议
  • go 集成viper 配置管理
  • 简易抽奖器源码以及打包操作
  • 【网络-交换机】生成树协议、环路检测
  • Java 8 Stream API 详解
  • 实时金融股票数据API接口websocket接入方法