《2013年408第41-47题》

📅 第 41 题（数据结构）—— 主元素查找

• 核心考点：Boyer-Moore 投票算法（最优解） / 计数数组法（因为限制了 0 ≤ ai < n）。
• 核心公式（判断条件）：
  • 主元素定义：出现次数 m > n / 2。
  • 防坑极简写法：if (count[i] * 2 > n)（完美避开整数除法向下取整的歧义）。
• 复杂度铁律：
  • 最优解（投票法）：时间 O(n)，空间 O(1)。
  • 计数数组法：时间 O(n)，空间 O(n)。
• 💣 易错大坑（必看）：
  1. 必须“验证阶段”：投票法只能找出“候选者”，如果数组没有主元素，候选者是错的。最后一定要再遍历一次验证，没有验证直接返回，0 分。
  2. C 语言内存申请：千万别写 malloc(n, sizeof(int))（逗号是错的），要写 calloc(n, sizeof(int)) 自动清零。如果用了 malloc 不手动清零，count[arr[i]]++ 会从垃圾值开始加，结果全错。
  3. 扫描范围：计数数组循环一定要 i < n，千万别漏掉下标 0（主元素完全可能是 0）。

📅 第 42 题（数据结构）—— 查找最优排列（ASL）

• 核心考点：顺序查找的最优排列原则（概率降序）。
• 核心公式（平均查找长度 ASL）：
  • $AS{L}_{成功}={\sum }_{i=1}^n(p_i\times {\text{比较次数}}_i)$
  • 交换法证明底层逻辑：若 $p_A>p_B$，则 A 必须排在 B 前面。否则交换 A、B 后，ASL 会减少 $(p_A-p_B)\times (po{s}_B-po{s}_A)>0$。
• 💣 易错大坑（必看）：
  1. 折半查找 vs 顺序查找：只有在顺序查找下才能按概率排。如果是折半查找（二分查找），元素必须严格按**关键字大小（如字典序）**排列，绝对不能按概率排（强行按概率排会破坏有序性，无法二分）。
  2. 概率相等时可互换：题目中 do 和 while 概率都是 0.35，两者顺序可以调换，ASL 不变，写上这句是加分项。

📅 第 43 题（组成原理）—— 总线、交叉存储与 Cache 时间

• 核心考点：时钟周期、总线带宽、多体交叉存储的流水线重叠、CPU 执行时间计算。
• 核心公式（极其详细，死磕计算）：
  1. 时钟周期：$T=\frac{1}{f}$（注意频率单位：$800MHz=800\times 10^{6}Hz$）。
     • CPU 周期 $=1/800MHz=1.25ns$；总线周期 $=1/200MHz=5ns$。
  2. 总线带宽（最大数据传输率）：$\text{带宽}=\text{总线宽度（字节）}\times \text{总线频率}$。
     • 此处：$4B\times 200MHz=800MB/s$（注意大写 B 是字节，不是比特）。
  3. 突发传送事务总耗时（本题最难公式）：
     • 总耗时 = 送地址/命令 + 存储器准备数据（交叉存储流水线启动） + 传送数据周期数 $\times$ 总线周期。
     • 关键点（8体交叉）：虽然 8 个体，但准备时间只算 1 次存储周期（40ns），后续 7 个数据会在接下来的 7 个总线周期（5ns/个）流水线产出。
     • 计算：$5ns+40ns+(8\times 5ns)=85ns$。
  4. CPU 执行总时间公式（大题必考）：
     • $T_{总}=(\text{指令条数}\times CPI\times T_{CPU})+(\text{缺失次数}\times \text{缺失额外开销})$
     • 其中，缺失次数 $=\text{访存总次数}\times \text{缺失率}$。
• 💣 易错大坑（必看）：
  1. 千万不能把 8 体准备时间算成 $8\times 40ns$！那是顺序存储，这里是交叉存储（流水线），只有首次启动需要 40ns。
  2. 单位陷阱：总线带宽一定是 MB/s，写 Mbps 直接扣分（差了 8 倍）。
  3. 重复计算命中时间：题目给的 CPI=4 已经包含了 Cache 命中的访问时间，计算额外开销时只算 Cache 缺失去主存取数的 85ns，不要再加一遍 4 个周期。

📅 第 44 题（组成原理）—— 指令格式、相对寻址与标志位

• 核心考点：补码偏移量计算、标志位（CF/ZF/NF）逻辑、无符号数比较条件。
• 核心公式（相对寻址）：
  • 转移目标地址 $=(PC)+2+2\times OFFSET$（当前指令 16 位占 2 字节，所以 PC 先自增 2）。
  • 最大反向跳转指令条数：OFFSET 是 8 位补码，最小为 -128。
    • 回跳字节数 $=2\times (-128)=-256$ 字节；
    • 每条指令 2 字节，所以最多反向跳转 $256/2=128$ 条指令。
• 标志位逻辑（极大易错点，必背）：
  • 指令中 C, Z, N 位为 1 表示**“需要检测该标志”**。
  • 条件转移成立规则：需要检测的标志位中，只要有一个为 1，就跳转。
  • 无符号数小于等于转移（A ≤ B）：
    • 若 A < B（减法有借位）$\Rightarrow CF=1$；
    • 若 A = B（减法结果为 0）$\Rightarrow ZF=1$；
    • 无符号数不看符号，$NF$ 无需检测（设为 0）。
    • 结论：指令中 C=1, Z=1, N=0。
• 💣 易错大坑（必看）：
  1. OFFSET 的符号扩展：8 位补码 E3H 转为 16 位参与运算，一定要先符号扩展为 FFE3H，千万不要前面直接补 0。
  2. 检测逻辑反直觉：题目说“某检测位为 1 时表示需检测”，千万别误以为是“该位为 1 才能跳转”。例如此处 C=0, Z=1, N=1，代表只看 Z 和 N；若 NF=1，即使 ZF=0，条件也满足（跳转）。

📅 第 45 题（操作系统）—— PV 操作（博物馆容量）

• 核心考点：信号量控制容量（同步） + 互斥访问临界区。
• 核心公式 / 逻辑：
  • empty 信号量：初值 = 500（剩余容量），执行 P(empty) 申请入场名额。
  • mutex 信号量：初值 = 1（出入口互斥），执行 P(mutex) / V(mutex) 夹住“进门”和“出门”。
• 💣 易错大坑（必看）：
  1. P 的顺序绝对不能反：进门必须先 P(empty) 再 P(mutex)。如果先拿锁（mutex）再判断容量（empty），一旦博物馆满员，这个人会拿着锁堵在门口，后面所有人（包括出门的人）都进不来，造成死锁。
  2. 出门释放顺序：离开时，先 V(mutex) 释放门锁，再 V(empty) 释放容量。如果先释放容量再开门，逻辑上虽然没死锁，但不符合“人出门后再腾出空间”的物理语义（考试标准顺序是先解锁再腾位）。

📅 第 46 题（操作系统）—— Inode 索引结构（最大长度与 I/O 次数）

• 核心考点：直接/间接索引地址结构、磁盘块地址换算、I/O 磁盘块读取次数。
• 核心公式（极其详细，死磕计算）：
  1. 一个索引块能存多少个地址：$\text{地址数}=\frac{\text{磁盘块大小}}{\text{地址占字节数}}=\frac{1024B}{4B}=256$ 个。
  2. 最大文件长度公式（分级计算）：
     • 直接块：$10\times 1KB=10KB$
     • 一级间接：$256\times 1KB=256KB$
     • 二级间接：$256^2\times 1KB=64MB$
     • 三级间接：$256^3\times 1KB=16GB$
     • 总和：$10KB+256KB+64MB+16GB\approx 16.06GB$
  3. 判断偏移量落在哪一级（定位块号）：
     • 目标块号 = $\lfloor \frac{目标偏移量（字节）}{块大小（1024B）}\rfloor$。
     • 此处 $100000/1024\approx 97$（块号从 0 开始）。
     • 直接块覆盖 $0\sim 9$；一级索引覆盖 $10\sim (10+256-1)=265$。$97$ 落在一级索引区。
• 💣 易错大坑（必看）：
  1. 题目是否说 inode 已在内存（本题说了）：如果没说，读文件需要额外 +1 次磁盘 I/O（读入 inode）。本题明确 inode 已在内存，所以算 I/O 次数绝对不要加 1！
  2. I/O 次数计算：访问目标数据块，需要先读入存放地址的索引块（1 次），再读入目标数据块本身（1 次），总共 2 次。很多同学只算数据块，漏掉了索引块。

📅 第 47 题（计算机网络）—— 路由聚合与 BGP 协议

• 核心考点：CIDR 路由聚合（找共同前缀）、最长前缀匹配、BGP 协议特性。
• 核心公式（路由聚合）：
  • 将两个网段聚合成一个：找出两个网络地址的共同二进制前缀位数。
  • 例：194.17.20.0/25 和 194.17.21.0/24。前者第三个字节是 20，后者是 21（00010100 与 00010101），前 7 位相同（0001010），加上前两个字节（16 位），共 $16+7=23$ 位相同 $\Rightarrow$ 聚合为 194.17.20.0/23。
• 协议规定：
  • 不同自治系统（AS）之间跑的是 BGP（边界网关协议）。
  • BGP 报文封装在 TCP 协议段中（端口号 179），绝对不是 UDP。
• 💣 易错大坑（必看）：
  1. 聚合后直连路由依然存在：R2 直连的 194.17.20.128/25 虽然是聚合网段 /23 的子集，但标准路由表必须有一条单独的直连路由（接口 E0）。同时，为了“表项尽可能少”，用聚合网段 /23 覆盖 R3 那边的两个子网。
  2. 最长前缀匹配覆盖聚合路由：当目的 IP 194.17.20.200 到达 R2 时，它同时匹配聚合路由 /23 和直连路由 /25。路由器不会选聚合的，而是选掩码更长的直连路由 /25（通过 E0 接口）。一定要写出“最长前缀匹配”这 6 个关键字，这是给分点。

🎯 终极考场心态提醒

遇到计算题（尤其是组成原理的总线时间、操作系统的 Inode 块号），先在草稿纸上画出时间轴或层级结构图，把每一步拆开写，不要跳步。改卷是“按步给分”，即使最后结果算错，公式和过程对了也能拿一大半分！

把这 7 页的知识点在脑子里过一遍，2013 年你就彻底征服了！还有哪一年想继续攻克，随时喊我。🚀