【笔记】408刷题笔记

文章目录

  • 三对角
    • 三叉树求最小带权路径
    • UDP报文首部和TCP报文首部
      • IP报文首部
      • TCP报文首部
      • UDP报文首部
    • 刷新和再生的区别
      • 地址译码

为了区分队空队满,可以使用三种处理方式
1)牺牲一个单元 队头指针在队尾指针的下一位置作为队满的标志

  • 队满条件:(Q.rear+1)%MaxSize==Q.front
  • 队空条件:Q.front==Q.rear
  • 队列中元素的个数:(Q.rear-Q.front+MaxSize)%MaxSize
  1. 设置tag数据队员 区分队满队空
  2. 类型中增设表示元素个数的数据队员

森林转换为二叉树时满足左孩子,右兄弟,如果二叉树中左指针为空,说明在森林中该界定啊没有孩子,即该节点在森林中为叶子节点。

B树中所有结点的孩子结点数最大值称为B树的阶(m)

  • 树中每个节点至多有m棵子树,即m-1个关键字
  • 若根节点不是终端结点,至少有2棵子树
  • 除根结点外的所有非叶结点至少有⌈m/2⌉ 棵子树,(即至少含有⌈m/2⌉-1个关键字)
  • 结点中关键字个数n满足⌈m/2⌉ 1<=n<=m-1
  • 所有叶节点都在同一层次上

平衡二叉树的查找:平均查找长度为 O ( l o g 2 n ) O(log_2n) O(log2n)

  • 每个结点最多有m-1个关键字(m指阶数,阶代表B树中所有节点的孩子个树的最大值),至少有m棵子树;
  • 根节点最少可以只有1个关键字(若根节点为非终端结点,最少有两棵子树);
  • 非根节点至少有⌈m/2⌉-1个关键字;
  • 每个结点中的关键字都按照从小到大的顺序排列,每个关键字的左子树中的所有关键字都小于它,而右子树中的所有关键都大于它;
  • 所有叶子节点都位于同一层,并且不携带信息(即绝对平衡);
  • 每个节点都存有索引和数据,也就是对应的key和value。

三对角

在这里插入图片描述

小根堆的调整操作:插入关键字x时候,先将其放在小顶堆的末端,再将该关键字向上进行调整。

平衡二叉树
链接

B-树删除操作:

  • 被删关键字所在结点中的关键字数目不小于「m/2],直接删
  • 兄弟够借,被删关键字所在结点中的关键字数目等于「m/2]-1,与该结点相邻的右兄弟(或左兄弟)结点中的关键字数目【大于】「m/2]-1,将其兄弟结点中的最小(或最大)的关键字上移至双亲结点中,
  • 兄弟不够借,被删关键字所在结点和其相邻的兄弟结点中的关键字数目【均等于】「m/2]-1。假设该结点有右兄弟, 且其右兄弟结点地址由双亲结点中的指针pi 所指,则在删去关键字之后, 它所在结点中剩余的关键字和指针,加上双亲结点中的关键字Ki一起, 合并到pi 所指兄弟结点中
    在这里插入图片描述
    参考文章
    链接

三叉树求最小带权路径

2、3、4、5、6、7
在这里插入图片描述

需要补一个0权值的结点
最小带权路径
链接
为啥补零

段是不定长的连续区域

slab分配器,采用伙伴关系内存管理方式。有以下三个基本目标:

  1. 减少伙伴算法在分配小块连续内存是所产生的内部碎片
  2. 将频繁使用的对象缓存起来,减少分配,初始化和释放对象的时间开销
  3. 通过着色技术调整对象以更好地使用硬件高速缓存

为了使用磁盘存储文件,操作系统还需要将数据结构记录在磁盘上。
磁盘格式化

  • 物理格式化 分区 为每个扇区采用特别的数据结构,包括校验码。
  • 逻辑格式化(创建文件系统)
    • 将初始化的文件系统数据结构存储到磁盘上,这些数据结构包括空闲和已分配的空间及一个初始为空的目录。

以簇为单位进行空间分配

软链接新增文件时计数值直接复制
硬链接就是多个指针指向一个索引节点
文件的物理地址和其他文件属性信息放在索引节点中
硬链接不可用于跨文件系统
硬链接查找速度比软链接快

平均查找扇区时间是磁盘【转半圈】的时间
平均寻道时间

索引节点个数就是文件的总数,与单个文件的长度无关
单个文件长度主要取决于两个因素:

  • 文件系统索引节点中地址项个数
  • 间接地址索引的级数

不会导致磁臂黏着的是:先来先服务(FCFS)

FAT12文件系统
紧接着引导扇区的是两个完全相同的FAT表,每个FAT表占用9个扇区

  1. UNIX系统中,文件的索引结构存放在inode节点中,每个文件都有一个inode节点,包含了文件的元数据信息,如文件大小,创建时间,访问权限等。
  2. 超级块存储的是文件系统的元数据信息
  3. 目录块存储的是文件或目录的名称和inode指针等信息
  4. 空闲块存储的是未被分配的磁盘块信息

文件目录的重要作用是按名存取

open函数需要文件名(包含路径),之后会给一个文件描述符返回给进程

  • 设备独立性程序:实现逻辑设备名到物理设备名的映射
  • 设备驱动程序:将I/O请求转换为具体信号(物理I/O操作)

read系统调用和write系统调用均在open调用之后,仅需提供文件描述符fd和其他参数,不用文件名

read系统调用要求用户提供三个输入参数:

  • 文件描述符
  • buf缓冲区首址
  • 传送的字节数n 没有文件名

TCP中,发送窗口的大小为N,意味着在没有收到确认的情况下可以连续发送N个字节。
可靠的传输协议:使用确认机制保证传输数据的不丢失

拥塞窗口到12发生超时,门限值为6
慢启动从1,2,4开始,然后到6之后以公差为1进行递增

UDP报文首部和TCP报文首部

udp报文首部不包含目的地址,目的地址是在检验时候加上去的伪首部。
udp报文之后使用ip头进行封装,ip头有目的ip地址
tcp报文的头也是没有目的ip地址的

IP报文首部

在这里插入图片描述

TCP报文首部

在这里插入图片描述

在这里插入图片描述
TCP报文由首部和数据两部分组成。首部一般由20-60字节(Byte)构成,长度可变。其中前20B格式固定,后40B为可选。

1、源端口号(Source Port)
16位的源端口字段包含初始化通信的端口号。源端口和IP地址的作用是标识报文的返回地址。

2、目的端口号(Destination Port)
 16位的目的端口字段定义传输的目的。这个端口指明接收方计算机上的应用程序接口。

3、序列号(Sequence Number)
该字段用来标识TCP源端设备向目的端设备发送的字节流,它表示在这个报文段中的第几个数据字节。序列号是一个32位的数。

4、确认号(Acknowledge Number)
  TCP使用32位的确认号字段标识期望收到的下一个段的第一个字节,并声明此前的所有数据已经正确无误地收到,因此,确认号应该是上次已成功收到的数据字节序列号加1。收到确认号的源计算机会知道特定的段已经被收到。确认号的字段只在ACK标志被设置时才有效。
5、首部长度
长度为4位,用于表示TCP报文首部的长度。用4位(bit)表示,十进制值就是[0,15],一个TCP报文前20个字节是必有的,后40个字节根据情况可能有可能没有。如果TCP报文首部是20个字节,则该位应是20/4=5。
6、保留位(Reserved)
长度为6位,必须是0,它是为将来定义新用途保留的。
7、标志(Code Bits)
长度为6位,在TCP报文中不管是握手还是挥手还是传数据等,这6位标志都很重要。6位从左到右依次为:
• URG:紧急标志位,说明紧急指针有效;
• ACK:确认标志位,多数情况下空,说明确认序号有效; 取1时表示应答字段有效,也即TCP应答号将包含在TCP段中,为0则反之。
• PSH:推标志位,置位时表示接收方应立即请求将报文交给应用层;
• RST:复位标志,用于重建一个已经混乱的连接,用来复位产生错误的连接,也会用来拒绝错误和非法的数据包。
• SYN:同步标志,该标志仅在三次握手建立TCP连接时有效
• FIN:结束标志,表示发送端已经发送到数据末尾,数据传送完成,发送FIN标志位的TCP段,连接将被断开。
8、窗口大小(Window Size)
长度为16位,TCP流量控制由连接的每一端通过声明的窗口大小来提供。
9、检验和(Checksum)
长度为16位,该字段覆盖整个TCP报文端,是个强制性的字段,是由发送端计算和存储,到接收端后,由接收端进行验证。
10、紧急指针(Urgent Pointer)
长度为16位,指向数据中优先部分的最后一个字节,通知接收方紧急数据的长度,该字段在URG标志置位时有效。
11、选项(Options)
长度为0-40B(字节),必须以4B为单位变化,必要时可以填充0。通常包含:最长报文大小(MaximumSegment Size,MSS)、窗口扩大选项、时间戳选项、选择性确认(Selective ACKnowlegement,SACK)等。
12、数据
可选报文段数据部分。

UDP报文首部

在这里插入图片描述

UDP数据报由首部和数据两部分组成,其中首部只有8B(字节)。
1、源端口号(Source Port)
长度为16位,指明发送数据的进程。
2、目的端口号(Destination Port)
长度为16位,指明目的主机接收数据的进程。
3、长度
长度为16位,该字段值为报头和数据两部分的总字节数。
4、检验和(Checksum)
长度为16位,UDP检验和作用于UDP报头和UDP数据的所有位。由发送端计算和存储,由接收端校验。
5、数据

参考链接

TCP既有流量控制也有拥塞控制。TCP在发送数据的时候要考虑拥塞窗口也要考虑接受窗口。TCP能够发送的最大字节数要受到两窗口最小值的限制


【TCP首部长度必须是4B的整数倍】
某TCP分组的选项字段长度为9B,该TCP分组的数据偏移字段1000
【TCP首部长度必须是4B的整数倍】,这里报头定长20B不定长选项9B之和为29B
并不是4B的整数倍,所以需要填充3B
此报文首部的长度为32B
32B/4=8 二进制表示为1000


门限值变成16后,超时后处于慢启动阶段的为4RTT
发送窗口的初始值设置为1,然后依次增大为2、4、8、16,需要经过4个RTT
UDP不适用于远程登录(需要可靠链接),适用于实时性高的应用(实时性应用,【远程调用rdp】,【客户/服务器领域】 编码简单,需要很少的信息)

一个udp用户数据包数据字段为8192B,链路层使用以太网来传输,应该分成6个ip数据报

以太网帧的最大数据负载是1500B,ip首部长度为20B,数据字段长度为1480B,udp数据字段可被分为8192/1480 -> 6

根域名-顶级域名-权限域名-本地域名
dns解析时过程:本地域名,根域名,顶级域名,权限域名

ftp:21控制和20数据连接0
邮件服务器的功能:监控邮件
电子邮件系统中用户代理的功能:

  1. 处理邮件
  2. 显示邮件
  3. 撰写邮件

采用客户机/服务器模型的主要原因:
4. 更好实现资源共享
5. 通信的异步问题
客户机提交查询请求,服务器返回查询结果
网络传输线路上之传送【请求命令】和【执行结果】,从而降低通信开销

集中目录式p2p网络结构代表性软件:Napster,Maze
分布式非结构化p2p网络:Gnutella
分布式结构化:Pastry,Tapestry,Chord,CAN
混合式:Skype,eDonkey,BitTorent,PPLive

客户机是面向用户的(通常位于前端),服务器是面向任务的(通常位于后端)
客户机和服务器之间通过网络实现协同计算
p2p是网络结点之间采取对等方式直接交换信息的工作模式

域名和地址可以是一对多,多对一的关系
www不是一种协议,而是应用层提供的一种最为重要和普及的服务
www中网站唯一地址:统一资源定位符URL
http详细规定了浏览器和万维网服务器之间相互通信的规则

发送邮件使用的协议SMTP
收取邮件使用的协议:POP3和IMAP

刷新和再生的区别

参考地址
对于破坏性读出的存储器进行读/写操作时,为维持原信息不变,必须辅以的操作是:再生
刷新
DRAM中刷新和重写的区别
在DRAM(动态随机存取存储器)中,刷新和重写是两个不同的操作。

1.刷新(Refresh):DRAM是一种易失性存储器,它的存储单元是由电容构成的。由于电容的特性,它们会逐渐丧失电荷,导致存储的数据逐渐衰减。为了防止数据丢失,DRAM需要定期进行刷新操作。刷新操作是将存储单元中的数据读出并重新写入,以恢复电荷状态并保持数据的完整性。刷新操作通常由DRAM控制器自动执行,遵循内存芯片制造商指定的刷新频率。

2.重写(Rewrite):重写是指将新的数据写入DRAM的过程。当CPU或其他设备需要将新的数据存储到DRAM中时,它会发送写入指令,将数据写入到指定的DRAM存储单元中。重写操作会覆盖原有的数据,并更新存储单元中的内容。重写可以是随机的,根据需要进行读写操作

总结来说,刷新是为了防止数据丢失而对DRAM中的数据进行定期读取和重新写入操作,而重写是将新的数据写入到DRAM中,覆盖原有的数据。刷新是为了保持数据的完整性,而重写是为了更新数据。

地址译码

地址译码电路有单译码和双译码两个方式:
单译码只有一个译码器,双译码方式有两个译码器(X和Y地址译码器)
XY两个方向译码器输出线在存储体内部的一个记忆单元上交叉,以选择相应的记忆单元
单译码输入线6,译码输出线64( 2 6 2^6 26)根
双译码输入线6,译码输出线16( 2 3 + 2 3 2^3+2^3 23+23

存储器采用部分译码法片选时,会产生地址重叠

直接映像(一Cache对多主存)
请添加图片描述
直接映射就是一个Cache页面对应多个主存页面。
直接映射函数为: i = j % 2c,其中i是Cache页号;j是主存页号。

例如:主存的页面0 % 2c = 0 ,只能映射到Cache的页面0
例如:主存的页面(2c+ 1)% 2c =1,只能映射到Cache的页面1
在Cache中给每个页面设一个t位长的标记(t = m -c),主存某一页调入了Cache后,就将主存页号的高t位放入Cache相应的那个页的标记中。

容量64块的cache采用组相联映射方式,字块大小为128个字,每4块为1组。如果主存为4k块,且按字编址,那么主存地址和主存标记的位数分别为
主存容量:4k*128字=2^19字(按字编址,主存地址19位)
组号:cache被分的组号 64/4=16(组号4位)
块号:块内地址(128个字 7位)
(组相联)主存标记=主存地址大小-组号-块号=19-4-7=8位

DRAM集中刷新刷新一行需要一个存储周期

位扩展之后作为【一个存储体】进行地址选择
块冲突概率最小的是全相联映射

LRU将在cache中驻留时间最长而且没有使用的块作为被替换的块

零操作数可能隐含操作数,在【堆栈】中

JMP指令程序总是顺序执行,指令本身无堆栈操作过程
CALL指令跳转到指定目标程序执行子程序,执行完子程序后,会返回CALL指令的【下一条指令处】执行程序,执行CALL指令有堆栈过程。

中断返回被中断的那一条指令继续执行

操作码OP 操作数/地址码(被执行的对象)

处于硬件和软件交界面的是:指令系统

返回指令RET和中断返回指令
return(RET)可以是人为编写的,可以携带操作数
中断返回指令是特权指令,程序员不可以编写,不携带操作数

DRAM即使不断电,在规定时间内没有及时刷新,存储信息也会丢失

低位交叉存储器

  • 轮流启动 连续的地址分布在相邻的块中,同一模块内的地址都是不连续的,采用分时启动的方法。 连续读出4个字所需要的时间t=T+(m-1)*r,每1/4存储周期启动一个体,每1/4个存储周期可以读出或写入一个数据,存取速度提高m倍
  • 同时启动

高位交叉编址/连续编址方式:主存地址的高位表示模块号(体号),低位表示模块内地址(或体内地址)。地址在模块内连续

cache与主存一致性:

  1. 写回法
  2. 直写法

cache完全由硬件实现,不涉及软件
虚拟存储器由硬件和os共同完成
虚拟存储器中,主存的内容只是辅存的一部分
虚拟存储器【失效】时处理器会【切换进程】来更新内存

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/874384.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

会声会影2024发布了没有? 会声会影2024更新哪些内容?

嘿&#xff0c;亲爱的的朋友们&#xff0c;今天我要跟大家安利一款让我彻底沉迷、不能自拔的神器 —— 会声会影2024&#xff01;如果你还在为视频编辑头疼&#xff0c;那么准备好迎接你的救星吧&#xff01; 会声会影2024是一款功能全面的视频编辑软件&#xff0c;它不仅能帮你…

ThreadLocal常见面试题

1.请介绍一下ThreadLocal底层是怎么实现的&#xff1f; 一个线程开始运行的时候&#xff0c;通过set方法会把值放入threadLocals这个变成中&#xff0c;他的类型是ThreadLocalMap对象&#xff0c;里面是Entry数组&#xff0c;每一个Entry是键值对形式&#xff0c;key就是Thread…

Vue 3 + Element Plus 封装单列控制编辑的可编辑表格组件

在Web应用开发中&#xff0c;经常需要提供表格数据的编辑功能。本文将介绍如何使用Vue 3结合Element Plus库来实现一个支持单列控制编辑功能的表格&#xff0c;并通过封装组件的形式提高代码的复用性。通过本教程&#xff0c;你将学会如何构建一个具备单列控制编辑功能的表格组…

NISP 一级 | 3.3 网络安全防护与实践

关注这个证书的其他相关笔记&#xff1a;NISP 一级 —— 考证笔记合集-CSDN博客 0x01&#xff1a;虚拟专用网络 VPN 概述 虚拟专用网络&#xff08;Virtual Private Network&#xff0c;VPN&#xff09;是在公用网络上建立专用网络的技术。整个 VPN 网络的任意两个节点之间的连…

基于Java+SpringBoot+Vue+MySQL的美容美发管理系统

作者&#xff1a;计算机学姐 开发技术&#xff1a;SpringBoot、SSM、Vue、MySQL、JSP、ElementUI等&#xff0c;“文末源码”。 专栏推荐&#xff1a;前后端分离项目源码、SpringBoot项目源码、SSM项目源码 系统展示 基于SpringBootVue的美容美发管理系统【附源码文档】、前后…

HAProxy--高性能反向代理

文章目录 Web架构负载均衡介绍为什么使用负载均衡负载均衡类型 HAProxy简介应用场景HAProxy是什么HAProxy功能 脚本安装HAProxy基础配置global多进程和线程HAProxy日志配置项 Proxies配置-listen-frontend-backendserver配置 frontendbackend配置实例子配置文件 HAProxy调度算法…

OpenCV findTours函数及其用法

OpenCV的findTours函数的原型如下&#xff1a; 函数参数&#xff1a; Image 输入图像&#xff0c;需8位单通道图像。非零像素被视为1。零像素保持为0&#xff0c;因 此图 像被视为二进制。您可以使用compare、inRange、threshold、adaptiveThreshold、Canny等从灰度或彩色图像…

注册网站怎么注册

网站注册成为我们日常生活中不可或缺的一部分。无论是社交媒体、电子商务平台还是各种在线服务&#xff0c;注册都是参与这些平台的第一步。下面将为您详细介绍一般网站注册的步骤&#xff0c;帮助您轻松完成注册过程。 1. 选择合适的网站 在注册之前&#xff0c;首先要确定您…

MeterSphere的一次越权审计

1 MeterSphere简介 MeterSphere是一个一站式开源持续测试平台&#xff0c;它提供了测试跟踪、接口测试、UI测试和性能测试等功能。它全面兼容JMeter、Selenium等主流开源标准&#xff0c;助力开发和测试团队实现自动化测试&#xff0c;加速软件的高质量交付。MeterSphere 的特点…

python爬虫基础:了解html

编辑器vscode <!DOCTYPE html> <html><head><title>第一个网页</title></head><body><h1>字体</h1><h2>字体</h2><h3>字体</h3><p>Lorem, ipsum dolor sit amet consectetur adipisicing…

网络学习-eNSP配置NAT

NAT实现内网和外网互通 #给路由器接口设置IP地址模拟实验环境 <Huawei>system-view Enter system view, return user view with CtrlZ. [Huawei]undo info-center enable Info: Information center is disabled. [Huawei]interface gigabitethernet 0/0/0 [Huawei-Gigabi…

ETL数据集成丨MySQL到MySQL的数据迁移实践

前言 MySQL数据迁移至另一MySQL数据库的过程&#xff0c;不仅是数据复制或移动的操作那么简单&#xff0c;它还涉及到一系列策略性考量和技术优化&#xff0c;旨在实现数据的高效、安全传输&#xff0c;以及确保目标系统的高性能运行。其深远意义在于为企业的数字化转型提供强…

vscode 中使用 yarn 出错

问题 vscode 中使用 yarn 爆红&#xff0c;类似下图的错误&#xff1a; 原因 由于vscode中的集成终端使用的是powershell&#xff0c;所以需要设置下该权限才能正常使用yarn 解决 找到 powershell&#xff0c;以管理身份运行 输入&#xff1a;set-ExecutionPolicy Remot…

【目标检测数据集】铁轨表面缺损检测数据集4789张VOC+YOLO格式

数据集格式&#xff1a;Pascal VOC格式YOLO格式(不包含分割路径的txt文件&#xff0c;仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数)&#xff1a;4789 标注数量(xml文件个数)&#xff1a;4789 标注数量(txt文件个数)&#xff1a;4789 标注…

前端---对MVC MVP MVVM的理解

就需要从前端这些年的从无到有、从有到优的变迁过程讲一下。 1. Web1.0时代 在web1.0时代并没有前端的概念&#xff0c;开发一个web应用多数采用ASP.NET/Java/PHP编写&#xff0c;项目通常用多个aspx/jsp/php文件构成&#xff0c;每个文件中同时包含了HTML、CSS、JavaScript、…

安科瑞Acrelcloud-6000银行安全用电管理平台在湖南新盛业的应用

摘要 安科瑞Acrelcloud-6000安全用电管理平台是针对我国当前电气火灾事故频发而创新的一套电气火灾预警和预防管理系统&#xff0c;该系统是基于移动互联网、云计算技术、通过物联网传感终端&#xff08;现场监控模块、传输模块&#xff09;&#xff0c;将供电侧、用电侧电气安…

jupyter出错ImportError: cannot import name ‘np_utils‘ from ‘keras.utils‘ ,怎么解决?

文章前言 此篇文章主要是记录一下我遇到的问题以及我是如何解决的&#xff0c;希望下次遇到类似问题可以很快解决。此外&#xff0c;也希望能帮助到大家。 遇到的问题 出错&#xff1a;ImportError: cannot import name np_utils from keras.utils &#xff0c;如图&#xf…

Sky Takeaway

软件开发整体介绍 软件开发流程 角色分工 软件环境 苍穹外卖 项目介绍 定位&#xff1a;专门为餐饮企业定制的一款软件产品 技术选型 前端环境搭建 阅读readme文档 nginx.exe放入无中文目录运行并启动 后端环境搭建 项目结构 Nginx反向代理 优点 配置 Nginx反向代理 负…

Open CASCADE学习|通过指定点的曲线

在OpenCASCADE中&#xff0c;如果你想通过一系列指定的点来创建一条曲线&#xff0c;你可以使用Geom2dAPI_Interpolate类来实现二维曲线的插值&#xff0c;或者使用GeomAPI_Interpolate类来实现三维曲线的插值。这些类允许你定义一条B样条曲线&#xff0c;这条曲线将精确地通过…

【Sceneform-EQR】通过sceneform-eqr实现一个视频播放器(使用安卓MediaPlayer实现视频播放)

在前一篇文档中介绍了如何在AR\三维场景创建几种背景 【Sceneform-EQR】scenefrom-eqr中的几种背景实现(不仅用于AR、三维场景&#xff0c;在图片、视频播放器中也适用) 本文将侧重介绍如何使用安卓MediaPlayer实现视频播放。 ↓↓↓↓↓↓↓↓↓↓↓↓ 以下正文 ↓↓↓↓↓↓…