2020年计算机408真题

答案：C。

对称矩阵满足 $m_{i,j}=m_{j,i}$，只存上三角也能表示下三角。$m_{7,2}$ 位于下三角，应先改查相同的 $m_{2,7}$，不能把原行列号直接代入上三角存储公式。

按列优先，上三角第 j 列依次保存第 1～j 行，共 j 个元素。第 7 列之前有 $1+2+\cdots+6=6\times7/2=21$ 项，$m_{2,7}$ 又是该列第 2 项，在整个序列中为第 23 项。C 数组下标从 0 起，所以下标为 22，选 C。A、B 与按行存储等错误计数有关，D 的 23 把序号当成下标。通式是 $j(j-1)/2+i-1$，最后的 -1 不能漏掉。

答案：D。

栈后进先出，Push 每次取入栈序列中尚未入栈的下一个元素，Pop 只能弹当前栈顶。可逐步记录状态，栈内自左向右表示从底到顶。

输出为 b、c、e，选 D。A、B 的第二个输出 a 不可能，因为第三次 Push 后栈顶是 c；C 的第三个输出 a 也不可能，因为最后两次 Push 后顶端是 e。a 虽最先入栈，却一直被后来的元素盖住，不会因发生了三次 Pop 就必然被弹出。

答案：A。

二叉树顺序存储按完全二叉树位置编号，根为 1 时左右孩子分别为 2i、2i+1；不能把实际存在的结点紧密放成连续 10 项，否则父子关系的下标公式会失效。高度 5 按五层计，最深层位置编号为 16～31。

题目说“任意一棵”，所以容量必须覆盖最不利树形。沿连续右孩子可出现编号 1、3、7、15、31 的链，再在其他合法位置加入 5 个结点，仍是高度 5、共 10 个结点，却占到位置 31。因此至少预留 $2^5-1=31$ 单元，A 正确。B 只够最深层最左位置，C 连第五层都无法容纳，D 只按结点数算，忽略空位置。若数组从 0 编号，末下标为 30，容量仍是 31。

答案：C。

森林转二叉树采用左孩子右兄弟表示，森林先根序对应二叉树先序，森林中根序对应二叉树中序。于是 T 的先序为 a,b,c,d,e,f，中序为 b,a,d,f,e,c，可按“先序首元素是根，中序根左右划分子树”重建。

a 是根，中序左边只有 b，所以左孩子是 b；右子树先序为 c,d,e,f，中序为 d,f,e,c，根为 c，且只有左子树。继续划分可知 c 的左孩子是 d，d 的右孩子是 e，e 的左孩子是 f。按左、右、根输出，左边得 b，右边得 f,e,d,c，最后 a，结果 b,f,e,d,c,a，选 C。A 原封照搬中序，B、D 都未按重建后的各子树后序次序输出。

答案：B。

普通二叉排序树插入从根比较大小，小则左走、大则右走，在遇到的空链接处建立新叶；不像 AVL 树那样随后旋转。图中根 4，左孩子 2，2 的孩子为 1、3，右孩子为 5。所以根必须先插 4，在小于 4 的三个值中，2 也必须先于 1、3 插入。

A 插入 4、5 后再插 2，随后 1、3 分别成为 2 的左右孩子，可生成。C 先插 4、2，再插 5、3、1，也符合；D 的 4、2、1、3、5 同样符合。B 在 2 之前插 1，1 会成为 4 的左孩子，2 只能落在 1 的右侧，之后不会自动提升成 4 的左孩子，因此 B 不能生成图中树。兄弟子树插入可以交错，关键是祖先要先出现。

答案：B。

普通 DFS 常在进入递归时输出，表示首次发现顶点；本题改到完成所有后继递归、退出前才输出，得到完成次序。对 DAG 的任一弧 u→v，若 v 未访问，先递归完成 v 才能完成 u；若 v 已访问，无环保证它不会是尚未完成的祖先，因此它已完成。两种情况都是 v 先于 u 输出。

拓扑序要求每条弧的起点 u 先于终点 v，本题恰好相反，故得到逆拓扑序，选 B。A 需要将输出序列反转；C BFS 按层次输出，与完成次序不同；D 通常 DFS 序列指首次发现次序，并非此处的退出输出。题设保证输出全部顶点，覆盖不连通部分，不能只讨论一次递归所到达的局部。

答案：A。

Kruskal 将所有边按权升序考虑，只有连接两个不同连通分量的边才加入，否则会成环。6 个顶点的生成树需 5 条边，不是选前 5 条最小边就一定可行。

按图，依次考虑 b-f=5（加入）、b-d=6（加入），此时 b,d,f 已连通；d-f=7 若加入会闭合三角形，所以跳过。随后 a-e=9 加入，c-e=10 加入，使 a,c,e 成另一分量；b-e=11 将两个分量接通，完成生成树。加入顺序为 (b,f),(b,d),(a,e),(c,e),(b,e)，选 A，总权 41。B 提前选择权 11 的 b-e，违反先考虑 9、10；C、D 含图中不存在的 e-f 边，也不合法。

答案：B。

AOE 网以弧代表活动，权值为持续时间；事件必须等所有前驱活动结束才能发生，所以总工期由从源点到汇点的最长加权路径决定，这条路径称关键路径，B 正确。

A 错在按边数计长度：两条长活动可能比许多短活动更耗时，应把权值相加。C 错：关键活动位于某条最长路径，延长它会使这条路径更长，工程工期随之延长。D 也不总成立：若存在多条关键路径，缩短一个只属于其中一条的活动，其他路径仍维持原工期，总时间不变。只有缩短的活动覆盖所有制约工期的关键路径，才可能使总体工期下降。区分“延长”与“缩短”的条件非常关键。

答案：C。

大根堆满足完全二叉树形状，且每个父结点关键字不小于孩子。I 正确；完全形状没有中间空位，按层放数组即可由下标定位父子，因此 II 正确。III 错：二叉排序树要求左子树均小、右子树均大，堆只约束父子大小，不限制左右兄弟及子树之间的相对次序。

IV 正确：根为最大值，其他结点都属于某个根孩子的子树，子树内任意值不超过该子树根，所以根两个孩子的较大者就是次大值；只有两个元素时唯一孩子就是次大。正确集合为 I、II、IV，选 C。A 漏 IV，B 错含 III，D 错含 III 且漏 II。这里次大按堆中元素的大小次序理解，有重复时也可由根孩子取得相应最大非根值。

答案：B。

4 阶 B 树每结点最多 3 个关键字，插入后暂有 4 个就分裂；按该题的分裂规则，上提第 $\lceil4/2\rceil=2$ 个关键字，剩余两侧分别成为孩子。插入先找到对应叶，不能直接对整个序列取中位数。

插入 5、6、9 后根为 [5,6,9]；插 13 溢出成 [5,6,9,13]，上提 6，新根 [6]，孩子 [5]、[9,13]。插 8 后右叶 [8,9,13]；插 2 后左叶 [2,5]；插 12 后右叶 [8,9,12,13] 分裂，上提 9，根成 [6,9]，三个孩子 [2,5]、[8]、[12,13]。最后 15 放入最右叶，变 [12,13,15]，不再溢出。根仍为 6、9，选 B；A、C、D 均不符合逐次插入结果。

答案：A。

直接插入排序把当前元素插到前面有序部分，若原数组大部分已有序，向前比较很快就停止，比较次数接近线性。简单选择排序每轮仍需扫描整个未排序区间找最小值，比较次数始终为 $n(n-1)/2$，不会因近乎有序明显减少，所以 I 是原因。

II 错：两者通常都只用固定数目的临时变量，额外空间均 $O(1)$。III 不成立：选择排序每轮至多交换一次，移动次数本就只有 $O(n)$；近乎有序的插入排序仍可能移动一些元素，并不保证少于选择排序。故只选 I，A 正确。B 仅列错误的 III，C 错含 II，D 错含 II、III。比较次数的优势不能直接推广成所有指标都更优。

答案：B。

机器字长是处理器一次能直接处理的基本整数数据位数。在题目采用的基本计算机模型中，ALU 的整数运算宽度和通用寄存器保存一个机器字的宽度与它一致，故 I、III 正确。

II 指令寄存器保存当前机器指令，宽度取决于指令字格式，指令可长于或短于数据字，不必等于机器字长。IV 浮点寄存器取决于支持的浮点格式，例如整数机器字为 32 位仍可支持 64 位浮点数据，所以也不能保证相同。正确集合为 I、III，选 B。A、C 错含 II，D 错含 II、IV。应区分数据字长、指令字长、地址位数和浮点格式位数，它们不是同一个参数。

答案：A。

机器位串的含义由数据类型决定。按 32 位 int 补码解释，C8000000H 最高位为 1，真值为 $\mathrm{C8000000H}-2^{32}=-\mathrm{38000000H}=-7\times2^{27}$，对应 A。

再检查 float：位串划分为 $1\mid10010000\mid000\ldots0$，符号为负，阶码 $144-127=17$，小数部分为 0，规格化有效数为 1，所以浮点值为 $-2^{17}$。选项 B 的 $-2^{16}$ 指数少 1，C 的 $2^{17}$ 符号错误，D 的 $25\times2^{27}$ 是按无符号整数解释得到的正数，但题设 int 为带符号。因此四项中只有 A 是可能真值。不能单凭十六进制形式就断定变量类型。

答案：D。

先处理结构体对齐，再处理字节序。short 占 2 B，x1 放在首地址 FE00H、FE01H；int 占 4 B，需从 4 字节边界开始，因此 FE02H、FE03H 为填充，x2 从 2020FE04H 起存放。

小端方式把数的低字节放低地址。12340000H 从低到高的四个字节为 00H、00H、34H、12H，分别位于 2020FE04H、FE05H、FE06H、FE07H，所以 34H 在 2020FE06H，选 D。A 的 FE03H 是对齐填充区；B、C 均存 00H。若漏掉对齐会把 x2 误放 FE02H，若按大端又会把 34H 误放 FE05H，两类错误应分别检查。

答案：D。

TLB 缓存虚页到物理页框的映射，Cache 缓存指令或数据块，它们内容不同，但都利用局部性减少慢访问。A 正确：最近使用的页或数据再次被用到时容易命中。B 正确：TLB 未命中通常要查主存页表，Cache 未命中要从主存取块；页表确认缺页时还可能继续访问外存。C 正确：TLB 页表遍历和 Cache 调入均可以由硬件处理，虽然某些机器用软件处理 TLB 缺失。

D 错：两者要求高速访问，通常采用高速静态存储单元及相应查找逻辑，不能说都由 DRAM 组成；DRAM 主要用于较大容量主存。因此选错误项 D。TLB 缺失不等于页面一定不在内存，Cache 缺失也不等于发生缺页。

答案：A。

定长指令分成固定操作码、寻址方式和单个地址字段。区分 48 条指令至少需 $\lceil\log_2 48\rceil=6$ 位操作码，因为 5 位只能表示 32 种；4 种寻址方式需 $\log_2 4=2$ 位。剩下地址位数为 $16-6-2=8$。

直接寻址时，该 8 位直接作为无符号内存地址，可表示 $0\sim2^8-1=255$，选 A。B 的 0～1023 是 10 位地址范围，漏扣寻址方式位；C 的 -128～127 是 8 位补码有符号范围，用于相对偏移等情形，不能套到直接地址；D 同时把字段当 10 位和有符号。注意 48 不是 2 的整数幂，操作码位数必须向上取整。

答案：B。

CPI 为完成一条指令平均使用的时钟周期。I 单周期 CPU 将一条指令全部动作放在一个长周期内，所以 CPI=1，但一个周期本身可能很长。III 基本流水线虽然每条指令跨越多个阶段，理想稳态每周期完成一条，平均 CPI=1。

II 多周期 CPU 将指令分成多个周期顺序执行，同一指令通常耗费多个周期，CPI>1。IV 超标量理想每周期可完成多条，发射宽度为 w 时可达 CPI≈1/w，不是 1。因此正确为 I、III，选 B；A 错含 II，C 错含 II、IV，D 错含 IV。流水线的一条指令延迟与平均完成速率应分开，有限批次还存在装入排空开销。

答案：A。

Trap 是处理器在执行程序时有意触发的一类内部异常，常由陷阱指令、调试机制等产生，与来自外部设备的中断不同。A 虽提到陷阱指令，却称为“外部中断事件”，分类错误，所以选 A。

B 正确：断点和单步跟踪可利用调试陷阱，让系统在指定位置获得控制，检查程序状态。C 正确：发生陷阱后，CPU 进入相应内核处理程序执行服务。D 正确：陷阱通常是报告一项已完成的指令事件，处理后返回下一条指令；缺页等故障则常需修复后重执行原指令。不要把所有异常都统称为外部中断，也不要把陷阱的返回位置套用到需要重试的故障。

答案：C。

按题目给定口径，QPI 带宽统计有效数据，并把两个全双工方向相加。每方向一次传 20 位，其中 16 位是数据、4 位是校验，有效数据为 16 bit=2 B，不能把校验位算进有效数据量。

每个周期传 2 次，所以每秒传送次数 $2.4\times10^9\times2$。单向带宽为 $2.4\times10^9\times2\times2=9.6\times10^9$ B/s，再乘双向系数 2，得到 19.2 GB/s，选 C。A 只计一个方向每周期一次，B 只计单向带宽，D 多乘了一次 2。一个 80 位包分两周期、每周期两次，是上述传送次数的同一条件，不能再次重复作为加倍因素。

答案：C。

外部中断由处理器外的定时器、I/O 设备等请求，通常与当前执行的哪条指令无直接因果关系；内部异常则由执行某条指令时的具体事件触发。

I 缺页在访存指令的地址转换过程中发现目标页不在内存，由当前访存触发，是内部异常。II 定时器到时由计时硬件发出中断，III 网络数据包到达由网络设备请求 CPU 服务，都属于外部中断。因此正确集合为 II、III，选 C。A、B 各漏一个外部事件且错含 I，D 也错含 I。缺页处理可能随后发起磁盘 I/O，其完成中断属于外部事件，但不能据此把原先缺页异常也归为外部中断。

答案：B。

外部请求提出、CPU 响应与执行服务程序是不同阶段。B 错：可屏蔽中断信号有效后，还要检查是否开中断、相应请求是否被屏蔽、是否达到响应条件，通常在当前指令结束的中断检查点响应，不能声称立即响应。

A 正确：普通关中断针对可屏蔽请求，不阻止 NMI，所以 CPU 仍可响应不可屏蔽中断。C 正确：NMI 用于严重事件，优先级通常高于可屏蔽中断。D 正确：通过设置屏蔽字，在处理一种中断时允许或禁止其他类中断，能形成所需的处理优先关系。因此选择错误项 B。屏蔽字决定哪些中断可被处理，与改变设备请求是否实际发生也应区分。

答案：C。

周期挪用 DMA 每次只占用传送所需的存储/总线周期，传完一份缓冲数据后把总线交还 CPU。接口缓冲寄存器为 32 位=4 B，因此 512 B 数据块需要 128 次这样的传送，不是一次连续独占主存到底。

A 正确：每准备好 32 位就请求总线，取得使用权后写入主存。B 正确：为及时转移设备数据，DMA 的总线请求通常优先于 CPU。D 正确：整个块完成后发出结束中断，让 CPU 做后续处理。C 错：CPU 只在 DMA 实际占用的周期暂时不能通过同一总线访问主存，两次传送之间仍能访存，也可执行不需该总线的运算。因此应选 C，不能把周期挪用误认成停止 CPU 的整块传送。

答案：B。

按题目采用的文件表模型，系统打开文件表集中保存同一文件的属性及共享管理信息，各进程用户打开表保存自己的打开方式、访问状态等，并引用系统项。共享 F 的文件属性无需每进程复制一份，因此 B 正确。

A 错：权限与同步机制允许时也可写共享文件，并非只能读。C 错：不同进程可能有不同的访问方式、偏移或句柄，所以各自表项不必相同。D 错：一个进程关闭 F 只撤销自己的引用、减少引用计数，其他进程仍使用时不能删除共享系统项，应等最后引用关闭后再回收。区分“进程自己的打开记录”与“系统共享的文件信息”才能判断关闭的影响，不能把共享属性等同于共享全部访问状态。

答案：A。

题目同时要求文件可增长和随机定位。索引分配用索引表保存文件各逻辑块的物理位置，查询逻辑块 i 可直接查相应项，不必顺着之前的数据块走；新增文件块时再分配空块并加入索引即可，不要求物理块连续，所以 A 满足两项。

B 链接分配便于增长，但随机访问通常需要从首块沿链逐块走。C 连续分配可用首块+i 快速随机定位，却受后方空闲空间限制，增长时可能搬移整个文件，不适合一般可变长度要求。D 动态分区分配是内存管理中的概念，不是此处文件磁盘块的组织方式。索引也有索引空间开销，但题目比较的是这两个功能，而非谁完全没有任何开销。

答案：D。

中断响应有硬件自动完成的步骤，也有进入内核后执行的软件步骤。I 保存中断点即保存被中断程序的 PC，在基本中断响应模型中由硬件完成，保证 CPU 跳转后仍知道返回地址，不属于此处操作系统软件负责的项。

II 操作系统提供并执行相应中断服务程序；III 在初始化时设置中断向量表，把各中断关联到处理入口；IV 为处理中断并支持适当嵌套，保存、恢复中断屏蔽字现场，也由系统程序完成。因此正确集合 II、III、IV，选 D。A、B 错含 I，C 漏掉 II。不能把“操作系统最终控制中断处理”扩大成所有动作都由软件做，保存断点与保存其他通用寄存器现场也不是同一项。

答案：D。

多级反馈队列把不同运行特征的就绪进程分到多层队列，并根据运行反馈调整位置。I 队列数量决定有多少层；II 各层优先级决定先服务哪层；III 各队列还需规定时间片轮转、先来先服务等具体策略；IV 规定用完时间片后降级、等待过久后升级等迁移条件，才能体现“反馈”。四项都需要设计，D 正确。

A 漏掉队内算法和迁移，无法完整执行；B 漏掉层数和层间优先级；C 虽列后三项，仍未确定有几个队列。仅建立多个静态队列不等于多级反馈，进程必须能按规则改变层级。各队列的时间片大小也通常与层次相关，属于具体调度策略的一部分。

答案：B。

安全性检测先计算 Available，再以“总需求-已分配”得到还需资源 Need，不能把总需求直接与可用量比较。已分配合计 A=5、B=6，所以可用量为 (1,0)。P1、P2、P3 的 Need 分别为 (2,1)、(1,0)、(2,2)。

释放时加的是原已分配资源，检测中借给它的 Need 会随完成一并归还，所以净更新 Work+=Allocation。序列 P2、P1、P3 安全，选 B。A 的首个 P1 不满足；C 在 P2 后选 P3，B 类还少 1 个；D 被上表反证。

答案：D。

有效访存时间是一次逻辑访存实际耗时的平均值，不只看 RAM 的访问速度。设缺页率为 p，可概括为 $(1-p)T_{正常}+pT_{缺页}$。I 决定昂贵缺页事件出现频率；III 决定正常内存访问及处理中的内存访问耗时。

缺页时可能读入所需页面、写回脏页，所以 II 磁盘读写时间影响缺页代价；还需进入内核、选牺牲页、修改表项、恢复执行，IV 缺页处理程序的 CPU 时间同样占实际时间。因此四项全有影响，选 D。A 漏缺页频率和软件开销，B 漏磁盘与内存，C 漏通常最昂贵的磁盘。不能以缺页由操作系统处理为由，把它的时间排除在用户进程一次访存的等待之外。

答案：B。

父子进程是创建关系，不是线程关系。一般每个进程有自己的虚拟地址空间和保护边界，因此 B 的“共享虚拟地址空间”错误。创建时子进程可以复制父进程地址内容，写时复制也可暂时共享底层物理页，但两个虚拟空间的映射和修改仍分别管理，不等于所有地址内容始终共同改变。

A 正确：父子可都处于可运行状态，并发执行，不要求父亲一直等孩子结束。C 正确：各有不同 PCB，记录各自状态、寄存器、资源等。D 正确：同一临界资源需要互斥访问，亲子身份不能豁免。共享打开文件或显式共享内存是特定资源共享，也不能据此说整个虚拟地址空间共享。选择错误项 B。

答案：D。

设备独立性让应用使用统一逻辑名称和接口，把具体物理设备差异交由操作系统及驱动处理。A 正确：设备可抽象成特殊文件，用文件名和统一操作访问。B 正确：用户程序使用逻辑设备名，不必直接写硬件端口或某台设备编号。C 正确：系统要建立逻辑名称到物理设备的映射，才能将请求交给实际驱动。

D 错：换成提供同类功能的新设备时，系统调整映射、驱动等即可，通常无需修改使用逻辑接口的应用程序；这正是设备独立性的目的。逻辑名称不必等于实际物理设备标识，同一个名称也可以在系统配置改变后映射到另一台设备。故选错误项 D，不能把驱动可能需变化误认为所有应用都必须重写。

答案：B。

目录项的文件名用于查找，索引节点号用于唯一关联文件的控制信息。4 B 节点号有 32 位，最多区分 $2^{32}$ 个编号，所以文件数量上限不可能超过 $2^{32}$，B 正确，实际还可能受保留编号、磁盘空间等限制。

每名最多 60 个小写字母，名字可能数很大，仅长度 60 就有 $26^{60}$ 种，远大于 $2^{32}$，不是本题瓶颈。A 的 $2^{26}$ 将 26 种字母当成编号位数；C 的 $2^{60}$ 把 60 字节文件名当成 60 位唯一编号；D 的 $2^{64}$ 将目录项的 64 字节长度当成 64 位编号，也都错误。目录项总体多长不决定可编码多少不同索引节点。

答案：C。

I 是忙则等待/互斥要求：同一临界资源不能同时由两个进程在临界区访问。II 是空闲让进：资源无人占用时应允许符合条件的进程进入，不能无故阻止。III 是有限等待：申请者不能无限期被其他进程越过，避免饥饿。三者是实现临界区互斥机制必须满足的基本要求。

IV 立即放弃 CPU 属于让权等待策略，能节省无效忙等，但不是所有正确互斥算法都必须采用；例如适当的自旋算法可满足互斥、进展及有限等待，而等待期间仍占 CPU。因此选 I、II、III，即 C。A、D 错含 IV 且漏基本条件，B 漏 I。应区分正确性条件与提高 CPU 利用率的等待实现策略。

答案：C。

协议三要素中，语法规定报文字段、编码和格式；语义规定字段含义及应采取的动作；时序规定事件先后和时间关系。图的纵向是时间，两个纵线是发送方、接收方，箭头展示先发送、收到响应后再继续发送的过程，直接描述的是 III 时序。

图中没有画出报文的字段结构或各字段长度，不能据此判定 I 语法；也没有给控制字段的值及相应具体解释，不能据此判定 II 语义。因此 C 正确，A、B 判断错了维度，D 多列 I、II。实际协议当然需要三者，但题目问这张图展示的要素，不能因三者对协议都必要就选择全部。

答案：B。

虚电路网络先建立一条逻辑连接，在沿途设备中设置转发表项，后续分组沿该路径转发。C 正确：建立时要进行路由选择。D 正确：转发依据局部虚电路标识 VCID 查表，不必每个分组重新选择路径。A 正确：同一虚电路分组按同一路径通过，按本题模型可保持传输顺序。

B 错：虚电路是逻辑路径，链路仍可由许多连接统计复用，不必为每条虚电路预分配固定带宽；是否资源预留取决于具体服务。固定专用资源是电路交换的典型特征，不能看到“电路”二字就把它移到虚电路分组网络。因此选择错误项 B。逻辑连接存在不等于整条物理通道被该连接独占。

答案：C。

集线器是物理层转发设备，一个端口收到信号就向其他端口重复，所连主机共享介质访问，同一集线器及其连接段属于同一冲突域。图中四个集线器接在交换机不同端口上，交换机隔离这些共享段，因此需计四个共享冲突域，不能按上方两个交换机各算一个。

广播域看广播帧能到哪里：交换机与集线器通常转发广播，不隔离广播域；中间路由器不把链路层广播转到另一侧。因此左侧交换机及两组主机是一个广播域，右侧是另一个，共 2 个。结果为 4、2，选 C。A 少算冲突域，B 少算冲突域且多算广播域，D 把每个集线器组误当作独立广播域。两种域的隔离设备不同。

答案：D。

停等一次只发一帧，必须收到确认后才发下一帧，所以一轮时间包括数据帧发送、到乙传播、确认发送、回甲传播。题中确认帧与数据帧同为 1000 B，不能像常见短 ACK 题那样忽略确认发送时间。

每帧 $1000\times8=8000$ bit，在 $10\,\mathrm{kbps}=10000$ bit/s 下发送需 0.8 s；单向传播 0.2 s，往返 0.4 s。周期 $0.8+0.2+0.8+0.2=2$ s，有效数据发送占 0.8 s，最大利用率 $0.8/2=40\%$，选 D。A 的 80% 无法包含所有等待，B 的 66.7% 忽略 ACK 发送，C 的 44.4% 少算一段传播。无需再加题目未给的处理开销。

答案：A。

CSMA/CA 通过不同帧间间隔安排优先级。普通站点开始争用发送机会，先等待较长的 DIFS；已建立的一次交换中，CTS、数据续传和 ACK 用较短的 SIFS，使响应优先于其他站点的新争用，避免交换被打断。

图中 H 发 RTS 前的 IFS1 属于开始争用，使用 DIFS。AP 回 CTS 前 IFS2、H 收 CTS 后发数据前 IFS3、AP 收数据后回 ACK 前 IFS4，都是同一握手/数据交换内的响应，使用 SIFS。因为 DIFS>SIFS，最长是 IFS1，选 A；B、C、D 都对应较短 SIFS。退避时间可以另外影响发送等待，但本题比较已标出的 IFS，不把随机退避误当成其中一个帧间间隔。

答案：D。

TCP 窗口可按不同阶段增长。慢开始通常每 RTT 近似翻倍，8→16→32 KB 只需 2 RTT，是较快情形；拥塞避免则每 RTT 约增 1 MSS。本题问“不出现拥塞”时的最长时间，意味着无需考虑窗口下降，应取持续拥塞避免的较慢增长。

MSS=1 KB，从 8 KB 增至 32 KB 需增加 24 个 MSS，耗费 24 RTT；RTT=2 ms，所以时间 $24\times2=48$ ms，选 D。A 的 4 ms 是慢开始的快速情形，B 的 8 ms 与最慢增长不符，C 的 24 ms 漏乘 RTT 的 2 ms。没有给阈值并不影响最长值，只要窗口从 8 KB 起一直采用每轮加一即可达到此上界。

答案：C。

TCP 数据按字节编号，SYN 与 FIN 各消耗一个序号，即使本身不携带应用数据。甲的 SYN 序号为 1000，故第一个应用数据字节应从 1001 开始；FIN 序号为 5001，说明此前应用数据的最后字节为 5000，FIN 自己的序号不属于应用数据。

应用数据范围为 1001～5000，数量 $5000-1001+1=4000$ B，等价于 $5001-1000-1=4000$，选 C。B 的 4001 未扣 SYN，A 又多计一个端点，D 的 3999 则重复扣除了 FIN；用“FIN 序号减首数据序号”已经排除 FIN，不应再扣一次。题设无重传，发送次数与实际数据字节数无需额外区别。

答案：D。

请求 http://www.abc.com/index.html 需先获得 www.abc.com 的地址，再建 TCP 并请求纯文本主页。按题目基础 HTTP 模型，未建立连接时 TCP 三次握手需 1 RTT，随后 HTTP 请求与页面返回需 1 RTT，共 20 ms；纯文本没有需另取的图片等对象。

最短时本机或本地域名服务器已缓存目标地址，本地查询的其他时延忽略，DNS 不增加外部 RTT，所以最短 20 ms。最长时本地域名服务器无缓存，替 H 依次向根、com 顶级、abc.com 权威服务器发迭代查询，各等一次 10 ms RTT，DNS 共 30 ms，再加 Web 的 20 ms，最长 50 ms，选 D。A、B 的最短 10 ms 漏建连；C 的最长 40 ms 漏一轮 DNS。递归服务由本地服务器替主机完成查询，不意味着远端只需查一次。

**（1）化简与设计思想。**三重枚举分别从三数组取一个值要 $O(nmp)$。先观察距离只依赖最大值与最小值：把三个值排序为 $u\le v\le w$，则

$$D=(v-u)+(w-v)+(w-u)=2(w-u)=2(\max-\min).$$

三指针从三个升序数组开头出发，每轮算当前距离并更新最优值，再只把当前最小值所在数组的指针向前移动。如果保留该最小值，却增大另两个值，最大值只会不变或变大，不可能使当前范围更窄，所以有机会改善必须去掉这个最小值。任一数组耗尽即结束，距离为 0 时达到理论下限，也可提前结束。

示例中的关键状态如下，移动的是本轮最小值对应指针：

**（2）C++ 实现。**三个集合按题设非空且已升序，n、m、p 为长度。

#include <algorithm>
#include <climits>
#include <iostream>

long long minTripleDistance(const int a[], int n,
                           const int b[], int m,
                           const int c[], int p) {
    int i = 0, j = 0, k = 0;
    long long best = LLONG_MAX;
    while (i < n && j < m && k < p) {
        long long lo = std::min({(long long)a[i], (long long)b[j], (long long)c[k]});
        long long hi = std::max({(long long)a[i], (long long)b[j], (long long)c[k]});
        best = std::min(best, 2 * (hi - lo)); // 不需计算三次绝对值
        if (best == 0) break;
        if (a[i] <= b[j] && a[i] <= c[k]) ++i; // 最小值并列时移动任意一个
        else if (b[j] <= a[i] && b[j] <= c[k]) ++j;
        else ++k;
    }
    return best;
}
// 输出：std::cout << minTripleDistance(a,n,b,m,c,p);

**（3）正确性与复杂度。**在一轮中，保留已选最小值、配上另两数组当前及后面的值，所得最大最小差都不会小于当前候选；因此排除该最小值不会漏掉更优方案。反复应用这一排除规则，最优结果始终保留在已记录候选或未排除范围内。并列最小值时也可移任意一个，因为另一最小值留着只会阻止范围收窄。

每轮仅前进一个指针，三指针总共最多前进 n+m+p 次，每轮工作常数，时间 $O(n+m+p)$；变量固定，额外空间 $O(1)$。负数、集合只有一个元素、重复值都可处理；先转 long long 再作差，避免 int 两端值相减溢出。示例返回 2，若三集合含同一个值则可返回 0。

**（1）适合的结构。**采用二叉编码树，即 0/1 字典树。根代表空前缀，左边标 0、右边标 1；从根走到某字符结点的边标序列就是该字符编码。结点可包含两个孩子指针、是否终止及字符值。前缀特性保证字符结点没有后续孩子，因而字符只在叶/终止结点保存；中间结点仅表示共同前缀，树高最多 L。不要求所有内部结点都有两个孩子，也不要求给定编码就是哈夫曼最优码。

**（2）译码。**指针从根开始，逐位读取输入，0 走左、1 走右；到字符结点后输出该字符，并把指针复位到根，继续读取下一个码字。比如 A=0、B=10、C=11，串 01011 可依次译为 A、B、C，不需要额外分隔符。若走到空分支，则位串不属于该编码；若输入用完时仍停在非根的中间结点，则末尾只是部分码字，不能作为完整字符串输出。每位处理一次，译码时间为 $O(\text{输入位数})$。

**（3）检查前缀特性。**从空树逐个插入码字，按位走并在缺少分支时建结点。若码字尚未读完就遇已有字符终点，旧码是新码前缀；若读完后当前结点已有孩子，新码是某个旧码前缀；若当前已经存字符，是两个字符使用重复编码，也不能唯一译码。任一情形拒绝，否则把当前结点标为字符终点。

这能同时检查长码后插短码、短码后插长码两种顺序。例如先插 10 再插 101，在读完前遇到 10 的终点；反过来插，在 10 终点发现还有孩子。字符数≥2 时空码字也不能接受，因为它是所有码字的前缀。若所有插入均成功，即具有前缀特性；总时间与码字总位数成正比，空间也至多为该数量级。

**（1）没有乘法指令仍可计算。**二进制乘数可展开为 $y=\sum y_i2^i$，因此 $xy=\sum y_i(x\ll i)$。软件循环逐位检查 $y_i$，该位为 1 就将对应移位后的被乘数加到部分积。例如 $5\times6=5\times(2+4)=(5\ll1)+(5\ll2)=30$。无符号用移位加法，有符号可另处理符号或采用补码乘法规则。编译器可展开为多条指令或调用软件乘法程序，ALU 不必有独立乘法功能。

**（2）控制逻辑作用。**控制器按算法顺序测试乘数或相关位，决定本步加、减或不做算术操作；选择 ALU 输入，控制位移器移位方向与位数，更新部分积、被乘数、乘数寄存器，再根据计数或状态判断是否重复、结束。它把现有部件协调成多步乘法运算，并不是让 ALU 突然能直接做乘法。

**（3）执行时间比较。**题设三种组织中，①无乘法指令的软件实现最长：每一步还有取指、译码、条件分支等开销。②有乘法指令但复用 ALU、位移器，硬件控制减少软件指令开销，却仍需多次迭代。③阵列乘法器最短：专用硬件并行产生、相加部分积，减少串行迭代。这里比较的是所给组织的通常实现，不意味着所有阵列乘法器必在一个时钟内完成，实际周期还取决于硬件延迟与时钟设计。

**（4）完整乘积、截断与溢出。**x=$2^{31}-1$=7FFFFFFFH，y=2，二者无论解释为带符号还是无符号都为正数，数学乘积 $2^{32}-2$，两种乘法指令的完整 64 位乘积相同：

00000000 FFFFFFFE H

umul 返回低 32 位 FFFFFFFEH，表示无符号数 4294967294，小于最大值 $2^{32}-1$，不溢出。imul 的数学结果超过带符号上界 $2^{31}-1$，发生有符号溢出；硬件若只保留低位，FFFFFFFEH 按补码解释为 -2，不能代表正确数学积。C 中有符号溢出不能当作规定必返回 -2 的行为。

无符号乘法的 n 位结果范围为 $0\sim2^n-1$，完整 2n 位乘积的高 n 位全为 0 时无溢出，非零则溢出。有符号判据不同：高半须等于低半符号位的扩展；本例低半符号位为 1、高半却全 0，所以有符号溢出。完整乘积能保存，并不保证截成半长后仍能按原类型表示。

**（1）地址划分与控制位。**每个 Cache 的数据容量 32 KB，64 B 一行，共 $32\times1024/64=512$ 行。8 路组相联每组 8 行，共 64 组；块内偏移 $\log_2 64=6$ 位，组号也为 6 位，因此 32 位地址中的 Tag 为 $32-6-6=20$ 位。

**本题采用的考试默认约定是：每行保存自己在本组中的 LRU 使用次序，编号为 0～7。**8 种次序要用 $\log_2 8=3$ 位表示，所以每行 LRU 字段为 3 位。例如把 0 记为最近使用、7 记为最久未用，命中某行时将它移到次序 0，并相应调整其他行的次序；组满时替换次序 7 的行。这里计算的是这种每行次序编码，不是所有精确 LRU 硬件编码的存储下界；若另行指定不同编码方案，需要按该方案计算。

直写时，每次写 Cache 也更新主存，因此不需要标记“尚未写回主存”的修改/脏位；仍需有效位区分初始空行。3 位 LRU、20 位 Tag 和有效位分别承担替换、识别主存块和判断行是否有效的作用，不能混淆。

**（2）数组缺失次数。**起址 008000C0H 的低 6 位为 0，是 64 B 边界。每块可容纳 $64/4=16$ 个 int，1024 个元素占 4096 B，覆盖 $1024/16=64$ 块。连续读写一块时，首元素的读取触发缺失、调入整块，其他 15 个元素读取及各元素随后的写入均命中。64 个连续块分布于 64 组，且数组远小于容量，没有自身导致的替换，所以缺失 64 次。k 在寄存器中，不额外占数据块；每元素先读后写，直写向主存写回不等于发生一次新的 Cache 缺失。

**（3）第一次取指。**对 00010003H，偏移 $A\bmod64=3$，组号 $(A\gg6)\bmod64=0$，Tag $A\gg12=00010\mathrm H$。先用组号定位指令 Cache 第 0 组，再并行比较该组八行的有效位与标记。初始都无效，因此不命中。

控制器向主存请求从块首地址 00010000H 开始的 64 B，调入第 0 组任一空行，写 Tag=00010H、置有效位并更新 LRU；再从该块偏移 3 处取得所需指令内容，交 CPU 使用。若将来组满，才选 LRU 行替换；直写无需先写回脏行。题目未指定指令长度，若实际指令跨 64 B 块边界，其他字节还要查询下一块，不能把一个地址直接等同于完整指令字长。

依赖关系是 A→C、B→C、C→E、D→E，不要求 A、B、D 互斥。用四个完成事件信号量 ac、bc、ce、de，初值均为 0，分别代表 A、B 可让 C 继续，以及 C、D 可让 E 继续。wait 在事件尚未发生时阻塞，signal 在对应操作完成后发出许可。

CoBegin
线程 A:
    执行 A
    signal(ac)
线程 B:
    执行 B
    signal(bc)
线程 C:
    wait(ac)
    wait(bc)
    执行 C
    signal(ce)
线程 D:
    执行 D
    signal(de)
线程 E:
    wait(ce)
    wait(de)
    执行 E
CoEnd

C 顺序 wait(ac)、wait(bc)，只有两项都成功后才执行，因此既满足 A 完成，也满足 B 完成。E 同理等待 ce 与 de。signal 先发生也不会丢失，因为许可留在信号量中，后来的 wait 可直接消费；因此不限定哪个前驱先结束。A、B、D 之间可并发，C 完成后与尚未结束的 D 也可并行。

不能把两个前驱都 signal 到一个信号量后只 wait 一次，这只能保证至少一个前驱完成，不保证两者都完成。本题是每个操作执行一次的同步，可用独立事件清楚表达；若这些操作重复多轮，还需明确每轮许可对应关系，不能直接把不同轮次的完成混在一起。

**（1）逐层地址计算。**二维 C 数组按行存放，下标从 0 起。a[1][2] 前有一整行 1024 个元素和本行 2 个元素，字节偏移 $(1\times1024+2)\times4=4104=1008\mathrm H$，虚拟地址为 $10800000\mathrm H+1008\mathrm H=10801008\mathrm H$。

图示地址字段为 10 位目录号、10 位二级页号、12 位偏移，页大小 $2^{12}=4096$ B。分别提取：目录号 $(VA\gg22)=042\mathrm H$，二级页号 $(VA\gg12)\mathbin{\&}3FF\mathrm H=001\mathrm H$，偏移 008H。这里“页号”指第二级表的索引，不是合并后的 20 位完整虚页号。

目录项 4 B，所以其物理地址为 $00201000\mathrm H+042\mathrm H\times4=00201108\mathrm H$。该项页框号 00301H 指向二级页表，其物理基址为 $00301\mathrm H\times1000\mathrm H=00301000\mathrm H$；再加页号×4，所需页表项地址为 $00301000\mathrm H+1\times4=00301004\mathrm H$。该页表项地址仍不是 a[1][2] 的最终物理地址，还需读取它的页框号并加 008H；题目未给这个内容。

**（2）连续性。**数组全部元素组成连续的虚拟地址区间，以便由基址和下标计算地址，区域大小 $1024\times1024\times4=4$ MB。页表逐页建立映射，物理页框可分散，甚至部分页面暂在外存，所以不要求物理空间连续。虚拟连续与物理连续是两个独立层次。

**（3）局部性。**每行 1024×4=4096 B，起址页对齐，恰好一行一页。按行连续遍历可在同页访问 1024 个相邻元素，还能充分利用 Cache 块的空间局部性。按列相邻访问间隔一行，即 4096 B，每次跳到另一页；当页框有限时，重访同一页前可能已被换出，导致更多缺页。因此按行更好，原因是数组的实际存放次序，而不是行列下标本身有固定优劣。

**（1）地址重叠与映射配置。**图中两个私网都使用 192.168.1.x，H2 的 192.168.1.2 与左侧 Web 服务器的 192.168.1.2 是不同主机。H2、H3 不能直接以该服务器私网地址访问，否则会把目的当作自己的本地网段。应在 R2 配置静态目的地址/端口转换，把外网 TCP 80 映射到内部 Web 服务器 TCP 80：

H2、H3 使用 R2 的外网地址 203.10.2.2 访问，默认 HTTP 端口为 80。常规主机默认网关设为本地 R3 的 192.168.1.1，R3 按图示 NAT 将右侧私网流量转换为其公网源地址 203.10.2.6；R1～R3 之间还须具备正常可达路由。静态映射保证主动从外部进入的请求能定位服务器，单靠动态源 NAT 并不能公开一个可访问的服务。

**（2）逐跳 IP。**H2 构造请求时，源为自身私网地址，目的为服务器公开的 R2 外网地址。R3 做源 NAT，R1 只按路由转发，R2 按静态映射做目的 NAT：

R3 转发后源变为 203.10.2.6，目的仍 203.10.2.2；经过 R2 后目的变为 192.168.1.2（左侧服务器），源仍 203.10.2.6。尽管出发源和最终目的都写 192.168.1.2，它们位于不同 NAT 域，没有被当成同一局域网主机。动态 NAT 还可能调整 H2 的源端口，题目未给该端口，不凭空填写；目的 HTTP 端口按静态规则为 80。回包分别利用 R2 静态规则和 R3 已建立的转换表逆向转换，才能回到 H2。