408 大纲重要考点——填空题整理
一、数据结构
（一）并查集与红黑树
填空题
- 并查集典型应用包括：判断图的 ________、判断图是否 ________、实现 ________ 算法以及判断无向图是否 ________。
- 在使用并查集判断“是否为一棵树”时，需要同时满足 ________ 条边、且图是 ________ 的条件。
- 红黑树是一种自平衡的 ________ 树，通过在结点上增加 ________ 属性来维持平衡。
- 红黑树要求从根到每个叶结点（空结点）的任意一条路径上， ________ 结点的数量必须相同。
- 当红黑树中所有结点都为 ________ 时，这棵树一定是一棵 ________ 二叉树。
参考答案
- 连通性；有环；Kruskal（最小生成树）；一棵树
- n−1；连通
- 二叉搜索；颜色（红/黑）
- 黑
- 黑；满
二、计算机组成原理（计组）
（一）补码加减与标志位、乘除法电路
填空题
- 在计算机中，加减运算统一使用 ________ 加法器来完成，有符号数和无符号数都可以在同一个硬件上实现。
- 带符号整数通常采用 ________ 表示，这样加减运算都可以统一为模 $2^n$ 的 ________ 运算。
- 常见的四个标志位分别是：零标志 ________，进位标志 ________，符号标志 ________，溢出标志 ________。
- 在补码运算中，条件跳转指令会根据标志位的组合来判断有符号数的大小关系，其中“有符号 A>B”通常要求 ________=OF 且 ________=0。
- 在 CPU 中，为了支持乘法和除法，通常在加法器基础上配合专门的 ________ 电路和 ________ 电路，通过重复加/减与移位实现运算。
参考答案
- n 位（二进制）
- 补码；无符号加法
- ZF；CF；SF；OF
- SF；ZF
- 乘法；除法
（二）固态硬盘 SSD 与磨损均衡
填空题
- 固态硬盘（SSD）基于 ________ 技术，是一种电可擦除 ROM，属于 ________ 存储器。
- SSD 中负责逻辑块地址到物理页的映射的关键软件/硬件层叫做 ________（缩写为 ________）。
- SSD 的存储介质由多个闪存芯片组成，每个芯片包含多个 ________，每个块又包含多个 ________。
- SSD 的读写以 ________ 为单位，而擦除以 ________ 为单位，因此常被形象概括为“写页擦块”。
- SSD 读写访问采用 ________ 访问方式，因此没有机械寻道时间和旋转延迟，相比 HDD 具有更快的访问速度。
- SSD 的性能特点可以概括为“读 ________、写 ________”，因为写入新数据前往往需要先 ________ 整个块，甚至出现“写放大”现象。
- SSD 相比机械硬盘 HDD，一般是 ________（速度快/慢）、功耗 ________（高/低）、抗震能力 ________（强/弱），但价格 ________（更贵/更便宜）。
- SSD 的擦除寿命有限，每个块大约只能被擦除 ________ 次数量级，而机械硬盘的扇区则几乎没有写入寿命问题。
- 为了延长寿命，SSD 采用“磨损均衡”技术，其中动态磨损均衡的策略是优先写入擦除次数 ________ 的块，而静态磨损均衡会定期迁移 ________ 数据，以释放老旧块。
参考答案
- 闪存（Flash Memory）；EEPROM
- 闪存翻译层；FTL
- 块（Block）；页（Page）
- 页；块
- 随机
- 快；慢；擦除
- 更快；低；强；更贵
- $10^3 \sim 10^5$
- 较少；冷
（三）高级语言与多处理器/SMP
填空题
- 高级语言源程序必须经过编译/汇编和 ________ 等步骤，最终转化为 ________ 代码才能在机器上执行。
- 在高级语言与机器指令的对应关系中，一条高级语言语句通常会对应多条 ________ 指令序列。
- 对称多处理机（SMP）结构中，多个 CPU 平等地共享同一个 ________ 和 ________，每个处理器的工作能力基本相同。
- 在 SMP 中，负载具有可 ________ 性：当某个 CPU 过于繁忙时，其他 CPU 可以分担任务，从而提升整体 ________。
- 非对称多处理机采用主从结构，其中 ________ 处理器负责核心调度、内核访问和任务分配，而 ________ 处理器仅执行特定任务或用户进程。
- 在典型的主从式结构中，只有 ________ 处理器可以访问内核区，这种设计有利于提升系统的 ________ 性与控制的集中化。
参考答案
- 链接（链接装载）；机器
- 机器
- 内存；其他系统资源（如总线、I/O 设备）
- 迁移；效率 / 吞吐量
- 主；从
- 主；安全
（四）多处理机调度、就绪队列与负载均衡
填空题
- 在对称多处理机中，“公共就绪队列”方式是指所有处理机共享一个 ________ 就绪队列来获取可运行进程。
- 使用公共就绪队列的优点是任务分配 ________，天生支持 ________ 均衡；缺点是在高并发下队列需要加锁同步，容易产生严重的 ________ 。
- “私有就绪队列”方式中，每个处理机拥有独立的 ________ 就绪队列，从而减少了对共享队列的争用。
- “处理机亲和性”指的是将进程/线程尽量固定在 ________ CPU 上运行，以提高 ________ 命中率并减少上下文切换。
- 按强度划分，软亲和表示操作系统“尽量但不 ________”保持进程在同一 CPU 上运行；硬亲和则通过系统调用（如 ________）强制绑定。
- 负载均衡的目标是将任务尽量 ________ 分配到各处理器，使各处理器的 ________ 大致相等。
- “推迁移（Push）”是 ________ 策略，由系统周期性检查各 CPU 负载，从忙碌 CPU 的队列中 ________ 进程到空闲 CPU。
- “工作窃取（拉迁移 Pull）”是当前主流方式，它属于 ________ 策略，由 ________ CPU 主动从负载较重的 CPU 队列中“窃取”任务。
参考答案
- 全局
- 灵活；负载；争用 / 冲突
- 私有 / 本地
- 同一 / 固定；Cache
- 强制；
sched_setaffinity - 均匀；负载（工作量）
- 主动；推
- 被动；空闲
三、操作系统
（一）多处理器调度、UMA/NUMA、多核
填空题
- 在 UMA 结构中，每个处理器对所有存储单元的访问时间 ________（一致/不一致），这种结构常用于典型的 ________ 多处理机。
- 在 NUMA 结构中，处理器访问不同存储单元的时间可能 ________，取决于存储单元与处理器之间的 ________ 位置关系。
- 在 NUMA 系统中，访问本地内存通常比访问 ________ 内存更快，因此操作系统会尽量实现“内存 ________ 性”。
- 多核处理器中，为了优化多个核访问同一条内存条的速度，可以使用 ________ RAM，使两个端口可以 ________ 访问。
- 多处理器调度中，调度器需要同时考虑进程的 ________ 亲和性和系统整体 ________ 均衡。
参考答案
- 一致；对称（SMP）
- 不一致；物理拓扑 / 物理
- 远程；局部
- 双端口；并发 / 同时
- 处理机；负载
（二）多级队列调度与同步互斥方式
填空题
- 多级队列调度算法通常将进程按照不同属性（如前台/后台、交互/批处理）分到不同的 ________ 中，每个队列可以采用不同的 ________ 策略。
- 典型的同步与互斥三种方式包括： ________、 ________ 和 ________。
- 使用互斥锁（Lock）时，同一时刻只允许 ________ 线程进入临界区，从而避免 ________ 条件。
- 条件变量（Condition Variable）通常与 ________ 一起使用，用于在线程之间实现条件等待与 ________。
- 信号（Signal）是一种简单的进程间通信方式，主要用于进程之间或进程与操作系统之间的 ________ 通知机制。
参考答案
- 队列；调度
- 锁；条件变量；信号
- 一个；竞态
- 互斥锁 / 锁；唤醒
- 异步
（三）信号的特点与分类
填空题
- 信号具有 ________ 性，可以在进程执行的任何时刻送达，而不依赖进程当前的 ________。
- 信号是一种轻量级通信方式，一般不携带 ________，只通过信号 ________ 表示事件类型。
- 同步信号通常由进程自身的错误操作触发，如除零错误或非法内存访问，与执行流是 ________ 的。
- 异步信号通常由外部事件或其他进程触发，例如键盘输入 ________ 产生 SIGINT，与当前进程的执行流 ________ 。
- 若进程没有注册自定义的信号处理函数，信号由系统按照每种信号预设的 ________ 动作处理，例如 SIGTERM 默认导致进程 ________。
- 使用
sigaction()可以注册用户自定义的 ________ 函数，当信号到达时中断主流程执行该函数。 - 使用
sigprocmask()可以设置信号 ________ 字，从而暂时阻塞某些信号，常用于保护 ________ 区或延迟处理。 - 已被发送但被屏蔽或暂未处理的信号会保留在 ________ 队列中，待解除屏蔽后再被 ________。
参考答案
- 异步；状态
- 具体数据；编号 / 标识符
- 同步
- Ctrl+C；无关 / 不相关 / 独立
- 默认；终止
- 信号处理
- 屏蔽；临界
- 挂起；处理
（四）内存映射文件与文件系统结构
填空题
- 使用内存映射文件时，操作系统在进程的 ________ 地址空间中分配一块连续区域作为映射区域，并将该区域与磁盘上文件内容建立 ________ 关系。
- 进程可以像访问 ________ 一样通过虚拟地址直接访问文件内容，从而避免频繁的 ________ 调用。
- 内存映射文件只在初次访问和发生 ________ 中断时需要系统参与，大量读写主要在 ________ 空间中完成。
- 内存映射技术常用于大文件处理、 ________ 间通信以及 ________ 系统。
- 在磁盘的全局结构中，通常会包含一个特殊的 ________ 块，用于存放系统启动所需的引导程序。
参考答案
- 虚拟；映射
- 内存；系统（syscall）
- 缺页；用户
- 进程；数据库
- 引导（boot）
（五）外核、闲逛进程与虚拟机
填空题
- 外核（Exokernel）结构下，内核主要负责进程调度和 ________ 通信等核心管理功能，而外核负责直接分配 ________ 硬件资源。
- 在外核中，硬件资源不再被过度 ________ 或抽象，而是尽量直接分配给用户进程，从而减少 ________ 开销并提升灵活性。
- 外核的优点包括：应用程序可以自定义资源 ________ 策略，例如自定义文件系统或 ________ 管理器。
- 外核的缺点之一是系统一致性降低，不同进程可能以不同方式访问 ________，增加了系统的 ________ 性和开发难度。
- 闲逛进程是操作系统内核创建的第一个进程（在某些系统中为 PID= ________），是一个永远不会 ________ 的低优先级系统进程。
- 当 CPU 没有其他进程可运行时，就运行闲逛进程，以避免 CPU ________ 或陷入未知状态，从而保证处理机看起来 ________ 不空闲。
- 操作系统还可以通过引导虚拟机的方式，在一台硬件上同时运行多个 ________ 系统实例，为应用提供隔离的运行环境。
参考答案
- 进程；物理
- 虚拟化；映射
- 管理；内存
- 硬件；复杂
- 0；终止
- 空转；永远
- 操作
四、计算机网络
（一）VLAN 与端口类型
填空题
- VLAN 的主要作用是按照逻辑方式对二层网络进行 ________，从而在同一物理网络上划分多个 ________ 域。
- 访问端口（Access Port）通常连接终端设备，一个端口只属于 ________ VLAN，进入该端口的数据帧一般不带 ________ 标签。
- 汇聚/中继端口（Trunk Port）可以同时承载多个 VLAN 的数据帧，帧中会携带 ________ 标签，用以区分不同 VLAN。
- 利用 VLAN 可以提高网络的 ________ 性，隔离不同业务或部门之间的广播，同时提升网络的 ________ 和管理灵活性。
参考答案
- 划分 / 分段；广播
- 一个；VLAN
- VLAN
- 安全；性能
（二）SDN 与三类接口
填空题
- SDN 软件定义网络将“控制平面”和“数据平面”分离，其中控制平面由 ________ 实现，负责决策“数据包如何 ________”。
- 数据平面由交换机/路由器实现，负责实际的数据包 ________。
- SDN 控制器与交换机之间使用 ________ 接口（南向接口）通信，典型协议包括 ________、NETCONF 等。
- 应用与控制器之间通过 ________ 接口（北向接口）交互，控制器向应用提供统一的网络 ________，常使用 RESTful API 或 gRPC。
- 控制器与控制器之间通过 ________ 向接口进行状态同步与协作，常采用 Paxos、 ________ 等一致性协议。
- 在 SDN 中，通过集中式控制可以更方便地实现全局的流量工程、 ________ 策略和网络虚拟化。
参考答案
- SDN 控制器；转发
- 转发
- 南；OpenFlow
- 北；抽象
- 东西；Raft
- 安全 / 访问控制
以上填空题均根据你提供的《错题点》笔记中的知识点整理而成，方便直接保存为
.md文件进行自测与复习。 oai_citation:0‡错题点.md
本网站基于 Halo 进行创作，希望能够使用愉快。
相关链接
在使用过程中，有任何问题都可以通过以上链接找寻答案，或者联系我们。