【嵌入式八股精华版】三、计算机基础篇

完整版见以下专栏：

【嵌入式八股】一、语言篇https://www.nowcoder.com/creation/manager/columnDetail/mwQPeM

【嵌入式八股】二、计算机基础篇https://www.nowcoder.com/creation/manager/columnDetail/Mg5Lym

【嵌入式八股】三、硬件篇https://www.nowcoder.com/creation/manager/columnDetail/MRVDlM

【嵌入式八股】四、嵌入式Linux篇https://www.nowcoder.com/creation/manager/columnDetail/MQ2bb0

三、计算机基础

计算机组成原理

92.什么是哈佛结构和冯诺依曼结构？

冯诺依曼结构釆用指令和数据统一编址，使用同条总线传输，CPU读取指令和数据的操作无法重叠。 哈佛结构釆用指令和数据独立编址，使用两条独立的总线传输，CPU读取指令和数据的操作可以重叠。

哈佛结构的优点：

1. 可以同时进行指令和数据的访问，提高了处理器的效率；
2. 指令和数据使用不同的总线进行传输，避免了互相干扰；

哈佛结构的缺点：

1. 硬件成本较高，需要额外的存储器和总线；
2. 存储器的分离可能会导致指令和数据的管理变得更加复杂；
3. 需要一些额外的机制来解决指令和数据之间的同步问题。

冯诺依曼结构的优点：

1. 硬件成本较低，只需要一个存储器和一个总线即可；
2. 程序设计和管理相对简单，只需要一种地址寻址方式；
3. 可以通过缓存等技术提高存储器的访问效率。

冯诺依曼结构的缺点：

1. 指令和数据使用同一个总线进行传输，可能会影响数据的访问效率；
2. 可能会发生指令和数据访问的竞争，影响处理器的效率；
3. 存储器管理比较复杂，需要一些额外的机制来实现程序的运行。

哈佛结构适合需要高效访问指令和数据的应用场景，如嵌入式系统；而冯诺依曼结构适合通用计算机系统，由于硬件成本低和管理简单的优点，冯诺依曼结构在现代计算机中得到了广泛应用。

93.存储系统

寄存器，缓存，RAM，ROM

94.寄存器和内存的区别？

寄存器（Registers）和内存（Memory）是计算机系统中两个重要的存储组件，它们在功能和特性上有一些区别。

1. 功能：寄存器是计算机处理器内部的一组高速存储单元，用于存储和操作指令、数据和地址。它们用于存储处理器的临时变量、计算结果和控制信息。寄存器的主要作用是提供高速访问和执行指令的能力。内存是计算机系统中用于存储数据和指令的主要存储区域。它是相对较慢的存储介质，但能够容纳更大量的数据。

2. 容量：寄存器的容量通常比较有限，每个寄存器可以存储少量的数据。内存的容量相对较大，可以容纳更多的数据。内存的大小通常以字节为单位进行度量，而寄存器的大小可以是几个字节或更小。

3. 访问速度：寄存器位于处理器内部，由于与处理器直接连接，因此可以以非常高的速度进行读取和写入操作。相比之下，内存位于处理器之外，因此访问速度较慢。

4. 成本：由于寄存器是处理器内部的组件，其成本相对较高。内存作为独立的存储设备，成本较低。

5. 层次结构：计算机系统中的存储通常以层次结构的方式组织。寄存器属于顶层，位于处理器内部，速度最快。内存属于中间层，位于处理器外部，速度较快。还可以有更大容量但速度较慢的辅助存储器，如硬盘驱动器。

95.Cache一致性？

缓存一致性是指在多个处理器或多个核心的计算机系统中，它们共享同一个内存区域时，保证每个处理器或核心的缓存中存储的数据是一致的。当一个处理器或核心修改共享内存中的数据时，它必须通知其他处理器或核心，以便它们更新自己的缓存。

如果不进行缓存一致性处理，就可能导致不同处理器或核心看到不同的数据，这会引发程序错误，例如死锁、竞争条件等。缓存一致性可以通过硬件或软件实现。

常见的缓存一致性协议包括MESI、MOESI和MESIF等。这些协议都通过一些机制来保证缓存数据的一致性，例如当一个处理器修改共享内存时，它会发送一个信号给其他处理器或核心，通知它们将缓存中的数据置为无效状态，从而保证了数据的一致性。

在多核心和多处理器的计算机系统中，缓存一致性是一个非常重要的概念，它对于系统的性能和正确性都有着重要的影响。

96.NOR Flash与NAND Flash的区别？

NOR NAND

单位	字节	页（一般为512字节）
运行	代码可以直接在NOR flash运行	代码不可以直接在NAND flash运行（因为按块访问）需搬移到内存，即重定位。或者也可以按块放到芯片内iRAM运行
容量	一般为1~16MB	一般为8~128M
结构	并行存储结构，每个存储单元都可以独立访问，适用于读取速度较快的应用	串行存储结构，多个存储单元串联在一起，适用于存储容量大、读取速度相对较慢的应用
成本	较高	较低
性能	读速度比NAND Flash稍快	写入、擦除速度比NOR Flash快很多
接口	带有SRAM接口，有足够的地址引脚来寻址，可以很容易地存取其内部的每一个字节	使用复杂的I/O口来串行地存取数据，8个引脚用来传送控制、地址和数据信息
耐用性	最大擦写次数是十万次	最大擦写次数是一百万次
软件支持	写入和擦除都需要MTD（Memory Technology Devices，内存技术驱动程序），运行代码不需要任何软件支持	写入和擦除都需要MTD，运行代码也要需要MTD
适用	适用于需要快速读取、执行代码和数据的应用，如固件、引导程序和系统软件等	适用于需要高存储容量、相对较慢读取速度的应用，如移动存储、数字相机、MP3等。

注意：nandflash 和 norflash 的0地址是不冲突的，norflash占用BANK地址，而nandflash不占用BANK地址，它的0地址是内部的。在NOR Flash中，每个存储单元都可以独立访问，因此0地址可以映射到第一个存储单元。而在NAND Flash中，多个存储单元串联在一起，形成一个页（Page），每个页都有一个页地址。因此，0地址通常映射到第一个页的第一个存储单元，而不是直接映射到第一个存储单元。因此，尽管NAND Flash和NOR Flash的0地址不会直接冲突，但在使用中还是需要根据具体的芯片型号和数据手册来确定各个地址的具体映射关系。

97.SRAM、DRAM、SDRAM的区别？

RAM可分为两类，一类是动态随机存储器（Dynamic RAM，DRAM，电容实现），另一类是静态随机存储器（Static RAM，SRAM，双稳态触发器实现，更快更贵）。由于 DRAM 具有结构简单、高集成度、低功耗、低制造成本等优点，被大量地应用在计算机内存中。

DRAM 又可根据工作原理中是否与系统时钟同步，分为同步动态随机存取存储器 SDRAM 和异步动态随机存取存储器 EDO DRAM。

DDR SDRAM（简称“DDR”）的速度是 SDRAM 的 2 倍，也就是双倍速率 SDRAM。

SDRAM 大体上经历了 5 个主流发展阶段：SDRAM、DDR、DDR2、DDR3、DDR4、DDR5。

DDR5来了，这些新内存技术你掌握了吗？ - 腾讯云开发者社区-腾讯云 (tencent.com)

SRAM、DRAM、SDRAM的区别如下：

（1）SRAM：静态的随机存储器，加电情况下，不需要刷新，数据不会丢失，CPU的缓存就是SRAM。

（2）DRAM：动态随机存储器，加电情况下，也需要不断刷新，才能保存数据，最为常见的系统内存。

（3）SDRAM：同步动态随机存储器，即数据的读取需要时钟来同步，也可用作内存。

SRAM SRAM DRAM

存储原理	触发器	电容
是否刷新	不需要	需要
运行速度	快	慢
存储成本	高	低
发热量	大	小
送行列地址	同时送	分两次送
破坏性读出	否	是
集成度	低	高

98.RISC（精简指令集计算机）和CISC（复杂指令集计算机）的区别

RISC（Reduced Instruction Set Computer，精简指令集计算机）和CISC（Complex Instruction Set Computer，复杂指令集计算机）是两种指令集架构，它们有以下几个方面的不同之处：

1. 指令集复杂度：CISC指令集的指令通常包含多个操作，而RISC指令集的指令通常只包含一个简单的操作，因此RISC指令集比CISC指令集更加简单。
2. 指令执行时间：由于RISC指令集只包含一个简单的操作，因此执行单个指令所需的时间更短，因此在相同的时钟频率下，RISC处理器通常比CISC处理器更快。
3. 硬件复杂度：由于CISC指令集包含多个操作，因此需要更多的硬件来支持这些操作，因此CISC处理器通常比RISC处理器更复杂。
4. 编译器复杂度：由于RISC指令集更加简单，因此编译器的设计和实现更容易，因此编译器的复杂度更低。
5. 内存访问方式：RISC处理器倾向于将数据存储在寄存器中进行操作，而CISC处理器倾向于将数据存储在内存中进行操作。

总体而言，RISC处理器的设计更加简单，具有更快的执行速度和更低的成本，适用于需要高效处理大量数据的应用，例如图形处理和嵌入式系统。而CISC处理器则更加复杂，可以支持更多的操作，适用于需要处理复杂算法的应用，例如数据库和计算机辅助设计。

99.什么是ARM流水线技术？

流水线技术通过多个功能部件并行工作来缩短程序执行时间，提高处理器核的效率和吞吐率，从而成为微处理器设计中最为重要的技术之一。通过增加流水线级数简化了流水线各级的逻辑，进一步提高了处理器的性能。

ARM流水线技术是一种高效的指令执行方式，它将指令的执行过程划分成多个阶段，并同时处理多条指令。当一条指令在一个阶段执行时，下一条指令可以在前一条指令的后续阶段同时执行，从而提高了指令的执行速度。

ARM处理器的流水线一般分为三个阶段：取指阶段、解码和执行阶段以及访存和写回阶段。在取指阶段，处理器从内存中读取指令；在解码和执行阶段，处理器解析指令并执行操作；在访存和写回阶段，处理器将结果写回内存中。由于每个阶段都可以同时执行不同的指令，所以处理器可以快速处理多条指令，从而提高了执行效率。

操作系统

100.系统调用是什么，你用过哪些系统调用，和库函数有什么区别？

系统调用

系统调用是操作系统提供给应用程序的一组接口，用于访问底层系统资源（如文件、网络、进程等）。应用程序通过系统调用请求操作系统执行某些特定的操作，例如创建进程、读取文件、发送数据等。

常见的系统调用包括：

1. 文件系统操作：打开文件、读取文件、写入文件、关闭文件等。
2. 进程控制：创建进程、终止进程、等待进程结束等。
3. 网络通信：建立连接、发送数据、接收数据等。
4. 内存管理：分配内存、释放内存等。
5. 设备控制：读取设备、写入设备等。

不同的操作系统可能会提供不同的系统调用，但通常都会提供以上基本的功能。应用程序通过系统调用与操作系统进行交互，从而实现对底层系统资源的访问。

库函数 库函数（Library function）是把函数放到库里，供别人使用的一种方式。方法是把一些常用到的函数编完放到一个文件里，供不同的人进行调用。一般放在.lib文件中。库函数调用则是面向应用开发的，库函数可分为两类，一类是C语言标准规定的库函数，一类是编译器特定的库函数。

区别

1. 库函数在用户地址空间执行，系统调用是在内核地址空间执行，库函数运行时间属于用户时间，系统调用属于系统时间，库函数开销较小，系统调用开销较大
2. 库函数是有缓冲的，系统调用是无缓冲的
3. 库函数并不依赖平台，库函数调用与系统无关，不同的系统，调用库函数，库函数会调用不同的底层函数实现，因此可移植性好。系统调用依赖平台

101.进程有几种状态？画一下进程状态转换图？

创建状态 一个应用程序从系统上启动，首先就是进入创建状态，需要获取系统资源创建进程控制块（PCB）完成资源分配。

就绪状态 在创建状态完成之后，进程已经准备好，但是还未获得处理器资源，无法运行。

运行状态 获取处理器资源，被系统调度，开始进入运行状态。如果进程的时间片用完了就进入就绪状态。

阻塞状态 在运行状态期间，如果进行了阻塞的操作，如耗时的I/O操作，此时进程暂时无法操作就进入到了阻塞状 态，在这些操作完成后就进入就绪状态。

终止状态 进程结束或者被系统终止，进入终止状态

102.LINUX进程间通信方式有哪些？有什么优缺点？

• 管道：用来实现进程间相互发送非常短小的、频率很高的消息，通常适用于两个进程间的通信。

  • 无名管道（内存文件）：管道是一种半双工的通信方式，数据只能单向流动，而且只能在具有亲缘关系的进程之间使用。进程的亲缘关系通常是指父子进程关系。半双工速度慢，利用内核中的一串缓存，容量有限。只有具有亲缘关系的进程间通讯。面向字节流。
  • 有名管道（FIFO文件，借助文件系统）：有名管道也是半双工的通信方式，但是允许在没有亲缘关系的进程之间使用，管道是先进先出的通信方式，克服了管道没有名字的限制。但速度慢。
  • 流管道（s_pipe）: 去除了第一种限制,可以双向传输（全双工），或者用两个管道实现全双工也行。

• 共享内存：共享内存就是映射一段能被其他进程所访问的内存，这段共享内存由一个进程创建，但多个进程都可以访问。共享内存是最快的IPC方式，它是针对其他进程间通信方式运行效率低而专门设计的。但需要进程自行解决进程同步和互斥问题，往往与信号量，配合使用来实现进程间的同步和通信。共享内存用来实现进程间共享的、非常庞大的、读写操作频率很高的数据。

• 消息队列：消息队列是有消息的链表数据块，存放在内核中并由消息队列标识符标识。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。是一种异步的通信方式可以使多个进程之间传递数据块。消息队列通常用于进程间的同步，进程可以从队列中读取数据，或者向队列中写入数据。进行通信时不再需要考虑同步问题，使用方便， 但是信息的复制需要额外消耗CPU的时间，通信不及时，不适宜于信息量大或操作频繁的场合。

• 套接字：是一种基于网络协议的通信方式，适用于不同机器间进程通信，在本地也可作为两个进程通信的方式。

• 信号：信号是一种异步通信方式，可以向进程发送一个软件中断请求。用于通知接收进程某个事件已经发生，比如按下ctrl + C就是信号。主要作为进程间以及同一进程不同线程之间的同步手段。

• 信号量：信号量是一个计数器，可以用来控制多个进程对共享资源的访问。它常作为一种锁机制，防止某进程正在访问共享资源时，其他进程也访问该资源。实现进程、线程对临界区的同步及互斥访问。主要作为进程间以及同一进程内不同线程之间的同步手段。不能用来传递复杂消息，只能用来同步。

管共消，套两信。

103.进程调度算法

常见的操作系统进程调度策略有哪些？

1、 先来先服务 first-come first-serverd（FCFS）

• 非抢占式的调度算法，按照请求的顺序进行调度。

• 有利于长作业，但不利于短作业，因为短作业必须一直等待前面的长作业执行完毕才能执行，而长作业又需要执行很长时间，造成了短作业等待时间过长。

• 不会导致饥饿

2、 短作业优先 shortest job first（SJF）

• 非抢占式的调度算法，按估计运行时间最短的顺序进行调度。

• 有利于短作业，但不利于长作业

• 会饥饿。长作业有可能会饿死，处于一直等待短作业执行完毕的状态。因为如果一直有短作业到来，那么长作业永远得不到调度。

3、最短剩余时间优先 shortest remaining time next（SRTN）

短作业优先的抢占式版本，按剩余运行时间的顺序进行调度。 当一个新的作业到达时，其整个运行时间与当前进程的剩余时间作比较。

如果新的进程需要的时间更少，则挂起当前进程，运行新的进程。否则新的进程等待。

4、时间片轮转（RR Round-Robin）

按照各进程到达就绪队列的顺序（FCFS 的原则），轮流让各个进程执行一个时间片（如100ms）。若进程未在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾重新排队。当时间片用完时，由计时器发出时钟中断，调度程序便停止该进程的执行，并将它送往就绪队列的末尾，同时继续把 CPU 时间分配给队首的进程。

• 抢占式算法，发出时钟中断告知时间片已到。
• 优点:公平;响应快，适用于分时操作系统。 缺点:由于高频率的进程切换，因此有一定开销;不区分任务的紧急程度。
• 不会饥饿

时间片轮转算法的效率和时间片的大小有很大关系：

进程切换都要保存进程的信息并且载入新进程的信息，如果时间片太小，会导致进程切换得太频繁，在进程切换上就会花过多时间。

而如果时间片过长，那么实时性就不能得到保证。

5、优先级调度

为每个进程分配一个优先级，按优先级进行调度。

为了防止低优先级的进程永远等不到调度，可以随着时间的推移增加等待进程的优先级。

• 抢占非抢占式都有
• 优点:用优先级区分紧急程度、重要程度，适用于实时操作系统。可灵活地调整对各种作业/进程的偏好程度。缺点:若源源不断地有高优先级进程到来，则可能导致饥饿
• 会饥饿

6、最高响应比优先（HRRN）

基于响应比计算的优先级，响应比越高的进程优先执行。响应比的计算公式为等待时间加服务时间/服务时间。

• 非抢占式
• 综合考虑了等待时间和运行时间（要求服务时间) 等待时间相同时，要求服务时间短的优先(SJF的优点）要求服务时间相同时，等待时间长的优先（FCFS的优点>对于长作业来说，随着等待时间越来越久，其响应比也会越来越大，从而避免了长作业饥饿的问题
• 不会饥饿

7、多级反馈队列

一个进程需要执行 100 个时间片，如果采用时间片轮转调度算法，那么需要交换 100 次。

多级队列是为这种需要连续执行多个时间片的进程考虑，它设置了多个队列，每个队列时间片大小都不同，例如 1,2,4,8,..。进程在第一个队列没执行完，就会被移到下一个队列。

这种方式下，之前的进程只需要交换 7 次。每个队列优先权也不同，最上面的优先权最高。因此只有上一个队列没有进程在排队，才能调度当前队列上的进程。

可以将这种调度算法看成是时间片轮转调度算法和优先级调度算法的结合。

1. 设置多级就绪队列，各级队列优先级从高到低，时间片从小到大

2. 新进程到达时先进入第1级队列，按FCFS原则排队等待被分配时间片，若用完时间片进程还未结束，则进程进入下一级队列队尾。如果此时已经是在最下级的队列，则重新放回该队列队尾

3. 只有第k级队列为空时，才会为k+1级队头的进程分配时间片

• 抢占式的算法。在k级队列的进程运行过程中，若更上级的队列( 1~k-1级）中进入了一个新进程，则由于新进程处于优先级更高的队列中，因此新进程会抢占处理机，原来运行的进程放回k级队列入队尾。
• 对各类型进程相对公平(FCFS的优点）﹔每个新到达的进程都可以很快就得到响应（RR的优点）﹔短进程只用较少的时间就可完成(SPF的优点）﹔不必实现估计进程的运行时间（避免用户作假)﹔可灵活地调整对各类进程的偏好程度，比如cPU密集型进程、I/o密集型进程（拓展:可以将因I/o而阻塞的进程重新放回原队列，这样/o型进程就可以保持较高优先级)
• 会饥饿

先剩短轮，反响优

会饥饿的：短作业优先，优先级调度，多级反馈队列

104.进程和线程有什么区别？

1. 进程是资源分配的最小单位。 线程是程序执行的最小单位，处理器调度的基本单位，两者均可并发执行。
2. 进程有自己的独立地址空间，每启动一个进程，系统就会为它分配地址空间，建立数据表来维护代码段、堆栈段和数据段，这种操作非常昂贵。而线程是共享进程中的数据，使用相同的地址空间， 因此，CPU切换一个线程的花费远比进程小很多，同时创建一个线程的开销也比进程小很多。
3. 线程之间的通信更方便，同一进程下的线程共享全局变量、静态变量等数据，而进程之间的通信需要以通信的方式（IPC)进行。
4. 进程切换时，消耗的资源大，效率低。所以涉及到频繁的切换时，使用线程要好于进程。同样如果 要求同时进行并且又要共享某些变量的并发操作，只能用线程不能用进程。
5. 执行过程：每个独立的进程有一个程序运行的入口、顺序执行序列和程序入口。但是线程不能独立执行，必须依存在应用程序中，由应用程序提供多个线程执行控制。
6. 线程执行开销小，但是不利于资源的管理和保护。进程执行开销大，但是能够很好的进行资源管理和保护。如何处理好同步与互斥是编写多线程程序的难点。但是多进程程序更健壮，多线程程序只要有一个线程死掉，整个进程也跟着死掉了，而一个进程死掉并不会对另外一个进程造成影响，因为进程有自己独立的地址空间。

分配空间通消，独立保护

105.内核线程和用户线程的区别？

什么是内核线程和用户线程？

内核线程和用户线程有什么优缺点？

1. 管理：内核线程由操作系统内核来创建和管理的线程，它是由操作系统调度器调度的。用户线程是由用户应用程序自己管理的线程，它是在用户空间中运行。
2. 创建和销毁：内核线程是由操作系统内核来调度和管理的，而用户线程则是由用户程序来实现调度。因此，在线程的创建和销毁方面，内核线程比用户线程消耗更多的系统资源和时间。
3. 访问资源：由于内核线程是由操作系统内核来管理的，所以它可以直接访问操作系统内核的资源，如系统调用和底层硬件设备等。而用户线程只能访问用户空间的资源，如应用程序的数据和内存等，而无法直接访问操作系统内核的资源。
4. 线程切换：由于内核线程是由操作系统内核来管理的，所以线程切换需要从用户态切换到内核态，这个过程需要进行上下文切换，切换代价较高。而用户线程则是在用户态下运行的，线程的切换代价相对较低。
5. 并发性：内核线程可以在多个CPU上并发执行，因为内核线程可以被分配到任何一个可用的CPU上。用户线程只能在单个CPU上执行。

记忆：管创资切发

106.进程同步的方法

结合嵌入式Linux部分Linux内核中的进程同步方式一起学

同步是指在多个进程之间共享资源时，需要协调它们的执行顺序，以避免出现竞态条件等问题。以下是一些常用的进程同步方法：

临界区

临界区是指一段代码，在同一时刻只能被一个进程执行。为了保证多个进程在访问共享资源时不会产生冲突，可以使用临界区机制对共享资源进行保护。进程需要先获得对应的锁或信号量，才能进入临界区执行代码，执行完后再释放锁或信号量。

互斥锁（Mutex）

互斥锁用于保护共享资源，同一时间只允许一个进程访问共享资源。当进程需要访问共享资源时，它需要先获取互斥锁，如果互斥锁已经被其他进程获取了，那么进程就会被阻塞，直到互斥锁被释放为止。当进程完成对共享资源的访问时，它需要释放互斥锁，这样其他进程就可以访问共享资源了。

信号（Signal）

信号是一种进程间通信机制，用于在多个进程之间传递异步事件。当一个进程需要发送信号时，它可以调用发送函数，这样目标进程就会收到信号，并执行相应的处理函数。信号可以用于中断进程的执行，或者触发进程的某些行为。

信号量（Semaphore）

信号量是一种计数器，它用于保护共享资源。当进程需要访问共享资源时，它需要先获取信号量，如果信号量的值为正数，那么进程可以继续执行，同时信号量的值会减一；如果信号量的值为零，那么进程就会被阻塞，直到信号量的值大于零为止。当进程完成对共享资源的访问时，它需要释放信号量，同时信号量的值会加一，这样其他进程就可以访问共享资源了。

事件（Event）

事件是一种进程同步机制，用于在多个进程之间传递信号。当一个进程需要等待某个事件发生时，它可以调用事件的等待函数，这样进程就会被阻塞，直到事件发生为止。当另一个进程触发了事件后，它可以调用事件的通知函数，这样等待事件的进程就会被唤醒，继续执行。

条件变量（Condition Variable）

条件变量用于在多个进程之间传递信息，以协调它们的执行顺序。当一个进程需要等待某个条件成立时，它可以调用条件变量的等待函数，这样进程就会被阻塞，直到条件成立为止。当另一个进程满足了条件后，它可以调用条件变量的通知函数，这样等待条件的进程就会被唤醒，继续执行。

读写锁（Read-Write Lock）

读写锁用于保护共享资源，允许多个进程同时读取共享资源，但只允许一个进程写入共享资源。当一个进程需要读取共享资源时，它需要先获取读锁，如果没有其他进程持有写锁，那么进程可以获取读锁，同时其他进程也可以获取读锁；如果有进程持有写锁，那么进程就会被阻塞，直到写锁被释放为止。当一个进程需要写入共享资源时，它需要先获取写锁，如果没有其他进程持有读锁或写锁，那么进程可以获取写锁；否则进程就会被阻塞，直到读锁和写锁都被释放为止。

交换（Exchange）

交换是一种进程同步机制，用于在多个进程之间交换数据。当一个进程需要交换数据时，它可以调用交换函数，这样它就会被阻塞，直到另一个进程也调用了交换函数为止。当另一个进程调用了交换函数后，两个进程就会交换数据，并继续执行。

屏障（Barrier）

屏障用于协调多个进程的执行顺序，保证它们在某个点上同时开始执行或同时结束执行。当一个进程到达屏障时，它会被阻塞，直到所有进程都到达屏障为止。当最后一个进程到达屏障时，所有进程都会被唤醒，继续执行。

管程

管程是一种高级的同步机制，是一种抽象数据类型，提供了一组共享变量和一组操作共享变量的过程，保证多个进程在访问共享资源时的互斥和同步。管程封装了共享资源的访问方法，使得进程只能通过管程提供的接口访问共享资源，从而保证了共享资源的访问顺序和互斥性。管程可以使用条件变量等机制实现进程之间的同步和互斥。

两信互临，读事件，换屏管。

107.死锁的四个必要条件是什么？

死锁是指在多进程或多线程并发执行时，彼此持有对方需要的资源而陷入无法继续执行的一种状态。发生死锁，必须同时满足以下四个必要条件：

1. 互斥条件：每个资源同一时间只能被一个进程使用。
2. 请求和保持条件：一个进程因请求资源而阻塞时，已获得的资源保持不放。
3. 不可剥夺条件：进程已获得的资源，在未使用完之前不能被其他进程强制性地抢占。
4. 循环等待条件：若干进程之间形成一种头尾相连的循环等待资源的关系。

如果这四个条件同时满足，就可能会导致死锁的发生。要避免死锁，就需要采取相应的措施来打破上述条件之一，例如破坏环路等待条件、规定资源请求顺序、设置超时等待、资源剥夺或预防性阻塞等。

互求不等

108.如何预防死锁？

1. 破坏互斥条件：尽可能地允许多个进程同时访问资源，例如在某些情况下可以采用共享资源的方式，避免只允许一个进程使用资源。
2. 破坏请求和保持条件：在一个进程请求新的资源时，要求其释放已经获得的资源，等到新的资源获得后再重新申请之前释放的资源。
3. 破坏不可剥夺条件：对于某些资源，应该允许操作系统强制剥夺它们，例如如果某个进程因为某些原因无法继续运行，则系统可以剥夺其已经获得的资源。
4. 破坏循环等待条件：对所有的资源进行编号，进程只能按照编号顺序请求资源，避免形成环形等待。另外，可以采用资源分配策略，例如银行家算法，通过计算系统中可用资源的总量和已经分配的资源量，判断某个请求是否会导致死锁，从而避免死锁的发生。

109.解释下虚拟地址、逻辑地址、线性地址、物理地址、总线地址？

一个由程序员给出的逻辑地址，要先经过分段机制的转化变成线性地址，再经过分页机制的转化变成物理地址。

虚拟地址是指由程序产生的由段选择符和段内偏移地址组成的地址。这两部分组成的地址并没有直接访问物理内存，而是通过分段地址的变换处理后才会对应到相应的物理内存地址。 由MMU虚拟出来的地址。

逻辑地址指由程序产生的段内偏移地址。有时直接把逻辑地址当成虚拟地址，两者并没有明确的界限。

线性地址是指虚拟地址到物理地址变换之间的中间层，是处理器可寻址的内存空间（称为线性地址空间）中的地址。程序代码会产生逻辑地址，或者说是段中的偏移地址，加上相应段基址就生成了一个线性地址，线性地址 = 逻辑地址 + 基地址。如果启用了分页机制，那么线性地址可以再经过变换产生物理地址。若没有采用分页机制，那么线性地址就是物理地址。

物理地址是指现在CPU外部地址总线上的寻址物理内存的地址信号，是地址变换的最终结果。虚拟地址到物理地址的转化方法是与体系结构相关的，一般有分段与分页两种方式。以x86CPU为例，分段、分页都是支持的。内存管理单元负责从虚拟地址到物理地址的转化。逻辑地址是段标识+段内偏移量的形式，MMU通过査询段表，可以把逻辑地址转化为线性地址。

• 如果CPU没有开启分页功能，那么线性地址就是物理地址；

• 如果CPU开启了分页功能，MMU还需要查询页表来将线性地址转化为物理地址：

  逻辑地址（段表）→线性地址（页表）→物理地址。 映射是一种多对一的关系，即不同的逻辑地址可以映射到同一个线性地址上；不同的线性地址也可以映射到同一个物理地址上。而且，同一个线性地址在发生换页以后，也可能被重新装载到另外一个物理地址上，所以这种多对一的映射关系也会随时间发生变化。

总线地址是指在x86下的I/O地址，ARM下的物理地址。（在x86下，外设的I/O地址是独立的，即有专门的指令访问外设I/O，I/O地址就是“总线地址”，而RAM地址就是“物理地址”。在ARM下，I/O和RAM统一编址，但linux为了统一各个平台，仍然保留这个概念，总线地址其实就是物理地址。）

• IO内存空间，统一编址，设备地址作为内存的扩展，一般嵌入式用这种
• IO端口空间，独立编址，设备地址独立编制，一般用于x86，了解即可

逻辑地址：我们程序员写代码时给出的地址叫逻辑地址，其中包含段选择子和偏移地址两部分。

线性地址：通过分段机制，将逻辑地址转换后的地址，叫做线性地址。而这个线性地址是有个范围的，这个范围就叫做线性地址空间，32 位模式下，线性地址空间就是 4G。

物理地址：就是真正在内存中的地址，它也是有范围的，叫做物理地址空间。那这个范围的大小，就取决于你的内存有多大了。

虚拟地址：如果没有开启分页机制，那么线性地址就和物理地址是一一对应的，可以理解为相等。如果开启了分页机制，那么线性地址将被视为虚拟地址，这个虚拟地址将会通过分页机制的转换，最终转换成物理地址。

110.简述处理器在读内存过程中，CPU、MMU、cache、内存如何协同工作？

1. 首先，CPU发出一个读取内存的指令，并提供要读取的内存地址。
2. MMU (Memory Management Unit) 接收到这个内存地址，并进行地址转换。因为CPU使用的是虚拟地址，而内存使用的是物理地址，所以MMU会将虚拟地址转换为物理地址。
3. 如果需要的内存数据已经在cache中，那么cache会将数据返回给CPU。否则，cache会向内存发出请求，请求读取需要的数据。
4. 内存将所需数据返回给cache，cache将数据返回给CPU。同时，cache还会将这些数据保存在自己的缓存中，以备将来使用。

总的来说，CPU发送内存读取请求时，MMU会负责地址转换，cache会负责缓存数据，内存会提供所需的数据。这些组件共同协作，使得处理器能够高效地读取内存中的数据。

111.内存非连续分配管理的三种方式

• 分页存储管理：优点是不需要连续的内存空间，且内存利用率高（只有很小的页内碎片）；缺点是不易于实现内存共享与保护。

• 分段存储管理：优点是易于实现段内存共享和保护；缺点是每段都需要连续的内存空间，且内存利用率较低（会产生外部碎片）。

• 段页式存储管理（对每个段分页存储）：优点是不需要连续的内存空间，内存利用率高（只有很小的页内碎片），且易于实现段内存共享和保护；缺点是管理软件复杂性较高，需要的硬件以及占用的内存也有所增加，使得执行速度下降。

112.什么是快表，你知道多少关于快表的知识？

快表，又称联想寄存器(TLB) ，是一种访问速度比内存快很多的高速缓冲存储器，用来存放当前访问的若干页表项，以加速地址变换的过程。与此对应，内存中的页表常称为慢表。

113.虚拟内存是什么？

虚拟内存是一种计算机内存管理技术，它可以将物理内存和磁盘空间结合起来，让操作系统可以在物理内存不足的情况下运行更多的应用程序。它通过将应用程序使用的内存分为虚拟页面（虚拟地址空间）和物理页面（物理地址空间），并使用分页机制将虚拟页面映射到物理页面上来实现。

当应用程序需要访问一个虚拟页面时，操作系统将根据页面映射表将虚拟页面映射到物理页面上，如果该页面不在物理内存中，操作系统将会将其中的一部分数据存储到磁盘中，并将该页面从物理内存中移除。当应用程序需要再次访问该页面时，操作系统会将该页面从磁盘中加载回物理内存中，这个过程称为页面调度或页面置换。

114.虚拟内存的目的是什么？

虚拟地址的优点

1. 扩大可用内存：虚拟内存可以将物理内存和磁盘空间结合起来，以实现更大的可用内存。在物理内存不足时，虚拟内存可以将不常用的页面从物理内存中移除，并将它们暂时保存在磁盘上。这样，系统就可以用磁盘空间来模拟更大的物理内存。
2. 保护内存：虚拟内存可以实现地址空间隔离，使每个应用程序都拥有自己独立的虚拟地址空间。这样，应用程序就无法访问其他应用程序的内存，从而增强了系统的安全性。
3. 简化内存管理：虚拟内存可以使内存管理更加灵活和高效。它可以将内存分为多个页面，并使用页面置换算法来管理内存。这样，操作系统就可以按需加载页面，并将不常用的页面从物理内存中移除，从而实现更高效的内存管理。

计算机网络

115.什么是OSI七层模型？每层列举2个协议。

1. 物理层:

   • 传输单位为bit

   • 功能：通过物理媒介透明的传输比特流,确定机械及电气规范

   • 主要包括的协议为：IEE802.3 CLOCK RJ45

2. 数据链路层:

   • 传输单位为帧
   • 功能：将网络层传来的IP数据包封装成帧，标识网络中各主机。功能概括为封装成帧、差错检测、流量控制和传输管理
   • 主要包括的协议为：MAC VLAN PPP ARP协议、RARP协议

3. 网络层：

   • 传输单位为数据报
   • 功能：负责数据包从源端到目的端的传递和网际互连。关键问题是网络和主机的编址问题和对分组进行路由选择，实现流量控制、拥塞控制、差错控制和网际互联。
   • 主要包括的协议为：IP协议、ICMP协议

4. 传输层：

   • 传输单位为报文

   • 功能：负责主机中两个进程间的通信，提供端到端的可靠报文传递和错误恢复。为端到端连接提供流量控制、差错控制、服务质量和数据传输管理。

   • 主要包括的协议为：TCP UDP

5. 会话层：

   • 传输单位为SPDU

   • 功能：建立、管理和终止会话，运行不同主机的各个进程之间进行会话。

   • 主要包括的协议为：RPC NFS

6. 表示层:

   • 传输单位为PPDU

   • 功能：处理在两个通信系统中交换信息的表示方式，对数据进行翻译、加密和压缩。

   • 主要包括的协议为：JPEG ASII

7. 应用层:

   • 传输单位为APDU，
   • 功能：为特定类型的网络应用提供访问允许访问OSI环境的手段
   • 主要包括的协议为：FTP（文件传送协议）、Telnet（远程登录协议）、DNS（域名解析协议）、SMTP（邮件传送协议），POP3协议（邮局协议），HTTP协议。

记忆：物链网，传话实用

116.应用层常见协议？

协议 名称 默认端口(传输层) 底层协议

HTTP	超文本传输协议	80	TCP
HTTPS	超文本传输安全协议	443	TCP
Telnet	远程登录服务的标准协议	23	TCP
FTP	文件传输协议	20传输和21连接	TCP
SMTP	简单邮件传输协议（发送用）	25	TCP
POP3	邮局协议（接收用）	110	TCP
DNS	域名解析服务	53	服务器间进行域传输的时候用TCP,客户端查询DNS服务器时用 UDP
TFTP	简单文件传输协议	69	UDP
SNMP	简单网络管理协议	161	UDP

117.传输层常见协议

协议 名称 作用

TCP	传输控制协议(Transmission Control Protocol)	是一种面向连接的、可靠的、基于字节流的传输层通信协议。
UDP	用户数据报协议(User Datagram Protocol)	是OSI参考模型中一种无连接的传输层协议，提供面向事务的简单不可靠信息传送服务。

118.网络层常见协议？

协议 名称 作用

IP	网际协议	IP协议不但定义了数据传输时的基本单元和格式，还定义了数据报的递交方法和路由选择
ICMP	网络控制报文协议	ICMP就是一个“错误侦测与回报机制”，其目的就是让我们能够检测网路的连线状况﹐也能确保连线的准确性，是ping和traceroute的工作协议
RIP	路由信息协议	使用“跳数”(即metric)来衡量到达目标地址的路由距离
IGMP	网络组管理协议	用于实现组播、广播等通信

119.数据链路层常见协议？

协议 名称 作用

ARP	地址解析协议	根据IP地址获取物理地址
RARP	反向地址转换协议	根据物理地址获取IP地址
PPP	点对点协议	主要是用来通过拨号或专线方式建立点对点连接发送数据，使其成为各种主机、网桥和路由器之间简单连接的一种共通的解决方案
MAC	Media Access Control Address，直译为媒体存取控制位址，也称为局域网地址、以太网地址或物理地址	MAC 地址作为数据链路设备的地址标识符，需要保证网络中的每个 MAC 地址都是唯一的，才能正确识别到数据链路上的设备

120.http请求报文与响应报文格式

http报文由三个部分组成：

• 对报文进行描述的起始行（start line）

• 包含属性的首部（header）块，

• 可选的、包含数据的主体（body）部分。

起始行和首部就是由行分隔的 ASCII 文本。每行都以一个由两个字符组成的行终止序列作为结束，其中包括一个回车符（ASCII 码 13）和一个换行符（ASCII 码 10）。这个行终止序列可以写做 CRLF。需要指出的是，尽管 HTTP 规范中说明应该用CRLF 来表示行终止，但稳健的应用程序也应该接受单个换行符作为行的终止。有些老的，或不完整的 HTTP 应用程序并不总是既发送回车符，又发送换行符。

一、请求报文

HTTP请求报文分为三部分，有请求行、请求头部、请求数据。

1.请求行（HTTP请求报文的第一行）

请求行包括了方法，url，以及http协议版本。这三个字段之间由空格符分隔。例如：

POST /api/post HTTP/1.1

其中，方法字段严格区分大小写，当前HTTP协议中的方法都是大写，方法字段介绍如下：

• 【方法字段】

①GET:请求获取Request-URI(URI:通用资源标识符,URL是其子集，URI注重的是标识，而URL强调的是位置，可以将URL看成原始的URI),所标识的资源

②POST：在Request-URI所标识的资源后附加新的数据；支持HTML表单提交，表单中有用户添入的数据，这些数据会发送到服务器端，由服务器存储至某位置（例如发送处理程序）

③HEAD:请求Request-URI所标识的资源响应消息报头，HEAD方法可以在响应时不返回消息体。

④PUT：与GET相反，请求服务器存储一个资源，并用Request-URI做为其标识；例如发布系统。

⑤DELETE：请求删除URL指向的资源

⑥OPTIONS：请求查询服务器的性能，或者查询与资源相关的选项

⑦TRACE：跟踪请求要经过的防火墙、代理或网关等，主要用于测试或诊断

⑧CONNECT保留将来使用

• 【URL】

一个完整的包括类型、主机名和可选路径名的统一资源引用名，如：http://www.example.com/path/to/file.html

• 【版本】

报文使用的HTTP协议版本

2.请求头部：位于请求行的下面

请求报文中常见的标头有：

Connetion标头（连接管理）、Host标头（指定请求资源的主机）、Range标头（请求实体的字节范围）、User-Agent标头（包含发出请求的用户信息）、Accept标头（首选的媒体类型）、Accept-Language(首选的自然语言)

• 【通用首部：请求和响应都可以使用的】；

这些是客户端和服务器都可以使用的通用首部。可以在客户端、服务器和其他应用程序之间提供一些非常有用的通用功能。

Connection：允许客户端和服务器指定与请求 / 响应连接有关的选项，Connection: keep-alive

Date5：提供日期和时间标志，说明报文是什么时间创建的

Via: 显示了报文经过的中间节点

Cache-Control: 缓存指示

• 【请求首部】：

从名字中就可以看出，请求首部是请求报文特有的。它们为服务器提供了一些额外信息，比如客户端希望接收什么类型的数据。

Host: 请求的主机名和端口号，虚拟主机环境下用于不同的虚拟主机

Referer：指明了请求当前资源的原始资源的URL

User-Agent: 用户代理，使用什么工具发出的请求

1、Accept首部：用户标明客户自己更倾向于支持的能力

Accept: 指明服务器能发送的媒体类型

Accept-Charset: 支持使用的字符集

Accept-Encoding: 支持使用的编码方式

Accept-Language: 支持使用语言

2、条件请求首部：

Expect: 告诉服务器能够发送来哪些媒体类型

If-Modified-Since: 是否在指定时间以来修改过此资源

If-None-Match:如果提供的实体标记与当前文档的实体标记不符，就获取此文档

跟安全相关的请求首部：

Authorization: 客户端提交给服务端的认证数据，如帐号和密码

Cookie: 客户端发送给服务器端身份标识。客户端用它向服务器传送一个令牌——它并不是真正的安全首部，但确实隐含了安全功能

Cookie2：用来说明请求端支持的 cookie 版本

• 【实体首部：用于指定实体属性】

实体首部指的是用于应对实体主体部分的首部。比如，可以用实体首部来说明实体主体部分的数据类型。实体首部提供了有关实体及其内容的大量信息，从有关对象类型的信息，到能够对资源使用的各种有效的请求方法。总之，实体首部可以告知报文的接收者它在对什么进行处理。

实体主体用于POST方法中。用户向Web服务器提交表单数据的时候，需要使用POST方法，此时主体中包含用户添写在表单的各个属性字段的值，当Web服务器收到POST方法的HTTP请求报文后，可以从实体中取出需要的属性字段的值。

也就是说，当用户通过Web浏览器向Web服务器发送请求时,Web浏览器会根据用户的具体请求来选择不同的HTTP请求方法，再将相应的URL和HTTP协议版本及相关的标头填入头部行中，若是POST方法，还会将相关的表单数据填入实体主体中，产生一个HTTP请求报文，然后将这个报文发送给Web服务器。

Location: 资源的新位置

Allow: 允许对此资源使用的请求方法

1、内容首部：

Content-Encoding：支持的编码

Content-Language：支持的自然语言

Content-Length：文本长度

Content-Location：资源所在位置

Content-Range：在整个资源中此实体表示的字节范围

Content-Type：主体的对象类型

2、缓存首部：

ETag: 实体标签

Expires: 过期期限

Last-Modified: 上一次的修改时间

3.请求数据

报文的主体（或者就称为主体）是一个可选的数据块。与起始行和首部不同的是，主体中可以包含文本或二进制数据，也可以为空。

二、响应报文

HTTP响应报文同样也分为三部分，有状态行、首部行、实体。

1.状态行（HTTP响应报文的第一行）

响应行包括了http协议版本，响应状态码以及原因短语。这三个字段之间由空格符分隔，例如：

HTTP/1.1 200 OK

• 【状态码】：

状态码 类别 含义

1XX	Informational（信息性状态码）	接收的请求正在处理
2XX	Success（成功状态码）	请求正常处理完毕
3XX	Redirection（重定向状态码）	需要进行附加操作以完成请求
4XX	Client Error（客户端错误状态码）	客户端错误，服务器无法处理请求
5XX	Server Error（服务器错误状态码）	服务器错误，处理请求出错

2.首部行（响应首部）（位于响应报文状态行之后）

响应报文有自己的响应首部集。响应首部为客户端提供了一些额外信息，比如谁在发送响应、响应者的功能，甚至与响应相关的一些特殊指令。这些首部有助于客户端处理响应，并在将来发起更好的请求。

Date标头：消息产生的时间

Age标头:（从最初创建开始）响应持续时间

Server标头: 向客户端标明服务器程序名称和版本

ETage标头：不透明验证者

Location标头：URL备用的位置

Content-Length标头：实体的长度

Content-Tyep标头：实体的媒体类型

协商首部：

Accept-Ranges: 对当前资源来讲，服务器所能够接受的范围类型

Vary: 首部列表，服务器会根据列表中的内容挑选出最适合的版本发送给客户端

跟安全相关的响应首部：

Set-Cookie: 服务器端在某客户端第一次请求时发给令牌

WWW-Authentication: 质询，即要求客户提供帐号和密码

3.实体（位于首部行之后）

实体包含了Web客户端请求的对象。Content-Length标头及Content-Type标头用于计算实体的位置、数据类型和数据长度。当Web服务器接收到Web客户端的请求报文后，对HTTP请求报文进行解析，并将Web客户端的请求的对象取出打包，通过HTTP响应报文将数据传回给Web客户端，如果出现错误则返回包含对应错误的错误代码和错误原因的HTTP响应报文。

121.http协议版本http1.1和http1.0的区别？

HTTP1.0最早在网页中使用是在1996年，那个时候只是使用一些较为简单的网页上和网络请求上，而 HTTP1.1则在1999年才开始广泛应用于现在的各大浏览器网络请求中，同时HTTP1.1也是当前使用最为广泛的HTTP协议。 主要区别主要体现在：

1. 缓存机制不同

   HTTP 1.1 引入了缓存控制机制，使得客户端和服务器可以更好地控制缓存的使用。HTTP 1.1 中的缓存控制机制包括强缓存和协商缓存两种，而 HTTP 1.0 中只有简单的过期时间控制。

2. 持久连接

   HTTP 1.1 支持持久连接（也称为 HTTP keep-alive），即客户端与服务器之间的 TCP 连接可以被重用，从而避免了每个请求都要建立新的连接的开销。HTTP 1.0 中则默认不支持持久连接。

3. 分块传输编码

   HTTP 1.1 引入了分块传输编码，使得服务器可以动态地生成响应内容，而不需要事先知道响应数据的大小。HTTP 1.0 中则只能使用 Content-Length 头部来指定响应数据的大小。

4. 范围请求

   HTTP 1.1 支持范围请求，使得客户端可以请求服务器发送指定范围的数据。HTTP 1.0 中则不支持范围请求。

5. Host 头部

   HTTP 1.1 中的每个请求和响应都必须包含 Host 头部，这个头部用来指示服务器的主机名和端口号。HTTP 1.0 中没有 Host 头部。

122.http2.0与http1.1和http1.0的区别

1. 传输方式

   HTTP/1.0 和 HTTP/1.1 使用的是文本格式的传输方式，即通过文本协议来传输数据，而 HTTP/2.0 使用的是二进制格式的传输方式。

2. 多路复用

   HTTP/1.0 和 HTTP/1.1 只能同时处理一个请求，需要等待前一个请求完成后才能处理下一个请求。而 HTTP/2.0 引入了多路复用的概念，可以同时处理多个请求，提高了传输效率。

3. 请求优先级

   HTTP/1.0 和 HTTP/1.1 没有提供请求优先级的机制，所有请求都是平等的。而 HTTP/2.0 可以通过设置请求的优先级，使得服务器优先处理重要的请求。

4. 压缩方式

   HTTP/1.0 和 HTTP/1.1 使用的是 gzip 压缩格式，而 HTTP/2.0 引入了 HPACK 压缩格式，可以更好地压缩请求和响应头部。

5. 服务器推送

   HTTP/1.0 和 HTTP/1.1 不能主动向客户端推送资源，需要客户端发送请求才能获取资源。而 HTTP/2.0 可以通过服务器推送机制，主动向客户端推送资源，提高了加载速度。

123.http协议有什么特点？

1. 支持多种数据格式：HTTP 协议支持多种数据格式，包括文本、图片、音频、视频等，可以通过不同的 Content-Type 头部字段来指定数据格式。
2. 无状态性：HTTP 协议是无状态的，即每个请求与响应之间都是独立的，服务器不会保存请求或响应的状态信息。这种无状态性有利于提高服务器的并发处理能力，但也意味着服务器无法直接识别同一用户发出的不同请求。
3. 明文传输：HTTP 协议传输的数据是明文的，不具有加密和认证功能，因此容易受到攻击，不适合传输敏感信息。为了解决这个问题，可以使用 HTTPS 协议来加密和认证数据传输。
4. 基于TCP协议
5. 默认端口80

多无明T8

124.HTTPS采用的加密方式有哪些？是对称还是非对称？

HTTPS是什么？加密原理和证书。SSL/TLS握手过程_哔哩哔哩_bilibili

HTTPS采用的加密方式通常是对称加密和非对称加密的混合使用，首先使用非对称加密算法交换对称加密算法所使用的密钥，然后使用对称加密算法对数据进行加密和解密。

需要注意的是，HTTPS采用的加密方式是与所使用的证书有关的。证书中包含了加密算法的相关信息，客户端和服务器端通过证书来协商使用的加密方式。在建立HTTPS连接时，客户端会向服务器端发送一个“客户端协商列表”，该列表中包含了客户端支持的加密算法。服务器端从列表中选择一种加密算法，并将该算法的相关信息作为证书的一部分发送给客户端，客户端使用该算法进行加密和解密。

125.请你来说一下数字证书是什么，里面都包含哪些内容？

SSL中的认证中的证书是什么？了解过吗？

数字证书是一种用于验证身份和安全通信的数字文件。它通常由第三方机构（证书颁发机构或CA数字证书认证机构）颁发，用于证明某个实体（例如个人、组织或网站）的身份。数字证书包含以下内容：

1. 公钥：数字证书中包含一个公钥用于加密数据。
2. 所有者信息：数字证书中包含所有者的信息，例如名称、电子邮件地址和组织名称等。
3. 证书颁发机构信息：数字证书中包含颁发证书的证书颁发机构（CA）的信息，例如名称和数字签名等。
4. 有效期：数字证书中包含证书的有效期，即证书颁发日期和过期日期。
5. 数字签名：数字证书中包含证书颁发机构使用其私钥对证书进行数字签名的信息，以便验证证书的真实性和完整性。

126.HTTPS是如何保证数据传输的安全，整体的流程是什么？

https建立连接过程是什么?

SSL是怎么工作保证安全的

SSL握手的基本过程

HTTPS 通过使用 SSL/TLS 协议来保证数据传输的安全，（其实就是非对称加密算法rsa原理）其整体的流程如下：

1. 客户端向服务器发起 HTTPS 请求（SSL 请求，请求建立 SSL 连接）。
2. 服务器返回数字证书，证书中包含服务器公钥、证书颁发机构信息和证书有效期等信息。
3. 客户端使用内置的证书验证机构或者自定义的证书验证机构对数字证书进行验证，以确保证书的真实性和有效性。如果验证不通过，通信将被终止。
4. 客户端随机生成对称密钥，并使用服务器公钥加密后发送给服务器。
5. 服务器使用私钥解密客户端发送的数据，得到对称密钥。
6. 通信双方使用对称加密算法进行加密通信，保证数据传输的机密性。

在这个过程中，对称密钥的生成和传输是关键步骤。通过对称密钥加密数据，可以在保证传输速度的同时保证数据的安全性。由于对称密钥的生成和传输只发生在 HTTPS 会话的开始阶段，因此可以避免在数据传输过程中反复进行密钥的生成和传输，提高了传输效率和安全性。同时，通过数字证书的验证，可以确保服务器的身份和证书的真实性，防止中间人攻击等安全威胁。

发返验，加解通

127.GET 和 POST 的区别，你知道哪些？

1. 数据操作类型：GET是获取数据，POST是修改数据

2. 数据传输方式：GET 方法传输的数据是明文的，GET把请求的数据放在url上， 以?分割URL和传输数据，参数之间以&相连，所以GET不太安全。而POST把数据放在HTTP的包体内（request body 相对安全）。GET比POST不安全，因为参数直接暴露在url中，所以不能用来传递敏感信息。而 POST 方法可以通过 SSL/TLS 加密传输数据，保证传输的安全性。

   //GET把请求的数据放在url上的示例：在bilibili搜bilibili
   https://search.bilibili.com/all?keyword=bilibili&from_source=webtop_search&spm_id_from=333.1007&search_source=5
   

3. 请求数据长度：GET提交的数据最大是2k（ 限制实际上取决于浏览器）， post理论上没有限制。

4. GET产生一个TCP数据包，浏览器会把http header和data一并发送出去，服务器响应200(返回数据); POST产生两个TCP数据包，浏览器先发送header，服务器响应100 continue，浏览器再发送data，服务器响应200 ok(返回数据)。

5. GET请求会被浏览器主动缓存，而POST不会，除非手动设置。

6. 数据传输格式：GET 方法只能传输 ASCII 码字符，而 POST 方法可以传输二进制数据。

7. 本质区别：GET是幂等的，而POST不是幂等的。

   这里的幂等性：幂等性是指一次和多次请求某一个资源应该具有同样的副作用。简单来说意味着对同一URL的多个请求应该返回同样的结果。

正因为它们有这样的区别，所以不应该且不能用get请求做数据的增删改这些有副作用的操作。因为get请求是幂等的，在网络不好的隧道中会尝试重试。如果用get请求增数据，会有重复操作的风险，而这种重复操作可能会导致副作用（浏览器和操作系统并不知道你会用get请求去做增操作）。

记忆：获u2两缓

128.Cookies Session Token区别是什么？

• Cookies是存储在用户浏览器中的小型文本文件，用于跟踪用户在网站上的活动。Cookies通常包含一个标识符和一些附加信息，例如用户偏好设置或购物车内容。Web应用程序使用Cookies来保持用户状态，例如在用户进行登录认证后保持用户的登录状态。Cookies是无状态的，也就是说，它们本身不存储任何有关用户的信息，但可以用于识别用户。
• Session是一种服务器端的机制，用于在Web应用程序中存储和管理用户状态。Web应用程序在服务器端为每个用户创建一个唯一的Session ID，该ID用于在服务器端跟踪用户的会话信息。Session ID通常存储在Cookies中，但也可以存储在URL参数中。Web应用程序使用Session来管理用户状态，例如在用户进行登录认证后存储用户的登录信息，或在用户在网站上进行购物时存储购物车内容。
• Token是一种加密字符串，用于验证用户的身份和授权用户对Web应用程序的访问。Web应用程序在用户进行登录认证后，生成一个Token并将其存储在客户端的Cookies或本地存储中。之后，当用户进行后续的请求时，Web应用程序使用Token来验证用户的身份和授权用户对资源的访问。

总的来说，Cookies和Session都是用于管理用户状态的机制，而Token则是用于验证用户身份和授权访问的机制。Cookies是存储在客户端的文本文件，Session是存储在服务器端的会话信息，而Token是加密字符串。

129.DNS的工作原理

谈谈DNS解析过程，具体一点

将主机域名转换为ip地址，属于应用层协议，使用UDP传输。

过程总结： 浏览器缓存，系统缓存，路由器缓存，ISP服务器缓存，根域名服务器缓存，顶级域名服务器缓存，主域名服务器缓存。

DNS解析过程指的是将用户输入的URL域名解析为IP地址的过程。DNS解析过程包括以下步骤：

1. 浏览器缓存：浏览器会首先检查自己的缓存中是否有该域名对应的IP地址。如果有，浏览器将直接使用这个IP地址，而不需要进行后续的DNS查询过程。
2. 操作系统缓存：如果浏览器缓存中没有该域名对应的IP地址，操作系统会检查自己的DNS缓存中是否有该域名对应的IP地址。如果有，操作系统会直接返回这个IP地址给浏览器，而不需要进行后续的DNS查询过程。
3. 路由器缓存：如果操作系统缓存中也没有该域名对应的IP地址，那么请求将被发送到本地网络中的路由器。路由器通常也会有自己的DNS缓存，它会检查是否有该域名对应的IP地址。如果有，路由器会返回这个IP地址给操作系统，否则它会将请求转发给ISP的DNS服务器。
4. ISP DNS服务器(ISP互联网服务提供商)：如果在缓存中没有找到该域名对应的IP地址，那么ISP的DNS服务器就会被用来解析域名。ISP的DNS服务器可能会有多个，一般按照距离和性能来选择最优的服务器。ISP DNS服务器会按照从右到左的顺序，依次查找该域名的顶级域名服务器、权威域名服务器等，并将最终的IP地址返回给用户的计算机。
5. 根DNS服务器：如果ISP的DNS服务器也没有找到该域名对应的IP地址，那么它会向根DNS服务器发出请求。根DNS服务器负责维护整个DNS树形结构，它会返回一个指向顶级域名服务器的IP地址给ISP的DNS服务器。
6. 顶级域名服务器：ISP的DNS服务器收到根DNS服务器返回的顶级域名服务器的IP地址后，就会向顶级域名服务器发出请求。顶级域名服务器会返回一个指向负责该域名的权威域名服务器的IP地址给ISP的DNS服务器。
7. 权威域名服务器：最后，ISP的DNS服务器会向权威域名服务器发出请求，并获取该域名对应的IP地址。权威域名服务器返回IP地址给ISP的DNS服务器，ISP的DNS服务器再将这个IP地址返回给用户的计算机，完成整个DNS解析过程。

浏操路，I根顶权

130.在浏览器中输入url地址后显示主页的过程?

• 根据域名，进行DNS域名解析；
• 拿到解析的IP地址，建立TCP连接；
• 向IP地址，发送HTTP请求；
• 服务器处理请求；
• 返回响应结果；
• 关闭TCP连接；
• 浏览器解析HTML；
• 浏览器布局渲染；

输入地址并确认后，浏览器对域名进行访问，浏览器对域名进行解析，如果浏览器有域名对应的DNS相关信息的缓存，有的话可以拿到服务端的IP地址，如果没有的话，会去本地的host文件查看是否进行了配置，如果host文件没有配置相关的信息，那么就会发起DNS请求用来获取对应的服务器的IP地址。应用端会构造DNS的请求报文，应用层会调用传输层的UDP的相关协议进行数据传输，会在DNS的基础上加上UDP的请求头然后传输信息至网络层，网络层会在UDP的请求报文基础上加上IP的请求头然后到数据链路层，数据链路层会实现二层寻址，会加上自己的mac信息和通过网络层的ARP协议里拿到的下一步基地的mac信息一起通过物理层一起传输出去，通常传到路由器，然后路由器这个三层设备最终会通过运营商的路线传输到下一个路由器地址，达到服务器后信息通过相同步骤进行层层解析HTTP的请求报文，然后构造HTTP响应报文沿着相同的步骤传输至客户端。

131.搜索baidu，会用到计算机网络中的什么层？每层是干什么的?

访问网址的过程

浏览器中输入URL 浏览器要将URL解析为IP地址，解析域名就要用到DNS协议，首先主机会查询DNS的缓存，如果没有就给本地DNS发送查询请求。DNS查询分为两种方式，一种是递归查询，一种是迭代查询。如果是迭代查询，本地的DNS服务器，向根域名服务器发送查询请求，根域名服务器告知该域名的一级域名服务器， 然后本地服务器给该一级域名服务器发送查询请求，然后依次类推直到查询到该域名的IP地址。DNS服 务器是基于UDP的，因此会用到UDP协议。

得到IP地址后，先建立TCP连接，再浏览器就要与服务器建立一个http连接。因此要用到http协议，http协议报文格式上面 已经提到。http生成一个get请求报文，将该报文传给TCP层处理，所以还会用到TCP协议。如果采用 https还会使用https协议先对http数据进行加密。TCP层如果有需要先将HTTP数据包分片，分片依据路径MTU和MSS。

TCP的数据包然后会发送给IP层，用到IP协议。IP层通过路由选路，一跳一跳发送到目的地址。当然在一个网段内的寻址是通过以太网协议实现(也可以是其他物理层协议，比如PPP，SLIP)，以太网协议需要直到目的IP地址的物理地址，有需要ARP协议。

其中：

1、DNS协议，http协议，https协议属于应用层 应用层是体系结构中的最高层。应用层确定进程之间通信的性质以满足用户的需要。这里的进程就是指正在运行的程序。应用层不仅要提供应用进程所需要的信息交换和远地操作，而且还要作为互相作用的 应用进程的用户代理，来完成一些为进行语义上有意义的信息交换所必须的功能。应用层直接为用户的 应用进程提供服务。

2、TCP/UDP属于传输层 传输层的任务就是负责主机中两个进程之间的通信。因特网的传输层可使用两种不同协议：即面向连接 的传输控制协议TCP，和无连接的用户数据报协议UDP。面向连接的服务能够提供可靠的交付，但无连 接服务则不保证提供可靠的交付，它只是“尽最大努力交付”。这两种服务方式都很有用，备有其优缺 点。在分组交换网内的各个交换结点机都没有传输层。

3、IP协议，ARP协议属于网络层 网络层负责为分组交换网上的不同主机提供通信。在发送数据时，网络层将运输层产生的报文段或用户 数据报封装成分组或包进行传送。在TCP/IP体系中，分组也叫作IP数据报，或简称为数据报。网络层的 另一个任务就是要选择合适的路由，使源主机运输层所传下来的分组能够交付到目的主机。

4、数据链路层

当发送数据时，数据链路层的任务是将在网络层交下来的IP数据报组装成帧，在两个相邻结点间的链路 上传送以帧为单位的数据。每一帧包括数据和必要的控制信息（如同步信息、地址信息、差错控制、以及流量控制信息等）。控制信息使接收端能够知道—个帧从哪个比特开始和到哪个比特结束。控制信息 还使接收端能够检测到所收到的帧中有无差错。

5、物理层 物理层的任务就是透明地传送比特流。在物理层上所传数据的单位是比特。传递信息所利用的一些物理媒体，如双绞线、同轴电缆、光缆等，并不在物理层之内而是在物理层的下面。因此也有人把物理媒体当做第0层。

132.TCP头部中有哪些信息？

TCP数据报格式（左图） UDP数据报格式也放这（右图），不具体解释了。

结合三次握手四次挥手来看

• 端口：

  区分应用层的不同应用进程

  扩展：应用程序的端口号和应用程序所在主机的 IP 地址统称为 socket（套接字），IP:端口号, 在互联网上 socket 唯一标识每一个应用程序，源端口+源IP+目的端口+目的IP称为”套接字对“，一对套接字就是一个连接，一个客户端与服务器之间的连接。

• 序号seq（32bit）：

  传输方向上字节流的字节编号。用于 TCP 通信过程中某一传输方向上字节流的每个字节的编号，为了确保数据通信的有序性，避免网络中乱序的问题。接收端根据这个编号进行确认，保证分割的数据段在原始数据包的位置。初始时序号会被设置一个随机的初始值（ISN），之后每次发送数据时，序号值 = ISN + 数据在整个字节流中的偏移。假设A -> B且ISN = 1024，第一段数据512字节已经到B，则第二段数据发送时序号为1024 + 512。

• 确认序号ack（32bit）：

  确认序列号是接收确认端所期望收到的下一序列号。确认序号应当是上次已成功收到数据字节序号seq加1，只有当标志位中的 ACK 标志为 1 时该确认序列号的字段才有效。主要用来解决不丢包的问题。

• 首部长（4bit）：

  标识首部有多少个4字节 * 首部长，最大为15，即60字节。

• 标志位（6bit）：

  • URG：(urgent紧急) 标志紧急指针是否有效。
  • ACK：(acknowledgement 确认)标志确认号是否有效（确认报文段）。用于解决丢包问题。
  • PSH：(push传送) 提示接收端立即从缓冲读走数据。
  • RST：(reset重置) 表示要求对方重新建立连接（复位报文段）。
  • SYN：(synchronous同步) 表示请求建立一个连接（连接报文段）。
  • FIN：(finish结束) 表示关闭连接（断开报文段）。

• 窗口（16bit）：

  接收窗口,滑动窗口大小。用于告知对方（发送方）本方的缓冲还能接收多少字节数据。用于解决流控。

• 校验和（16bit）：

  接收端用CRC检验整个报文段有无损坏。

• 紧急指针（16bit）:

  紧急指针表示紧急数据的末尾位置，用于标识紧急数据的范围。

133.简述一下TCP建立连接和断开连接的过程。

三次握手

TCP建立连接过程（三次握手）：

1. 客户端向服务端发送SYN包（SYN=1，ACK=0），表示请求建立连接，并指定客户端的初始序列号seq=x。客户端进入 SYN_SENT状态，等待Server确认。

2. 服务端收到客户端的SYN=1知道Client请求建立连接，向客户端发送SYN/ACK包（SYN=1，ACK=1），表示同意建立连接，并指定服务端的初始序列号seq=y，同时确认客户端的序列号ack=x+1。服务端进入 SYN_RCVD状态。

3. 客户端收到服务端的SYN/ACK包后，检查ack是否为x+1，ACK是否为1，如果正确则向服务端发送ACK包（SYN=0，ACK=1），确认建立连接，并指定确认序列号ack=y+1。服务端检查ack是否为y+1，ACK是否为1，如果正确则连接建立成功，客户端和服务端进入ESTABLISHED状态，完成三次握手，随后Client与Server之间可以开始传输数据了。

四次挥手

TCP断开连接过程（四次挥手）：

1. 客户端向服务端发送FIN包（FIN=1，ACK=1），表示请求断开连接，并指定序列号seq=x。客户端进入 FIN_WAIT_1状态，此时客户端依然可以接收服务器发送来的数据。

2. 服务端收到客户端的FIN包后，向客户端发送ACK包（ACK=1），确认接收到了断开连接请求，并指定确认序列号ack=x+1。服务器进入CLOSE_WAIT 状态。客户端收到后进入FIN_WAIT_2状态。

3. 当服务器没有数据要发送时，发送FIN包（FIN=1，ACK=1），请求断开连接，并指定序列号seq=y。此时服务器进入LAST_ACK状态，等待客户端的确认。

4. 客户端收到服务端的FIN包后，向服务端发送ACK包（ACK=1），确认接收到了断开连接请求，并指定确认序列号ack=y+1。此时客户端进入TIME_WAIT状态，等待2MSL（MSL：报文段最大生存时间），然后关闭连接。

完整过程

134.TCP的三次握手和四次挥手的原因是什么？

为什么TCP建立连接是三次握手，而关闭连接却是四次挥手？

为什么是三次握手？

1. 三次握手才可以阻止重复历史连接的初始化(主因)
2. 三次握手才可以同步双方的初始序列号
3. 三次握手才可以避免资源浪费

解释： 1、阻止重复历史连接的初始化（主因）

为了防止已失效的连接请求报文段突然有送到了B，而产生错误

假设两次握手时，A发出的第一个请求连接报文段在某一网络节点长时间滞留，以致延误到连接释放后才到达B。B收到失效的连接请求报文段后，认为是A又发出一次新的连接请求。于是向A发送确认报文段，同意建立连接，此时在假定两次握手的前提下，连接建立成功。这样会导致B的资源白白浪费。

如果已失效的连接请求报文段突然又送到了服务端

1. 当旧的SYN报文先到达服务端时，服务端回⼀个ACK+SYN报文。

2. 客户端收到后可以根据自身的上下文，判断这是⼀个历史连接（序列号过期或超时），那么客户端就会发送RST 报文给服务端，表示中止这一次连接。

   两次握手在收到服务端的响应后开始发生数据，不能判断当前连接是否是历史连接。 三次握手可以在客户端准备发送第三次报文时，客户端因有足够的上下文来判断当前连接是否是历史连接。

2、同步双方的初始序列号 TCP 协议的通信双方， 都必须维护⼀个「序列号」 ， 序列号是可靠传输的⼀个关键因素。

• 接收端可以去除重复数据。

• 接收端可以按照序列号顺序接收。

• 标识发送的数据包，哪些已经被收到。

  两次握手只保证了一方的初始序列号能被对方成功接收，没办法保证双方的初始序列号都能被确认接收。

  三次握手一来一回，才能确保双方的初始序列号能被可靠的同步。

3、避免资源浪费。

1. 两次握手会造成消息滞留情况下，服务器重复接受无用的连接请求 SYN 报文，而造成重复分配资源。

2. 只有两次握手时，如果客户端的SYN请求连接在网络中阻塞，客户端没有收到服务端的ACK报文，会重新发送SYN。

3. 由于没有第三次握手，服务器不清楚客户端是否收到了自己发送的建立连接的 ACK 确认信号，所以每收到一个 SYN 就只能先主动建立个连接。

为什么是四次挥手？

• TCP协议是全双工通信，这意味着客户端和服务器端都可以向彼此发送数据，所以关闭连接是双方都需要确认的共同行为。

• 服务端通常需要等待完成数据的发送和处理， 所以服务端的ACK和FIN⼀般都会分开发送，从而比三次握手导致多了⼀次。

  关闭连接时，客户端发送FIN报文，表示其不再发送数据， 但还可以接收数据。

  服务端收到FIN报文，先回一个ACK应答报文，服务端可能还要数据需要处理和发送，等到其不再发送数据时，才发送FIN报文给客户端表示同意关闭连接。

• 如果采用三次挥手来关闭连接，可能会出现以下问题：

  • 客户端发送FIN报文后，服务端无法确认客户端是否真的已经关闭了连接，因此需要等待一段时间才能确认客户端已经关闭连接。
  • 服务端发送FIN报文后，客户端还可能会发送一些数据，如果没有第四次ACK报文的确认，服务端可能会误认为客户端仍然需要传输数据。

135.请说说你对TCP连接中time_wait状态的理解

为什么要设置time_wait？

为什么客户端最后还要等待2MSL？

TCP连接的TIME_WAIT状态是指在TCP连接关闭时，主动关闭连接的一方会进入TIME_WAIT状态，在这个状态下等待一段时间，以确保对方收到了自己的FIN包并成功关闭连接。这个等待时间一般是2倍的最大段生存时间（Maximum Segment Lifetime, MSL），也就是2*60s=120s，或者根据具体的操作系统实现而定。

TIME_WAIT状态的主要作用是防止连接复用和连接的混淆。如果连接关闭时没有TIME_WAIT状态，那么在关闭连接之后，如果有一个新的连接出现，并且它的初始序列号恰好与刚关闭的连接的序列号相同，那么这个新的连接就可能会收到之前关闭连接的数据，导致混淆和错误。

**time_wait状态产生的原因 **

1. 确保客户端正确关闭连接

当服务器发送FIN包表示要关闭连接时，客户端需要回复ACK包确认收到FIN包，并且等待一段时间确保对方没有发送任何数据。如果服务器确实没有发送数据，那么对方的FIN包已经成功到达，连接成功关闭（服务器发的FIN丢了或者客户端发的ACK丢了，服务器都会重传，当然进入了time_wait状态说明收到服务器的FIN包了）。而2MSL的时间正好足够长，可以确保服务器收到ACK包。

2. 避免旧数据包的混淆

TCP连接中，每个数据包都有一个序列号，用于标识数据包在传输过程中的顺序。在TIME_WAIT状态中，等待2MSL的时间可以确保网络上所有可能的延迟数据包都已经被丢弃，从而避免旧的数据包被错误地传递到新的连接中，即防止新的连接使用旧连接的相同序列号，避免数据的混淆和干扰。

TCP还设有一个保活计时器，显然，客户端如果出现故障，服务器不能一直等下去，白白浪费资源。服务器每收到一次客户端的请求后都会重新复位这个计时器，时间通常是设置为2小时，若两小时还没有收到客户端的任何数据，服务器就会发送一个探测报文段，以后每隔75秒发送一次。若一连发送10个探测报文仍然没反应，服务器就认为客户端出了故障，接着就关闭连接。

如果 TIME-WAIT 等待足够长的情况就会遇到两种情况：

1. 服务端正常收到四次挥手的最后⼀个 ACK 报文，则服务端正常关闭连接。

2. 服务端没有收到四次挥手的最后⼀个 ACK 报文时，则会重发 FIN 关闭连接报文并等待新的 ACK 报文。

如果没有TIME_WAIT等待

• 网络情况不好时，如果主动方无TIME_WAIT等待，关闭前个连接后，主动方与被动方又建立起新的TCP连接，这时被动方重传或延时过来的FIN包过来后会直接影响新的TCP连接；
• 同样网络情况不好并且无TIME_WAIT等待，关闭连接后无新连接，当接收到被动方重传或延迟的FIN包后，会给被动方回一个RST包，可能会影响被动方其它的服务连接。

136.为什么 TIME_WAIT 等待的时间是 2MSL？

在TCP连接中，TIME_WAIT状态的等待时间通常被设置为2倍的最大段生存时间（Maximum Segment Lifetime, MSL）。MSL是指网络上一个数据包被允许存活的最长时间，也就是一个数据包从发送出去到被丢弃之间的时间。

因为客户端不知道服务端是否能收到ACK应答数据包，服务端如果没有收到ACK，会进行重传FIN，考虑最坏的一种情况：第四次挥手的ACK包的最大生存时长(MSL)+服务端重传的FIN包的最大生存时长(MSL)=2MSL

1. 等待MSL两倍：网络中可能存在发送方的数据包，当这些发送方的数据包被接收方处理后又会向对方发送响应，所以⼀来⼀回需要等待 2 倍的时间。

2. 2MSL 的时间是从客户端接收到 FIN 后发送 ACK 开始计时的。如果在 TIME-WAIT 时间内，因为客户端的ACK没有传输到服务端，客户端又接收到了服务端重发的 FIN 报文，那么 2MSL 时间将重新计时。

137.TCP拔了网线还有连接吗

TCP 协议是一种面向连接的协议，它在建立连接时需要进行三次握手，而在关闭连接时需要进行四次挥手。因此，在正常情况下，当一方主动关闭连接后，另一方也会发送 ACK 确认报文，表示同意关闭连接，此时连接才会真正断开。

但是，如果在连接建立之后，其中一方的网络连接出现故障或者断开，比如拔掉网线或者出现网络中断等情况，那么连接会出现异常关闭的情况，也就是说，连接并没有经过正常的四次挥手过程，而是在一方出现故障后直接中断了。

当出现异常关闭的情况时，另一方的 TCP 协议会尝试重新建立连接，而这个过程会涉及到超时重传，保活机制等，直到重新建立成功或者超过最大重试次数后，连接才会彻底断开。

因此，尽管在 TCP 连接建立之后拔掉网线或者出现网络中断等情况，连接并不会立即断开。

138.TCP相比UDP为什么是可靠的？

TCP的可靠性

TCP怎么保证可靠性

TCP为什么是可靠连接？

1. 校验和：发送数据报的二进制相加然后取反，检测数据在传输过程中的变化，有差错则丢弃。
2. 确认应答：接收方收到正确的报文就会确认。
3. 超时重传：发送方等待一定时间后没有收到确认报文则重传。
4. 序列号：发送方对每一个数据包编号，接收方对数据包排序，保证不乱序、不重复。
5. 流量控制：滑动窗口机制，双方会协调发送的数据包大小，保证接收方能及时接收。
6. 拥塞控制：如果网络拥塞，发送方会降低发送速率，降低整个网络的拥塞程度。

校认时序流拥

139.TCP和UDP的区别

TCP，UDP的优缺点是什么？

1、TCP面向连接（如打电话要先拨号建立连接）;UDP是无连接的，即发送数据之前不需要建立连接

2、每一条TCP连接只能是点到点的;UDP支持一对一，一对多，多对一和多对多的交互通信

3、TCP面向字节流，实际上是TCP把数据看成一连串无结构的字节流;UDP是面向报文的

4、TCP提供可靠的服务。通过TCP连接传送的数据，无差错，不丢失，不重复，且按序到达;UDP尽最大努力交付，即不可靠交付

5、TCP 保证数据顺序，UDP 不保证

6、TCP有拥塞控制；UDP没有拥塞控制，因此网络出现拥塞不会使源主机的发送速率降低（对实时应用很有用，如IP电话，实时视频会议等）

7、TCP首部开销20字节;UDP的首部开销小，只有8个字节，程序结构较简单

连点字，可顺拥开

数据结构

140.顺序表和链表的比较

数组和链表的区别是什么？

解释一下顺序存储和链式存储

存取（读取）方式

顺序表可以顺序存取，也可以随机存取，链表只能从表头顺序存取元素。

逻辑结构与物理结构

采用顺序存储时，逻辑上相邻的元素，对应的物理存储位置也相邻。而采用链式存储时，逻辑上相邻的元素，物理存储位置不一定相邻，对应的逻辑关系是通过指针链接来实现的。

查找、插入和删除操作

查找：对于按值查找，顺序表无序时，两者的时间复杂度均为O（n）；顺序表有序时，可采用折半查找，此时的时间复杂度为O (log2n)。对于按序号查找，顺序表支持随机访问，时间复杂度仅为O（1），而链表的平均时间复杂度为O（n）。

插入、删除：顺序表的插入、删除操作，平均需要移动半个表长的元素；链表的插入、删除操作，只需要修改相应的结点指针域即可。由于链表的每个结点都带有指针域，故而存储密度不够大。

空间分配

顺序存储在静态存储分配情形下，一旦存储空间装满就不能扩充，若再加入新的元素，则会出现内存溢出，因此需要预先分配足够大 的存储空间。预先分配过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。动态分配存储虽然存储空间可以扩 充，但需要移动大量元素，导致操作效率降低，而且若内存中没有更大块的连续存储空间，则会导致分配失败。

链式存储的结点空间只在需要时申请分配，只要内存有空间就可以连续分配，操作灵活、高效。

存存插删空

141.链表有环怎么处理

链表有环是指链表中存在一个节点的指针指向了链表中的某个已经访问过的节点，从而形成了一个环形结构。链表有环可能会导致一些问题，比如遍历链表时出现死循环，或者在查找某个节点时无法结束。

在判断链表是否有环时，可以使用快慢指针的方法。具体步骤如下：

1. 定义两个指针 slow 和 fast，初始时都指向链表的头节点；
2. slow 指针每次向后移动一个节点，fast 指针每次向后移动两个节点；
3. 如果链表中不存在环，fast 指针最终会指向链表的末尾（即为 NULL），此时可以结束遍历；
4. 如果链表中存在环，由于 fast 指针移动的速度是 slow 指针的两倍，因此在遍历的过程中 fast 指针一定会追上 slow 指针，并且在某个节点处相遇；
5. 如果两个指针相遇，则说明链表中存在环，此时可以使用类似于找到环的起点的方法来处理环形链表。

找到环的起点的方法可以使用双指针，具体步骤如下：

1. 定义两个指针 p1 和 p2，初始时都指向链表的头节点；
2. p1 指针向后移动一个节点，p2 指针向后移动两个节点，直到两个指针相遇；
3. 让 p1 指针重新指向链表的头节点，p2 指针不动；
4. 同时移动 p1 和 p2 指针，每次都向后移动一个节点，直到两个指针再次相遇，相遇的节点即为环的起点。

142.双向链表插入结点

插入：

不唯一，但是1、2必须在3前面

s->next=p->next; //将结点s插入到结点p之后
p->next->prior=s;
s->prior=p;
p->next=s;

删除：

p->next=q->next; 
p->next->prior=p; 
free(q); 

143.一道类似于数据接收处理，然后返回的题目

题目描述：

有一个从计算机接收数据的函数：

void data_recevied(uint8_t *data, size_t size, size_t offset);

这个函数的功能，是从计算机接收到数据，数据的大小，数据的偏移量；如果数据连续的话，就使用数据发送函数，将数据发送给用户，如果不连续的话，应该怎么处理。

考虑问题：

1.怎么样去判断数据是否连续；

2.在不知道数据大小的情况下，怎么去存储多个不连续的数据；

定义一个存储数据，大小，偏移量三个元素的链表，在数据不连续的时候，将数据插入到链表中，形成一个有序链表，然后在数据连续之后，遍历链表，一次性的将链表的数据发送给用户，然后清除链表，只保留最后一个节点的信息。

144.循环队列？

向循环队列插入一个元素。 (rear + 1) % capacity;

删除一个元素 (front + 1) % capacity;

获取队首元素 return elements[front];

获取队尾元素 return elements[(rear - 1 + capacity) % capacity];

判断队空 return rear == front;

判断队满

• 判断队满，((rear + 1) % capacity) == front这种写法会浪费一个空间
• 可以多一个size的变量来记录元素个数，可以不浪费一个空间
• 可以增加tag标志，根据上一次是增加还是删除元素来区分rear==front是队空还是队满

队列中元素个数 (rear + capacity - front ) % capacity

class MyCircularQueue {
private:
    int front;
    int rear;
    int capacity;
    vector<int> elements;

public:
    MyCircularQueue(int k) {
        this->capacity = k + 1;
        this->elements = vector<int>(capacity);
        rear = front = 0;
    }

    bool enQueue(int value) { //向循环队列插入一个元素。
        if (isFull()) {
            return false;
        }
        elements[rear] = value;
        rear = (rear + 1) % capacity;
        return true;
    }

    bool deQueue() { //从循环队列中删除一个元素。
        if (isEmpty()) {
            return false;
        }
        front = (front + 1) % capacity;
        return true;
    }

    int Front() { //从队首获取元素。
        if (isEmpty()) {
            return -1;
        }
        return elements[front];
    }

    int Rear() { //获取队尾元素
        if (isEmpty()) {
            return -1;
        }
        return elements[(rear - 1 + capacity) % capacity];
    }

    bool isEmpty() { //判断队空
        return rear == front;
    }

    bool isFull() { //判断队满，这种写法会浪费一个空间，可以多一个size的变量来记录元素个数，可以不浪费一个空间
        return ((rear + 1) % capacity) == front;
    }
};

145.什么是二叉树？介绍各种树？

二叉树：是一种树形结构，其特点是每个结点至多只有两颗子树，并且二叉树的子树有左右之分，其次序不能任意颠倒。

平衡二叉树：树上任意结点的左子树和右子树的深度差不超过1。

满二叉树：一颗二叉树的结点要么是叶子结点要么它有两个子节点。

完全二叉树：若设二叉树的深度为h，除第h层外，其他各层节点数都达到最大个数，第h层结点都连续集中在最左边。

二叉堆：二叉堆是一种特殊的完全二叉树，它满足堆的性质，即父节点的值总是大于或等于（最大堆）或小于或等于（最小堆）其子节点的值。二叉堆常用于实现优先队列等数据结构，可以高效地进行插入、删除最值等操作。

最优二叉树：也叫哈夫曼树，是一种用于数据压缩的二叉树结构。它是通过哈夫曼编码算法生成的，树中的每个叶节点都对应着一个字符，并且叶节点的权重（频率）越高，离根节点的距离越短。哈夫曼树可以实现高效的数据压缩和解压缩。

线索二叉树：线索二叉树是一种对普通二叉树进行改进的数据结构，它的节点除了包含左右子节点的指针外，还包含指向中序遍历的前驱和后继节点的线索。这样可以实现在不使用递归或栈的情况下，高效地遍历二叉树。

二叉搜索树（Binary Search Tree，BST）：又称二叉排序树：左子树结点值<根节点值<右子树结点值。二叉搜索树是一种特殊的二叉树，它满足以下性质：对于树中的每个节点，其左子树中的所有节点的值都小于该节点的值，而右子树中的所有节点的值都大于该节点的值。这个性质使得二叉搜索树可以用来高效地进行查找、插入和删除操作。

自平衡二叉搜索树AVL：它通过在插入或删除节点时进行旋转操作来保持树的平衡。AVL树的特点是任何节点的左子树和右子树的高度差不超过1，这使得它具有较快的查找和插入操作的时间复杂度。

红黑树：红黑树是一种特殊的二叉搜索树，它在二叉搜索树的基础上增加了一些性质，以保证树的平衡性。红黑树的性质包括：每个节点要么是红色，要么是黑色；根节点是黑色的；每个叶节点（NIL节点，空节点）是黑色的；不能有相邻的两个红色节点等。

B树：B树是一种平衡多路查找树，广泛用于文件系统和数据库中。它的特点是每个节点可以存储多个关键字和对应的值，并且可以拥有多个子节点。B树通过增加节点的容量和调整树的结构来保持平衡，从而提供高效的数据检索和插入/删除操作。

B+树：B+树是一种平衡的多路查找树，它在数据库和文件系统中被广泛应用。

146.如何构造哈夫曼树？哈夫曼编码的意义是什么？

数据结构——五分钟搞定哈夫曼树，会求WPL值，不会你打我_哔哩哔哩_bilibili

哈夫曼树:带权路径长度（WPL）最小的二叉树。

构造哈夫曼树的算法描述如下：

1）将n个结点分别看作n棵仅含一个结点的二叉树。

2）在所有的根节点中选取两个根节点权值最小的数构造成新的二叉树，再将根节点与其他n-1个根节点进行比较，选出根节点权值最小的两棵树进行归并，重复上述步骤，直至所有结点都归并到一个树上为止。

哈夫曼编码的意义：

将出现频率高的字符使用较短的编码，反之出现频率较低的则使用较长的编码，降低字符串的平均期望长度。频繁使用的机器指令操作使用较短的编码，这样会提高执行的效率。

147.什么是二叉树退化？

二叉树的退化是指二叉树变成了一条链，即每个节点只有一个子节点或没有子节点。这种情况下，二叉树的高度就变成了n-1，其中n是树中的节点数。

二叉树的退化可能是由于插入节点的顺序导致的。例如，如果我们按照升序或降序依次插入节点，那么得到的二叉树就是一条链。这种情况下，二叉树的查找操作和插入操作的时间复杂度都变成了O(n)，因为它们需要遍历整个链。

二叉树的退化还可能是由于树的不平衡导致的。例如，如果树的左子树或右子树过深，而另一侧子树过浅，那么树就会退化成一条链。这种情况下，我们需要通过旋转操作或者平衡二叉树等方法来重新平衡树的结构，以保证树的高度尽可能地小，从而提高查找和插入的效率。

在实际应用中，为了避免二叉树的退化，我们可以使用平衡二叉树等数据结构来代替普通的二叉树。平衡二叉树能够自动调整节点的位置，以保证树的高度始终是log(n)，从而保证了查找和插入操作的时间复杂度是O(log(n))。

148.什么是红黑树

【数据结构】红 黑 树_哔哩哔哩_bilibili

红黑树（Red-Black Tree）是一种自平衡二叉查找树（BST），它在树的每个节点上增加了一个存储位来表示节点的颜色，可以保证任何一个节点的左右子树的高度差小于两倍，从而保证了红黑树的查找、插入、删除的时间复杂度都是O(log n)。

红黑树的特点如下：

1. 每个节点都有一个颜色，红色或黑色。
2. 根节点是黑色的。
3. 所有叶子节点（NIL节点）都是黑色的。
4. 如果一个节点是红色的，则它的子节点必须是黑色的。
5. 从任意一个节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。

红黑树的自平衡性是通过节点颜色和旋转操作来实现的。当插入或删除一个节点时，如果破坏了红黑树的特性，就需要通过重新着色和旋转操作来保持平衡。

（应对面试），面试官问红黑树怎么旋转调整的，一般能问到这么细的就看真本事了，要我我选择放弃，但是问我红黑树是什么，有什么意义还是可以回答的：排序二叉树有不平衡的问题，可能左子树很长但是右子树很短，造成查询时性能不佳（logn退化成n），完全平衡的二叉树能保证层数平均，从而查询效率高，但是维护又很麻烦，每次插入和删除有很大的可能要大幅调整树结构。红黑树就是介于完全不平衡和完全平衡之间的一种二叉树，通过每个节点有红黑两种颜色、从节点到任意叶子节点会经过相同数量的黑色节点等一系列规则，实现了【树的层数最大也只会有两倍的差距】，这样既能提高插入和删除的效率，又能让树相对平衡从而有还不错的查询效率。从整体上讲，红黑树就是一种中庸之道的二叉树。

149.红黑树的优缺点

红黑树是一种自平衡的二叉查找树，它在插入、删除等操作后能够自动调整以保持树的平衡，从而保证了其在最坏情况下的时间复杂度为 O(log n)。红黑树的优缺点如下：

优点：

1. 平衡性：红黑树通过对节点进行特定的着色和旋转操作，保持了树的平衡性，使得树的高度保持在一个相对较小的范围内，保证了查找、插入和删除操作的高效性，最坏情况下的时间复杂度为 O(log n)。

2. 高效的插入与删除：红黑树的自平衡特性使得插入和删除节点的操作相对简单快速，并且不会导致树的过度深度。

3. 数据顺序性：红黑树是二叉查找树的一种，它保持了节点之间的有序性，因此支持一些特定的操作，如范围查找。

4. 广泛应用：红黑树被广泛用于实现C++的STL中的map和set，以及Java的TreeMap和TreeSet等标准库中，这些数据结构要求高效的查找、插入和删除操作，红黑树正好满足这些需求。

缺点：

1. 略微复杂：红黑树的实现比较复杂，包括节点着色、旋转等操作，容易出错，需要仔细处理边界情况，使得其实现相对困难。

2. 内存占用较大：相比于其他平衡二叉查找树，红黑树的节点需要额外存储用于表示节点颜色的位，因此相对于简单的二叉查找树，红黑树的内存占用会更大一些。

3. 不适合频繁的插入和删除操作：尽管红黑树能够保持相对平衡，但在频繁插入和删除节点的情况下，可能会引起频繁的调整操作，导致性能下降。

4. 不适合小规模数据集：对于小规模的数据集，红黑树的优势可能无法充分体现，因为它的平衡性带来的好处在小规模情况下可能并不明显。

综上所述，红黑树在大规模数据集上具有较好的平衡性和高效的查找、插入和删除操作，但对于小规模数据集和频繁插入删除操作，可能不是最优选择。在实际应用中，需要根据具体情况综合考虑数据规模和操作类型来选择合适的数据结构。

150.什么是B+树

终于把B树搞明白了(一)_B树的引入，为什么会有B树_哔哩哔哩_bilibili

设计一个文件系统的索引：

• 数组/顺序表：慢，插入删除移动成本很高

• 哈希：

  缺点: 1.hash冲突后，数据散列不均匀，产生大量线性查询，效率低 ⒉.等值查询可以，但是遇到范围查询，得挨个遍历，hash就不合适了 优点:等值查询比较快

• 二叉树

• BST二叉查找树：问题：二叉树退化。

• AVL平衡二叉树：问题：变平衡移动成本很高（插入少，查询多时使用比较好）

• 红黑树：（最长子树不超过最短子树的二倍，保证了插入效率和查找效率）问题：数据量大时，树的深度变深，查找的IO次数越多，影响读取效率。

• B树（一个有序的多路查询树）

• B+树（相对B树：数据在叶子节点上，数据之间有关系，查找要最终找到叶子节点上）

151.图的存储方式

邻接矩阵：矩阵的第i行第j列表示i到j是否连接。

邻接表：链表后面跟着所有指向的点。

邻接矩阵的优点是可以很方便的知道两个节点之间是否存在边，以及快速的添加或删除边；缺点是如果节点个数比较少容易造成存储 空间的浪费。

邻接表的优点是节省空间，只给实际存在的边分配存储空间；缺点是在涉及度时可能需要遍历整个链表。

十字链表法

邻接多重表

152.图的遍历

简述一下广度优先遍历和深度优先遍历

广度优先搜索BFS：首先访问结点v，由近至远依次访问和v邻接的未被访问过的结点，类似于层次遍历。

深度优先搜索DFS：首先访问顶点v，若v的第一个邻接点没有被访问过，则访问该邻接点；若v的第一个邻接点已经被访问，则访问其第 二个邻接点；类似于先序遍历。

153.简述一下求最小生成树的两种算法。

最小生成树：生成树集合中，边的权值之和最小的树。

普利姆（prim）算法：从某一个顶点开始构建生成树，每次将代价最小的新的顶点纳入生成树中，直到所有顶点都纳入为止，适用于边稠密图。

克鲁斯卡尔（kruskal）算法：按照边权值递增的次序构建生成树，每次选择一条权值最小的边，使这条边的两头连通（原本已连通就不选），直到所有结点都连通为止，适用于边稀疏图。

154.简述一下求最短路径的两种算法

最短路径：把带权路径长度最短的那条路径称为最短路径。

迪杰斯特拉（Dijkstra）算法：数据结构——看完这个视频终于会用迪杰斯特拉算法求最短路径啦_哔哩哔哩_bilibili

求单源最短路径，用于求某一顶点到其他顶点的最短路径，它的特点是以起点为中心层层向外扩展， 直到扩展到终点为止，迪杰斯特拉算法要求的边权值不能为负。

弗洛伊德（Floyd）算法：数据结构——看完这个视频终于会用Floyd算法求最短路径啦_哔哩哔哩_bilibili

求各顶点之间的最短路径，用于解决任意两点间的最短路径，它的特点是可以正确处理有向图或负权值的 最短路径问题。

155.哈希冲突怎么解决？

哈希冲突是指不同的输入数据在经过哈希函数计算后得到相同的哈希值，这是一种常见的情况。解决哈希冲突的方法有以下几种常见的技术：

1. 链地址法（Chaining）：在哈希表的每个槽位（桶）中，使用链表等数据结构存储冲突的元素。当发生冲突时，新元素可以直接插入到链表的末尾。这种方法可以高效地解决冲突，但需要额外的空间来存储链表。
2. 开放地址法（Open Addressing）：在哈希表的每个槽位中存储一个元素，当发生冲突时，通过一定的探测方法（如线性探测、二次探测、双重哈希等）找到下一个可用的槽位。这种方法不需要额外的数据结构存储冲突的元素，但可能导致聚集性冲突，即一旦发生冲突，后续的插入操作可能会更加耗时。
3. 再哈希（Rehashing）：当发生冲突时，重新计算哈希函数，使用新的哈希值来定位元素的位置。这种方法可以一定程度上避免冲突，但如果哈希函数设计不合理，仍然可能导致冲突。

记忆：再开链

156.常见的三种哈希结构

当我们想使用哈希法来解决问题的时候，我们一般会选择如下三种数据结构。

• 数组
• set(集合
• map(映射)

这里数组就没啥可说的了，我们来看一下set。

在C++中，set 和 map 分别提供以下三种数据结构，其底层实现以及优劣如下表所示：

集合 底层实现 是否有序 数值是否可以重复 能否更改数值 查询效率 增删效率

std::set	红黑树	有序	否	否	O(log n)	O(log n)
std::multiset	红黑树	有序	是	否	O(logn)	O(logn)
std::unordered_set	哈希表	无序	否	否	O(1)	O(1)

std::unordered_set底层实现为哈希表，std::set 和std::multiset 的底层实现是红黑树，红黑树是一种平衡二叉搜索树，所以key值是有序的，但key不可以修改，改动key值会导致整棵树的错乱，所以只能删除和增加。

映射 底层实现 是否有序 数值是否可以重复 能否更改数值 查询效率 增删效率

std::map	红黑树	key有序	key不可重复	key不可修改	O(logn)	O(logn)
std::multimap	红黑树	key有序	key可重复	key不可修改	O(log n)	O(log n)
std::unordered_map	哈希表	key无序	key不可重复	key不可修改	O(1)	O(1)

std::unordered_map 底层实现为哈希表，std::map 和std::multimap 的底层实现是红黑树。同理，std::map 和std::multimap 的key也是有序的（这个问题也经常作为面试题，考察对语言容器底层的理解）。

当我们要使用集合来解决哈希问题的时候，优先使用unordered_set，因为它的查询和增删效率是最优的，如果需要集合是有序的，那么就用set，如果要求不仅有序还要有重复数据的话，那么就用multiset。

那么再来看一下map ，在map 是一个key value 的数据结构，map中，对key是有限制，对value没有限制的，因为key的存储方式使用红黑树实现的。

虽然std::set、std::multiset 的底层实现是红黑树，不是哈希表，std::set、std::multiset 使用红黑树来索引和存储，不过给我们的使用方式，还是哈希法的使用方式，即key和value。所以使用这些数据结构来解决映射问题的方法，我们依然称之为哈希法。 map也是一样的道理。

157.说下你知道的排序算法？说下快排的过程，快排的时间复杂度

快速排序是一种常用的排序算法，它是基于分治法的思想，其基本思路是选定一个基准元素，将待排序数组分为左右两部分，左部分的元素均小于等于基准元素，右部分的元素均大于等于基准元素，然后对左右两部分递归地进行快速排序，最终将整个数组排好序。

下面是快速排序的详细过程：

1. 选择基准元素：从数组中选择一个元素作为基准元素，通常选择数组的第一个元素或者最后一个元素。
2. 分割操作：将数组分成两部分，小于等于基准元素的放在左边，大于等于基准元素的放在右边，相等的可以放在任意一边。这个过程叫做分割操作，也称为划分操作。
3. 递归排序：对左右两部分递归进行快速排序。
4. 合并结果：将左右两部分已经排好序的结果合并起来，就得到了最终的排序结果。

下面是快速排序的时间复杂度：

快速排序的时间复杂度为 O(nlogn)，其中 n 是数组的长度。最坏情况下的时间复杂度是 O(n^2)，出现在每次选取的基准元素都是当前序列的最大或最小值的情况下。但是，实际上快速排序的平均时间复杂度是 O(nlogn)，且它的常数因子比归并排序要小，所以它在实际应用中表现很好。

158.快速排序什么时候最坏?如何避免？

快速排序在以下情况下可能变得最坏：

1. 当输入数组已经按照相反的顺序排列时，即数组已经是按照降序排列的情况。这是因为快速排序的分割过程选择第一个元素作为基准，如果数组已经按照相反的顺序排列，每次分割都会产生最不平衡的子数组，导致快速排序的性能变差。

2. 当输入数组中存在大量相同的元素时，即存在重复元素的情况。这是因为快速排序的分割过程通常将数组划分为两个子数组，如果有很多重复元素，可能会导致两个子数组的大小差异很大，使得快速排序的性能下降。

为了避免快速排序在最坏情况下的性能问题，可以采取以下措施：

1. 随机选择基准元素：在选择基准元素时，可以随机选择数组中的一个元素作为基准，而不是固定选择第一个元素。这样可以减少最坏情况的出现概率，提高算法的平均性能。

2. 使用三数取中法选择基准元素：三数取中法是一种选择基准元素的方法，它选择数组的头部、尾部和中间位置的元素，然后取这三个元素的中间值作为基准元素。这样可以避免在已经有序或接近有序的数组中选择最小或最大的元素作为基准而导致的最坏情况。

3. 使用插入排序优化：在数组的大小较小（通常小于一定阈值）时，可以切换到使用插入排序等简单排序算法，而不是继续使用快速排序。这是因为对于小规模的数组，简单排序算法的性能可能比快速排序更好。

159.概述一下大根堆的构造过程？并说说堆排序的适用场景。

数据结构——堆排序_哔哩哔哩_bilibili

• 堆排序是完全二叉树，但不是排序二叉树
• 第一个非叶子节点，即第[n/2]个结点

排序

对于第[n/2]个结点为根的子树进行筛选，使得它的根结点大于等于左右子树（小根堆反之），之后向前依次（[n/2]-1~1）为根的子树进行筛选，看该结点值是否大于其左右子树结点，若不大于，则将左右子结点中较大者与之交换，交换后可能会破坏下一级堆，于是继续采用上述方法构造下一级的堆，直到以该结点为根的子树构建成堆为止。

插入

直接放到完全二叉树最后，然后排序它相关的父节点

删除

把最后一个节点放到删除的元素的位置，，然后排序它相关的父节点

适用场景：

堆排序适用于关键字较多的情况，比如在1亿个数中选出前100个最大值。

#嵌入式##八股#