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

文章目录

  • 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.rhkb.cn/news/465953.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

越权访问漏洞

V2Board Admin.php 越权访问漏洞 ## 漏洞描述 V2board面板 Admin.php 存在越权访问漏洞,由于部分鉴权代码于v1.6.1版本进行了修改,鉴权方式变为从Redis中获取缓存判定是否存在可以调用… V2Board Admin.php 越权访问漏洞 漏洞描述 V2board面板 Admin.ph…

接口测试用例设计的关键步骤与技巧解析!

简介 接口测试在需求分析完成之后,即可设计对应的接口测试用例,然后根据用例进行接口测试。接口测试用例的设计也需要用到黑盒测试用例设计方法,和测试流程与理论章节的功能测试用例设计的方法类似,设计过程中还需要增加与接口特…

Redis常见面试题(二)

Redis性能优化 Redis性能测试 阿里Redis性能优化 使用批量操作减少网络传输 Redis命令执行步骤:1、发送命令;2、命令排队;3、命令执行;4、返回结果。其中 1 与 4 消耗时间 --> Round Trip Time(RTT,…

功能超全的客服快捷回复软件

客服日常工作繁忙,需要一款满足各项日常需求的客服工具,完成咨询的快捷回复,并能共享客服团队优质话术,实现云端文件储存,管理表情动图等功能 前言 客服日常工作繁忙,需要一款满足各项日常需求的客服工具。…

靠Python真的能实现经济自由,学会了你也可以

不知道大家有没有注意到,最近关注的很多人都在聊“副业and兼职”这件事。 毕竟单一收入已经不能满足现代人的需求了。 对于普通人来说,想要跳出固定思维和舒适圈,相比于孤注一掷的创业,更推荐兼职。 很多人想要创业,…

【案例分享】借助 iSpring,创造客户真正欣赏的专业在线培训体验

Safety Bee Training是一家领先的认证在线学习提供商,专门提供职业健康、安全和环境项目。它也是中东和亚洲唯一一家提供经 NASP 等国际认证机构认可的课程的培训提供商。它已经培训了超过 28,000 名学习者,并且正在不断扩大其课程范围,以提供…

IP可用端口扫描器工具(bun + typescript)

IP可用端口扫描器工具(bun typescript) 学习方式:源码学习。通过项目和源码可以学习到如下内容:1、bun搭建项目,打包项目2、net、dns等node内置模块的使用3、yargs、assert、progress、cli-color等三方包的使用ps&am…

docker镜像仓库常用命令

docker镜像仓库常用命令 docker logindocker logoutdocker pulldocker pushdocker searchdocker imagesdocker image inspectdocker tagdocker rmidocker image prunedocker savedocker loaddocker history docker login 语法: docker login [options] [server] 功能&#xff…

软件开发项目管理:实现目标的实用指南

由于软件项目多数是复杂且难以预测的,对软件开发生命周期的深入了解、合适的框架以及强大的工作管理平台是必不可少的。项目管理系统在软件开发中通常以监督为首要任务,但优秀的项目计划、管理框架和软件工具可以使整个团队受益。 软件开发项目管理的主要…

外包干了2年,快要废了。。。

先说一下自己的情况,普通本科,在外包干了2年多的功能测试,这几年因为大环境不好,我整个人心惊胆战的,怕自己卷铺盖走人了,我感觉自己不能够在这样蹉跎下去了,长时间呆在一个舒适的环境真的会让一…

【青牛科技】GC8549替代LV8549/ONSEMI在摇头机、舞台灯、打印机和白色家电等产品上的应用分析

引言 在现代电子产品中,控制芯片的性能直接影响到设备的功能和用户体验。摇头机、舞台灯、打印机和白色家电等领域对控制精度、功耗和成本等方面的要求日益提高。LV8549/ONSEMI等国际品牌的芯片曾是这些产品的主要选择,但随着国内半导体技术的进步&…

Spring挖掘:(AOP篇)

学习AOP时,我们首先来了解一下何为AOP 一. 概念 AOP(面向切面编程,Aspect Oriented Programming)是一种编程技术,旨在通过预编译方式或运行期动态代理实现程序功能的统一管理和增强。AOP的主要目标是在不改变原有业务逻辑代码的…

Centos Linux 7 搭建邮件服务器(postfix + dovecot)

准备工作 1. 一台公网服务器(需要不被服务商限制发件收件的,也就是端口25、110、143、465、587、993、995不被限制),如有防火墙或安全组需要把这些端口开放 2. 一个域名,最好是com cn org的一级域名 3. 域名备案&am…

深入了解Bootstrap框架:从入门到精通

文章目录 前言Bootstrap的核心特性1. 响应式设计2. 丰富的组件库3. 易于使用4. 良好的兼容性 安装与使用安装1. 通过CDN引入2. 下载源码3. 使用npm或yarn 基本使用1. 栅格系统2. 按钮3. 导航条4. 卡片5. 模态框6. 轮播图7. 表单 高级定制1. 修改 Sass 变量2. 按需引入组件 最佳…

ENSP RIP动态路由

RIP(距离矢量路由协议)以网络中所有链路的距离和矢量为依据计算最佳路径,是第一个动态路由协议。条数作为唯一的度量单位。默认开启水平分割(从一个路由接口学到的路由信息,便不在从这个接口发送出去)防止路…

华为海思招聘-芯片与器件设计工程师-模拟芯片方向- 机试题-真题套题题目——共8套(每套四十题)

华为海思招聘-芯片与器件设计工程师-模拟芯片方向- 机试题-真题套题题目分享——共九套(每套四十题) 岗位——芯片与器件设计工程师 岗位意向——模拟芯片 真题题目分享,完整题目,无答案(共8套) 实习岗位…

MySQL45讲 第十一讲 怎么给字符串字段加索引?

文章目录 MySQL45讲 第十一讲 怎么给字符串字段加索引?一、引言二、前缀索引(一)概念与创建方式(二)数据结构与存储差异(三)确定前缀长度的方法 三、前缀索引对覆盖索引的影响四、其他索引创建方…

字节青训-小S的倒排索引

问题描述 小S正在帮助她的朋友们建立一个搜索引擎。为了让用户能够更快地找到他们感兴趣的帖子,小S决定使用倒排索引。倒排索引的工作原理是:每个单词都会关联一个帖子ID的列表,这些帖子包含该单词,且ID按从小到大的顺序排列。 例…

讲讲分布式与集群的区别?

大家好,我是锋哥。今天分享关于【讲讲分布式与集群的区别?】面试题。希望对大家有帮助; 讲讲分布式与集群的区别? 1000道 互联网大厂Java工程师 精选面试题-Java资源分享网 在现代计算和信息技术领域,分布式系统和集…

大数据新视界 -- 大数据大厂之 Impala 性能优化:解锁大数据分析的速度密码(上)(1/30)

💖💖💖亲爱的朋友们,热烈欢迎你们来到 青云交的博客!能与你们在此邂逅,我满心欢喜,深感无比荣幸。在这个瞬息万变的时代,我们每个人都在苦苦追寻一处能让心灵安然栖息的港湾。而 我的…