数据结构阶段测试2的一点小补充
数据结构阶段测试2的一点小补充
1.已知⼩根堆为8,15,10,21,34,16,12,删除关键字8之后需重建堆,最后的叶⼦ 节点为()
A. 34 B. 21 C. 16 D. 12
解题思路
向下调整算法删除堆顶元素
💡 答案:C
删除堆顶元素的思路:
先将堆顶元素和当前堆结构的最后⼀个元素交换,堆有效元素个数 减⼀,从⽽实现堆顶元素的删除。但是交换后的堆顶元素还需要进⾏向下调整的操作,从 ⽽保持现有堆的性质。
运用到的知识:
堆的概念与结构
如果有⼀个关键码的集合 ,把它的所有元素按完全⼆叉树的顺序存储⽅ 式存储,在⼀个⼀维数组中,并满⾜: ( 且 ), i = 0、1、2… ,则称为⼩堆(或⼤堆)。将根结点最⼤的堆叫做最⼤堆或⼤根堆,根结点最⼩的堆叫做最⼩堆或⼩根堆。
堆具有以下性质
• 堆中某个结点的值总是不⼤于或不⼩于其⽗结点的值;
• 堆总是⼀棵完全⼆叉树。
进阶结论:
小堆的堆顶是最小值;大堆的堆顶是最大值
虽然堆的底层是数组,但是不一定有序的
💡 ⼆叉树性质
• 对于具有 n 个结点的完全⼆叉树,如果按照从上⾄下从左⾄右的数组顺序对所有结点从 0 开始编号,则对于序号为 i 的结点有:
- 若 i>0 , i 位置结点的双亲序号: (i-1)/2 ; i=0 , i 为根结点编号,⽆双亲结点
- 若 2i+1=n 否则⽆左孩⼦
- 若 2i+2=n 否则⽆右孩⼦
注意点:
第一点是求父节点的;第二第三点是求左右孩子节点的
堆的实现:
堆的基本结构:
typedef int HPDataType;
typedef struct Heap
{HPDataType* arr;HPDataType size;//有效的数据个数HPDataType capacity;//空间大小
}HP;
堆的初始化:(类似于顺序表)
void HPInit(HP* php)
{assert(php);php->arr = NULL;php->size = php->capacity = 0;
}
堆的销毁:
void HPDestory(HP* php)
{assert(php);if (php->arr)free(php->arr);php->arr = NULL;php->size = php->capacity = 0;
}
堆的插入:
这里会用到堆的向上调整算法
void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}void AdjustUp(HPDataType* arr,int child)
{int parent = (child - 1) / 2;while (child > 0)//不需要等于,child只要走到根节点的位置,根节点没有父节点不需要交换{if (arr[child] < arr[parent]){Swap(&arr[parent], &arr[child]);child = parent;parent = (child - 1) / 2;}else{break;}}}void HPPush(HP* php, HPDataType x)
{assert(php);//判断空间是否足够if (php->size == php->capacity){//扩容int newCapacity = php->capacity == 0 ? 4 : 2 * php->capacity;HPDataType* tmp = (HPDataType*)realloc(php->arr, newCapacity * sizeof(HPDataType));if (tmp == NULL){perror("realloc fail!");exit(1);}php->arr = tmp;php->capacity = newCapacity;}php->arr[php->size] = x;AdjustUp(php->arr, php->size);++php->size;
}
堆的删除:(删除元素,删除的是堆顶的元素)
这里会用到堆的向下调整算法
void AdjustDown(HPDataType* arr, int parent, int n)
{int child = parent * 2 + 1;//左孩子while (child < n){//找左右孩子中最小的if (child + 1 < n && arr[child] > arr[child + 1]){child++;}if (arr[child] < arr[parent]){Swap(&arr[child], &arr[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}
void HPPop(HP* php)
{assert(php && php->size);Swap(&php->arr[0], &php->arr[php->size - 1]);--php->size;AdjustDown(php->arr,0, php->size);}
- 对于序列{ 12,13,11,18,60,15,7,19,25,100 },⽤筛选法建堆,应该从值为 ()的数据开始建初始堆。
A. 100 B. 12 C. 60 D. 15
解析思路
💡 答案:C
筛选法建堆:
就是从最后⼀个⾮叶⼦节点开始向下调整建堆。这⾥其实就是要计算最后⼀ 个⾮叶⼦节点的数据。
即:从最后⼀个结点的⽗亲结点开始,所以是n/2。
3.将整数数组( 7-6-3-5-4-1-2 )按照堆排序的⽅式进⾏升序排列,请问在第⼀ 轮排序结束之后,数组的顺序是()
A. 1-2-3-4-5-6-7 B. 2-6-3-5-4-1-7 C. 6-5-3-2-4-1-7 D. 5-4-3-2-1-6-7
💡 答案:C
堆排序的原理:
每次将堆顶元素和当前堆结构的最后⼀个元素进⾏交换,从⽽将当前堆中的最值交换到最 后,从⽽将数据进⾏排序。
不同的顺序排序应该建⽴什么堆:
排升序需要建⽴⼤堆,排降序需要建⽴⼩堆。
4.以30为基准,设⼀组初始记录关键字序列为 (30,15,40,28,50,10,70),则第⼀ 趟快速排序结果为()
A. 10,28,15,30,50,40,70
B. 10,15,28,30,50,40,70
C. 10,28,15,30,40,50,70
D. 10,15,28,30,40,50,70
解题思路
💡 答案:B
**下⾯的思路是使⽤挖坑法: **
初始化左指针为1,右指针为6
从右指针开始⽐较,右指针⾃减,到10的时候发现⽐30⼩,两者交换得到:
10,15,40,28,50,30,70
从左指针开始⽐较,左指针⾃增,到40的时候发现⽐30⼤,两者交换得到:
10,15,30,28,50,40,70
从右指针开始⽐较,右指针⾃减,到28的时候发现⽐30⼩,两者交换得到:
10,15,28,30,50,40,70
此时完成第⼀趟排序,已经满⾜30的左边都⽐30⼩,右边都⽐30⼤
知识点:
挖坑法
思路: 创建左右指针。⾸先从右向左找出⽐基准⼩的数据,找到后⽴即放⼊左边坑中,当前位置变为新 的"坑",然后从左向右找出⽐基准⼤的数据,找到后⽴即放⼊右边坑中,当前位置变为新的"坑",结 束循环后将最开始存储的分界值放⼊当前的"坑"中,返回当前"坑"下标(即分界值下标)
从右指针开始⽐较,右指针⾃减,到28的时候发现⽐30⼩,两者交换得到:
10,15,28,30,50,40,70
此时完成第⼀趟排序,已经满⾜30的左边都⽐30⼩,右边都⽐30⼤
知识点:
挖坑法
思路: 创建左右指针。⾸先从右向左找出⽐基准⼩的数据,找到后⽴即放⼊左边坑中,当前位置变为新 的"坑",然后从左向右找出⽐基准⼤的数据,找到后⽴即放⼊右边坑中,当前位置变为新的"坑",结 束循环后将最开始存储的分界值放⼊当前的"坑"中,返回当前"坑"下标(即分界值下标)
相关文章:

数据结构阶段测试2的一点小补充
数据结构阶段测试2的一点小补充 1.已知⼩根堆为8,15,10,21,34,16,12,删除关键字8之后需重建堆,最后的叶⼦ 节点为() A. 34 B. 21 C. 16 D. 12 解题思路 向下调整算法删除堆顶元素 💡 答案:C 删除堆顶元素的思路: …...
量化交易里面的挂单成交率大概是多少呢
炒股自动化:申请官方API接口,散户也可以 python炒股自动化(0),申请券商API接口 python炒股自动化(1),量化交易接口区别 Python炒股自动化(2):获取…...

【Android 14源码分析】Activity启动流程-3
忽然有一天,我想要做一件事:去代码中去验证那些曾经被“灌输”的理论。 – 服装…...
Javascript客户端时间与服务器时间
在Java代码中使用new Date(),获取的是本机时间; 但是在Javascript 中使用new Date(),获取的却是访问该页面的客户端时间。 这样,就可能会出现一个问题:我的电脑时间比正常时间要快,我访问一个页面&#x…...
系统架构设计师教程 第11章 11.4 边缘计算概述 笔记
11.4 边缘计算概述 ★★☆☆☆ 11.4.1 边缘计算概念 边缘计算将数据的处理、应用程序的运行甚至一些功能服务的实现,由 网络中心下放到网络边缘的节点上。在网络边缘侧的智能网关上就近采集并且处理数据,不需要上传原生数据。 11.4.2 边缘计算的定义 1…...
CSS全解析
文章目录 CSS全解析一、CSS是什么二、基本语法规范三、引入方式(一)内部样式表(二)行内样式表(三)外部样式 四、代码风格(一)样式格式(二)样式大小写…...

一款基于 Java 的可视化 HTTP API 接口快速开发框架,干掉 CRUD,效率爆炸(带私活源码)
平常我们经常需要编写 API,但其实常常只是一些简单的增删改查,写这些代码非常枯燥无趣。 今天给大家带来的是一款基于 Java 的可视化 HTTP API 接口快速开发框架,通过 UI 界面编写接口,无需定义 Controller、Service、Dao 等 Jav…...

CSS3渐变
一、线性渐变 通过background-image: linear-gradient(...)设置线性渐变 语法: linear-gradient(direction,color1,color2, . . ) direction:渐变方向,默认从上到下,可选值: 简单选取: ① to right&…...

Emissive CEO Fabien Barati谈《消失的法老》背后的故事:XR大空间体验的创新与未来
在最近的一次播客访谈中,虚拟现实之声(Voices of VR)的主持人Kent Bye与Emissive公司的联合创始人兼CEO Fabien Barati进行了深入交流。Emissive是全球顶级的VR大空间体验制作商之一,以其沉浸式探险项目如《永恒的巴黎圣母院》和《胡夫地平线》而闻名。以下是这次访谈的核心…...
mysql设置表的某一个字段每天定时清零
推荐学习文档 golang应用级os框架,欢迎stargolang应用级os框架使用案例,欢迎star案例:基于golang开发的一款超有个性的旅游计划app经历golang实战大纲golang优秀开发常用开源库汇总想学习更多golang知识,这里有免费的golang学习笔…...

实例分割、语义分割和 SAM(Segment Anything Model)
实例分割、语义分割和 SAM(Segment Anything Model) 都是图像处理中的重要技术,它们的目标是通过分割图像中的不同对象或区域来帮助识别和分析图像,但它们的工作方式和适用场景各有不同。 1. 语义分割(Semantic Segme…...

深度学习项目----用LSTM模型预测股价(包含LSTM网络简介,代码数据均可下载)
前言 前几天在看论文,打算复现,论文用到了LSTM,故这一篇文章是小编学LSTM模型的学习笔记;LSTM感觉很复杂,但是结合代码构建神经网络,又感觉还行;本次学习的案例数据来源于GitHub,在…...

《精通开关电源设计》笔记一
重点 效率 纹波 环路响应 尺寸,从静态到动态的研究方法,假设开关电源稳态运行,以电感为中心,根据半导体器件(mos管或二极管)分段分析电路的状态,工具有电路原理和能量守恒 影响效率的主要是开关损耗,所以…...
QLoRA代码实战
QLoRA原理参考: BiliBili:4bit量化与QLoRA模型训练 zhihu:QLoRA(Quantized LoRA)详解 下载llama3-8b模型 from modelscope import snapshot_download model_dir snapshot_download(LLM-Research/Meta-Llama-3-8B-In…...
pyqt QGraphicsView 以鼠标为中心进行缩放
注意几个关键点: 1. 初始化 class CustomGraphicsView(QGraphicsView):def __init__(self, parentNone):super(CustomGraphicsView, self).__init__(parent)self.scene QGraphicsScene()self.setScene(self.scene)self.setGeometry(0, 0, 1024, 600)# 以下初始化…...

FPGA-Vivado-IP核-逻辑分析仪(ILA)
ILA IP核 背景介绍 在用FPGA做工程项目时,当Verilog代码写好,我们需要对代码里面的一些关键信号进行上板验证查看。首先,我们可以把需要查看的这些关键信号引出来,接好线通过示波器进行实时监测,但这会用到大量的线材…...

基于webComponents的纯原生前端框架
我本人的个人开发web前端前框架xui,正在开发中,业已完成50%的核心开发工作,并且在开发过程中逐渐完善. 目前框架未采用任何和市面上框架模式,没有打包过程,实现真实的开箱即用。 当然在开发过程中也会发现没有打包工…...
OpenCV-背景建模
文章目录 一、背景建模的目的二、背景建模的方法及原理三、背景建模实现四、总结 OpenCV中的背景建模是一种在计算机视觉中从视频序列中提取出静态背景的技术。以下是对OpenCV背景建模的详细解释: 一、背景建模的目的 背景建模的主要目标是将动态的前景对象与静态的…...
一个简单的摄像头应用程序6
主要改进点: 使用 ThreadPoolExecutor 管理多线程: 使用 concurrent.futures.ThreadPoolExecutor 来管理多线程,这样可以更高效地处理图像。 在 main 函数中创建一个 ThreadPoolExecutor,并在每个循环中提交图像处理任务。 减少…...

Pikachu-目录遍历
目录遍历,跟不安全文件上传下载有差不多; 访问 jarheads.php 、truman.php 都是通过 get 请求,往title 参数传参; 在后台,可以看到 jarheads.php 、truman.php所在目录: /var/www/html/vul/dir/soup 图片…...
谷歌浏览器插件
项目中有时候会用到插件 sync-cookie-extension1.0.0:开发环境同步测试 cookie 至 localhost,便于本地请求服务携带 cookie 参考地址:https://juejin.cn/post/7139354571712757767 里面有源码下载下来,加在到扩展即可使用FeHelp…...

JavaSec-RCE
简介 RCE(Remote Code Execution),可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景:Groovy代码注入 Groovy是一种基于JVM的动态语言,语法简洁,支持闭包、动态类型和Java互操作性,…...
[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解
突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 安全措施依赖问题 GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...

Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误
HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误,它们的含义、原因和解决方法都有显著区别。以下是详细对比: 1. HTTP 406 (Not Acceptable) 含义: 客户端请求的内容类型与服务器支持的内容类型不匹…...
椭圆曲线密码学(ECC)
一、ECC算法概述 椭圆曲线密码学(Elliptic Curve Cryptography)是基于椭圆曲线数学理论的公钥密码系统,由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA,ECC在相同安全强度下密钥更短(256位ECC ≈ 3072位RSA…...

AI书签管理工具开发全记录(十九):嵌入资源处理
1.前言 📝 在上一篇文章中,我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源,方便后续将资源打包到一个可执行文件中。 2.embed介绍 🎯 Go 1.16 引入了革命性的 embed 包,彻底改变了静态资源管理的…...
鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南
1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发,使用DevEco Studio作为开发工具,采用Java语言实现,包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...
高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数
高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...

AirSim/Cosys-AirSim 游戏开发(四)外部固定位置监控相机
这个博客介绍了如何通过 settings.json 文件添加一个无人机外的 固定位置监控相机,因为在使用过程中发现 Airsim 对外部监控相机的描述模糊,而 Cosys-Airsim 在官方文档中没有提供外部监控相机设置,最后在源码示例中找到了,所以感…...

(一)单例模式
一、前言 单例模式属于六大创建型模式,即在软件设计过程中,主要关注创建对象的结果,并不关心创建对象的过程及细节。创建型设计模式将类对象的实例化过程进行抽象化接口设计,从而隐藏了类对象的实例是如何被创建的,封装了软件系统使用的具体对象类型。 六大创建型模式包括…...