Ephemeral

P19 1：更新找到最小的值，固定这个位置的序号，然后交换即可 2：直接逆置即可 3：放在数值该在的位置上、移动到数值该在的位置上 4：放在数值该在的位置上、移动到数值该在的位置上 补充：计数排序思想也是把数值放在该放的位置上 5：放在该在的位置上比较容易理解 6：While，循环，将两边中比较小的给放在数组中，用三个数组下标即可，最后复制 7：全部逆置、前部分逆置、后部分逆置 8：有序表，先查，再决定操作；顺序或折半查找，然后找到交换，没找到插入 9：三个工作指针，小的向大的靠拢，当三者相同时打印并同时自增 10：全部逆置、前部分逆置、后部分逆置 11：设变量，X1、X2，A【X1】大，X2++，B【X2】大，X1++，While，条件X1+X2<N 最后判断A【X1】、B【X2】，哪个大哪个是中位数，本质是找X1+X2=N，找中间位置点 思想：小的向大的靠拢 最优解：折半，实现比较复杂 12：利用辅助数组存储对应值的出现次数，访问辅助数组查看是否有大于半数次数 利用题设条件：Ai<N，明显说明可以考虑用辅助数组 或者考虑先排序，然后统计相同元素出现的次数，若小 ...

P10 1：模拟题、统考题中均需留意描述对象，做题前的反复阅读回顾是必要的 3：逐个分组确认与整个文件确认之间的优缺点和特性 分组确认，失败只需要重传分组；整个文件确认，失败则需要重传整个文件 按什么确认，就按什么重传 分组确认存在大量确认帧，整个文件确认仅存在一个确认帧 P39 1：绘画出流水线时间图计算，针对个人必须非常留意流水段是否写完整，易漏 基本流程：发送-传播-处理时延-发送-传播，以此判断是否缺漏 流水线注意事项：不同段的流水线不能重叠(虽然一般情况下不可能出现) 2：虚电路采取直通式，不可用流水线公式计算传输速率 虚电路传输过程中任何一个报文均携带首部，仅是首部携带内容是虚电路号而已 虚电路第一个分组首部会携带目的地址与源地址，数据报方式每个首部均会携带地址 P73 此类题型，务必注意单向传播时延、端到端时延、双向传播时延之间的描述关系 2：本题拓展知识点：信道利用率的定义是有效数据发送时间占比，排除确认帧这一类 3、4：经典错误类型，初始端的发送时延没有计算在内 信道利用率=发送时间/(RTT+第一个的发送时间) 5：极为经典的传输案例，后续一切传输都可以以此为基 ...

第一节 网络应用模型 C/S模型：客户机间不直接通信、网络管理集中、可拓展性差，服务器客户机模型 P2P模型：任意一对计算机任意通信、共享文档、可拓展性好、容错率高、点对点模型 随记 采用C/S模型协议：HTTP、FTP、DNS、SMTP、Telnet、SSH、POP3、IMAP、SQL 服务器、客户端都可以主动向对方发送消息，而没有限制 P2P，定义为一种逻辑网络，P2P，分发速度往往快于C/S，资源利用率和系统效率较高 补充内容 Web、FTP、电子邮件、文件服务器，均使用TCP，从而均需要构建三次握手、四次释放 DHCP、DNS，均使用UDP，不需要构建握手和释放，直接传输 这种一般不会显性给出，往往给定隐含条件：实时传输、文件传输，需要辨别类型 第二节 层级域名空间 知晓域名读法：右向左读，从右向左分别：顶级、二级、三级 域名服务器 外部层级：根域名服务器、顶级域名服务器、权限域名服务器 内部层级：本地域名服务器、主机 当本地域名服务器无法解析该域名时就需要求助根域名服务器，均采用网络地址 根域名服务器一般只返回需要搜索的顶级域名服务器网络地址 ...

第一节 概述为主，统考会涉及相应知识点 传输层概述 传输层不属于通信子网，但只有主机端会使用传输层，路由器不会使用传输层 传输层提供端到端的服务，链路层提供点到点的服务 传输层功能 主机进程间的逻辑通信，即端到端的通信 复用和分用，传输层可以准确封装、转交从应用程序来，到应用程序去的各类数据 差错检验：临时封装伪首部，检验内容包括伪首部与数据部分内容 UDP：检验到差错后直接丢弃，或者直接向上层汇报；有连接服务、可靠 TCP：检验到差错后要求重传；无连接服务、不可靠 同一个传输层同时支持两个协议的实现，各个应用程序可以根据需要选择协议 即，同一个主机可以实现两个协议，应用程序可以按照需求选择协议 端口号 服务访问点，重点内容，需要背诵 端口号内容，同样需要背诵，主要背诵常见协议的端口号即可 无连接服务、面向连接服务 TCP：点对点，只允许单播，具体实现在传输层，与网络层无关，开销大、可靠性高 UDP：支持广播，开销小、实时性高、无连接不带确认不可靠 随记 传输层应当算是通信子网到资源子网的过渡段，很难明确说明属于何层 会话层与传输层的区别：前者管理的主语是会话，后者管理的对象是端到端的 ...

第一节 网络层基本功能 路由选择：根据当前网络拓扑选择到达某个网络的最佳路径，并计算出转发表 分组转发：拆封后修改对应信息，重新封装，根据转发表从某个端口向外转发 OSI、TCP/IP，前者网络层有连接和无连接，后者网络层只有无连接 异构网络互联 路由器可以实现异构网络的互联，这个异构指代从网络层向下，各层均可不同 不同可以在介质、协议、拓扑，均可以不同，路由器能协调这些问题 本质是因为路由器是存储转发式设备 交换技术与转发技术 交换技术：报文交换、分组交换 交换技术主要关注数据如何在网络中被拆分和处理，例如报文、分组两种情况 转发技术：虚电路交换、数据报交换 转发技术决定数据包在网络中是通过预设路径还是动态选择路径进行传输 动态则为数据报，静态则为虚电路，动态任意选择路径，静态固定一条路径发送 因而交换技术与转发技术是没有冲突的，报文、分组交换均可以搭配虚电路或者数据报 虚电路、数据报内容：背诵为主 虚电路的转发中是含有差错检验的，数据报的转发是不存在差错检验的 SDN 远程控制器是控制平面，进行路由选择，通过协议方式将转发表或称流表下放给路由器 路由器是转发平面，仅接收 ...

第一节 链路层信道、广域网与局域网 数据链路层信道：广播信道（局域网）、点对点信道（广域网） 局域网主要工作在数据链路层，广域网主要工作在网络层，本章重点讨论局域网链路层 广域网链路层协议仅做大致上的介绍 注：广域网工作在网络层，仅是因为其链路层独有特征而被单独划分到第三章讨论 广域网链路层、全双工以太网链路层不需要实现介质访问控制，因为不可能产生冲突 局域网链路层需要实现介质访问控制，因为局域网往往是半双工工作 链路层基本功能 封装成帧、透明传输、差错检验，封装成帧与透明传输是为实现协议栈下其的职责 链路层差错检验，根据链路层是否可靠采用不同技术 当物理信道不可靠时需要链路层实现可靠传输，通常采用海明码、流量控制实现可靠性 物理信道不可靠的案例：无线局域网 当物理信道总体可靠时，链路层只需要采用检错码即可，有错则丢弃，上层实现可靠 物理信道可靠的案例：有线局域网（以太网） 数据链路层的可靠传输与流量控制由滑动窗口协议实现，有滑动窗口即可认定可靠 链路层的基本服务类型 无确认的无连接：有线以太网采用无确认的无连接，半双工采用冲突协议，全双工不用 有确认的无连接：无线通信，往往采用流量控 ...

第一节 通信基础 模拟信号、数字信号、通信系统 数字数据变为基带信号于数字信道上传输称为基带传输，数字信号是离散的 基带数据调制为模拟信号于模拟信道上传输被称为宽带传输，模拟信号是连续的 中继器、集线器放大数字信号，放大器放大模拟信号 数据转换为模拟信号称为调制，数据转换为数字信号称为编码，调制器、编码器对应 通信系统被分为：信源、信道、信宿，主要考察点在于全双工、半双工 通信传输 K进制码元，有2^K个离散值，携带Kbit信息，有2^K种码元 码元传输速率是波特，在曼彻斯特那边依旧存在一定争议的问题，不过应该不会考察 信道传输容量 奈奎斯特、香农定理，分别应用在无噪声、有噪声信道 奈奎斯特、香农定理，重点谈几个易错点即可 当两者均可以直接算出时，那么比较两者的值，取小为准，参考：12、14 并且记忆一个点：以太网采用曼彻斯特编码，故码元默认为二进制 宽度高速网中常使用差分曼彻斯特编码 信噪比存在两个概念，一个是公式内的计算概念，一个是外在的公式计算概念 当给出127：1，表示是S/N，当给出30dB时，给出的是10log10(S/N) 具体香农中计算使用的是S/N这个信噪比，而不是用 ...

第一节 计算机网络的概念、组成、功能 Internet，专有名词；inernet，泛指网络名词 硬件、软件、协议三者构成计算机网络；实际分类常分为通信子网和资源子网两者 计网功能，略微背诵即可 三种数据交换方式 电路交换，不会考察，统考从未命题，仅供参考 分组交换、报文交换均属于数据交换方式，具体可以由虚电路或者数据报方式实现 由虚电路实现就能保证有序，用数据报方式就可能会失序、丢失、重复分组 该部分内容见，P131，网络层提供的面向连接、不面向连接的服务，主要于网络层间交换 分组交换、报文交换需要记忆各自的特性 统考考察落点主要在流水线和存储转发两个主要特性上面，可以参考后续习题 计算机网络的分类 拓扑结构，该指代为物理结构，通信子网结构 其余内容为次要内容，可归纳为背诵内容，不是特别重要 计网的性能指标 速率：计网中常用，K，相对于计组有一定区别，这里的单位是十进制不是二进制 带宽：一般同样采用十进制作为上层单位，为理论值；吞吐量为实际值 时延：发送时延、传播时延、处理时延、排队时延 信道利用率：定义有一定争议，后续有道统考题的信道利用率反而是有效数据传输率 详细可见P73，29题 ...

第一章 电路交换、报文交换、分组交换的特性，以及应用场景 数据链路层、网络层、传输层、会话层、表示层、应用层各自的特性和内容 TCP/IP模型与OSI模型的区别，相应的特征和考察重点 第二章 五种编码和其对应的编码准则、波形等内容 传输介质相关内容、中继器和集线器相关细节和划线点 第三章 组帧的基本方法，四类几乎全都是背诵类内容；违规编码与曼彻斯特编码关系 海明码以及该节的部分结论性内容 CSMA/CA，相应的流程、隐蔽站问题内容，全文背诵 PPP协议 链路层帧汇总：HDLC帧(P55)、以太网帧(P103)、802.11帧(P106)、802.1Q帧(P108） PPP帧(P116)，需要背诵 以太网介质访问控制方式、以太网拓扑、低速以太网内容、高速以太网内容 第四章 虚电路、数据报方式的特征和内容 IPV6、IPV4 第五章 端口号、应用协议与端口号的对应，各种协议分别基于什么层、使用什么协议 UDP帧、TCP帧，帧各种字段的内容和相关容易混淆的地方 第六章 SMTP，工作方式和流程，重点在于背诵相关内容 HTTP报文结构 待整理内容：帧、协议 需 ...

文件系统 1. 文件创建（Create） 文件创建是指在文件系统中生成一个新的文件。 操作步骤: 指定文件名: 用户或应用程序需要指定新文件的名称和路径。 分配目录项: 文件系统会在目标目录下分配一个新的目录项，用于存储文件的元数据。 分配磁盘空间: 文件系统分配一定数量的磁盘块给该文件，通常至少包含一个用于存储文件的内容。 初始化文件描述符: 创建一个文件描述符，供后续文件操作使用。 系统调用: creat()：创建一个新文件，通常同时打开该文件。 open()：可以用于创建文件，当文件不存在时，如果指定了O_CREAT标志，文件将被创建。 2. 文件删除（Delete） 文件删除是指从文件系统中移除一个文件，使其无法再被访问。 操作步骤: 找到文件路径: 系统需要确定要删除的文件的完整路径。 释放目录项: 文件系统从目录结构中移除该文件的目录项。 释放磁盘空间: 文件系统释放该文件占用的所有磁盘块，使这些块可以被其他文件重用。 关闭文件描述符: 如果文件正被打开，需要关闭其对应的文件描述符。 系统调用: unlink()：用于删除文件。 ...

第一节 I/O设备分类 块设备：磁盘、可寻址、传输速率高、分时共享设备 字符设备：打印机、无寻址概念、传输速率低、独占式共享设备 共享属性的分类都是基于该设备可共享的基础上的阐述，独占或者非独占两类 易混淆概念 共享资源分为两种模式：互斥共享、同时访问 互斥共享的共享资源被称为临界资源，同时访问的共享资源简称为共享资源 被进程占据后不能被其他进程抢占的资源被称为不可剥夺资源 同一时刻只能被一个进程占用的设备被称为独占式共享设备 同一时间段可以被多个进程共享的设备被称为共享设备，简称而已 设备控制器 一个设备控制器可控制多个外设，需要记忆和背诵其组成部分与基本功能 I/O端口：设备控制器中的寄存器，直接被处理器控制，统一编址或独立编址 各自背诵优缺点、特征即可 I/O控制方式 程序查询方式、中断驱动方式均以字为传输单位，其目的均是将数据经处理器传到内存 且正是因为要经过处理器，才会导致大量处理器的时间被浪费，完全不必要 程序查询方式由处理器主动查询设备控制器中的寄存，中断由设备控制器主动中断 设备控制器是不会被替代的，即使在直接存储器存取方式中（DMA） 在 ...

第一节 文件基本概念 文件本身即为计算机中的数据集合，操作系统对数据的管理诞生文件系统 系统运行时，以进程为基本单位分配和调度；I/O，以文件为基本单位分配资源与调用 文件类型 知晓基本概念对应类别即可；普通文件为数据集、目录文件为目录集 I/O，相关设备为特殊文件 文件控制块 用于形容、描述一片有序数据集的标签；内包含信息需要背诵，含文件属性与基本信息 基本结构：文件控制块->数据块 目录与索引 文件控制块即为目录项，连续存放的目录项组合成目录文件；目录文件与数据分区存放 基本查询结构：目录->目录项->数据块 为加速目录查询过程缩减目录项内容，增设索引块，目录项指向索引块，索引块存信息 基本查询结构：目录->目录项->索引节点->数据块 磁盘索引、内存索引：其内容同样需要背诵 磁盘索引内容即为文件基本描述信息与内容，相当于文件控制块描述信息 内存索引存放于内存中的系统打开文件表的表项内，被进程所共享，增设使用信息 文件基本操作 文件基本操作：创、删、读、写、打开、关闭，见补充知识体系，书上不够完整 系统打开文件表、进程打开文件表： 系统首次打开某 ...

第一节 内存管理功能概括 内存空间的分配与回收、地址转换、内存共享、存储保护 进程的链接与装入 绝对装入、静态重定向、动态重定向 静态链接、装入时动态链接、运行时动态链接 绝对装入：逻辑地址等同物理地址、程序中一般采用符号地址代表绝对地址，不考 静态重定位：逻辑地址一整段直接映射到内存物理地址，占用连续内存空间、一次性分配、不可变、不可移动 动态重定位：先装一部分到某不知名区域，等真正需要执行时才进行物理地址转换，需要重定向寄存器、支持离散分配、可变大小、可以浮动、按需分配进入内存 静态链接：装入前一次性链接各个模块、变更各个模块内部地址与符号为逻辑地址 装入时动态链接：边装入边链接各个模块、形成各个模块逻辑地址 运行时动态链接：当真正需要执行时才开始链接形成逻辑地址，有必要才链接，不需要用的不链接 注：想象链接为将一系列模块串成一串链条，并形成逻辑地址，会是精确形象的理解 物理地址与逻辑地址 物理地址大小取决于硬件性能、逻辑地址大小取决于编址空间位数(地址线 进程各模块于链接阶段形成逻辑地址、操作系统于装入阶段将逻辑地址变为物理地址 逻辑地址转为物理地址的过程也被称为地址重定位 进程 ...

第一节 进程的概念 进程实现操作系统的并发、共享，进程映像包含进程控制块、代码段、数据段组成 将进程理解为一件手头上未完成的事会是最精准的 动态性：不连续、间断 异步性：也称失去封闭性 进程的组成 参考，P179，进程映像于内存中的存储形式，PCB、页表等常驻内存，其余按需调入 进程控制块内容需要背诵；操作系统中谈到的程序均为代码段含义 进程状态与转换 运行、就绪、阻塞、创建、终止 一般性转换案例：请求资源中断、资源获取、时间片剥夺、时间片轮到、异常终止 其余态转变依据具体情况判断，不一一列出，书有补充 进程控制 高频考点，重点在于创建、终止、阻塞、唤醒四大原语的具体执行步骤、细节 创建：PCB数量决定创建成功与否；资源分配决定创建态或就绪态；容量决定插入与否 终止：终止条件需要背诵；终止态立即释放进程资源；线程终止不立刻释放资源 阻塞：请求操作系统服务需要陷入；用户态陷入内核态 唤醒：由中断处理程序唤醒，同样处于内核态；返回用户态 上述原语均可被用户采用系统调用间接使用 进程通信 共享存储区、消息传递、管道通信 共享存储区：分为队列共享、内存共享区域共享；速度快；系统调用 消息传递： ...

第一节 操作系统的特性 并发、共享、虚拟、异步 并发：区别于并行；单处理器必然并发；多处理器支持并行； 共享：互斥共享、同时共享 虚拟：时分复用、空分复用、设备虚拟化 异步：并发性导致异步性 操作系统的目标与功能 计算机资源管理、响应用户请求并分发为硬件执行 用户请求服务接口：命令接口（联机、脱机）、程序接口（系统调用） 随记 用户程序中调用的服务：库函数，绝大多数运行在用户态，部分涉及系统调用 用户只能通过用户程序间接使用系统调用，但系统调用并非请求服务的唯一方式 对于敏感操作，用户无法执行，只能请求操作系统服务 第二节 单道批、多道批； 单：内存仅一道程序；异常或完成时替换；处理器外设串行工作 多：内存多道作业；阻塞即被替换，处理器外设并行工作；作业调度；无交互性； 分时：多道批；时间片剥夺(时间片到期、异常、阻塞、完成)；时分复用；强交互性； 实时：硬实时；软实时；及时性更强；分时基础； 网络、分布式、个人：目前流行 逻辑： 人机速度矛盾诞生单道批；机器外设矛盾诞生多道批；人机交互矛盾诞生分时、实时 顺应时代发展诞生实时、网络、分布式、个人 随记 单道批适用于批处理作业；多道批 ...

第一节：I/O系统概述(简要补充 常见外设均为I/O设备，外存也归属为I/O设备，I/O接口即为常见插口的全电路芯片 通道属于一类硬件，其通道程序存储在内存中，可以根据程序实现I/O操作 类似于DMA方式，不过统考中该内容出现频率极低，考察预计也是以DMA方式为主 I/O指令一般均为特权指令，在核心态下才能被使用 第二节：I/O接口 I/O系统结构 状态/控制寄存器之所以能够被统一使用，是因为其使用时间完全错开 且控制命令、状态反馈结束后该数据就不再有用，因而后续可以直接覆盖不保存 I/O接口具体与CPU的连接模式建议结合总线结构进行复习，一般分为三类 I/O接口数据线上传输的内容包含了一部分控制信号的内容，例如命令即在数据线传输 与主存数据总线的功能基本一致，需要刻意留意这样一个考点，被多次考察到 字、数据、信息结尾的内容放在数据线传输，信号结尾的内容访问控制线上传输 相对来说只需要背诵控制总线传输的内容即可，因为传输内容单一，其余均是数据线 例如指令字，其就是在数据线上传 ...

第五章： 第一节复习要点： 寄存器 重点记忆透明、不透明的寄存器，配合文档内容一起背其归属方 第二节复习要点： 指令周期 指令周期，包含多个机器周期，指令周期可以不等长，机器周期可以不等数 甚至机器周期也可以不等长时间，一般机器周期为访存周期，因为几乎每步均涉及访存 中断在一条指令执行完成后进行检测，因而中断不会影响指令的执行 通用指令周期 取址周期是公共周期，其能够被控制器自动执行而不需要单独的命令操作 不论取址、间址、中断周期，均需要进行一次访存，中断周期的访存目的是压栈保护 间址周期一般谈主存间址，其运行结果是MDR中存放有效地址 中断周期没有被考察过，但也同样属于公共操作，或许需要留意 不同周期处理器 单周期处理器一般会因为需要迎合最慢的指令，总体主频较低（一条一个时钟 SISD，均属于虚假意义上的并行，没有实现真正意义的并行 真正意义上的并行是多核处理器才能实现的，并行处理器的吞吐量远胜过串行指令的 因为流水线最大只能实现一个时钟周期一条指令，并行一个周期K条指令 一般采用五段式流水线，特殊考察则可能会删减流水线为四段左右，特殊考察 第三节：数据通路 数据通路 数据通路包 ...

第一节：指令系统 指令集 一台计算机只能运行自己的指令集，因为指令集和硬件有关 ISA是软件所能见的部分，软件可以调用计算机内的指令，例如操作系统实现一些功能 指令格式 指令字长而言，其可定长的，也可不定长，定长与否只影响执行操作复杂度 如果不定长指令，一般都采取填充的方式，否则可能导致存取一条指令需多次访存 流水线需要保证每条指令的取指令时长均一致，定长指令更适合于流水线作业 指令种类中需要注意的就是各个指令的访存次数，需要看清，及目的和源操作数的位置 零地址指令可以用于数据结构的后缀表达式、前缀表达式的求和以及计算 四地址指令的A4字段是直接给出的地址，不需要单独访存 操作码及其拓展 做题的时候一般需要区分清楚是定长操作码还是非定长操作码 定长操作码和非定长操作码均是对“操作码”这个概念阐述的，和指令定长与否无关 拓展操作码设计方式从高位开始设计，而不是从低位向上设计，这点需要注意 同时必须保留拓展位，因为不能产生后者码和前者码前缀相同的情况 如果一定要拓展那么就是和哈夫曼树联系，变长编码，根据访问的频率划分哈夫曼编码 指令类型 重点强调转换指令，JMP/CALL ...

第一节：存储器概述 存储器分类 补充，以书上为主，因为已经极度详细 存储器分类，可以按照多种方式分类，具体应以书上为准，此处作为补充说明 主存也称内存，凡是运行期间的程序、变量均需要先调入主存，是整个计算机系统重点 辅存可以分多种，一般有：光盘、磁盘、硬盘、U盘、磁带等类型 Cache是SRAM，主存是DRAM，DRAM往往因为引脚数量多需要复用引脚，而SRAM并不需要 RAM/ROM均是半导体存储器，这在后面主存一节第一句话就是如此，所以需要区分 两者之间最大的差别在于是否断电易失性，其他基本一致，均是随机存取 存储器性能指标 存取时间一般比较短、存取周期一般比较长，这里后面会和多体交叉存储器一起概述 主要在于多体交叉存储器的数量其实是既有上限又有下限的，而书上仅给出了下限而已 关于时间单位换算： 多层次存储系统 存储系统的容量主要看的是外存和ROM当中的内容，即非主存、Cache中的内容 因为主存、Cache中保存的均只是外存中的副本而已，主存和Cache间的调度是硬件完成 而主存和辅存间的数据调度主要由硬件和操作系统一起完成（虚存、虚页 这一句话被个人所忽略了两次，需 ...

第一节：数制与编码 补充内容： 机器数内，补码表示整数、移码表示阶码、原码表示浮点数尾数部分 需要进行位拓展的原因： ALU的位数是固定的，运算前可能需要把短数据扩展为长数据 通用寄存器位数是固定的，把数据存入寄存器时，可能需要进行长度扩展 主存内的各种数据长度不一，有时需要把短数据扩展为长数据 进位计数法： 只需要记忆二进制、八进制、十六进制分别的前缀和后缀即可，容易遗忘和混淆 进制数转换： 二进制转为八进制、十六进制小数点左边高位补零，右边低位补零，解释均右向左翻译 例如0110.01010解释为八进制，06.24，解释为十六进制，6.50 十六进制、八进制的互相转换经由二进制完成互相转换 十进制转为十六进制、八进制首先转为二进制再考虑转为高位进制 十进制整数转为二进制直接考虑凑整法，速度远高于书上给定的计算方法 对于小数部分若位数少于五位内可以直接凑整，高于五位建议用乘基取余法得结果 高位进制（十进制）能覆盖所有低进制表达范围，低进制不一定能表达高进制 四大码以及相应计算： 高位、低位补零的数量具体以字长为定，低位、高位均是以零拓展不以其他拓展 提纲：（写一遍下列的转换过程是最迅 ...