816-Preliminary-fixed
补丁一:2026 真题暴露的“题型微调”与高分应对策略
- 题型风向变化:单项选择题由 40 题缩减至 30 题左右,大题(简答/应用计算/画表)题量增加。
- 本质不变:新增的“简答题”并非长篇纯文字默写,而是将原选择题中的高频考点(如 802.11 RTS/CTS、跨路由 IP/MAC 变化、散列表 ASL)拆解成了“1问概念(2句话) + 1至2问简单计算或画表”。
- 连续两年(2025 与 2026)100% 重复考查的五大绝对核心(必须达到闭眼满分水平):
- AOE 网画图 + 填表求 ve(i)、vl(i)、e(i)、l(i)、时间余量 d(i)=l(i)-e(i) 及关键路径(连考两年大题!)。
- 路由器路由表填写(含直连路由、静态下一跳路由、默认路由 0.0.0.0/0 及出接口)+ VLSM 可变长子网划分。
- 跨多台路由器转发过程中每一段链路的源/目的 MAC 与源/目的 IP 变化表 + 路由器转发 5 步操作。
- 802.11 无线局域网 CSMA/CA(RTS/CTS 作用 + SIFS/DIFS/NAV 时序与总耗时计算)。
- 散列表构造(线性探测法 vs 链地址法)及查找成功 ASL_success、查找失败 ASL_fail 精确计算。
补丁二:直接嵌入原 24 天计划表的 8 项增量必刷点(按天对应补充)
Day 1 - Day 3(物理层与线性表/栈队)
- (计网-新增组合题型) 香农公式 + 信道利用率联合计算(对应 2026-简答1):
- 核心公式:信噪比 dB = 10 * log10(S/N) -> S/N = 10^(dB/10)(记住常用值:30dB 对应 S/N=1000;15dB 对应 S/N = 10^1.5 ≈ 31.62,log2(1+31.62) ≈ 5.03)。
- 防坑考法 A:若仅从数据量角度求最小物理带宽 B,则 C = 数据率 R,直接用 B = R / log2(1 + S/N)。
- 防坑考法 B:若要求考虑链路利用率 eta(如 80%)后的实际信道容量需求,则所需信道传输速率 C = R / eta,再代入 B = C / log2(1 + S/N)。
- (数据结构-新增单选高频点) 栈与循环队列细节(对应 2026-选16, 17, 18, 19):
- 出栈序列合法性判别:入栈 1,2,3,4,5,若先出 4、3,再出 5,此时栈内2在1上面,绝不可能先出1后出2(选 4,3,5,1,2 不可能)。
- 两个队列实现一个栈:始终保持一个队列为空作为辅助;若入栈时直接入非空队,则出栈时需将前 n-1 个元素移入空队;若出栈直接弹出,则入栈时需先入空队再将原非空队元素全部移过来。
- 循环队列 A[0..m-1](front 指队头,rear 指队尾下一位置):
- 队列长度公式:(rear - front + m) % m。
- 入队 k 个元素后新尾指针:rear_new = (rear + k) % m(如 m=6, front=2, rear=5,再插 2 个元素后 rear = (5+2)%6 = 1,故 front=2, rear=1)。
Day 4 - Day 6(数据链路层与串/树)
- (计网-新增大题模板) 802.11 RTS/CTS 简答话术与发送总时间计算(对应 2026-简答2):
- 必背简答话术:
- RTS 帧作用:发送方向接收方(或 AP)请求预约信道使用权,帧内包含本次传输所需时长信息(供其他站点设置 NAV 虚拟载波侦听)。
-
使用 RTS/CTS 的两大主要优点:(1)有效解决无线网络中的“隐蔽站问题(Hidden Station Problem)”;(2)减少长数据帧因直接冲突重传造成的信道带宽浪费(RTS/CTS 控制帧很短,冲突代价极小)。
-
必背总耗时计算公式(从等待 DIFS 开始,到完整收到 ACK 结束,忽略传播时延):
- 总时间 = DIFS + T(RTS) + SIFS + T(CTS) + SIFS + T(DATA) + SIFS + T(ACK)(共含 1 个 DIFS、3 个 SIFS、4 个帧发送时延)!
-
极易错坑点:控制帧(RTS、CTS、ACK)通常按较低的“基本速率(如 1 Mbps)”计算发送时延,而数据帧(DATA)按较高的“数据速率(如 11 Mbps)”计算发送时延,千万不要用错分母速率!
-
(计网-新增计算) 停止-等待协议与滑动窗口信道利用率公式(对应 2026-选2, 3):
- 停止-等待利用率:eta = Tf / (Tf + 2tau + Tack),忽略确认帧与处理时延时 eta = Tf / (Tf + 2tau)。
- 滑动窗口(窗口大小 W)利用率:eta = min(100%, (W * Tf) / (Tf + 2*tau))。
- (数据结构-学长回忆必考) KMP 算法与二叉树基础性质(对应学长回忆 + 2026-选20, 21, 22, 23):
- KMP 选择题必练:给定模式串(如 'abaabcac' 或 'aaab'),在 30 秒内手算出 0 起始或 1 起始的 next[] 数组与优化后的 nextval[] 数组(口诀:nextval 看模式串当前字符 P[j] 是否等于 P[next[j]],相等则继承 nextval[next[j]],不等则保留 next[j])。
- 完全二叉树结点数 n = 1000 时:叶子结点数 = ceil(n / 2) = 500(或由 n = n0 + n1 + n2 = 2*n0 - 1 + n1 推导)。
- 先序遍历与后序遍历序列正好相反的二叉树:必定是“每层只有一个结点的单支树(即高度等于结点数,任一结点无右孩子或无左孩子)”。
- 二叉树度性质:叶结点数 n0 = n2 + 1。
Day 7 - Day 11(网络层与图论)
- (计网-新增选择计算) VLSM 变长子网掩码最省地址分配(对应 2026-选4, 5, 6):
- 规则:容纳 M 台主机(含网关),需满足 2^h - 2 >= M(h 为主机位数,减 2 是扣除全 0 网络地址和全 1 广播地址)。
- 实例(2026-选4):部门主机数为 60、30、30、10:
- 60 台 -> 2^6 - 2 = 62 >= 60 -> 主机位 6 位,前缀 /26,掩码 255.255.255.192;
- 30 台 -> 2^5 - 2 = 30 >= 30 -> 主机位 5 位,前缀 /27,掩码 255.255.255.224;
- 10 台 -> 2^4 - 2 = 14 >= 10 -> 主机位 4 位,前缀 /28,掩码 255.255.255.240;
-
若掩码为 255.255.255.248(即 /29,主机位 3 位),最多容纳主机数(含网关)= 2^3 - 2 = 6 台(2026-选6)。
-
(计网-新增大题模板) 跨路由器端到端转发过程与路由器 5 大操作(对应 2026-简答4):
- 链路地址变化表铁律:在无 NAT 情况下,从主机 A 经 R1、R2 到服务器 B,源 IP 与目的 IP 全程保持不变;源 MAC 和目的 MAC 每经过一跳路由器全部重新封装(A->R1 目的 MAC 为 R1 入接口 MAC;R1->R2 源 MAC 为 R1 出接口 MAC、目的 MAC 为 R2 入接口 MAC;R2->B 源 MAC 为 R2 出接口 MAC、目的 MAC 为 B 的 MAC)。
-
路由器转发数据包时的 5 步关键操作(简答必背采分点):
- 提取 IP 数据报首部的目的 IP 地址,按最长前缀匹配原则查询路由表,确定出接口与下一跳 IP;
- 将 IP 首部中的生存时间 TTL 字段减 1(若 TTL 减至 0 则丢弃并发送 ICMP 超时报文);
- 重新计算并更新 IP 首部检验和;
- 重新封装数据链路层帧:将帧的源 MAC 地址改为本路由器出接口的 MAC 地址,将目的 MAC 地址改为通过 ARP 获得的下一跳设备接口的 MAC 地址;
- 从对应出接口将帧发送到下一跳链路。
-
(计网-单选强化) RIP vs OSPF 核心对比(对应 2026-选9):
- RIP:基于距离向量,使用跳数(Hop)作度量,最大跳数 15,16 表示不可达,周期性向相邻路由器用 UDP(端口 520)广播整个路由表(RIPv2 支持 CIDR/子网掩码)。
- OSPF:基于链路状态(Dijkstra 算法),当链路状态变化时用洪泛法(直接用 IP 数据报封装,协议号 89)向本自治系统所有路由器发送与相邻路由器的链路状态信息,支持 CIDR 与区域划分。
Day 13 - Day 17(运输层与查找/排序)
- (计网-必考辨析) TCP 拥塞控制“超时”与“收到 3 个重复 ACK”对比(对应 2026-选10, 11, 12):
- 发生超时(Timeout):判定网络严重拥塞,执行慢开始:令 ssthresh = 当前 cwnd / 2,同时将 cwnd 重置为 1 MSS,进入慢启动阶段(如 cwnd=20 时超时,新 ssthresh = 10,cwnd = 1)。
-
收到 3 个重复 ACK:判定个别报文段丢失,执行快重传与快恢复:立即重传丢失报文段(不等待超时),令 ssthresh = 当前 cwnd / 2,同时令新 cwnd = 新 ssthresh(或加 3 MSS),直接进入拥塞避免阶段(不把 cwnd 降为 1)。
-
(数据结构-升格大题!) 散列表“线性探测 vs 链地址法”全流程大题模板(对应 2026-简答6):
-
必须同时掌握两种冲突处理法的画表与 ASL 计算:
-
线性探测法:画出下标 0 至 m-1 的散列表;每个已存元素成功比较次数 = (实际存放位置 - H(key) + m) % m + 1;ASL_success = 所有元素成功比较次数之和 / 元素个数 n。
-
线性探测查找失败 ASL_fail:对散列函数可能映射到的每一个初始位置 i(若 H(key) = key % p,则遍历 i = 0 到 p-1),从下标 i 开始向右数到第一个“空单元”为止(包含该空单元本身!若 i 本身为空则计 1 次),累加这 p 个位置的失败比较次数再除以 p!
-
链地址法(拉链法):同义词挂在同一槽位的单链表上,链表第 1 个结点比较 1 次、第 2 个结点比较 2 次、第 3 个结点比较 3 次……算得 ASL_success 通常小于线性探测法(无聚集现象,查找效率更高)。
-
-
(数据结构-防坑修正) 排序算法复杂度、稳定性与快排划分标准(对应 2026-选28, 29, 30):
- 最好情况 O(n)、最坏情况 O(n^2) 的排序:冒泡排序、直接插入排序(快速排序最好 O(nlogn)、最坏 O(n^2);堆排序和归并排序最好最坏均为 O(nlogn))。
- 大数据量(如 10000 个记录)要求“稳定”且时间复杂度尽量低 O(nlogn):唯一选择是【归并排序】(快排、堆排、希尔均不稳定!)。
- 快速排序一趟划分手算铁律:考场上务必按严蔚敏教材“首尾双指针 high 和 low 交替向中间扫描填坑”的标准步骤手算(如序列 49,38,65,97,76,13,27,49 一趟划分后为 [27,38,13], 49, [76,97,65,49]),切勿按从左到右直接抽离的稳定顺序写!
补丁三:基于 2025 + 2026 两年真题,今年考前最后押题轮换预警
既然 2025 和 2026 已经考过了:AOE 关键路径(连考2年)、BST 构造与删除(25年大题+26年单选)、散列表线性探测与拉链法(25年单选+26年大题),今年除了把这三道母题滚瓜烂熟外,必须重点防备同章节尚未出过大题的另外 5 个“轮换大题”:
- 1. 图论轮换预警:Dijkstra 单源最短路径(画 dist[] 与 path[] 每一步迭代更新表格) + Prim/Kruskal 最小生成树构造过程。
- 2. 树结构轮换预警:哈夫曼树构造、哈夫曼编码及 WPL 计算(含多叉哈夫曼树补 0 权虚叶) + 线索二叉树画图。
- 3. 查找/排序轮换预警:平衡二叉树 AVL 插入旋转调整(LL/RR/LR/RL) + B 树插入分裂与删除合并画图 + 堆排序建初堆与筛选调整画图。
- 4. 计网网络层/链路层轮换预警:RIP 距离向量路由表更新计算大题 + 以太网交换机/透明网桥自学习转发表构建大题。
- 5. 计网传输层轮换预警:TCP 拥塞控制(慢开始、拥塞避免、快重传、快恢复)cwnd 与 ssthresh 随轮次变化的完整画图计算大题(2026 已连出 3 道单选,今年极可能直接出成 9 分大题!)。