数据结构:

对称矩阵压缩存储与一维数组映射(第 1 题):

对称矩阵与特殊矩阵压缩存储全解秒杀模型

  • 核心秒杀铁律:==“翻坐标 切主向 两段数人头 对齐 C 下标”==
  • 考点复盘:存上三角按列优先求 。先对称归位为 (第 7 列);前 1~6 列完整填满共 个;第 7 列内部目标前有 共 1 个;前置总元素数 。C 语言数组从 0 开始,故下标正是 22(选 C)。

直接插入排序 vs 简单选择排序效率辨析(第 11 题):

排序算法总结

  • 核心秒杀铁律:“插排懂摸鱼(比一次遇小即停),选排死脑筋(全扫完才敢定夺);空间都是 O(1),移动插排并不省!”
  • 考点复盘:数组大部分已有序时,直接插入排序比较次数锐减为 ,而简单选择排序仍顽固维持 比较,故比较次数大幅减少(I 正确);两者均为原地排序,空间均为 (II 错误);直接插入腾空需后移,移动次数不比简单选择更少(III 错误)。故选 A(仅 I)。

树形结构与多路查找树辨析(第 3、5、9、10 题):

二叉树、二叉排序树、完全二叉树与堆全解秒杀模型 B树删除与调整规则全题型秒杀笔记

  • 核心秒杀铁律:==“堆管上下不管左右,BST 管左中右不管高矮;任意树顺序存看最大标号 ,完全树与堆存无缝紧凑选数组!”==
  • 考点复盘:
    • 第 3 题(顺序存储最大下标):高为 5 的二叉树要存“任意一棵”,必须防最坏情况右单支溢出,数组容量至少按满树 开辟(选 A)。
    • 第 5 题(BST 构造序列):首元素为根,左小右大,4, 5, 1, 2, 3 中 1 会直接抢占根 4 的左孩子,导致形态不符(选 B)。
    • 第 9 题(堆的本质):堆逻辑上是完全二叉树(I 正确),天然适合顺序存储(II 正确),堆只管垂直父子不管水平兄弟绝非 BST(III 错误),次大值必在第 2 层(IV 正确),故选 C(仅 I、II、IV)。
    • 第 10 题(4 阶 B 树动态构建与分裂):关键字满 4 个立即触发上溢分裂,提第 3 个偏右中位数上移。插入 13 提 9 成立新根,插入 2 提 6 上升并入根,最终根为 [6, 9],故选 B。

计算机组成原理:

TLB 与 Cache 特性对比及物理介质辨析(第 15 题):

  • 核心秒杀铁律:“TLB 与 Cache 都是高速小金库,SRAM 造身骨;主存靠 DRAM 电容充,缺失全往主存冲!”
  • 考点复盘:
    • 物理构成(致命考点):TLB(Translation Lookaside Buffer,页表快表)和 Cache(高速缓冲存储器)都是为了弥补主存与 CPU 之间的速度鸿沟而设置的高速暂存部件,均由双稳态触发器构成的 SRAM(静态随机存储器)(或 CAM 相联存储器)制成,速度极快但集成度低、造价高昂;而主存通常采用微小电容构成的 DRAM(动态随机存储器),需要定期动态刷新。因此两者绝非由 DRAM 组成(D 选项叙述错误,符合题意,选 D)。
    • 干扰项深度辨析:
      • A(局部性):两者都建立在程序的局部性原理(时间局部性 + 空间局部性)基础之上,局部性好则命中率高。
      • B(缺失处理对象):TLB 缺失意味着快表中没有该虚拟页对应的页表项,必须去访问主存中的慢表(页表);Cache 缺失意味着目标字/数据不在 Cache 中,必须去访问主存获取目标数据块。两者缺失后都必须访问主存。
      • C(硬件实现能力):Cache 缺失处理全程由纯硬件 Cache 控制器自动完成;TLB 缺失在现代主流架构(如 x86 等)中通常由硬件 MMU 内部的硬件页表遍历器(Page Table Walker)自动处理,在某些 RISC(如 MIPS、Alpha)架构中亦可由硬件产生 Trap 陷入内核由软件中断服务程序处理。因此两者缺失都可以由硬件实现。

16 位定长指令字结构与寻址范围计算(第 16 题):

  • 核心秒杀铁律:“定长指令切三段:先扣操作再扣寻,剩下全当地址码;直接寻址对主存,非负范围零到顶!”
  • 考点复盘:
    • 第一步:切分定长指令各字段位宽。单地址指令格式严格由三部分构成:[ 操作码 OP | 寻址方式 Mode | 形式地址码 A ]。
      1. 操作码 OP 位数:指令系统共有 48 条指令,位数固定,则必须满足 ,解得 (最大可容纳 条指令)。
      2. 寻址方式 Mode 位数:支持直接、间接、立即、相对共 4 种寻址方式,位数固定,需满足 ,解得 。
      3. 地址码 A 位数:形式地址码剩余位宽为 。
    • 第二步:直接寻址有效地址范围推导。直接寻址方式下,指令中的形式地址码 就是主存的物理/有效地址 (即 )。由于主存存储单元的物理地址本质为非负无符号整数(地址从 0 开始自增),因此 8 位地址码的可寻址空间为 ,故选 A。
    • 避坑提醒:选项 C、D 的带有符号数区间( 等)是针对**相对寻址(PC 偏移量采用补码)**的陷阱!直接寻址绝不使用补码,范围必定为无符号范围 。

QPI 点对点全双工总线带宽计算(第 19 题):

  • 核心秒杀铁律:“时钟翻倍看边沿,扣除校验留净荷;全双工乘二两头跑,十进制千兆秒出 G!”
  • 考点复盘:
    • 题干官方公式套用:题干已直接给出带宽计算公式:。
    • 公式各因子底层逻辑推导:
      1. 每秒传送次数:QPI 时钟频率为 (即每秒 个时钟周期)。每个周期传递 2 次(利用时钟上升沿和下降沿各传输一次,类似于 DDR 技术),因此每秒传送次数 。
      2. 每次传送有效字节数:每个方向传输 20 位信息,其中有效数据占 16 位,校验位占 4 位。计算机总线带宽只计算有效数据净荷,因此单次有效数据为 。
      3. 全双工系数:QPI 是全双工总线,收、发两个方向可以同时传输,聚合总带宽需乘 2。
    • 代入计算: 故选 C。
    • 易错点:总线带宽与传输速率的量纲词头 严格采用十进制 ,绝不是存储容量的二进制 。

不可屏蔽中断(NMI)与可屏蔽中断响应机制(第 21 题):

  • 核心秒杀铁律:“NMI 关中断也能冲,INTR 等指令末才采样;响应优先硬件定,屏蔽字改服务序!”
  • 考点复盘:
    • 核心辨析点(B 选项为什么错误):可屏蔽中断(INTR)请求信号有效时,CPU 绝不可能“立即响应”!其响应必须严格满足两大前置条件:
      1. CPU 内部中断允许标志位必须处于开中断状态();
      2. CPU 必须执行完当前指令,在**指令周期的最后一个时钟周期(中断采样周期)**统一检测中断引脚,判定通过后才响应。因此 B 项断言“一旦有效立即响应”严重违背 CPU 指令周期控制规律,选 B。
    • 正确项知识点巩固:
      • A 正确(NMI 特权):不可屏蔽中断(Non-Maskable Interrupt)用于严重紧急事件(如电源掉电、主存奇偶校验严重错误等),不受中断标志位 约束,即使 CPU 处于关中断状态()也必须予以响应。
      • C 正确(优先级压制):硬件体系设计中,不可屏蔽中断的优先级天然高于一切普通外设的可屏蔽中断。
      • D 正确(屏蔽字的作用):中断屏蔽字用于多重中断(中断嵌套)中,通过软件修改屏蔽字可以动态改变各个中断源的**“处理优先级(服务顺序)”;而硬件排队判优器固定的只是“响应优先级”**。

操作系统:

多进程共享文件的系统打开表与用户打开表机制(第 23 题):

  • 核心秒杀铁律:“系统表全局仅一份(看管 Inode 与总计数),用户表各持一本帐(记录各自读写游标与权限)!”
  • 考点复盘:
    • 系统打开文件表 vs 用户(进程)打开文件表核心机制:
      • 系统打开文件表(System-wide Open-File Table):整个操作系统全局只有一张。只要文件 被打开,系统打开文件表中仅对应一个表项,集中记录外存 Inode 副本、文件物理块位置、全局引用计数(打开计数器 count)等。故 B 选项正确,选 B。
      • 用户打开文件表(Per-process Open-File Table):每个进程各自独立持有一份。记录当前进程对文件 的私有操作状态,包括本进程私有的文件读写读头位置(当前偏移量 offset)、本进程的访问权限(只读/只写)等。因此不同进程的用户打开文件表项内容绝不相同(C 错误)。
    • 干扰项排除:
      • A 错误:文件共享允许多个进程以“读”或“写”甚至“读写”方式打开,由并发控制机制(如文件读写锁)维护一致性。
      • D 错误:单个进程调用 close(F) 时,系统只是将系统打开文件表项中的引用计数减 1(count--);只有当 count == 0(即所有共享进程全部关闭了该文件)时,系统才会真正注销并释放系统打开文件表中的表项。

文件物理分配方式辨析(动态增长与随机访问)(第 24 题):

  • 核心秒杀铁律:“连续快但定长呆,隐式链长难跳块;索引既能随心跳,又能随时加新块!”
  • 考点复盘:
    • 三大磁盘分配方式全景对比表:
      分配方式文件长度是否易变/动态扩展是否支持随机/直接访问典型优缺点
      连续分配否(需预留连续空间,扩展易冲突,有外碎片)是(通过起始块号加逻辑块号直接定位)顺序/随机读写速度最快,但灵活性极差
      隐式链接分配是(动态申请离散盘块,指针相连,无外碎片)否(只能顺序遍历链表,访第 块需读盘 次)空间利用率高,但严禁随机访问
      索引分配是(动态申请离散盘块并挂入索引表,无外碎片)是(通过索引表数组下标可直接寻址任意逻辑块)兼具随机访问与动态长度扩展能力,但需额外索引块开销
    • 题目要求“既支持文件长度可变、又支持随机访问”,唯一符合条件的正是索引分配,故选 A。(注:动态分区分配属于内存管理技术,绝非磁盘存储分配方式)。

中断处理中硬件中断隐指令与 OS 内核软件职责划分(第 25 题):

  • 核心秒杀铁律:“断点必由硬件扣(隐指令保 PC 与 PSW),服务全归内核跑(查表、排队、改屏蔽字)!”
  • 考点复盘:
    • 分水岭法则:中断隐指令(纯硬件完成)
      • 中断响应瞬间,CPU 硬件线路自动执行一组隐式操作(绝非通过软件指令执行):
        1. 关中断(将 PSW 的中断允许位 IF 置 0);
        2. 保存断点(将当前的程序计数器 PC 和程序状态字 PSW 压栈保存);
        3. 引出中断服务程序(根据中断向量获取入口地址送入 PC)。
      • 因此 I(保存被中断程序的中断点)完全由硬件中断隐指令完成,绝非操作系统软件完成!凡含 I 的选项(A、B)直接排除!
    • 操作系统内核软件完成的操作:
      • II(提供中断服务):中断服务程序(ISR)本身就是操作系统内核预编写的特权软件代码。
      • III(初始化中断向量表):系统在开机引导阶段,由操作系统内核将各个中断处理程序的首地址填写到中断向量表中。
      • IV(保存中断屏蔽字):在实现多重中断嵌套时,由操作系统中断服务程序的入口汇编代码保存旧的中断屏蔽字,并加载当前优先级屏蔽字。
    • 综上,由操作系统完成的是 II、III、IV,故选 D。

父进程与子进程的资源独立性与并发特性(第 29 题):

  • 核心秒杀铁律:“父子同源各独立,PCB 独有一套,虚拟空间各管各,谁占临界谁独霸!”
  • 考点复盘:
    • B 选项错误剖析(选 B):在现代操作系统(如 UNIX/Linux)中,父进程通过 fork() 创建子进程时,虽然可以采用写时复制(COW,Copy-On-Write)技术优化性能,但在逻辑机制上,父进程与子进程拥有完全独立的虚拟地址空间!子进程修改自己的变量绝不会影响父进程的变量空间。若两者共享虚拟地址空间,则在定义上就退化为了同一个进程内的“线程”而不是独立进程。
    • 正确项巩固:
      • A 正确:父子进程是独立的调度实体,在多道程序环境或多核 CPU 下可以并发甚至并行执行。
      • C 正确:操作系统为子进程分配独立的 PID,并创建独立的新进程控制块(PCB)。
      • D 正确:临界资源根据互斥访问铁律,在同一时刻严格只允许一个执行主体访问,即使是父子进程也必须遵循信号量或互斥锁机制,严禁同时进入临界区。

设备独立性(无关性)与逻辑设备映射(第 30 题):

  • 核心秒杀铁律:“设备无关认逻辑,底层改版换驱动;上层应用纹丝动,映射全靠 LUT 表!”
  • 考点复盘:
    • 设备独立性(Device Independence,设备无关性)的终极价值:用户编程时无需关注具体的物理设备型号与接口协议,统一使用逻辑设备名进行 I/O 请求。系统内部通过**逻辑设备表(LUT,Logical Unit Table)**将逻辑设备名动态映射为具体的物理设备名。
    • D 选项错误剖析(选 D):当系统更换或升级物理设备(如将激光打印机更换为喷墨打印机)时,只需由系统管理员重新安装或配置该硬件对应的设备驱动程序,并在系统内部更新 LUT 映射关系即可,绝对不需要修改任何调用该设备的应用程序源码!D 选项断言“必须修改应用程序”,直接违背了设备独立性存在的根本目的。
    • A 正确:在类 UNIX 体系中,“一切皆文件”,设备可直接挂载为 /dev/ 下的特殊设备文件,程序可像读写普通文件一样通过文件名访问设备。

Inode 文件系统全局文件数上限计算(第 31 题):

  • 核心秒杀铁律:“文件上限看 Inode,不看名字写多长;四字节即三十二位,二的 32 次方定乾坤!”
  • 考点复盘:
    • 破题关键:谁决定文件数量的上限?
      • 文件系统中的每个文件都由一个且仅由一个**索引结点(Inode)**全局唯一标识。
      • 题目明确给出:目录项中用于存放索引结点号的空间为 4 字节。
      • 。
      • 32 位的索引结点号可以编址的最大不同 Inode 数量为 个。因此该文件系统能创建的文件数量绝对上限正是 ,故选 B。
    • 命题人陷阱排除:
      • 题干给出的“60 字节存放文件名”、“由小写英文字母构成”,纯粹是用于诱导考生去计算 或 的干扰项!
      • 文件名只是存放在目录项中的外在字符串,不同目录下完全可以有同名的文件指向不同的 Inode,或者不同目录项指向同一个 Inode(硬链接)。文件名空间的大小绝不代表系统能容纳的文件总量。

临界区互斥四大准则的硬性约束辨析(第 32 题):

  • 核心秒杀铁律:“空闲让进、忙则等待、有限等待是底线;让权等待是美德,违反也能成互斥(自旋锁不让权)!”
  • 考点复盘:
    • 临界区互斥必须遵循的四大准则内涵:
      1. 忙则等待(准则 I):已有进程进入临界区时,其他试图进入的进程必须等待(必须遵循,互斥核心)。
      2. 空闲让进(准则 II):临界区资源处于空闲状态时,允许一个请求进程立即进入(必须遵循,防死锁)。
      3. 有限等待(准则 III):保证进程在有限时间内能进入临界区(必须遵循,防饥饿)。
      4. 让权等待(准则 IV):进程不能进入临界区时,应立即放弃 CPU 避免忙等(非必须遵循!)。
    • 为什么“让权等待”不是必须遵循的?
      • 经典的硬件互斥实现(如 TSL 指令、Swap 指令)以及纯软件互斥算法(Peterson 算法),在进程无法进入临界区时均采用 while 循环不断测试标志(即“忙等待 / 自旋锁 Spinlock”),它们并未放弃 CPU,直接违反了让权等待准则!
      • 但它们在单核或多核系统里仍然是完全正确、合法、广泛使用的临界区互斥实现方案!
      • 因此,实现临界区互斥机制必须遵循(强制保证)的准则只有 I、II、III,故选 C。

计算机网络:

停-等协议最大信道利用率计算(第 36 题):

  • 核心秒杀铁律:“停等周期四部曲:发数据 + 跑过去 + 发确认 + 跑回来;确认带长别漏算,数据发时除总长!”
  • 考点复盘:
    • 停-等协议完整交互时序拆解:
      1. 数据帧发送时延 :
      2. 往返传播时延 :单向传播延时 ,往返传播时延 。
      3. 确认帧发送时延 (审题巨坑):题干明确指出“确认帧长也为 1000B”,绝非可忽略的小包!
      4. 总发送周期:。
    • 信道利用率计算: 故选 D。

IEEE 802.11 CSMA/CA 帧间间隔(IFS)长度与优先级(第 37 题):

  • 核心秒杀铁律:“无线 IFS 越短级越高,SIFS 最短保连贯;初探信道等 DIFS,最长必是开路先锋!”
  • 考点复盘:
    • IEEE 802.11 帧间间隔长度铁律:
    • 时序与对应间隔盘点:
      • IFS1:主机 H 首次想要发送 RTS 预约信道,若侦听到信道空闲,必须至少等待一个分布式协调帧间间隔 DIFS 才能启动退避计时器或发送数据,故 IFS1 = DIFS。
      • IFS2、IFS3、IFS4:AP 回复 CTS 帧(IFS2)、主机 H 收到 CTS 后立即发送 DATA 数据帧(IFS3)、AP 收到数据后立即回复 ACK 帧(IFS4)。这三次交互属于正在占有信道的高优先级原子会话,为防止其他竞争站点插队,必须使用最短的短帧间间隔 SIFS,故 IFS2 = IFS3 = IFS4 = SIFS。
    • 结论:四个间隔中唯有 IFS1 为 DIFS,其余皆为 SIFS,因此最长的是 IFS1,故选 A。

TCP 拥塞控制窗口增长最长时间分析(第 38 题):

  • 核心秒杀铁律:“最长耗时按加法(拥塞避免每轮加 1),最短耗时按乘法(慢开始每轮翻倍);差值除步长乘 RTT,秒出最长时间!”
  • 考点复盘:
    • 破题逻辑:怎样才能使得耗时“最长”?
      • TCP 拥塞窗口增长有两条路径:
        1. 慢开始(指数增长):每个 RTT 翻倍,增长最快,耗时最短。
        2. 拥塞避免(线性加法增大):每个 RTT 仅增加 ,增长最慢,耗时最长。
      • 题目问的是**“所需的最长时间”,意味着在 的全程都处于拥塞避免阶段**(门限值 )。
    • 步进计算:
      • 每次增加量:每个往返时间 内增加 。
      • 总增量需求:。
      • 所需 RTT 轮数:。
      • 所需最长时间:,故选 D。
    • 发散对比(命题人变式):若题目问“所需的最短时间”,则全程处于慢开始阶段:,仅需 2 个 RTT (对应选项 A)。

DNS 迭代解析与 HTTP 页面获取总时延计算(第 40 题):

  • 核心秒杀铁律:==“HTTP 无论如何吞 2 个 RTT(握手一轮 + 页面一轮);DNS 命中耗 0 轮,三级迭代吞 3 轮(根 顶级 权限)!”==
  • 考点复盘:
    • 固定开销:HTTP 访问阶段(不可省略)
      • 主机获取到 IP 后访问 Web 服务器获取页面:
        1. 建立 TCP 连接:前两次握手耗时 (第三次握手携带 HTTP 请求数据);
        2. HTTP 请求与传输纯文本页面:耗时 。
      • 因此 HTTP 获取页面固定消耗 。
    • 可变开销:DNS 域名解析阶段
      • 最短时间(最好情况):本地域名服务器或本机缓存中已经命中了 www.abc.com 的 IP 地址,完全无需向 Internet 外发查询,DNS 解析时延为 。
      • 最长时间(最坏情况):DNS 缓存全部未命中,本地域名服务器必须向外进行迭代查询:
        1. 查询根域名服务器(耗时 ,返回 .com 顶级域名服务器地址);
        2. 查询 .com 顶级域名服务器(耗时 ,返回 abc.com 权限域名服务器地址);
        3. 查询 abc.com 权限域名服务器(耗时 ,返回主机 www.abc.com 的 IP 地址)。
        • DNS 迭代查询耗时共 。
    • 综上,最短与最长时间分别为 20ms,50ms,故选 D。

2020 年真题核心知识点专项精讲卡片索引