考研之路

408 跨科综合测（数据结构 · 计组 · OS · 计网）

范围：四科主干考点混合出卷，模拟 408 统考卷式但题量减半——单选 20 题（四科各 5 题）+ 大题 4 题（每科 1 题：算法设计 / 存储与流水线计算 / 页面置换计算 / 网络协议计算），共 24 题。全部为模拟题（非真题），风格与难度对齐 408 统考。限时 90 分钟；答案与解析见文末，计算题附自查演算，做完前不要下翻。

定位：本卷是 408 的科目级综合卷，检验跨科混合作答时考点切换与时间分配能力。四科各自的章节测已随各科章节编排（如数据结构章节测），错题本在各科测验目录。

第 1 题（数据结构）

下列程序段的时间复杂度为（ ）

int sum = 0;
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= i; j++)
        sum++;

A. O(n)O(n) B. O(nlog⁡n)O(n \log n) C. O(n2)O(n^2) D. O(2n)O(2^n)

第 2 题（数据结构）

循环队列容量 m = 8，front 指向队首元素，rear 指向队尾元素的下一位置。若 front = 2、rear = 5，则队列中元素个数为（ ）

A. 3 B. 5 C. 11 D. 6

第 3 题（数据结构）

某二叉树中有 8 个度为 2 的结点，则度为 0（叶子）的结点数为（ ）

A. 7 B. 8 C. 9 D. 10

第 4 题（数据结构）

对有 n 个顶点、e 条弧的有向图采用邻接表存储，深度优先遍历（DFS）的时间复杂度为（ ）

A. O(n2)O(n^2) B. O(n+e)O(n+e) C. O(e)O(e) D. O(n×e)O(n \times e)

第 5 题（数据结构）

下列排序算法中，每一趟结束后都能确定至少一个元素的最终位置的是（ ）

A. 直接插入排序 B. 快速排序 C. 二路归并排序 D. 基数排序

第 6 题（计组）

8 位补码 0xF0 表示的十进制真值是（ ）

A. 240 B. -16 C. -15 D. -240

第 7 题（计组）

IEEE 754 单精度浮点数 0x41C80000 的十进制值是（ ）

A. 4.5 B. 12.5 C. 25.0 D. 200.0

第 8 题（计组）

主存地址 32 位，Cache 容量 32 KB，块大小 64 B，采用 2 路组相联映射。主存地址中 Tag 字段的位数为（ ）

A. 18 B. 20 C. 22 D. 16

第 9 题（计组）

指令流水线中"转发（旁路）技术"主要用来解决（ ）

A. 结构冒险 B. 数据冒险 C. 控制冒险 D. Cache 缺失

第 10 题（计组）

下列关于 DMA 方式的叙述中，正确的是（ ）

A. DMA 完全不需要 CPU 干预即可完成整个数据传送的启动与结束处理 B. DMA 传送以字节为单位向 CPU 请求总线使用权 C. DMA 传送期间 CPU 可以继续执行与主存无冲突的工作，属于周期挪用（周期窃取） D. DMA 方式只适用于键盘等低速设备

第 11 题（OS）

下列进程状态转换中，不可能发生的是（ ）

A. 运行 → 就绪 B. 就绪 → 运行 C. 阻塞 → 就绪 D. 阻塞 → 运行

第 12 题（OS）

信号量 S 初值为 2，经过若干 P、V 操作后当前值为 -1。由此可知（ ）

A. 有 0 个进程在等待队列中，剩余可用资源 1 个 B. 有 1 个进程在等待队列中，可用资源 0 个 C. 有 1 个进程在等待队列中，剩余可用资源 1 个 D. 有 2 个进程在等待队列中

第 13 题（OS）

系统中共有 3 个进程，每个进程最多需要 4 台设备。设备总数至少为（ ）台时，系统不可能发生死锁

A. 9 B. 10 C. 12 D. 4

第 14 题（OS）

某分页系统页大小 4 KB，逻辑地址 0x5A1F 对应的页号为 5、该页装入页框 9（十进制），则物理地址为（ ）

A. 0x9A1F B. 0x5A1F C. 0x95A1 D. 0x4A1F

第 15 题（OS）

磁盘转速 6000 转/分，则平均旋转延迟（半圈时间）约为（ ）

A. 5 ms B. 10 ms C. 2.5 ms D. 20 ms

第 16 题（计网）

在 OSI 参考模型中，实现端到端（进程到进程）数据传送与可靠（或不可靠）传输服务的是（ ）

A. 数据链路层 B. 网络层 C. 传输层 D. 会话层

第 17 题（计网）

某以太网数据率 10 Mb/s，采用 CSMA/CD，单程端到端传播时延为 25.6 μs。为保证冲突检测有效，最小帧长为（ ）

A. 32 B B. 64 B C. 128 B D. 256 B

第 18 题（计网）

IP 地址块 192.168.10.0/26 可划分为若干子网，每个子网可用的主机地址数为（ ）

A. 62 B. 64 C. 30 D. 126

第 19 题（计网）

TCP 连接建立（三次握手）过程中，第二个报文段携带的标志位是（ ）

A. SYN B. ACK C. SYN + ACK D. FIN + ACK

第 20 题（计网）

主机向本地域名服务器发出的域名解析查询，通常采用的方式是（ ）

A. 递归查询 B. 迭代查询 C. 广播查询 D. 反向查询

第 21 题（数据结构 · 算法设计）

给定含 n 个互不相同整数的数组 a[0..n-1] 和整数 k（1 ≤ k ≤ n），设计算法在平均时间复杂度 O(n) 内找出第 k 小的元素。要求：

（1）写出算法思路（说明为何平均复杂度为 O(n)）； （2）用 C 语言实现核心函数 int kthSmallest(int a[], int n, int k)； （3）说明最坏时间复杂度及一种将其改进到最坏 O(n) 的思路。

第 22 题（计组 · 存储与流水线计算）

某计算机主存地址 32 位，Cache 数据容量 32 KB，块大小 64 B，2 路组相联；CPU 采用 5 段指令流水线（取指 IF、译码 ID、执行 EX、访存 MEM、写回 WB），每段时间 2 ns（含流水寄存器开销）。请计算：

（1）主存地址中 Tag、组号（index）、块内偏移各占多少位？主存第 0x12345678 号字节所在的主存块映射到 Cache 的哪一组？ （2）流水线连续执行 20 条无冒险指令需要多少时间？相比串行执行加速比是多少？该流水线的最大吞吐率是多少（条/秒）？

第 23 题（OS · 页面置换计算）

某系统为进程分配 3 个页框（初始为空），页面引用串为：

7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1

（1）分别用 FIFO 与 LRU（最近最久未使用）算法给出每次访问后的页框内容与缺页次数、缺页率； （2）FIFO 算法存在"Belady 异常"：对引用串 1 2 3 4 1 2 5 1 2 3 4 5 分别用 3 个与 4 个页框做 FIFO，通过计算验证缺页数不减反增。

第 24 题（计网 · 网络协议计算）

主机 A 与 B 之间建立 TCP 连接，设拥塞控制仅考虑慢开始与拥塞避免（忽略快重传对窗口的影响），初始 cwnd = 1 MSS，初始 ssthresh = 16 MSS；慢开始阶段每轮（RTT）cwnd 加倍，达到 ssthresh 后进入拥塞避免每轮加 1 MSS。请计算：

（1）第 1～7 轮每轮结束时的 cwnd 值，并标明各自所处阶段； （2）若第 7 轮结束时报文丢失发生超时，给出第 8～13 轮的 cwnd 与 ssthresh 变化； （3）若第 7 轮结束时不超时，而是收到 3 个重复 ACK 触发快恢复，说明此时 ssthresh 与 cwnd 如何设置，并给出其后两轮的 cwnd 值。

答案与解析（单选）

1. C　内层执行总次数为 1+2+⋯+n=n(n+1)21+2+\dots+n=\frac{n(n+1)}{2}，量级 O(n2)O(n^2)。考点标签：时间复杂度分析｜绪论与复杂度分析｜难度：易｜错因提醒：内层边界是 j ≤ i 而非 j ≤ n，误按两层 n 算出同样的 O(n2)O(n^2) 也对，但要能写出求和过程应对大题追问。

2. A　元素个数 = (rear − front + m) mod m = (5 − 2 + 8) mod 8 = 3。考点标签：循环队列｜栈、队列和数组｜难度：易｜错因提醒：rear 指向"队尾下一位置"约定下不能直接用 rear − front（rear 可能回绕），必须加 m 再取模。

3. C　二叉树性质 n0=n2+1n_0 = n_2 + 1：边数 = 总结点数 − 1 = n0+n1+n2−1n_0 + n_1 + n_2 - 1，又边数 = n1+2n2n_1 + 2n_2（由孩子数计），联立得 n0=n2+1=9n_0 = n_2 + 1 = 9。考点标签：二叉树性质｜树与二叉树｜难度：易｜错因提醒：结论对任意二叉树成立，与是否为完全二叉树无关。

4. B　邻接表下 DFS 访问每个顶点 O(n)、沿每条弧走一次 O(e)，总 O(n+e)O(n+e)；O(n2)O(n^2) 是邻接矩阵存储的复杂度。考点标签：图遍历｜图｜难度：易｜错因提醒：遍历复杂度必须与存储结构绑定作答，题目问"邻接表"时选 O(n2)O(n^2) 是最典型错误。

5. B　快速排序每趟以枢轴为界划分后，枢轴元素落在最终位置；直接插入、归并、基数排序都不能保证。具备该性质的还有冒泡排序与简单选择排序（本卷未列为选项）。考点标签：排序趟次性质｜排序｜难度：中｜错因提醒：该性质是选择题高频点，需整组记忆"冒泡、简单选择、快排、堆排（一趟交换后）"。

6. B　0xF0 = 1111 0000B，符号位为 1 是负数；真值 = 除符号位取反加 1：0000 1111 + 1 = 0001 0000 = 16，故真值 −16。快捷式：真值 = 0xF0 − 0x100 = 240 − 256 = −16。考点标签：补码｜数据的表示和运算｜难度：易｜错因提醒：把补码当无符号数读出 240 是首错；"取反加一"时漏掉符号位保持不变是次错。

7. C　0x41C80000 = 0100 0001 1100 1000 …0B：S=0；E=1000 0011B=131，阶码 e=131−127=4；尾数 1.M=1.1001B=1.5625。值 = 1.5625×241.5625×2^4=25.0。考点标签：IEEE 754｜数据的表示和运算｜难度：中｜错因提醒：隐含的"1."和偏置 127 是两大扣分点；先拆符号/阶码/尾数再动笔。

8. A　块内偏移 = log₂64 = 6 位；Cache 共 32KB/64B = 512 块，2 路组相联 → 256 组，组号 8 位；Tag = 32 − 8 − 6 = 18 位。考点标签：Cache 映射｜存储器层次结构｜难度：中｜错因提醒：组数 = 块数 ÷ 路数，常被漏除 2；Tag 位随相联度提高而变长。

9. B　转发/旁路把 EX 段刚算出的结果直接送回需要它的段，消除 RAW（写后读）数据冒险；结构冒险靠资源重复、控制冒险靠分支预测等手段。考点标签：指令流水线冒险｜中央处理器｜难度：中｜错因提醒：三类冒险与对策要成对记忆：结构—资源重复/停顿；数据—转发+停顿；控制—分支预测/延迟转移。

10. C　DMA 以数据块为单位传送，传送期间靠周期挪用（窃取存取周期）与 CPU 共享主存，CPU 可继续执行不冲突的工作；但传送的启动、结束后处理仍需 CPU。DMA 适合磁盘等高速设备，A、B、D 均错。考点标签：DMA 方式｜输入输出系统｜难度：中｜错因提醒："完全不需要 CPU"与"以字节为单位请求"是干扰经典款。

11. D　阻塞进程必须先经 I/O 完成或事件发生转为就绪，被调度后才能运行，"阻塞 → 运行"不存在。运行 → 就绪（时间片到）、就绪 → 运行（被调度）、阻塞 → 就绪（等待事件完成）均可能。考点标签：进程状态转换｜进程与线程｜难度：易｜错因提醒：画三角状态图时"阻塞 → 运行"这条边是最常见误画。

12. B　信号量 S<0 时，|S| = 等待队列中的进程数；S=−1 即 1 个进程在等待、可用资源 0。资源数初值 2 已全被占用。考点标签：信号量｜进程与线程｜难度：中｜错因提醒：S 的负值才表示等待数；"剩余资源 1"是把 |−1| 当剩余资源的典型错。

13. B　最坏情形是每个进程都差 1 台设备而被阻塞：3×(4−1)=9 台时可能互等而死锁；再加 1 台 = 10 台，必有进程能凑齐 4 台运行完并释放设备，死锁不可能。通式 n×(m−1)+1。考点标签：死锁必要条件｜进程与线程｜难度：中｜错因提醒：按"最多需要数×进程数"选 12 是没理解"最多"含义。

14. A　页大小 4 KB → 页内偏移 12 位；逻辑地址 0x5A1F 偏移 = 0xA1F。物理地址 = 页框号×页大小 + 偏移 = 9×0x1000 + 0xA1F = 0x9A1F。考点标签：分页地址变换｜内存管理｜难度：中｜错因提醒：页框号 9 是十进制，拼地址时须换算 9×4096=0x9000；选 C 是把 9 拼在页号位上的错。

15. A　6000 转/分 = 100 转/秒，转一圈 10 ms，平均旋转延迟取半圈 = 5 ms。考点标签：磁盘性能｜输入输出管理｜难度：易｜错因提醒：单位换算链"转/分 → 转/秒"是唯一陷阱，除 60 而不是乘。

16. C　传输层提供端到端（进程到进程）通信；数据链路层是"点到点"（相邻结点），网络层是"主机到主机"，会话层管理会话同步。考点标签：体系结构分层｜计算机网络体系结构｜难度：易｜错因提醒："端到端 vs 点到点"两组词的分界线是传输层。

17. B　CSMA/CD 要求发送时间 ≥ 2×单程传播时延（争用期）：最小帧长 = 2τ×数据率 = 2×25.6 μs×10 Mb/s = 512 bit = 64 B。考点标签：CSMA/CD 与争用期｜数据链路层｜难度：中｜错因提醒：忘记乘 2 或 bit/Byte 换算错（512 bit ÷ 8 = 64 B）是两大失分点。

18. A　/26 → 主机位 6 位，262^6−2 = 62 个可用地址（扣除全 0 网络地址与全 1 广播地址）。考点标签：子网划分｜网络层｜难度：易｜错因提醒：题干"192.168.10.0/26 可划分为若干子网"是烟雾弹，本题只问"每个 /26 子网"的可用主机数；64、30 分别对应漏减 2 与 /27 的错。

19. C　三次握手：① 客户端 SYN；② 服务器 SYN+ACK；③ 客户端 ACK。第二个报文段同时完成对客户端请求的确认和自己的同步请求。考点标签：TCP 连接管理｜传输层｜难度：易｜错因提醒：连接建立 3 段、连接释放 4 段的报文标志序列要成对背。

20. A　主机 → 本地域名服务器通常为递归查询（"你必须给我最终答案"）；本地域名服务器向根/顶级/权限域名服务器则为迭代查询。考点标签：DNS｜应用层｜难度：易｜错因提醒：递归/迭代的分界在"谁向根服务器发问"，不在"谁发起解析"。

答案与解析（大题）

21.（数据结构 · 算法设计）

  • 考点标签：快速选择（QuickSelect）｜排序（划分思想）+绪论与复杂度分析｜难度：中
  • （1）思路：借鉴快速排序的划分。任取一个元素作枢轴，一趟划分后枢轴落位 p（左边都小、右边都大）：若 p 恰为第 k 位（0 编号 k−1），即为答案；若第 k 位在左半，只递归左半，否则只递归右半。只搜一侧是与快排的本质区别：期望划分规模 n、n/2、n/4、…，求和 n(1+12+14+… )≈2nn(1+\frac12+\frac14+\dots)\approx 2n，故平均 O(n)O(n)，空间平均 O(log⁡n)O(\log n)（递归栈）。
  • （2）参考实现：
int partition(int a[], int lo, int hi) {   /* 以 a[lo] 为枢轴，返回落位下标 */
    int pivot = a[lo], i = lo, j = hi;
    while (i < j) {
        while (i < j && a[j] >= pivot) j--;
        a[i] = a[j];
        while (i < j && a[i] <= pivot) i++;
        a[j] = a[i];
    }
    a[i] = pivot;
    return i;
}

int quickSelect(int a[], int lo, int hi, int r) {  /* r 为 0 编号的目标位次 */
    if (lo == hi) return a[lo];
    int p = partition(a, lo, hi);
    if (p == r) return a[p];
    else if (r < p) return quickSelect(a, lo, p - 1, r);
    else return quickSelect(a, p + 1, hi, r);
}

int kthSmallest(int a[], int n, int k) {   /* 第 k 小，k 从 1 开始 */
    return quickSelect(a, 0, n - 1, k - 1);
}
  • （3）最坏情况：每次划分极度倾斜（枢轴总为最小/最大），退化为 O(n2)O(n^2)。改进思路：① 随机选枢轴，使最坏概率任意小（概率保证）；② 中位数的中位数（BFPRT）算法——按 5 个一组取各组中位数再递归取中位数作枢轴，可证划分至少丢弃固定比例元素，最坏 O(n)O(n)。另注：元素互异保证第 k 小唯一，算法同样适用于有重复元素（稳定性不要求）。
  • 错因提醒：大题三问层层递进——只写"用快排排完取第 k 个"得复杂度 O(nlog⁡n)O(n\log n)，不满足第（1）问 O(n)O(n) 的要求，是本题最大失分点。

22.（计组 · 存储与流水线计算）

  • 考点标签：组相联映射 + 流水线性能｜存储器层次结构+中央处理器｜难度：中
  • （1）自查演算：
    • 块内偏移 = log₂64 B = 6 位；Cache 32 KB / 64 B = 512 块，2 路一组 → 组数 = 512/2 = 256，组号 = log₂256 = 8 位；Tag = 32 − 8 − 6 = 18 位（地址结构：Tag | 组号 | 块内偏移）。
    • 0x12345678 = 0001 0010 0011 0100 0101 0110 0111 1000B。低 6 位为块内偏移；块号 = 地址右移 6 位 = 0x48D159。组号 = 块号 mod 256 = 0x48D159 mod 0x100 = 0x59，即映射到第 0x59 组（十进制 89 组）。组内可放 2 路中任一路，具体命中与否看 Tag 比对。
  • （2）自查演算：
    • 流水线总时间 T=(k+n−1)Δt=(5+20−1)×2 ns=48 nsT = (k+n-1)\Delta t = (5+20-1)×2\,\text{ns} = 48\,\text{ns}（5 段流水 k=5，注入 20 条指令 n=20：先 5 拍灌满，再 19 拍每拍出 1 条）。
    • 串行时间 = 20 条 × 5 段 × 2 ns = 200 ns；加速比 S=200/48≈4.17S = 200/48 ≈ 4.17（理想上限为段数 5）。
    • 最大吞吐率 = 稳态后每拍（2 ns）流出 1 条 = 1/(2×10⁻⁹ s) = 5×10⁸ 条/秒。
  • 错因提醒：① 组号用"块号 mod 组数"而非 mod 路数；② (k+n−1) 中 k 是段数不是"指令数+1"；③ 吞吐率问"最大"时给的是稳态值 1/Δt，若问 n 条的平均吞吐率则是 n/T = 20/48 ≈ 0.417 条/ns。

23.（OS · 页面置换计算）

  • 考点标签：FIFO / LRU / Belady 异常｜内存管理｜难度：中
  • （1）逐次演算（F 指该次访问缺页）：
    • FIFO（始终淘汰最先进入者）：7F 0F 1F｜2F 淘汰 7 → [0,1,2]｜0 命中｜3F 淘汰 0 → [1,2,3]｜0F 淘汰 1 → [2,3,0]｜4F 淘汰 2 → [3,0,4]｜2F 淘汰 3 → [0,4,2]｜3F 淘汰 0 → [4,2,3]｜0F 淘汰 4 → [2,3,0]｜3 命中｜2 命中｜1F 淘汰 2 → [3,0,1]｜2F 淘汰 3 → [0,1,2]｜0 命中｜1 命中｜7F 淘汰 0 → [1,2,7]｜0F 淘汰 1 → [2,7,0]｜1F 淘汰 2 → [7,0,1]。缺页 15 次，缺页率 15/20 = 75%。
    • LRU（淘汰最近最久未使用，前 7 步与 FIFO 相同）：7F 0F 1F｜2F 淘汰 7 → [0,1,2]｜0 命中（0 变最新）｜3F 淘汰 1 → [0,2,3]｜0 命中｜4F 淘汰 2 → [0,3,4]｜2F 淘汰 3 → [0,4,2]｜3F 淘汰 0 → [4,2,3]｜0F 淘汰 4 → [2,3,0]｜3 命中｜2 命中｜1F 淘汰 0 → [3,2,1]｜2 命中｜0F 淘汰 3 → [2,1,0]｜1 命中｜7F 淘汰 2 → [1,0,7]｜0 命中｜1 命中。缺页 12 次，缺页率 12/20 = 60%。
    • 结论：对同一引用串，LRU（利用历史信息）通常优于 FIFO；LRU 属栈式算法，页框增多缺页必然不增。
  • （2）Belady 异常验证（FIFO）：引用串 1 2 3 4 1 2 5 1 2 3 4 5。
    • 3 个页框：1F 2F 3F｜4F 淘汰 1｜1F 淘汰 2｜2F 淘汰 3｜5F 淘汰 4 → [1,2,5]｜1、2 命中｜3F 淘汰 1 → [2,5,3]｜4F 淘汰 2 → [5,3,4]｜5 命中。缺页 9 次。
    • 4 个页框：1F 2F 3F 4F｜1 命中｜2 命中｜5F 淘汰 1 → [2,3,4,5]｜1F 淘汰 2 → [3,4,5,1]｜2F 淘汰 3 → [4,5,1,2]｜3F 淘汰 4 → [5,1,2,3]｜4F 淘汰 5 → [1,2,3,4]｜5F 淘汰 1 → [2,3,4,5]。缺页 10 次。
    • 页框从 3 增到 4，FIFO 缺页反而 9 → 10，验证 Belady 异常：FIFO 不是栈式算法（各页框数的驻留集不满足包含关系）。
  • 错因提醒：① LRU 每次命中必须刷新"最近使用"顺序，漏刷一次全盘皆错；② FIFO 淘汰依据是进入内存的先后而非"最近是否被用"，把 FIFO 当 LRU 推是本题最常见翻车点；③ 缺页率分母是访问总次数 20（含命中）。

24.（计网 · 网络协议计算）

  • 考点标签：TCP 拥塞控制｜传输层｜难度：中
  • （1）自查演算（cwnd 按"每轮结束"口径）：第 1 轮 1 → 第 2 轮 2 → 第 3 轮 4 → 第 4 轮 8 → 第 5 轮 16（达到 ssthresh=16，慢结束束）→ 第 6 轮 17（拥塞避免 +1）→ 第 7 轮 18（拥塞避免 +1）。
  • （2）第 7 轮末超时：ssthresh = max(cwnd/2, 2) = 18/2 = 9 MSS，cwnd 重置为 1 MSS。其后：第 8 轮 1（慢开始）→ 第 9 轮 2 → 第 10 轮 4 → 第 11 轮 8（8 < 9 仍可倍增）→ 第 12 轮本应 16，但超过 ssthresh，取 9（进入拥塞避免）→ 第 13 轮 10（+1）。
  • （3）第 7 轮末收到 3 个重复 ACK 触发快重传 + 快恢复：ssthresh = 18/2 = 9 MSS，cwnd = ssthresh = 9 MSS（TCP Tahoe 之外的现代实现直接从新门限起步，不回到 1）。其后两轮按拥塞避免每轮 +1：下一轮 cwnd = 10 MSS，再下一轮 = 11 MSS。
  • 错因提醒：① ssthresh 减半的基数是当前 cwnd（18），不是旧门限 16；② 慢开始倍增"撞线"时 cwnd 取 ssthresh 而非继续翻倍，第 12 轮的 9 是本题设的坑；③ 超时（重传计时器超时）与快重传（3 个重复 ACK）的恢复动作不同：前者 cwnd=1 从头再来，后者 cwnd=ssthresh 直接进入拥塞避免。