数据结构:
时间复杂度分析(第 1 题):
树与遍历(第 3 题):
“二叉树中序遍历相邻,左子树根右子树,中间必隔爹,绝不可能右兄弟!”
- 中序遍历顺序:左子树 根结点 右子树。
- 相对位置判定:
- 若 与 中序相邻且 在 前面:
- 可以是 的双亲(左孩子访问完访问根);
- 可以是 的右孩子(根访问完,若右孩子没有左子树,紧接着访问右孩子);
- 可以是 双亲的双亲( 作为子树最右结点,回溯到更上层祖先);
- 绝对不可能: 是 的右兄弟!因为 (左孩子)访问完,必须先访问它们的双亲(根),然后才轮到右兄弟,中间必然隔着双亲!
- 若 与 中序相邻且 在 前面:
- 🚨 避坑动作:审题看到“不可能的是”,拿到笔第一秒在试卷上画双重红圈,选项打叉打勾防手抖。
AOE 网时间余量计算(第 7 题):
“时间余量就是松弛度:最迟开始减最早开始,关键路径余量全为零!”
- 公式:活动 的时间余量 = 。
- 最早开始时间 :等于箭线起点事件的最早发生时间 ;
- 最迟开始时间 :等于箭线终点事件的最迟发生时间 ;
- 秒杀技巧:
- 先挑出关键路径(耗时最长的路径),关键路径上的所有活动余量为 0;
- 非关键路径上哪个分支富余时间最多,哪个活动的松弛度/时间余量就最大。
B 树删除与关键字调整(第 8 题):
==“ 阶 B 树除根外,关键字下限 ;删根找前驱或后继借,借不到就合并!”==
- 5 阶 B 树除根外每个结点的关键字个数在 个之间。
- 根结点关键字 260 被删除后,通常由其**左子树的最大值(直接前驱 110)或右子树的最小值(直接后继 280)**顶替;若发生下移合并,根结点的结构随之更新,不可能保留非法的关键字组合。
归并排序基本概念(第 10 题):
“归并归并,把两个及以上有序表‘合二为一’!”
- 二路归并核心定义:将两个有序表合并为一个新的有序表(选项 A)。
- 干扰项秒杀:
- 划分数组元素个数大致相等 分治法的划分阶段;
- 一部分均小于另一部分 快速排序的
Partition划分操作。
计组:
补码整数表示范围(第 13 题):
==“ 位补码零不重,负数多一记心中:!”==
- 32 位有符号整数补码表示范围:。
- 最高位是符号位,数值位 31 位;最小负数由
1000...00专门表示。
IEEE 754 浮点数机器码表示(第 14 题):
“一符八阶廿三尾,负一正零偏百廿七,切出四位变十六!”
- 标准四步走模板(以 为例):
- 符号位 :负数取 ;
- 绝对值化为二进制: ,实际指数 ;
- 移码阶码 (偏置值 127): ;
- 拼盘分组变十六进制:
[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;
- 页面大小 4KB = 低 12 位(十六进制低 3 位
- 🚨 避坑关键:
- 页表第 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. 考场规范推导链条(步步紧扣):
-
第一步:二地址指令计算
- 地址码长 6 位,两个地址码占 位;
- 留给操作码的长度为: 位;
- 4 位操作码最多有 种编码状态;
- 题目要求:有 12 条二地址指令;
- 留给下一级的扩展前缀数: 种。
-
第二步:一地址指令计算
- 一地址指令只需要 1 个 6 位地址码,多空出了原本用于 A2 的 6 位空间;
- 这 6 位并入操作码,使得操作码扩展到 位;
- 一地址指令最多可容纳条数:
- 题目要求:有一地址指令 254 条;
- 留给下一级的扩展前缀数: 种。
-
第三步:零地址指令计算
- 零地址指令不需要地址码,把最后的 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 次调度!”
- 全流程推演(优先级数值越小越优先):
- :挑 P0(15) 上 CPU 第 1 次调度;
- :P2(10) 到达,抢占 P0 第 2 次调度;
- :P3(6) 到达,抢占 P2 第 3 次调度;
- :P3 跑完 10ms,唤回 P2 第 4 次调度;
- :P2 跑完,挑就绪队列中优先级最高的 P0 第 5 次调度;
- :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 题):
“主动关闭进 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 掉入陷阱!)。
- S 必须收到 C 对其 FIN 的最终 ACK 才能真正进入
- 【最终结论】:C 和 S 进入 CLOSED 所需最短时间分别为 和 (选 D)。
HTTP/1.1 持续连接传输时延(第 40 题):
“HTTP/1.1 虽持久,慢启动门限不可逾:初始 cwnd 仅 1 MSS,图片 3 MSS 必须两轮传!”
- 客户端已完成域名解析,TCP 连接刚建立时处于慢开始阶段(初始拥塞窗口 ):
- 第 1 个 RTT:TCP 三次握手建立连接(第 3 次握手捎带 HTTP 请求);
- 第 2 个 RTT:请求并完整接收 的基础 HTML 页面(此时 正好传完);客户端解析出图片,服务器收到 ACK 后慢开始翻倍: 扩大为 ;
- 第 3 个 RTT:客户端请求 的图片;由于此时发送端受限于 ,本轮服务器最多只能发送 的图像数据;
- 第 4 个 RTT:客户端确认前 2 MSS,服务器发送图片剩余的最后 数据,客户端全部接收完毕;
- 【最终结论】: (🚨 常见陷阱:误以为持续连接下一个 RTT 就能把 3MSS 全部发完而错选 30ms)。
计算机组成原理综合应用题(第 43、44 题):
CPU数据通路识图与控制信号全题型破题指南 外存磁盘物理结构与DMAI_O传输全题型秒杀笔记
操作系统综合应用题(第 45、46 题):
- 第 45 题(文件系统):UNIX混合索引文件与目录检索访盘次数全题型秒杀
- 第 46 题(线程同步):前趋图与多线程同步PV操作全题型秒杀模板