408 卷子

26 王道模拟一

T2 双重循环时间复杂度

列出内外层循环的执行次数，再加和 ${\sum }_{i=1}^{n/2}(n-2i+1)=\frac{n^2}{4}+\frac{n}{2}=\mathcal{O}(n^2)$

T4 $n$ 个结点的二叉树形态数

• 为第 $n$ 个卡特兰数 $C_n=\frac{1}{n+1}\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$
• 树转为二叉树后，二叉树只有左子树，所以二叉树的形态数为 $n-1$ 对应的卡特兰数

T5 高度为 $h$ 哈夫曼树的叶节点数

• 最多：$2^h$ 个叶节点（满二叉树）
• 最少：$h+1$ 个叶节点（退化为链表）

T7 强连通分量的数量减少的情形

顶点 A,A’ 处于 2 个不同的强连通分量中，且 A 和 A’ 原先存在一条路径，在 A 和 A’ 间添加一条边后，可能使得 A 和 A’ 处于同一个强连通分量中（减少了强连通分量的数量）。

例子：

• A->B->C->A, A'->D->E->A', A'->A，添加 A->A' 后，A 和 A’ 处于同一个强连通分量中。(原本的单向变双向)

T8 构成二叉排序树的先序遍历序列的要求

• 中序遍历序列必为升序排列，该序列和先序遍历序列一起唯一确定一个二叉树
• 也可以按先序构造 NLR，并要求左子树 L>右子树 R，若不满足说明序列不存在

T9 AVL 树最少结点数的递归性质

$H_n=H_{n-1}+H_{n-2}+1$, 且 $H_1=1,H_2=2,H_3=1+1+2=4$

T12 CPU 指令执行时间

• 指令执行时间 = 指令数 × CPI × 时钟周期时间
• 时钟周期时间 = 1 / 时钟频率

T15 SDRAM 数据预取

• 每次访问一个数据单元时，将该单元所在行的多个连续数据单元读入到高速缓存中，称为数据预取。
• 例如 8 位预取，一次访存读取并传输 8 个数据单元。

T17 TLB 和 Cache 缺失涉及的指令周期

• 只与 IF(取指)、Mem(访存) 阶段有关
• ID(译码) 阶段不访问存储器，通过寄存器操作
• WB(写回) 阶段只写寄存器，不访问存储器

T18 处理器指令周期与 CPI

• 单周期处理器：每条指令一个时钟周期完成，CPI=1
• 多周期处理器：每条指令多个时钟周期完成，CPI>1
• 流水线处理器：每条指令多个时钟周期完成，但每个时钟周期完成一条指令，CPI≈1
• 超标量处理器：每个时钟周期完成多条指令，CPI<1

T20 流水线数据冒险 nop 插入数量

对于五段式流水线（IF,ID,Ex,Mem,WB），若指令 A 与 B 存在数据冒险，且 A 在 B 之前执行

• 前半周期写寄存器堆，后半周期读寄存器堆：意思是 A 的 WB 周期可以与 B 的 ID 周期重叠
  • IF(B) 与 ID(A) 重叠，ID(B) 与 WB(A) 重叠，中间插入 2 个 nop
• 不支持👆的特性的情况
  • IF(B) 与 ID(A) 重叠，ID(B) 在 WB(A) 之后，中间插入 3 个 nop

T23 第二类虚拟机管理程序可以运行在用户态

T26 进程的创建态与就绪态

• 进程创建成功后，进程状态转为就绪态
• 创建未完成、不能被调度的状态为创建态

T27 wait/signal 操作

• wait/signal 操作能解决一切同步互斥问题
  • 任何复杂的同步、互斥场景（如生产者 - 消费者问题、读者 - 写者问题、哲学家就餐问题等）都可以被分解为一系列基础的互斥和同步关系，所以理论上，只要有足够的信号量和正确的逻辑，wait/signal 组合就能够解决所有这类问题。
• 但不能防止系统发生死锁
  • 信号量本身只提供加锁和解锁的工具，但它不关心你如何使用这些工具。不良的加锁顺序是导致死锁的直接原因。

T29 整个系统只有一个共享段表

• 共享段表包含共享进程计数、存取控制、段号等，当计数等于 0 时系统才会回收该段所占内存。
• 一个共享段在不同的进程中有不同的段表项（以及段号），但它们都指向同一个共享段表。

T31 驱动程序应该可重入、不应该允许系统调用

• 驱动程序可重入：允许多个进程同时调用同一个驱动程序实例，避免阻塞，提高系统效率。
• 驱动程序不允许系统调用：驱动程序工作在内核态，只有用户态程序才能发起系统调用。

T33⚠️ 电路交换、报文交换与分组交换的时间计算

时间组成

报文共 x 位，分为 k 段传输，每段 p 位，链路带宽 b 位/秒，传播时延 d 秒，电路交换建立连接时间 c 秒，分组长度为 p 位。

• 电路交换：建立连接时间 + 总传播时延 + 发送时延
  • $c+kd+x/b$
• 报文交换：总传播时延 + 发送时延 + 转发时延（报文长度 / 带宽 * 转发次数）
• 分组交换：发送时延 + 转发时延（分组长度 / 带宽 * 转发次数） + 总传播时延
  • $kd+x/b+(k-1)p/b$

T36 IP 数据报重传，旧的分片不能与新分片组装

• 目的站两次接受的分片具有相同的源地址和目的地址，不同的标识符（内部计数器生成），所以不能组装。

T40 有些 HTTP 报文实体主体字段可以为空

• 某些 HTTP 方法（如 HEAD）请求的响应报文中，实体主体字段可以为空。
• 某些状态码（如 204 No Content）响应的报文中，实体主体字段可以为空。

T44 单周期CPU PC更新无须暂存器

• 单周期 CPU 每条指令在一个时钟周期内完成，PC 的更新可以直接在同一时钟周期内完成，无需额外的暂存器来存储中间值。

T45 生产2种产品要求 $-n<=A-B<=m$ 的同步问题

• $-n<=A-B$: 限制缓冲区中 B 产品的数量不能超过 A 产品的数量 n 个
  • 初始有0个B, 故设置信号量 LB=n
  • 每次生产 B 产品时 wait(LB), 生产 A 产品时 signal(LB)
• $A-B<=m$: 限制缓冲区中 A 产品的数量不能超过 B 产品的数量 m 个
  • 初始有0个A, 故设置信号量 LA=m
  • 每次生产 A 产品时 wait(LA), 生产 B 产品时 signal(LA)
• 还需设置对仓库的互斥信号量 mutex=1

T46 计算页表项物理地址

• 页表基址 + (页号 × 页表项大小)