2023年计算机408真题

答案：D。

顺序表把元素放在一段连续的存储空间中。“按位置取元素”与“按值找元素”是两种不同操作：位置已知时可以直接算地址，值已知时则需要比较关键字。

设首元素地址为 $B$，每个元素占 $w$ 字节，第 $i$ 个元素的地址就是

$$B+(i-1)w.$$

这个计算只包含固定次数的加法、乘法及一次访问，与表长 $n$ 无关，因此获取第 $i$ 个元素的时间复杂度为 $O(1)$。

• A 错：按给定值查找时，即使利用有序性进行折半查找，平均复杂度也是 $O(\log n)$，不能直接由值算出元素位置。
• B 错：插入时不仅要确定插入位置，还要把该位置及其后的元素向后移动。平均移动数量随 $n$ 增长，平均复杂度为 $O(n)$。
• C 错：删除第 $i$ 项以后，需要把后面的 $n-i$ 项向前移动，以保持顺序存储的连续性。等概率删除各位置时，平均移动 $(n-1)/2$ 项，复杂度为 $O(n)$；仅删除末项的特殊情况才是 $O(1)$。
• D 对：题目已经给出位置 $i$，直接按地址公式访问即可。

答案：C。

双向链表中，相邻结点必须同时满足“前结点的 next 指向后结点”和“后结点的 prev 指向前结点”。令原来的后继结点为 $q$，插入前有 p->next=q、q->prev=p；插入后应形成 p ↔ s ↔ q。

题目已经执行

s->next = p->next;   /* s 的后继成为原后继 q */
p->next = s;         /* p 的后继改为 s */

所以接下来要补齐的是 s->prev=p 和 q->prev=s。注意，此时 p->next 已经指向 s，不能再用它表示 q；q 仍可通过 s->next 找到。

C 的执行过程为：

s->prev = s->next->prev;  /* q->prev 尚为 p，所以令 s->prev=p */
s->next->prev = s;        /* 令 q->prev=s */

四个必要指针均连接正确。

• A 错：s->next->prev=p 仍把 q 的前驱设为 p，没有让 q 指向新结点 s。
• B 错：第一句实际上是 s->prev=s，第二句又把它覆盖为 p。最终 s 的前驱虽正确，q 的前驱仍为 p，遗漏了 q->prev=s。
• C 对：先利用尚未改写的 q 的前驱得到 p，再修正 q 的前驱。
• D 错：p->next->prev=s->prev 实际成为给 s->prev 赋它自身的值，未建立正确前驱；第二句仍让 q 的前驱指向 p。

p 不是尾结点保证 q 存在，因此 C 中对 s->next->prev 的访问有效。

答案：A。

稀疏矩阵的三元组通常为“行号、列号、元素值”，只保存非零元素。例如，三元组 $(2,3,5)$ 表示第 2 行第 3 列有非零值 5，但不能说明矩阵是否还存在更多全零行或全零列。

因此，必须另外保存：

• I，总行数：末尾的全零行不会出现在三元组中，不能靠最大非零行号确定。
• III，总列数：末尾的全零列同样无法由三元组确定。

II“含非零元素的行数”可由三元组中不同的行号计数得到，IV“含非零元素的列数”也可由不同的列号计数得到；它们不是恢复矩阵完整尺寸必需的独立信息。极端情况下，矩阵全为零，三元组表为空，但矩阵的总行数和总列数仍须保存。

• A 对：恰好保存 I、III。
• B 错：IV 不能替代总列数 III。
• C 错：只知道哪些行列有非零项，无法确定全零边界及矩阵尺寸。
• D 错：II、IV 可以统计得到，不属于题目问的“还需要保存”的必要信息。

答案：B。

哈夫曼编码每次合并权值最小的两棵树。字符权值是出现频次；字符的编码长度是其叶结点深度。总加权路径长度 WPL 是“频次乘码长”的总和，加权平均码长则为 WPL 除以总频次。

对权值 $3,4,5,6,8,10$，合并过程如下：

每合并一次，该子树的所有叶结点深度都增加 1，WPL 恰好增加本次新权值。因此

$$\mathrm{WPL}=7+11+15+21+36=90,\qquad \sum f_i=3+4+5+6+8+10=36.$$

加权平均码长为

$$\bar L=\frac{90}{36}=2.5.$$

也可以核对各字符码长：频次为 3、4、5、6 的字符各需 3 位，频次为 8、10 的字符各需 2 位，故 WPL 为 $3(3+4+5+6)+2(8+10)=90$。

• A 的 2.4 不等于 $90/36$。
• B 的 2.5 正好是按频次加权后的结果。
• C 的 2.67 不是本次哈夫曼树的加权平均码长，不能把码长直接作不带频次的平均。
• D 的 2.75 也不符合本次合并得到的 WPL。

答案：A。

后序遍历的顺序是“左子树、右子树、根”，前序遍历是“根、左子树、右子树”。需要先根据固定树形和后序序列确定每个结点上的字符，再改变遍历方式，不能直接把后序序列倒过来。

图中根的左子树有 4 个结点，右子树只有 1 个结点。后序序列为 f,d,b,e,c,a，因此：

1. 最后一个 a 是整棵树的根。
2. 右子树只有一个结点，对应根之前的 c。
3. 左子树的后序序列为 f,d,b,e，最后的 e 是左子树根。
4. e 的右孩子是单结点 b；其左子树的后序为 f,d，所以左孩子是 d，d 的右孩子是 f。

填好后的树为：

        a
       / \
      e   c
     / \
    d   b
     \
      f

从根开始，先访问 a，再前序遍历左子树 e,d,f,b，最后访问 c，得到 a,e,d,f,b,c。

• A 对：符合根、左、右的访问次序。
• B 错：访问 a 后立即访问右子树 c，越过了尚未遍历的左子树。
• C 错：以 c 开头，而前序的第一个结点必须是根 a。
• D 错：以 d 开头，也没有先访问根 a。

答案：B。

本题所有边的权值都是 1，因此一条路径的总权值就是它经过的边数。求最短路径等价于求“从起点到该顶点至少需要走几条边”。

广度优先搜索 BFS 按距离分层：先访问距离为 0 的起点，再访问距离为 1 的顶点，然后访问距离为 2 的顶点，依此类推。若某顶点第一次在第 $k$ 层被发现，就不存在更少于 $k$ 条边的路径，否则它应在更早一层被发现。因此 III 一定能够给出从指定起点到各顶点的最短路径。

Prim 和 Kruskal 求的是最小生成树，目标是使连接所有顶点的树的总边权最小，目标与单源最短路径不同。等权图的任意生成树都具有相同总权值，但树上的路径可能绕远。例如，四个顶点组成环 s-a-c-b-s，各边权均为 1；生成树可以选 s-a、a-c、c-b，此时树中 s 到 b 要走 3 条边，而原图中有直接边 s-b，只需 1 条边。Prim 在等权边的合法选择次序下以及 Kruskal 在合法的等权排序次序下，都可能得到这棵树。

• A 错：Prim 不保证所有起点到各顶点的树上路径最短。
• B 对：仅 BFS 具有这里所需的分层最短路径保证。
• C 错：两种最小生成树算法均不具备该保证，并且遗漏了 BFS。
• D 错：把最小生成树误当成了最短路径树。

答案：B。

B 树是多路平衡查找树，一个结点可以存放多个关键字。关键字不仅存放在最下层结点，也可以存放在内部结点；查找时先在当前结点比较，再决定是否进入某个孩子。

逐项判断：

• I 正确。插入造成结点超过容量时，需要分裂并把中间关键字提升到父结点。若一直分裂到原根，需建立一个新根，树高增加 1。
• II 正确。这里指成功删除已有关键字。若关键字已在最下层结点，直接删除或调整该层结点；若在内部结点，通常以其前驱或后继关键字替换，再到最下层删除替代关键字。因此删除最终会改变最下层的含关键字结点，必要时还会发生借关键字或合并。
• III 错误。若关键字在内部结点比较时已经找到，查找立即成功，无须再走到最下层。
• IV 错误。新关键字最初插入最下层结点，但在分裂时可能被提升。例如三阶 B 树某根结点原含 [10,30]，插入 20 后暂为 [10,20,30]，分裂后 20 成为新根，最终位于内部结点。

这里的叶结点按含关键字的最下层结点理解；关键点是不能把 B 树当成“所有记录都只在叶层”的结构。

• A 错：漏掉正确的 II。
• B 对：恰好包含 I、II。
• C 错：III、IV 均错误。
• D 错：I、II 正确，但额外选入了错误的 IV。

答案：B。

折半查找每比较一次，就在有序表的中间位置检查一个关键字；若未找到，继续查找的范围最多约减半。最坏比较次数等于折半查找判定树的最大层数。

$n$ 个元素的最大比较次数为

$$\lfloor\log_2 n\rfloor+1.$$

由于 $2^9=512\le600<1024=2^{10}$，有

$$\lfloor\log_2 600\rfloor+1=9+1=10.$$

也可以用判定树容量判断：9 层至多容纳 $2^9-1=511$ 个关键字，容纳 600 个关键字必须达到第 10 层。

• A 错：9 次比较对应的判定树最多容纳 511 个关键字，不足以覆盖 600 个。
• B 对：最大为 10 次关键字比较。
• C 错：30 不是折半查找的最大层数；本题计数的是与被查找关键字的比较次数。
• D 错：300 把问题按表长的一半估计，没有考虑查找范围会连续减半。

答案：C。

线性探查从散列地址开始，依次检查后面的槽，走到表尾时回到槽 0。查找失败只有在遇到“从未使用的空槽”时才能停止；标准逻辑删除采用删除标记，该标记可供以后插入使用，但查找仍需越过它，以保留原探测链。

散列函数为 $H(k)=(k+4)\bmod5$，依次插入：

删除 25 后的表为：

平均查找长度计入最终用于判定失败的空槽访问，并假设 5 个初始散列地址等可能。逐个计算：

所以

$$\mathrm{ASL}_{\text{失败}}=\frac{1+3+2+1+2}{5}=\frac95=1.8.$$

• A 错：只算一次初始访问，忽略了冲突链。
• B 错：1.6 对应把槽 4 直接当成从未使用的空槽，本题按标准逻辑删除保留标记，起点 4 应检查两槽。
• C 对：五种起点的探测次数总和为 9。
• D 错：2.2 对应总计 11 次探测，与逐起点计算不符。

删除标记用于保证一般情况下的查找正确性；本题没有采用压缩探测链或按空槽边界清理标记的额外删除规则。

答案：C。

排序稳定是指：两个记录的关键字相等时，排序后仍保持它们原来的先后顺序。只把关键字排成有序序列，不能证明算法稳定；判断时可把相等关键字分别标为 $k_a$、$k_b$ 来跟踪身份。

逐项判断：

这里按这些算法的常规实现判断，归并排序的相等关键字处理及基数排序的每趟处理均采用稳定规则。

• A 错：把稳定的 II 归并排序列为不稳定，且遗漏 III、IV。
• B 错：II、V 恰好是稳定的两种算法。
• C 对：不稳定的是 I、III、IV。
• D 错：遗漏 I 希尔排序，并错误地加入 V 基数排序。

答案：D。

快速排序的一次划分以枢轴为界，把较小的元素放在左侧、较大的元素放在右侧。划分后的两边内部可以仍然无序，但枢轴必须满足“左侧所有元素不大于它，右侧所有元素不小于它”。

对序列 68,11,70,23,80,77,48,81,93,88，逐个检查候选：

因此枢轴是 81。右侧出现 93,88 的降序并不影响判断，因为“一次划分”不要求子区间已经完成排序。

答案：C。

主频表示每秒的时钟周期数，CPI 表示平均每条指令所需的周期数。因此指令执行速度不能直接等同于主频，应先除以 CPI：

$$\mathrm{IPS}=\frac{f}{\mathrm{CPI}} =\frac{1.5\times10^9}{1.2} =1.25\times10^9\ \text{条/秒} =1.25\ \mathrm{GIPS}.$$

程序共执行 $5\times10^5$ 条指令，平均 CPI 为 1.2，所需周期数为

$$5\times10^5\times1.2=6\times10^5.$$

用户 CPU 时间为

$$T=\frac{6\times10^5}{1.5\times10^9} =4\times10^{-4}\ \mathrm{s} =0.4\ \mathrm{ms} =400\ \mu\mathrm{s}.$$

• A 错：把主频除以 CPI 的关系算反，0.8 GIPS 不正确，时间一项正确。
• B 错：速度与时间均不正确，0.4 μs 比正确时间少了 1000 倍。
• C 对：速度为 1.25 GIPS，用户 CPU 时间为 0.4 ms。
• D 错：速度正确，但把毫秒误写成微秒。

这里计算的是执行这些指令消耗的用户 CPU 时间，不包含等待 I/O 等未占用 CPU 的时间。

答案：A。

本题 short 用 16 位补码表示。补码中，非负数与普通二进制相同；负数 $-a$ 的 16 位机器数可由 $2^{16}-a$ 求得，也可把 $a$ 的 16 位二进制逐位取反后加 1。

先写出正数：

$$8190=8192-2=\mathrm{1FFEH}.$$

按 16 位取反得到 E001H，再加 1：

$$\overline{\mathrm{1FFEH}}+1 =\mathrm{E001H}+1 =\mathrm{E002H}.$$

直接计算也有 $65536-8190=57346=\mathrm{E002H}$。

• A 对：E002H 作为有符号 16 位补码表示 $57346-65536=-8190$。
• B 错：E001H 是正数 8190 的按位取反结果，还少了“加 1”；它的补码值为 -8191。
• C 错：9FFFH 的有符号值为 $40959-65536=-24577$，不是 -8190。
• D 错：9FFEH 的有符号值为 $40958-65536=-24578$，也不符合题值。

不要把补码当作“最高位为符号、其余位直接表示绝对值”的原码。

答案：A。

IEEE 754 单精度由 1 位符号位、8 位阶码和 23 位尾数字段组成。阶码全 0 且尾数非零时，表示非规格化数，数值公式为

$$x=(-1)^s(0.f)_2\,2^{1-127}.$$

这时没有规格化数使用的隐含前导 1，实际指数为 -126。

将 8020 0000H 分解：

因此

$$x=-0.01_2\times2^{-126} =-2^{-2}\times2^{-126} =-2^{-128}.$$

• A 对：得到 $-2^{-128}$。
• B 错：错误地使用隐含前导 1，并将全零阶码当成指数 -127。
• C 错：指数 -126 正确，但非规格化尾数应为 $0.01_2$，不是 $1.01_2$。
• D 错：NaN 要求阶码全为 1 且尾数非零，本题阶码全为 0。

答案：C。

30 根地址线可表示 $2^{30}$ 个地址，按字节编址意味着共有 $2^{30}$ B 的地址空间。地址从 0 开始，因此全部空间为

$$\mathrm{00000000H}\sim\mathrm{3FFFFFFFH}.$$

RAM 与 ROM 的容量比为 3:1，所以 ROM 占总空间的四分之一，即 $2^{28}$ B。RAM 位于连续低地址区，先占用 $3\times2^{28}$ B；ROM 的起始地址就是

$$3\times2^{28}=\mathrm{30000000H}.$$

ROM 结束于总空间的最高地址 3FFFFFFFH。划分结果为：

• A 错：容量虽为四分之一，却占用了低地址区，不满足 ROM 位于高地址区。
• B 错：10000000H～2FFFFFFFH 位于 RAM 区，且容量为 $2^{29}$ B，不是总容量的四分之一。
• C 对：起点、终点与容量均符合要求。
• D 错：40000000H 已超出 30 位地址能表示的最高地址 3FFFFFFFH。

结束地址应为“起点加容量减 1”，因为两端地址都计入区间。

答案：B。

OF 用于判断带符号运算是否超出可表示范围，CF 在本题的减法约定下表示无符号减法是否发生借位。题目给出 $100-200$ 时 CF=1，已经明确了“需要借位时 CF 置 1”的约定。

对带符号数：

$$10-(-20)=30.$$

30 可以由 int 表示，故 OF=0。正数减负数不等于一定溢出，必须检查真实结果是否越界。

再从同一机器数的无符号解释判断借位。设 int 宽度为 $w$ 位，-20 的补码位串按无符号数解释为 $2^w-20$。因此处理器的位串减法相当于

$$10-(2^w-20),$$

被减数小于减数，需要借位，故 CF=1。结果的低 $w$ 位仍是 30，与前面的带符号结果一致。

• A 错：OF=0 正确，但 CF 忽略了 -20 的补码按无符号数解释时很大。
• B 对：带符号结果没有溢出，无符号位串相减有借位。
• C 错：OF 应为 0，CF 应为 1，两项均错。
• D 错：CF=1 正确，但 OF=1 把有借位误当成了带符号溢出。

答案：A。

指令中的寄存器编号只告诉 CPU“使用哪一个寄存器”，还需寻址方式告诉 CPU“怎样解释该寄存器的内容”。

例如，假设某寄存器中存放 1000：

这两种情况下，寄存器编号和寄存器内的比特可以完全相同，只有指令指定的寻址方式不同。

• A 对：操作数的寻址方式决定寄存器内容是数据还是有效地址。
• B 错：操作数编码方式涉及整数、浮点数等位串如何表示数值，不能决定是否需要再次访问内存。
• C 错：同一个通用寄存器可以被不同指令用作数据寄存器或地址寄存器，编号本身不能区分。
• D 错：一个比特串既可能是数值也可能是地址，单看内容不能确定其用途。

答案：B。

组合逻辑元件只根据当前输入产生输出，不保存前一个时刻的状态；时序逻辑元件则能够保存状态，其内容在规定的时钟或控制条件下更新。

• I，ALU：对当前输入进行加减、逻辑运算等，输出由输入及操作控制信号决定，属于操作元件。
• II，PC：保存下一条待取指令的地址，属于状态元件。
• III，通用寄存器组：保存程序使用的数据，即使输入变化，已存内容也不会随意改变，属于状态元件。
• IV，MUX：按选择信号从多个当前输入中选出一个输出，不保存数据，属于操作元件。

所以操作元件为 I、IV。

• A 错：包含了状态元件 II，且遗漏 IV。
• B 对：仅 I、IV 是组合逻辑操作元件。
• C 错：II、III 都是保存状态的元件。
• D 错：比正确集合多选了 II 程序计数器。

答案：C。

五段流水线依次为取指、译码/取数、执行、访存、写回。转发技术可在结果尚未写回寄存器时，把已经产生的结果直接送给后面的使用者；它不能把尚未计算或读取出的结果提前产生。

本题依赖关系如下：

I2 虽然使用 I1 的结果，但可通过旁路取得 s2，正常进行地址计算。I3 紧邻 load，需要的 s3 来得太晚，发生 load-use 数据冒险，即使有旁路也必须等待。I3 又是条件分支，题设采用硬件阻塞处理控制冒险，I4 在分支方向未确定时也受到阻塞。

因此受阻塞的指令是 I3、I4。题目没有规定分支具体在哪一段完成判定，判断哪些指令阻塞即可，无须额外假定精确的阻塞周期数。

• A 错：只考虑了 I3 的数据冒险，遗漏 I4 的控制冒险阻塞。
• B 错：把能够通过转发继续执行的 I2 算作阻塞，却遗漏真正需要 load 数据的 I3。
• C 对：I3 因数据冒险等待，I4 因分支控制冒险等待。
• D 错：额外加入了无须停顿的 I2。

答案：D。

总线宽度为 64 位，即每次传送 $64/8=8$ B；32 B 的主存块必须分成

$$32/8=4$$

次数据读取。总线频率 1 GHz，所以一个时钟周期为

$$1/(10^9)=1\ \mathrm{ns}.$$

不支持突发传送意味着不能只发送一次块地址后连续取得四个数据；本题每个 64 位数据都要完成一次独立的读事务：

四次事务的时间为

$$T=4(1+6+1)=32\ \mathrm{ns}.$$

• A 错：8 ns 只够读取一个 64 位数据，即 8 B，不是整个 32 B 块。
• B 错：11 ns 相当于按“一次地址、一次准备、四次连续数据”的突发方式计算，不符合题设。
• C 错：26 ns 只计了 $4\times6$ ns 准备时间和 2 ns 总线开销，漏掉了四次独立事务各自所需的地址与数据传送。
• D 对：四个 64 位数据各需 8 ns，总计 32 ns。

答案：D。

异常和中断都会使 CPU 暂时转去执行处理程序，但它们的来源不同。异常通常由正在执行的指令引起，例如除数为 0、访问的页面不在主存；外部中断通常由键盘、磁盘等设备提出，用来通知 CPU 某个外部事件已经发生。

• A 正确：CPU 在执行指令的过程中检查是否出现异常。例如执行除法时才能发现除数为 0，进行地址转换时才能发现缺页。
• B 正确：外部中断与当前指令的执行过程通常没有直接关系，CPU 一般在当前指令执行完毕的边界检查中断请求，以便保存一个完整、确定的程序现场。
• C 正确：在本题通常的可屏蔽中断响应条件下，开中断使 CPU 可以响应有效的中断请求，随后保存现场并转入相应中断处理程序。
• D 错误：外部设备通过中断控制器向 CPU 发送的是中断请求。中断结束通知通常由 CPU 执行中断服务程序时发给中断控制器，用来表示本次中断处理已经完成。D 把请求与结束通知的来源、方向混淆了。

本题要求选择错误叙述，因此选 D。异常检测点、外部中断响应点和中断结束通知是三个不同概念。

答案：C。

区分 I/O 控制方式时，需要判断设备与主存之间的数据由谁搬运。查询方式和中断方式通常由 CPU 执行指令完成数据传送；DMA 方式由 DMA 控制器直接组织设备与主存之间的成块数据传送，CPU 主要负责设置参数、启动传送和处理完成事件。

• A 正确：查询方式下，CPU 执行查询程序，反复检查设备状态。设备准备好后，CPU 再执行相应指令读取或写入数据。
• B 正确：中断方式下，设备准备好后提出中断请求，CPU 转去执行中断服务程序，并由该程序完成相应 I/O 操作。
• C 错误：DMA 数据传送的主体是 DMA 控制器。CPU 可以设置内存起始地址、传送长度和方向，但不需要执行一个程序来逐项搬运这些数据。如果仍由 CPU 执行指令搬运每个数据，就失去了 DMA 的主要作用。
• D 正确：SSD、网络适配器等设备传送的数据量大、速度高，采用 DMA 能减少 CPU 参与每次数据传送的开销。

因此，错误叙述为 C。“CPU 参与配置 DMA”不等于“CPU 执行程序完成 DMA 的每次数据传送”。

答案：D。

宏内核把较多操作系统功能放在内核中执行；微内核只把必要的基础功能保留在内核中，将文件服务、设备服务等较多功能放在相互隔离的服务进程中。根据这种结构逐项判断：

正确组合是 II、III、IV。

• A 错：漏掉了正确的 III 安全性。
• B 错：包含错误的 I 性能，且漏掉正确的 IV 可扩展性。
• C 错：包含错误的 I 性能，且漏掉正确的 II 可靠性。
• D 对：恰好包含全部正确项目。

这些是结构带来的通常特征；可靠性和安全性的提高并不意味着所有微内核实现都不会出错。

答案：A。

中断向量表保存不同中断类型所对应的处理入口信息。CPU 获得中断类型编号后，需要迅速找到对应表项，因此这是按编号直接定位的访问需求。

数组把表项连续存放，可以用中断类型编号作下标。若每个表项长度固定，则对应表项地址为

$$\text{表项地址}=\text{表首地址}+\text{中断类型号}\times\text{表项长度}.$$

计算这个地址不需要遍历前面的表项，查找时间为 $O(1)$。

• A 对：数组适合按中断类型号直接访问固定表项。
• B 错：队列适合按先入先出的顺序处理元素，不能根据任意中断编号直接定位处理入口。
• C 错：单向链表需要沿指针依次访问结点，不具有数组按下标直接定位的能力。
• D 错：双向链表能向前或向后遍历，但仍需逐结点查找，而且增加了指针存储开销。

中断处理对入口定位速度要求高，所以采用数组更合适。

答案：C。

位图用一个二进制位表示一个页框的使用状态，例如 0 表示空闲、1 表示已分配。因此，先求页框数，再把位数换算成字节数。

按本题存储容量的二进制换算：

$$16\ \mathrm{GB}=16\times2^{30}\ \mathrm{B}=2^{34}\ \mathrm{B},\qquad 4\ \mathrm{KB}=4\times2^{10}\ \mathrm{B}=2^{12}\ \mathrm{B}.$$

页框总数为

$$\frac{2^{34}}{2^{12}}=2^{22}.$$

每页框只占 1 bit，位图占 $2^{22}$ bit。由于 8 bit=1 B：

$$\frac{2^{22}}8=2^{19}\ \mathrm{B}=512\ \mathrm{KB}.$$

• A 错：128 B 只能表示 $128\times8=1024$ 个页框，远不足以管理全部物理内存。
• B 错：128 KB 只能表示 $2^{20}$ 个页框，只有所需数量的四分之一。
• C 对：512 KB 恰好提供 $2^{22}$ 个二进制位。
• D 错：4 MB 对应给每个页框分配 1 B，实际每框只需 1 bit，多算了 8 倍。

答案：D。

用户程序需要操作系统提供特权服务时，通过系统调用进入内核态；内核完成服务后，利用返回机制恢复用户程序的执行位置和处理器状态，使 CPU 回到用户态。本题问的是操作完成时的转换，而非刚开始执行系统调用时的转换。

• A 错：阻塞进程是内核中的进程管理操作。当前进程阻塞后，内核还需进行调度，不会因为阻塞操作结束就直接返回这个仍在等待的进程的用户程序。
• B 错：CPU 调度程序在内核中选择下一个执行者，调度完成并不必然就是内核态到用户态的转换点。例如，选中的进程可能还要继续执行此前未完成的内核代码。
• C 错：唤醒只是把等待条件满足的进程变为就绪态，执行唤醒代码的 CPU 仍可继续处理内核事务。
• D 对：系统调用服务完成并返回用户程序时，CPU 从内核态恢复为用户态。

系统调用的进入和返回方向相反：进入服务时为用户态到内核态，服务完成返回时为内核态到用户态。

答案：C。

执行态表示线程正在使用 CPU；就绪态表示线程具备执行条件，只是暂时没有 CPU；阻塞态表示线程在等待输入、页面调入或其他事件，当前不能继续执行。执行态变为就绪态的关键是：线程仍然能执行，但让出了 CPU。

• A 错：线程请求键盘输入而输入尚未到达时，通常由执行态进入阻塞态。字符到达后可使等待线程由阻塞态变为就绪态，但这不是题目指定的状态转换。
• B 错：缺页异常需要调入不在主存中的页面，发生调页等待时通常由执行态进入阻塞态；不能把等待页面的线程视为已经就绪。
• C 对：主动出让 CPU，例如执行 yield，没有失去继续执行的条件，只是把处理器交给其他线程，因此可进入就绪态。
• D 错：执行信号量 wait() 时，资源可用则继续执行，资源不足则阻塞；该操作本身不是把仍可执行的线程放回就绪队列。

不能把“暂时不在 CPU 上执行”都称为就绪态，还要检查是否在等待某个必要条件。

答案：D。

虚拟地址是进程使用的逻辑地址，由操作系统与硬件把它转换为物理地址。虚拟地址空间的编号范围主要由体系结构支持的虚拟地址位数以及操作系统的地址布局决定，例如完整的 $k$ 位虚拟地址最多能表示 $2^k$ 个地址。

“地址可编号的范围”与“系统实际能提供的存储资源”不同。主存和磁盘容量会影响实际可分配、可提交的存储量，但不能直接决定虚拟地址的位数。

• A 正确：每个进程有独立虚拟地址空间，不同进程中相同的虚拟地址可以映射到不同物理位置。
• B 正确：malloc() 返回供该进程使用的指针，表示进程虚拟地址空间中的地址，不是直接交给程序一个物理内存地址。
• C 正确：页表等保护机制可以给代码所在页设置执行或只读权限，给数据所在页设置读写权限。
• D 错误：虚拟地址空间大小不能简单由内存与硬盘大小决定，例如增加硬盘不会使处理器原有的虚拟地址位数自动增加。

本题选择错误叙述，因此选 D。

答案：B。

抢占式优先权调度优先执行就绪队列中优先级最高的进程。更高优先级的进程到达时，可以抢占当前进程。本题规定数值越大优先权越高，故 $P3>P2>P1$。

按到达时刻模拟：

周转时间包括执行和等待，是完成时刻减去进入就绪队列的时刻：

$$T_1=115-0=115\ \mathrm{ms},\quad T_2=75-20=55\ \mathrm{ms},\quad T_3=43-30=13\ \mathrm{ms}.$$

平均值为

$$\bar T=\frac{115+55+13}{3} =\frac{183}{3}=61\ \mathrm{ms}.$$

• A 错：60 ms 对应总周转时间 180 ms，与实际的 183 ms 不符；P1 的执行时间 60 ms 也不能直接当作平均周转时间。
• B 对：61 ms 是三个进程各自周转时间的平均值。
• C 错：70 ms 对应总周转时间 210 ms，不符合两次抢占后的完成时刻与各自到达时刻。
• D 错：71 ms 对应总周转时间 213 ms，也与实际时间轴不符。

答案：C。

页号属于进程的虚拟地址空间，页框号属于物理内存。不同进程可以独立设置映射，因此同一份共享数据在两个进程中可以位于不同虚拟位置。

例如，R 可把共享数据映射到虚页 5，S 可把它映射到虚页 20；只要两者的页表项都指向同一个物理页框，就能访问同一份共享内容。于是：

$$p1\text{ 与 }p2\text{ 不一定相等},\qquad f1=f2.$$

• A 错：共享数据并不要求两个进程使用相同虚页号。
• B 错：既错误地要求虚页号相同，又允许页框不同。映射到不同页框不是通过同一个物理页面共享该数据。
• C 对：虚拟位置可以不同，共享页面对应的物理页框相同。
• D 错：虚页号可不同这一部分正确，但这里共享的物理页框应相同。

共享要求映射到同一份物理内容，不要求各进程看到的虚拟地址相同。

答案：B。

打开文件后，文件系统在内存中维护打开文件状态及访问所需的索引节点信息。关闭文件时，需要减少打开引用，并处理不再使用的内存状态。本题采用最后一个打开引用关闭后释放内存索引节点的模型。

F 只有进程 P 打开，P 关闭 F 后不再有其他打开者需要这份打开状态，因此可释放其内存索引节点及相关打开状态。文件仍存在于磁盘上，以后可以重新打开；关闭不是删除。

• A 错：删除目录项属于删除文件名的操作，普通关闭不会使文件名从目录中消失。
• B 对：最后一个打开者关闭文件后，不再需要的内存索引节点状态可以释放。
• C 错：外存索引节点保存文件的持久信息，仅关闭不能释放它，否则文件将失去磁盘管理信息。
• D 错：链接计数表示指向文件的目录项数量，不是当前打开它的进程数量。关闭影响打开引用，不使磁盘索引节点的链接计数减 1。

实际实现可保留索引节点缓存供再次打开使用，但关闭后的打开引用必须正确减少；这与本题所区分的内存状态和磁盘持久信息相符。

答案：D。

设备分配要为进程选择功能合适、允许访问且当前能使用的物理设备，因此需要同时考虑设备性质、权限、占用情况和名称映射。

四项均影响分配结果。

• A 错：忽略设备是否可用及逻辑名对应哪台设备。
• B 错：忽略设备类型以及逻辑到物理的映射。
• C 错：忽略设备功能是否匹配及进程是否有权限使用。
• D 对：包含全部四项。

答案：D。

H1 到 H2 经过两段链路和一个路由器。存储转发要求路由器完整收到一个分组后才开始发送它，但转发前一个分组时可以接收后一个分组，形成流水传输。

题目明确 $M=10^6$，故文件含分组数为

$$N=\frac{10^6\ \mathrm B}{1000\ \mathrm B}=1000.$$

每段链路的发送时延为

$$t_s=\frac{1000\times8}{100\times10^6} =80\ \mu\mathrm s.$$

时延带宽积为单向传播时延乘带宽，因此每段传播时延为

$$t_p=\frac{1000\ \mathrm{bit}}{100\times10^6\ \mathrm{bit/s}} =10\ \mu\mathrm s.$$

第一个分组完整到达 H2 需两次发送、两次传播，即 $2t_s+2t_p=180\ \mu\mathrm s$。链路速率相同，后续每隔 $80\ \mu\mathrm s$ 到达一个分组。所以：

$$\begin{aligned} T&=2t_s+2t_p+(N-1)t_s\\ &=(N+1)t_s+2t_p\\ &=1001\times80+2\times10\\ &=80100\ \mu\mathrm s=80.10\ \mathrm{ms}. \end{aligned}$$

等价地，第一段发送全部文件用 80 ms，最后一个分组还需在第二段发送 0.08 ms，再加两段传播共 0.02 ms。

• A 错：80.02 ms 漏掉最后一个分组在第二段链路的发送时延。
• B 错：80.08 ms 漏掉两段链路的传播时延。
• C 错：80.09 ms 只加了一段传播时延，实际经过两段。
• D 对：完整计算结果为 80.10 ms。

答案：C。

无噪声理想信道用奈奎斯特公式：

$$R_{\max}=2B\log_2V.$$

$B$ 是带宽，$2B$ 是理想最大码元速率，$V$ 是每码元可取的状态数，$\log_2V$ 是每码元的比特数。QAM-$V$ 通过幅度与相位的组合提供 $V$ 种状态。

代入本题：

$$48\times10^6=2\times4\times10^6\log_2V, \quad \log_2V=6,\quad V=2^6=64.$$

最大码元速率为 8 Mbaud，每码元携带 6 bit，故需 QAM-64。

• A 错：QAM-16 每码元 4 bit，最大速率为 $8\times4=32$ Mbps。
• B 错：QAM-32 每码元 5 bit，最大速率为 40 Mbps。
• C 对：QAM-64 每码元 6 bit，最大速率为 48 Mbps。
• D 错：QAM-128 每码元 7 bit，对应最大速率 56 Mbps。

本题没有给出噪声或信噪比，不应套用含信噪比的香农公式求状态数。

答案：B。

发送窗口表示尚未收到确认时，发送方最多可连续发送多少帧。同一信道、同样帧长下，较大窗口能够利用等待确认的时间继续发送，最大信道利用率随窗口增大不会降低。

3 bit 序号有 $2^3=8$ 种编号：

忽略确认帧长度时，窗口为 $W$ 的常用利用率模型为

$$U=\min\left(1,\frac{W t_{\text{帧}}} {t_{\text{帧}}+2t_{\text{传播}}}\right).$$

本题分母与帧长相同，比较窗口 $1、4、7$，得到

$$U_1\le U_3\le U_2.$$

使用不等号包含相等，是因为窗口足够大时可达到相同的 100% 利用率。

• A 错：把 GBN 和 SR 颠倒了，GBN 最大窗口 7 大于 SR 的 4。
• B 对：停等不高于 SR，SR 不高于 GBN。
• C 错：把窗口最小的停等放在利用率最高的位置。
• D 错：同样错误地要求 GBN 不高于停等，并把 SR 放在最低位置。

答案：C。

二进制指数退避随机延后重发，降低多个站点再次同时发送的概率。发生第 $n$ 次连续冲突后，取 $k=\min(n,10)$，从整数集合

$$\{0,1,\ldots,2^k-1\}$$

中随机选择退避倍数 $r$，等待 $r$ 个争用时间片。

连续冲突 4 次时，$k=4$，可选倍数为 0～15。最长等待为

$$(2^4-1)\times51.2\ \mu\mathrm s =15\times51.2\ \mu\mathrm s =768\ \mu\mathrm s.$$

• A 错：51.2 μs 只对应 1 个时间片，未按第 4 次冲突的范围求最大值。
• B 错：204.8 μs 是 $4\times51.2$，把冲突次数直接当成退避倍数，忽略指数规则。
• C 对：最大退避倍数 15，等待 768 μs。
• D 错：819.2 μs 是 $16\times51.2$，随机范围的最大值应为 15，不能取 16。

范围中有 16 个整数，并不表示最大整数是 16，因为计数从 0 开始。

答案：D。

CRC 把比特串视为二进制多项式，用生成多项式进行模 2 除法。模 2 减法就是逐位异或，没有借位，例如 $1\oplus1=0$、$1\oplus0=1$。

本题 $G(X)=X^4+X+1$ 对应生成串 10011，最高次数为 4，因此余数为 4 bit。接收方直接用完整接收串除以 10011，无须再在接收串末尾补 0。

以 D 为例，先把生成串与接收串最高位对齐后异或，再与剩余最高非零位对齐：

  101111100
⊕ 100110000
  ---------
  001001100
⊕ 001001100
  ---------
  000000000

最终余数为 0000，只有 D 通过校验；A、B、C 因非零余数被排除。四个选项的数据部分都是 10111，正确校验位为 1100。

本题采用的判题约定与严谨边界。 本题按 CRC 检查的考试约定，将题干“未发生错误”理解为“通过校验、未检出错误”，因此选 D。严格地说，CRC 通过并不能绝对证明传输无错：若差错模式恰为生成多项式的倍数，差错也会得到零余数而漏检。这个限制不改变本题四个候选串中只有 D 校验通过的计算结果。

答案：A。

H 向 Internet 发送分组时，R2 的 NAT 会把内部主机的私有源地址转换为公网地址。图中只给出了 R1 在连接 R2 的链路上的地址 195.123.0.34/30，必须先据此推算 R2 的外网接口地址。

/30 表示剩下 2 位主机位，子网有 $2^2=4$ 个地址。最后一字节按每 4 个地址划分，34 所属块的起点为

$$\left\lfloor\frac{34}{4}\right\rfloor\times4=32.$$

链路另一端 R2 使用剩余可分配地址 195.123.0.33，因此经其 NAT 转发后，源 IP 变为这个公网地址。

• A 对：.33 是根据 /30 地址块及 R1 已用地址推算出的 R2 外网地址。
• B 错：.35 是该子网的广播地址。
• C 错：192.168.0.1 是 R2 的内网接口地址。
• D 错：192.168.0.3 是 H 的私有地址，即转换前的源地址。

普通路由转发通常保留源 IP，而本题明确 R2 执行 NAT，因此要进行上述地址转换。

答案：B。

/20 表示前 20 位为网络位，后 12 位为主机位，对应掩码为 255.255.240.0。前两字节完全属于网络号，第三字节只有高 4 位属于网络号，因此第三字节按 $256-240=16$ 为块长划分子网。

主机地址的第三字节为 84，所属范围为 80～95；按位与也有

$$84\ \text{AND}\ 240=80.$$

将所有主机位设为 0 得到网络地址 168.16.80.0，设为 1 得到广播地址 168.16.95.255。普通主机不能使用这两个地址，所以：

$$\text{最小可分配地址}=168.16.80.1,\qquad \text{最大可分配地址}=168.16.95.254.$$

• A 错：起点正确，但 .84.254 不是 /20 子网的最大主机地址，第三字节还可到 95。
• B 对：同时正确排除了网络地址与广播地址。
• C 错：把主机所在的 .84 当成固定的第三字节，实际子网从 .80 开始。
• D 错：终点正确，但起点应为 .80.1，而非 .84.1。

不能按看到的第三字节直接当作 /24 子网，必须使用题目给定的 /20 前缀。

答案：D。

逐项比较地址长度、首部结构与过渡机制：

地址空间比例为

$$\frac{2^{128}}{2^{32}}=2^{96}.$$

因此只有 III、IV 正确。

• A 错：I、II 都错误。
• B 错：IV 正确，但 I 把增加的位数误当成空间倍数。
• C 错：III 正确，但 II 把 IPv6 基本首部误当成可变长。
• D 对：恰好包含 III、IV。

（1）基本设计思想

有向边从起点指向终点。顶点的出度是从它出发的边数，入度是指向它的边数。对于邻接矩阵，Edge[i][j] 表示从顶点 $i$ 指向顶点 $j$ 的边，因此：

• 第 $i$ 行中的边数就是顶点 $i$ 的出度。
• 第 $i$ 列中的边数就是顶点 $i$ 的入度。
• 只有出度严格大于入度，顶点 $i$ 才是 K 顶点。

本题为无权有向图，采用邻接矩阵中 1 表示存在边、0 表示不存在边的约定。依次遍历每个顶点 $i$，再用一个内层循环同时检查 Edge[i][j] 和 Edge[j][i]，统计出度和入度；比较后输出符合条件的顶点标识，并累计数量。

图中的边为 a→b、a→d、b→c、b→d、c→d，核对结果为：

所以该图应输出 a、b，并返回 2。算法本身按矩阵处理任意非空有向图，并不依赖此示例的顶点名称或边数。

（2）C 语言实现

使用给定的 MGraph 类型：

#include <stdio.h>

int printVertices(MGraph G)
{
    int count = 0;

    for (int i = 0; i < G.numVertices; ++i) {
        int outDegree = 0;
        int inDegree = 0;

        for (int j = 0; j < G.numVertices; ++j) {
            if (G.Edge[i][j] != 0) {
                ++outDegree;  /* 第 i 行：从 i 出发的边 */
            }
            if (G.Edge[j][i] != 0) {
                ++inDegree;   /* 第 i 列：指向 i 的边 */
            }
        }

        if (outDegree > inDegree) {
            printf("%c ", G.VerticesList[i]);
            ++count;
        }
    }

    return count;
}

正确性。 固定顶点 $i$ 后，内层循环处理完前 $j$ 个顶点时，outDegree 与 inDegree 分别等于对应行、列已经检查部分的边数。遍历完全部顶点后，二者就是完整出度和入度，所以 outDegree > inDegree 与 K 顶点定义完全等价。外层循环不遗漏也不重复任何顶点，因而输出全部且仅输出 K 顶点，count 也是其准确数量。若存在自环，它同时对出度、入度各加 1，不影响二者差值，无须特殊处理。

复杂度。 设顶点数为 $V$，两层循环各执行 $V$ 次，时间复杂度为 $O(V^2)$。除输入图及函数参数外，只使用计数器等固定数量变量，辅助空间复杂度为 $O(1)$。

置换-选择的规则

工作区容量为 $m$ 不意味着每个初始归并段只能有 $m$ 个记录。先读入 $m$ 个记录，反复输出当前段可用记录中的最小者，再从文件补入一条记录。设刚输出的关键字为 $L$：

• 新关键字不小于 $L$，可以参加当前段的后续输出。
• 新关键字小于 $L$，若立即输出会破坏升序，必须冻结，留到下一段。
• 当前段再无可用记录时结束该段，解冻剩余记录，开始下一段。

（1）$m=4$ 时的全部过程和结果

先装入 51、94、37、92，当前可用记录按关键字排列为 37、51、92、94。下表的“可用”“冻结”是本次输出并补入之后的工作区内容，均按关键字排列便于核对；它们合计不会超过 4 条。

共得到 3 个初始归并段：

段长分别为 6、9、4，总计 $6+9+4=19$，没有遗漏或重复记录；每段内部均为非递减顺序。归并段之间不要求整体有序，例如第一段结束后第二段从较小的 14 重新开始，这是正常现象。

（2）第一段的最大长度和最小长度

最大值为 $n$。若输入已按关键字非递减排列，每次补入的关键字都不小于刚输出者，没有记录被冻结，整个文件可成为一个段。因此工作区只需保存 $m$ 条，但第一段能长达 $n$ 条；不可能超过文件总记录数 $n$。

最小值为 $m$。初次读入的 $m$ 条全部属于第一段，算法不会把它们重新冻结，所以第一段至少输出这 $m$ 条。若文件关键字严格递减，每次补入的记录都小于当前输出值，全部冻结；初始 $m$ 条输出完后第一段结束，恰好达到下界。

正确性与实现开销。 当前可用集合中的关键字都不小于上次输出值，取其中最小者能维持当前段有序；冻结规则把不符合此条件的记录留到下一段，因此不会破坏任何段的顺序。若用最小堆维护可用记录并给记录标记归并段号，每条记录插入、输出各一次，每次调整至多涉及工作区的 $m$ 条记录，时间复杂度为 $O(n\log(m+1))$，工作区空间为 $O(m)$。冻结只改变记录所属段，不额外读回已经输出的记录。

数组共有 $24\times64=1536$ 个 int，每个 int 占 4 B；每行占 $64\times4=256$ B。按行优先存放时，任意元素的虚拟地址为

$$\mathrm{VA}(a[i][j])=\mathrm{00422000H}+(64i+j)\times4.$$

计算页面和 Cache 时，要区分页面大小 4 KB 与主存块大小 32 B；一次缺页调入一页，一次 Cache 缺失处理一个主存块，两者不是同一事件。

（1）页面数量、缺页次数及故障地址

数组总容量为

$$24\times64\times4=6144\ \mathrm B.$$

起始地址 00422000H 是 4 KB 页边界，数组最后一个字节地址为

$$\mathrm{00422000H}+6144-1=\mathrm{004237FFH}.$$

因此数组覆盖两个页面：

数组执行前不在主存，第一次访问每页会缺页；调入后题设保证不置换，所以之后不会因该页再次缺页。结论是 分布在 2 页、发生 2 次缺页异常，页故障地址为 00422000H、00423000H。

（2）数据访问的时间局部性

不考虑 i、j 时，程序对每个数组元素只执行一次写入，没有在短时间内反复访问同一个数组元素，因此数组元素的访问没有时间局部性。

原循环先沿一行连续访问，邻近元素也存放在邻近地址，因而具有很好的空间局部性。一个 Cache 块包含多个元素，其后续命中来源于相邻元素位于同块，不应据此把每个元素都说成被重复访问。

（3）块内地址、组号及指定元素地址

主存块长 32 B=$2^5$ B，因此低 5 位 A4～A0 为块内地址。

Cache 数据区为 8 KB，共有

$$\frac{8192}{32}=256$$

个 Cache 行，4 路组相联意味着每组 4 行，故组数为

$$\frac{256}{4}=64=2^6.$$

组号占紧接块内地址的 6 位，即 A10～A5。

页大小为 $2^{12}$ B，虚拟地址的 A11～A0 是页内偏移，在虚实地址转换时保持不变。块内地址和组号全部位于该偏移中，所以可以直接由本题虚拟地址计算，不需要假定两个页面的物理页框连续。

a[1][0] 位于首地址之后一行，即

$$\mathrm{00422000H}+256 =\mathrm{00422000H}+\mathrm{100H} =\mathrm{00422100H}.$$

该地址的组号为

$$\left\lfloor\frac{\mathrm{00422100H}}{32}\right\rfloor\bmod64 =8,$$

也可取其 A10～A5 得到二进制 001000。

（4）主存块数量与两种遍历的命中率

数组首地址按块对齐，每块可容纳 $32/4=8$ 个元素，数组共占

$$6144/32=192$$

个主存块。本题采用写分配约定：首次写缺失时先把所在整块调入 Cache，再完成写入。 题面没有单列写缺失策略，以下按这套考试计算模型，并按题设排除与其他数据的 Cache 冲突。若采用非写分配，写缺失本身不会把块调入 Cache，不能直接沿用以下命中率。写分配与写回/直写是两类不同的策略：这里需要的约定是写缺失时是否装块。

原来按行遍历时，每块的第一个元素访问缺失，随后 7 个元素命中。总访问 1536 次，缺失 192 次，命中 $1536-192=1344$ 次，命中率为

$$\frac{1344}{1536}=\frac78=\boxed{87.5\%}.$$

改为按列遍历时，相邻两次访问跨过一行，即跨 256 B=8 个块，但这并不自动意味着每次都缺失。必须检查组号和路数是否足以保留先前装入的块。

首地址的 Cache 组号为 0。令 $q=\lfloor j/8\rfloor$，元素 a[i][j] 所在的相对块号和组号为

$$b(i,j)=8i+q,\qquad g(i,j)=(8i+q)\bmod64.$$

固定一列 j 时，只访问 $q,q+8,\ldots,q+56$ 这 8 个组，每组恰好放 3 个不同块。例如 j=0 时：

每组有 4 路，3 个块能够全部保留。j=0 第一次访问各行的块时缺失；j=1～7 仍访问这些块，全部命中。j=8 开始各行的下一块，使用组号 1、9、……、57，随后 j=9～15 命中。每连续 8 列重复一次这个规律。

整个数组的 192 块在 64 组中各占 3 块，不超过每组 4 路，故没有由数组自身造成的替换冲突。按列遍历同样只有 192 次首次缺失和 1344 次命中，命中率仍为 87.5%。

数组 a[24][64] 按行优先存储，int 为 4 B、每行 256 B，首地址为 00422000H。机器指令地址属于代码的虚拟地址，数组地址属于数据的虚拟地址，分析时应分别检查。

（1）第 20 条指令的虚拟地址

第 19 条起始地址为 004010AEH，其机器码为

C7 84 82 00 20 42 00 0A 00 00 00

每两个十六进制数字表示 1 B，共 11 B，即 0BH。按字节编址，紧接的第 20 条地址为

$$\mathrm{004010AEH}+\mathrm{0BH} =\boxed{\mathrm{004010B9H}}.$$

不能按字长 32 位就认为每条指令均为 4 B；本题图中指令具有不同长度，必须数实际机器码字节。

（2）两条跳转的寻址方式及目标计算

两条指令均采用 相对寻址：机器码给出有符号相对位移，目标地址为顺序下一条指令地址加位移。

$$\text{目标地址}=\text{当前指令地址}+\text{当前指令长度}+\text{位移}.$$

第 2 条 jmp 位于 00401079H，机器码 EB 09 为 2 B。EBH 是操作码，09H 是正位移 9，不是绝对目标地址。因此：

$$\begin{aligned} \text{下一条地址}&=\mathrm{00401079H}+2=\mathrm{0040107BH},\\ \text{跳转目标}&=\mathrm{0040107BH}+\mathrm{09H} =\boxed{\mathrm{00401084H}}. \end{aligned}$$

第 7 条 jge 位于 00401088H，机器码 7D 32 同样为 2 B，其正位移 32H=50：

$$\mathrm{00401088H}+2+\mathrm{32H} =\mathrm{004010BCH}.$$

两条跳转都以执行时已指向下一条指令的 PC 为基准，而不是直接以本条起始地址为基准。

（3）源寻址方式、ecx 内容及字节顺序

第 19 条为

mov [ecx+edx*4+00422000h], 0Ah

源操作数为指令中直接给出的 0AH，即十进制 10，所以采用 立即数寻址。

目的地址应符合数组下标公式：

$$\mathrm{EA}=\mathrm{00422000H}+(64i+j)\times4 =\mathrm{00422000H}+256i+4j.$$

题设 edx 保存 j，而指令给出的地址为首地址加 ecx 加 $4\times\text{edx}$，因此 ecx 保存 $256i$，即 $i\times64\times4$，不是 i 本身，也不是已经包含数组首地址的完整行地址。

从机器码看，32 位地址位移 00422000H 按 00 20 42 00 存放；立即数 0000000AH 按 0A 00 00 00 存放。两者均为最低有效字节先放在低地址处，说明 M 使用 小端方式。判断依据是多字节数的存放次序，不是操作码本身的大小。

（4）首次取第 19 条时是否缺页

取指过程中不会发生缺页异常。 页大小为 4 KB，地址 004010AEH 位于代码页

$$\mathrm{00401000H}\sim\mathrm{00401FFFH}.$$

此前已经执行过第 1、2 条等同页指令，因而这个代码页已经在主存中。题设保证执行过程中不发生页面置换，该页不会被换出。第 19 条占用 004010AEH～004010B8H，也完全落在该页内，没有跨页取指。

首次执行该 mov 时，对 a[0][0] 的写访问可能因数组页尚未调入而缺页，但那是数据访问阶段的缺页，不是本问的取指缺页。

临界区是访问共享数据的一段代码，互斥要求任何时刻至多有一个线程进入。共享变量 lock 为 FALSE 表示空闲，为 TRUE 表示已被占用；key 是每个线程自己的私有变量。硬件 swap 指令把两个变量的读出和交换作为不可分割的原子操作完成。

（1）错误语句及修正

共有两处需要改正：

修改关键字与赋值即可，不增加语句条数。完整伪代码为：

bool lock = FALSE;       // 共享，在线程开始竞争前初始化一次
...
bool key = TRUE;         // 当前线程的私有变量
while (key == TRUE)
    swap key, lock;      // 原子交换
临界区;
lock = FALSE;            // 退出区释放锁
...

交换后的两种情况说明它为何有效：

原代码使用 if 时，即使交换后 key 仍为 TRUE，也会顺序执行临界区，破坏互斥；原退出语句继续设置 TRUE，则无法释放已占用的锁。

互斥正确性。 当 lock 为 FALSE 时，竞争线程的原子交换存在确定先后顺序，只有第一个交换者能读到 FALSE，并同时把 lock 置为 TRUE；其余交换者读到 TRUE，都继续等待。持锁者离开后才把 lock 改回 FALSE，才允许下一个线程取得锁。因此任意时刻至多一个线程通过进入区。

该方法采用忙等待，不保证等待线程立即获得 CPU 或在有限次数内获得锁。单次 swap 和释放操作均为 $O(1)$，但等待次数取决于占锁时长与调度，不能给整个进入区保证固定的时间上界；每线程额外只需一个 key，空间为 $O(1)$。

（2）能否用 newSwap() 代替 swap

不能直接代替。 普通函数的三个赋值只能实现交换数值的最终效果，不能保证从读 lock 到写 lock 的全过程原子化。线程可能在任何一条语句之间切换。

设线程 A、B 的私有 key 初始均为 TRUE，lock 初始为 FALSE。用下表给出一个合法的交错执行过程；函数中的 a 指向各自 key，b 指向同一个 lock。

两线程的 key 最终均为 FALSE，都会退出等待循环并进入临界区，互斥失败。硬件原子 swap 不允许别的线程在其中间步骤读到同一个空闲状态，这正是普通函数调用所缺少的保证。

进程 P 执行输入系统调用后，若键盘字符尚未到达，不能占着 CPU 空等，应阻塞等待；字符到达后，中断处理把数据读入缓冲区并唤醒 P，P 再由调度器选中，继续完成系统调用。

六个给定操作的主要先后关系为：

② → ⑥ → ④ → ③ → ① → ⑤。

表中列的是题目给出的六项操作；① 与⑤之间还要发生调度、恢复 P 的现场及继续执行内核代码，并不意味着唤醒会让 P 立即运行。

（1）相邻操作

在给定操作序列中，① 的前一个是 ③，因为先完成输入数据准备，再把等待者唤醒；① 的后一个是 ⑤。⑥ 的后一个是 ④，即输入引发键盘中断，CPU 转入相应处理程序。

（2）必然切换的时刻及可以选中 P 的时刻

完成 ② 后，P 已进入阻塞态，失去继续执行的条件，CPU 必须转去执行其他可运行进程；若没有普通就绪进程，则执行空闲进程。

完成 ① 后，P 才进入就绪队列，CPU 调度程序才能选中它。进入就绪态只是获得被选中的资格，何时真正运行还取决于调度策略与其他就绪进程。

（3）键盘驱动程序负责的操作

③ 属于键盘驱动程序的设备相关操作：读取键盘控制器中的数据，并放入系统缓冲区。驱动知道设备寄存器及数据读取方式；将进程加入就绪、阻塞队列则属于操作系统的进程管理功能。

（4）中断服务时的 P 状态及 CPU 模式

键盘中断到达、开始执行处理程序及读取字符时，P 仍处于 阻塞态；CPU 在 内核态 执行键盘中断处理程序。中断处理并不要求 P 此时正在运行，CPU 可能中断的是另一个进程。

当处理中完成①唤醒 P 后，P 变为就绪态；之后被调度选中才成为执行态。因此不能说 P 在整个中断处理期间始终阻塞。执行中断服务代码的 CPU 则处于内核态，P 只有在完成系统调用返回用户程序后才恢复用户态执行。

本题 H 向 FTP 服务器上传文件，TCP 数据连接的初始序号为 100，文件长 18000 B，MSS 为 1000 B，所以文件共有 $18000/1000=18$ 个满长数据段。RTT 为 10 ms，段传输时延忽略，且没有差错、丢包和乱序。

（1）控制连接、数据连接及登录时的连接

FTP 使用两类连接：

H 登录服务器时建立的是 控制连接。文件内容通过随后为上传建立的数据连接传输；不能把登录连接的序号与题目给出的数据连接初始序号混在一起。

（2）首字节序号和第二次挥手 ACK 的确认号

TCP 按字节编号，确认号表示“下一个期待接收的序号”。建立连接的 SYN 和释放连接的 FIN 虽然不包含文件字节，但各占用一个序号。

所以文件第一个字节的序号为 101。服务器在第二次挥手中确认 H 的 FIN，期待下一个序号为

$$18101+1=\boxed{18102}.$$

只确认全部文件数据时的 ACK 为 18101；确认包含 FIN 的序号后才是 18102，两者不可混淆。

（3）两个指定 ACK 到达时的拥塞窗口

本题采用传统慢开始教学约定。 初始拥塞窗口 cwnd 为 1 MSS，初始阈值 ssthresh 为 4 MSS，接收窗口足以容纳发送窗口；慢开始时每个满 MSS 的新数据段均获得确认，逐 ACK 增加 1 MSS。达到阈值后转入拥塞避免，按完整 RTT 轮次每轮增加 1 MSS。题面给出阈值而没有逐项列明这些默认参数，以下以这套教学模型计算，窗口均以 MSS 为单位。实际 TCP 可以采用其他初始窗口、延迟确认及更具体的逐 ACK 增长算法，不能把本题数值当成所有实现的固定结果。

数据从 101 开始，确认号 $A$ 已累计确认的数据量为 $A-101$ B。因此：

• ACK=2101 已确认 $2101-101=2000$ B，即前两个数据段。第一段的 ACK=1101 使 cwnd 从 1 增为 2；第二段的 ACK=2101 再使它从 2 增为 3 MSS=3000 B。此时第三段尚未计入该累计确认，不能直接按第二轮结束写成 4 MSS。
• ACK=3101 确认前三段，使 cwnd 达到阈值 4 MSS。
• ACK=7101 已确认 $7101-101=7000$ B，即前 7 段。在按轮次计算的过程里，前面三轮发送量为 $1+2+4=7$ MSS，此 ACK 表示窗口为 4 MSS 的一轮已全部确认。拥塞避免使窗口增加到 5 MSS=5000 B。

对应轮次为：

第二轮中途的 ACK=2101 对应 3 MSS，第三轮结束的 ACK=7101 对应 5 MSS。达到阈值后的四个确认不再按慢开始逐个增加 1 MSS，否则会错误得到 8 MSS。

（4）最短总时间与平均应用数据发送速率

三次握手中，H 发出 SYN 后经过 1 RTT 收到 SYN+ACK；忽略传输时延时，第三次握手 ACK 与首个数据段可在同一时刻发送，所以建立连接至可开始发送只需 1 RTT。

18 个数据段按拥塞窗口的轮次分配为

$$1,\ 2,\ 4,\ 5,\ 6,$$

总计 $1+2+4+5+6=18$，数据发送并收到全部确认需 5 RTT。

因此至少需要

$$T=(1+5)\times10\ \mathrm{ms} =\boxed{60\ \mathrm{ms}}.$$

应用层有效数据只有文件的 18000 B，不把 TCP 首部、握手报文或 FIN 当作文件数据。平均速率为

$$R=\frac{18000\ \mathrm B}{0.06\ \mathrm s} =300000\ \mathrm{B/s} =2.4\times10^6\ \mathrm{bit/s} =\boxed{2.4\ \mathrm{Mbps}}.$$

题目计时截止于 H 确认文件全部接收，不包含后续释放数据连接的四次挥手时间。