【笔记】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共同完成
虚拟存储器中,主存的内容只是辅存的一部分
虚拟存储器【失效】时处理器会【切换进程】来更新内存

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

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

相关文章

make、cmake、qmake的区别和联系

基本概念与用途 make&#xff1a; 定义&#xff1a;make是一个用于自动化构建项目的命令行工具。用途&#xff1a;它通过读取Makefile&#xff08;或makefile&#xff09;文件来执行编译、链接等操作&#xff0c;从而构建整个项目。Makefile中定义了项目中的文件依赖关系以及…

“CSS 定位”如何工作?(补充)——WEB开发系列34

CSS定位是一个非常重要的布局工具&#xff0c;它允许我们精确地控制元素的位置&#xff0c;从而创建复杂的布局效果。定位允许你从正常的文档流布局中取出元素&#xff0c;并使它们具有不同的行为&#xff0c;例如放在另一个元素的上面&#xff0c;或者始终保持在浏览器视窗内的…

数据库设计中的需求分析

在数据库设计中&#xff0c;需求分析 是至关重要的一步。它不仅是设计过程的起点&#xff0c;也是后续步骤的基础。如果需求分析出现问题&#xff0c;那么后续所有设计阶段的结果都会受到影响&#xff0c;最终可能导致整个设计返工&#xff0c;耗费大量时间和资源。因此&#x…

KubeBlocks 如何降低管理多种数据库的学习门槛

什么是 KubeBlocks KubeBlocks 是一个开源的 Kubernetes 数据库 operator&#xff0c;能够帮助用户在 Kubernetes 上运行和管理多种类型的数据库。据我们所知&#xff0c;大多数数据库 operator 通常只能管理某种特定类型的数据库&#xff0c;例如&#xff1a; CloudNativePG…

基于SSM开发的校园心理咨询平台系统的设计与实现---附源码80915

目 录 1 绪论 1.1 研究背景 1.2开发现状 1.3论文结构与章节安排 2 校园心理咨询平台系统系统分析 2.1 可行性分析 2.1.1 技术可行性分析 2.1.2 经济可行性分析 2.1.3 法律可行性分析 2.2 系统功能分析 2.2.1 功能性分析 2.2.2 非功能性分析 2.3 系统用例分析 2.4…

安卓13删除app 链接库警告弹窗Detected problems with app native

总纲 android13 rom 开发总纲说明 文章目录 1.前言2.问题分析3.代码修改彩蛋1.前言 有些客户的APP,打开首次会弹窗提示窗口, Detected problems with app native libraries (please consult log for detail):,需要删除这个窗口,避免挡住用户APP。而且这个提示有些app是以t…

MapBox Android版开发 4 国际化功能v11

MapBox Android版开发 4 国际化功能v11 前言遇到的问题国际化功能原文给出的方案(V10版)migrate-to-v11适用于V11版的代码 示例MapStyle类运行效果图 前言 在前文MapBox地图样式v11中&#xff0c;使用Style的localizeLabels方法本地化地图语言。但Mapbox Standard样式和Mapbox…

红队C2工具Sliver探究与免杀

吉祥知识星球http://mp.weixin.qq.com/s?__bizMzkwNjY1Mzc0Nw&mid2247485367&idx1&sn837891059c360ad60db7e9ac980a3321&chksmc0e47eebf793f7fdb8fcd7eed8ce29160cf79ba303b59858ba3a6660c6dac536774afb2a6330&scene21#wechat_redirect 《网安面试指南》…

纯国产芯片LT8911EXB,MIPI转EDP信号转换器,LT8911B升级版本

以下为视频转换芯片LT8911EXB的简介 LT8911EXB MIPI DSI/CSI到eDP转换器具有单端口MIPI接收器&#xff0c;1时钟通道和4每个数据通道的最大运行速度为2.0Gbps;一个最大输入带宽为8.0Gbps。转换器解码输入MIPIDSI 16/18/24/30/36位RGB数据包&#xff0c;并将格式化的视频数据流转…

异步文件操作的革命:探索aiofiles的魔力

文章目录 异步文件操作的革命&#xff1a;探索aiofiles的魔力1. 背景介绍2. aiofiles是什么&#xff1f;3. 如何安装aiofiles&#xff1f;4. 简单的库函数使用方法5. 场景应用6. 常见Bug及解决方案7. 总结 异步文件操作的革命&#xff1a;探索aiofiles的魔力 1. 背景介绍 在现…

【Java-反射】

什么是反射&#xff1f; JAVA反射机制是在运行状态中&#xff0c;创建任意一个类&#xff0c;能获取这个类的所有属性和方法&#xff1b;对于任意一个对象&#xff0c;都能够调用它的任意一个方法和属性&#xff1b;这种动态获取的信息以及动态调用对象的方法的功能称为java语言…

RHEL 7 安装配置( Linux 网络操作系统 02)

一、虚拟机安装 我们的每台电脑都已经安装了VMware 虚拟机&#xff0c;其安装相当简单&#xff0c;在此不再赘述。可以参考如下链接&#xff1a; VMWare安装傻瓜式教程 &#xff08;大家可以关注老师的博客&#xff0c;也建议大家写博客。&#xff09; 二、红帽 rhel 7 安装 找…

IEC103设备数据 转 IEC61850项目案例

目录 1 案例说明 1 2 VFBOX网关工作原理 1 3 准备工作 2 4 配置VFBOX网关采集103设备数是 2 5 用IEC61850协议转发数据 4 6 网关使用多个逻辑设备和逻辑节点的方法 6 7 IEC103协议说明 8 8 案例总结 9 1 案例说明 设置网关采集IEC103设备数据把采集的数据转成IEC61850协议转发…

通过 python 的 Opstrat 绘制收益图加深期权策略理解

本文介绍介绍一个 Python 包- opstrat&#xff0c;通过它绘制期权收益图&#xff0c;帮助我们理解期权策略的收益风险比。 什么是期权收益图&#xff1f; 期权收益图展示了某个期权或期权组合的盈亏情况&#xff0c;如下图中&#xff0c;展示一张标的现价 100&#xff0c;行权…

Carfilzomib (PR-171) 蛋白酶体 (proteasome) 抑制剂AbMole介绍

AbMole Carfilzomib (PR-171)是一种不可逆的蛋白酶体 (proteasome) 抑制剂&#xff0c;IC50为<5 nM&#xff0c;在体外优先抑制β5亚基的ChT-L活性&#xff0c;对PGPH和T-L活性很弱或没有作用。 Carfilzomib (PR-171)在体外优先抑制β5亚基的ChT-L活性&#xff0c;对PGPH和…

C#游戏服务器开发框架设计与架构详解

我一直在思考一个问题&#xff0c;什么样的服务端框架最好用&#xff0c;最适合? 经过这些年的项目经验&#xff0c;其实最好用&#xff0c;最适合的游戏服务端框架就是自己结合公司项目需求,团队特点与技术能力,自己整合的游戏框架是最好用的。 很多新手会担心自己整合的框架…

SprinBoot+Vue小区车辆管理系统的设计与实现

目录 1 项目介绍2 项目截图3 核心代码3.1 Controller3.2 Service3.3 Dao3.4 application.yml3.5 SpringbootApplication3.5 Vue 4 数据库表设计5 文档参考6 计算机毕设选题推荐7 源码获取 1 项目介绍 博主个人介绍&#xff1a;CSDN认证博客专家&#xff0c;CSDN平台Java领域优质…

CMU 10423 Generative AI:lec4(Modern Transformers + CNNs)

文章目录 1 概述2 内容摘录2.1 深度学习架构的历史2.2 预训练概念、三种训练方式、效果对比2.3 现代Transformer模型概览1. **PaLM (Pathways Language Model, 2022年10月)**2. **Llama-1 (2023年2月)**3. **Falcon (2023年6月-11月)**4. **Llama-2 (2023年8月)**5. **Mistral …

vba发邮件:如何设置自动化发送电子邮件?

vba发邮件的技巧有哪些&#xff1f;VBA如何调用outlook发邮件&#xff1f; VBA发邮件功能是一个非常实用的工具&#xff0c;能够帮助用户自动发送电子邮件&#xff0c;减少手动操作的时间和错误。AokSend将详细介绍如何通过VBA发邮件来实现自动化发送电子邮件的设置。 VBA发邮…

Java 设计模式-代理模式

目录 概述 一. 什么是代理模式 1. 举例说明 二. 代理模式作用 1. 保护代理 2. 增强功能 3. 代理交互 4. 远程代理&#xff1a; 三. 代理模式3个角色 四. 静态代理 1. 代码示例&#xff1a; 五. JDK动态代理 1. 代码示例&#xff1a; 六. CGLIB 动态代理 1.代码示…