数据结构:

时间复杂度分析(第 1 题):

时间复杂度全题型分析与级数求和模型


树与遍历(第 3 题):

“二叉树中序遍历相邻,左子树根右子树,中间必隔爹,绝不可能右兄弟!”

  • 中序遍历顺序:左子树 根结点 右子树。
  • 相对位置判定:
    • 若 与 中序相邻且 在 前面:
      1. 可以是 的双亲(左孩子访问完访问根);
      2. 可以是 的右孩子(根访问完,若右孩子没有左子树,紧接着访问右孩子);
      3. 可以是 双亲的双亲( 作为子树最右结点,回溯到更上层祖先);
      4. 绝对不可能: 是 的右兄弟!因为 (左孩子)访问完,必须先访问它们的双亲(根),然后才轮到右兄弟,中间必然隔着双亲!
  • 🚨 避坑动作:审题看到“不可能的是”,拿到笔第一秒在试卷上画双重红圈,选项打叉打勾防手抖。

AOE 网时间余量计算(第 7 题):

“时间余量就是松弛度:最迟开始减最早开始,关键路径余量全为零!”

  • 公式:活动 的时间余量 = 。
    • 最早开始时间 :等于箭线起点事件的最早发生时间 ;
    • 最迟开始时间 :等于箭线终点事件的最迟发生时间 ;
  • 秒杀技巧:
    • 先挑出关键路径(耗时最长的路径),关键路径上的所有活动余量为 0;
    • 非关键路径上哪个分支富余时间最多,哪个活动的松弛度/时间余量就最大。

B 树删除与关键字调整(第 8 题):

==“ 阶 B 树除根外,关键字下限 ;删根找前驱或后继借,借不到就合并!”==

  • 5 阶 B 树除根外每个结点的关键字个数在 个之间。
  • 根结点关键字 260 被删除后,通常由其**左子树的最大值(直接前驱 110)或右子树的最小值(直接后继 280)**顶替;若发生下移合并,根结点的结构随之更新,不可能保留非法的关键字组合。

归并排序基本概念(第 10 题):

“归并归并,把两个及以上有序表‘合二为一’!”

  • 二路归并核心定义:将两个有序表合并为一个新的有序表(选项 A)。
  • 干扰项秒杀:
    • 划分数组元素个数大致相等 分治法的划分阶段;
    • 一部分均小于另一部分 快速排序的 Partition 划分操作。

计组:

补码整数表示范围(第 13 题):

==“ 位补码零不重,负数多一记心中:!”==

  • 32 位有符号整数补码表示范围:。
  • 最高位是符号位,数值位 31 位;最小负数由 1000...00 专门表示。

IEEE 754 浮点数机器码表示(第 14 题):

IEEE 754 浮点数表示于C语言数据类型边界

“一符八阶廿三尾,负一正零偏百廿七,切出四位变十六!”

  • 标准四步走模板(以 为例):
    1. 符号位 :负数取 ;
    2. 绝对值化为二进制: ,实际指数 ;
    3. 移码阶码 (偏置值 127): ;
    4. 拼盘分组变十六进制:
      • [S (1位)] [E (8位)] [M (23位)] 1 | 01111101 | 11000...
      • 4位一组分组:1011 (B) 1110 (E) 1110 (E) 0000 (0) … BEE0 0000H。

分页虚实地址转换与防坑(第 15 题):

“十六进制切偏置,剩余页号莫大意:必先转成十进制,查对行数防阴谋!”

  • 套路推演:
    • 页面大小 4KB = 低 12 位(十六进制低 3 位 840H)为页内偏移;
    • 虚拟地址 0008 2840H 去掉低 3 位,虚页号为十六进制 00082H;
  • 🚨 避坑关键:
    • 页表第 1 列给的是十进制虚页号!(因为没有H)
    • 必须把十六进制 转成十进制:!
    • 查十进制第 130 行:存在位为 1,页框号为 018H,拼出主存物理地址 018 840H(无缺页异常!)。

Cache 组相联与比较器(第 16 题):

==“几路组相联就几个比较器;Tag 标记位 = 主存位数 - 组号位数 - 块内位数!”==

  • 比较器个数:8 路组相联每组 8 行,硬件并行比对 固定 8 个比较器(直接秒杀 C、D);
  • 标记位计算:
    • 主存地址 32 位;
    • 块大小 64B 块内地址 6 位;
    • Cache 总块数 = 块;8 路一组 组 组号 6 位;
    • 位。 由tag,组号,块内地址构成cache 详细链接:虚拟地址、页表、TLB、Cache

DRAM 芯片地址引脚与地址复用(第 17 题):

“DRAM 行列分时送,引脚减半取最大;SRAM 不搞分时送,引脚总和不打折!”

  • DRAM 芯片容量 ,单元数 。
  • DRAM 采用地址复用技术:行地址和列地址通过同一组地址引脚分时送入,芯片地址引脚数只需 根,绝不是 26 根!

指令系统扩展操作码计算(第 19 题):

“留出前缀向下扩:可用状态减已有,乘上空出地址位!”

1. 底层原理:为什么叫“扩展操作码”?

  • 核心矛盾:指令字长是固定的(本题是 16 位),既要有“二地址”、又要有“一地址”、还要有“零地址”。
  • 格式划分:
    • 二地址格式:[ 操作码 OP (4位) ] [ 地址码 A1 (6位) ] [ 地址码 A2 (6位) ]( 位)
    • 一地址格式:[ 操作码 OP (10位) ] [ 地址码 A1 (6位) ]( 位,操作码借用了原本 A2 的 6 位)
    • 零地址格式:[ 操作码 OP (16位) ](全部 16 位都当操作码,借用了 A1 和 A2 的 位)
  • CPU 怎么区分?
    • 采用前缀编码原则(类似哈夫曼树):短操作码绝不能是长操作码的前缀!
    • 比如:如果二地址指令已经把 0000 到 1011(共 12 种)占用了,那么一地址指令的操作码前 4 位就绝对不能用这 12 个,否则 CPU 看到前 4 位就不知道它是二地址还是一地址了!
    • 一地址指令只能使用二地址没用完的剩余状态(这里剩下 个)作为自己的开头前缀!

2. 考场规范推导链条(步步紧扣):

  1. 第一步:二地址指令计算

    • 地址码长 6 位,两个地址码占 位;
    • 留给操作码的长度为: 位;
    • 4 位操作码最多有 种编码状态;
    • 题目要求:有 12 条二地址指令;
    • 留给下一级的扩展前缀数: 种。
  2. 第二步:一地址指令计算

    • 一地址指令只需要 1 个 6 位地址码,多空出了原本用于 A2 的 6 位空间;
    • 这 6 位并入操作码,使得操作码扩展到 位;
    • 一地址指令最多可容纳条数:
    • 题目要求:有一地址指令 254 条;
    • 留给下一级的扩展前缀数: 种。
  3. 第三步:零地址指令计算

    • 零地址指令不需要地址码,把最后的 6 位地址码 A1 也空出来了;
    • 这 6 位再次并入操作码,操作码扩展到 位;
    • 零地址指令的最大条数:

3. 通用秒杀公式(以后遇到直接套)


编译程序四个阶段(第 20 题):

“预编汇链(.c -> .i -> .s -> .o -> .exe)”

  • 预处理(宏替换、头文件展开) 编译(生成汇编代码) 汇编(生成机器目标代码) 链接(合并库文件与目标文件为可执行程序)。

中断 I/O 方式硬件特性(第 21 题):

“外设干活慢吞吞(毫秒级),CPU 中断快如风(微秒级)!外设准备时 CPU 跑别家!”

  • 中断方式下,外设准备数据由外设独立完成,CPU 并行执行其他程序;
  • 外设准备数据的时间(机械/物理动作,毫秒级)远远大于 CPU 中断处理时间(微秒级)。“准备时间应小于中断处理时间”是荒谬的逆向表述。

操作系统:

系统初始化创建的对象(第 24 题):

“中断向量表进内存是系统造的;分区表、根目录、inode 表是磁盘自带格式化挂载的!”

  • 操作系统初始化时,必须在内存中建立中断向量表(或中断描述符表 IDT),使得 CPU 具备响应中断与异常的能力;
  • 硬盘分区表、文件系统根目录、索引节点表是存储在磁盘上的文件系统元数据,由格式化产生、开机挂载时读取,不是 OS 初始化在内存中从无到有“创建”的。

抢占式进程调度次数与防坑(第 25 题):

“408 恶心老规矩:零时刻挑第一个进程上机,直接就算第 1 次调度!”

  • 全流程推演(优先级数值越小越优先):
    1. :挑 P0(15) 上 CPU 第 1 次调度;
    2. :P2(10) 到达,抢占 P0 第 2 次调度;
    3. :P3(6) 到达,抢占 P2 第 3 次调度;
    4. :P3 跑完 10ms,唤回 P2 第 4 次调度;
    5. :P2 跑完,挑就绪队列中优先级最高的 P0 第 5 次调度;
    6. :P0 跑完,挑最后剩下的 P1 第 6 次调度。
  • 结论:总调度次数为 6 次(不要漏算 0 时刻派发!)。

进程状态转换(第 28 题):

“主动变阻塞,被动进就绪!”

  • 执行态 阻塞态:进程主动调用请求系统资源而未获满足(如 read() 读文件磁盘 I/O、申请独占外设、P(wait) 信号量不足);
  • 执行态 就绪态:被动打断(时间片用完、被更高优先级抢占)。

操作系统与硬件分工(系统调用)(第 31 题):

“硬件关中断、换模式、存断点(PC+PSW);软件(OS)保通用寄存器、执行服务程序!”

  • 用户态陷入内核是软硬件协同:
    • 硬件(中断隐指令):关闭中断、保护程序断点(PC与PSW)、将 CPU 切换为内核态;
    • 操作系统内核(软件):保存通用寄存器、根据系统调用号执行对应的内核服务程序、恢复现场返回。

设备驱动程序性质(第 32 题):

“驱动程序是硬件的翻译官,每种 I/O 方式底层代码各不相同!”

  • 驱动程序向上提供统一系统调用接口,向下直接控制硬件控制器寄存器;
  • 不同的 I/O 控制方式(轮询、中断、DMA)硬件交互逻辑天差地别,驱动程序绝不可能与 I/O 控制方式无关!

计算机网络:

OSI 参考模型各层功能与流量控制(第 33 题):

“相邻节点逐跳控在链路层,进程端到端控在传输层!”

  • 数据链路层:实现**两个相邻节点之间(点到点 / 逐跳 Hop-by-Hop)**的流量控制(如滑动窗口、停止-等待协议)与差错控制;
  • 传输层:实现**端到端之间(进程到进程 / 主机到主机)**的流量控制(如 TCP 滑动窗口与接收窗口 rwnd);
  • 网络层:负责全局路由与拥塞控制;物理层只透明传输比特流,无任何控制机制。

奈氏准则极限数据率(第 34 题):

物理层极限数据率与传输时延全题型计算秒杀

==“奈氏两倍宽乘对数状态:(bps)!”==

  • 关键词“无噪声信道” 奈奎斯特定理;
  • 带宽 ,4 个幅值的 ASK 即离散状态数 ;
  • 极限码元速率(波特率):;
  • 极限数据率:(公式里的系数 2 绝不能漏!)。

子网划分网络地址计算(第 35 题):

IPv4网络地址计算与子网划分全题型秒杀 IP地址范围计算通用公式与秒杀套路

“找准掩码非全零的那一字节,IP 与掩码按位与(AND)!”

  • 子网掩码 255.255.192.0 变化发生在第 3 字节 (步长块大小 );
  • 主机 IP 183.80.72.48 第 3 字节为 ;
  • 整数除法定位:(或按位与 );
  • 前两段 183.80. 照抄,末段直接为 .0 网络地址为 183.80.64.0。

默认网关与子网掩码(第 36 题):

局域网设备选型、网关配置与子网地址范围计算

“网关就是出远门的门神接口,必须与自己在同一子网!”

  • 前缀 /27 对应的掩码:前 27 位全为 1,第 4 字节为 掩码为 255.255.255.224;
  • 主机 H 连接在路由器的右边接口,默认网关必须是该接口在同网段内的 IP:192.168.1.62。

SDN 体系结构北向与南向接口(第 37 题):

“上北下南,管理东西:上面应用走北向,下面交换走南向(OpenFlow)!”

  • SDN 控制器面向上层业务应用 北向接口;
  • SDN 控制器面向底层数据平面转发设备(下发流表) 南向接口;
  • 多个 SDN 控制器之间协同交互 东西向接口。

TCP 超时重传拥塞窗口演变(第 38 题):

TCP 综合控制机制与时延分析 TCP 拥塞控制与滑动窗口全解析

==“超时一出,门限砍半(ssthresh = cwnd / 2),窗口归一(cwnd = 1 MSS)慢开始!”==

  • 原拥塞窗口 16KB,发生超时(Timeout):
    • ;
    • 重置回 ;
  • 慢开始阶段(指数翻倍,直到达到门限):
    • 起点:;
    • 经过 1 RTT:;
    • 经过 2 RTT:;
    • 经过 3 RTT:(达到门限 ,耗时 3 RTT);
  • 拥塞避免阶段(加法增大,每个 RTT 线性加 1):
    • 经过 4 RTT:;
    • …… 增长到 16KB 还需 轮 RTT;
  • 【最终结论】:总共需要经过 才能恢复到原来的 16KB。

TCP 连接释放 TIME_WAIT 时长(第 39 题):

TCP 综合控制机制与时延分析

“主动关闭进 TIME_WAIT,死等 2MSL 才解放;被动关闭收到最后 ACK 历经 1.5 RTT 就关门!”

  • 主动断开方 C:
    • C 发送 FIN 到 S(),S 回送 ACK+FIN 到 C(),历时 ;
    • C 收到后发出最终 ACK 并进入 TIME_WAIT 状态,强制等待 :
    • 主动方 C 进入 CLOSED 至少需要:;
  • 被动断开方 S:
    • S 必须收到 C 对其 FIN 的最终 ACK 才能真正进入 CLOSED 状态;
    • 经历交互传输:C 发 FIN() S 回送 FIN+ACK() C 发 ACK 给 S();
    • 被动方 S 进入 CLOSED 至少需要:(🚨 严防算成 50ms 掉入陷阱!)。
  • 【最终结论】:C 和 S 进入 CLOSED 所需最短时间分别为 和 (选 D)。

HTTP/1.1 持续连接传输时延(第 40 题):

TCP 综合控制机制与时延分析

“HTTP/1.1 虽持久,慢启动门限不可逾:初始 cwnd 仅 1 MSS,图片 3 MSS 必须两轮传!”

  • 客户端已完成域名解析,TCP 连接刚建立时处于慢开始阶段(初始拥塞窗口 ):
    1. 第 1 个 RTT:TCP 三次握手建立连接(第 3 次握手捎带 HTTP 请求);
    2. 第 2 个 RTT:请求并完整接收 的基础 HTML 页面(此时 正好传完);客户端解析出图片,服务器收到 ACK 后慢开始翻倍: 扩大为 ;
    3. 第 3 个 RTT:客户端请求 的图片;由于此时发送端受限于 ,本轮服务器最多只能发送 的图像数据;
    4. 第 4 个 RTT:客户端确认前 2 MSS,服务器发送图片剩余的最后 数据,客户端全部接收完毕;
  • 【最终结论】: (🚨 常见陷阱:误以为持续连接下一个 RTT 就能把 3MSS 全部发完而错选 30ms)。

计算机组成原理综合应用题(第 43、44 题):

CPU数据通路识图与控制信号全题型破题指南 外存磁盘物理结构与DMAI_O传输全题型秒杀笔记


操作系统综合应用题(第 45、46 题):


计算机网络综合应用题(第 47 题):

局域网冲突域_CSMA_CD_DHCP与802_11帧地址全题型秒杀