2026年计算机408真题

答案：A。

顺序表把元素放在一段连续空间中，某个位置后的元素不能留下空洞，原有元素的相对次序也必须保持。设原表为[a,b,c,…]：

• 表头插入x，为给x腾出第一个位置，必须从后向前把全部n个原元素各移动一次，得到[x,a,b,c,…]。
• 删除表头a，后面n−1个元素必须向前补位。题设n≥3，所以n−1至少为2，也属于移动多个元素。
• 表尾插入只需把新元素写入当前末尾之后的空闲位置，再增加长度；题设有空闲空间，不需要扩容搬迁。
• 表尾删除只需减少长度，原有元素无需移动。

因此只有I、II一定移动多个原有元素，选A；B、C、D均错误地把某种表尾操作纳入。这里“写入新元素”和“移动原有元素”是不同的操作。

答案：D。

原来的p1是后继指针，沿p1能依次访问头结点及所有数据结点。本题只改p2，因此遍历方向仍应保持为cu=cu->p1。新p2应跨过一个结点，指向当前结点的“后继的后继”。

若cu->p1非空，可以安全取cu->p1->p1；这个值本身允许为NULL，例如当前是倒数第二个结点。若cu->p1已经为空，当前就是尾结点，不能再访问空指针的成员，应直接令cu->p2=NULL。无论哪种情况都要推进cu，这正是D的做法。

A在尾结点解引用空指针；B用p2控制循环，但头结点的原前驱通常为空，会立即停止，而且p2正是正在改写的字段；C把推进语句放进条件分支，到尾结点时条件为假，cu永远不动，造成死循环。安全解引用与每轮都能推进，是这类链表代码的两个检查重点。

答案：C。

中序是“左子树—根—右子树”，层序按深度从上到下列出结点。先用层序确定根，再用中序划分其左右子树，递归进行：

1. 层序首项a为整树根。中序中a左侧是b,e,d,f,c，右侧只有g，所以g是a的右孩子。
2. 左子树中层序最早出现b，因此b为左子树根。中序中b左边没有元素，右边是e,d,f,c。
3. 在这四个结点中，层序最早出现c，因此c是b的右孩子；中序中c左侧为e,d,f，右侧为空。
4. 剩余子树根为d，中序把e分到其左边、f分到其右边。

后序采用“左—右—根”：d子树输出e,f,d，再输出c，再输出b；随后输出右子树g，最后根a，得到e,f,d,c,b,g,a。A、B把c或d提前输出，D把右子树g放进左子树处理过程，均不符合后序规则。

答案：B。

森林转换为二叉树时，使用“左孩子—右兄弟”表示：同一棵树的孩子通过左孩子及兄弟链表示，五棵树的根则连成一条右兄弟链。无论怎么排列，这条链已有五个结点，对应五层。

最后一个根所代表的树至少有2个结点，所以它还必须有孩子。从五根链的末端再向下至少一层，整体高度至少为6，A的5不可能。

还需要证明6能够达到。把五棵树按结点数7、5、4、3、2排列。可分别选择转换后高度为4、4、3、3、2的单树结构；第一棵根位于第1层，后续根依次多一层，所以整体各部分高度为4、5、5、6、6，最大为6。这样的单树结构可构造：根的右指针为空，其左侧二叉子树在所给高度内容纳其余结点；将其反向解释为孩子与兄弟即可得到一棵树。

因此最小高度是6，C、D只是更大的数值，没有给出最优下界。

答案：D。

叶结点权值确定时，带权路径长度最小的二叉树可以用哈夫曼算法构造：每次把当前最小的两个权相加，形成内部结点，再放回待选集合。

最后根的两个子树权为18、24。权18的两个孩子就是e=8与f=10，两者深度均为2；权24的孩子之一是原叶g=12，另一个是内部结点12，因此g深度也为2，而d=5在这个内部结点下，深度为3。

所以与e同深度的其他叶只有f、g，选D。A、C误把d放在同层，B漏掉f。两个权为12的结点，一个是原叶、一个是合并产生的内部结点，必须区分。

答案：D。

普通有向图邻接表中，顶点u的链表保存的是从u出发的边，因而沿自己的链表可以直接计算出度；目标顶点v的入边却可能分别出现在所有其他顶点的链表里。

求v的入度需要逐个检查|V|个表头，并访问总计|E|个边结点；每发现一条边的终点为v，计数加1。因此时间为

$$O(|V|+|E|)=O(\max(|V|,|E|)).$$

两者同阶，是因为最大项不超过两项之和，而两项之和不超过最大项的两倍。

A忽略边遍历；C忽略表头检查，例如有大量孤立顶点时，边数很少仍需扫描所有顶点；B取较小者更不能覆盖两部分工作。若另行维护入边表或预存入度，查询可以更快，但那是增加了本题未给出的数据结构。

答案：B。

本题把生成字符串的有向路线按“有向行走”理解，允许重复经过顶点和边。因此可以沿一个环反复绕行。这是题目考查“有环时能生成任意长字符串”的语境约定；不能把这里的“路径”替换成禁止重复顶点的简单路径。

每条边贡献一个字符，所以字符串长度等于该路线经过的边数。

• A 正确。 若 G 无环，一条路线不能重复顶点，否则重复部分就构成有向环。n 个顶点最多经过 n−1 条边，路线数量有限，因此生成的字符串集 S 也是有穷集。
• B 错误。 无环时字符串长度最多为 n−1，不可能达到 n。注意长度统计边数，而不是顶点数。
• C 正确。 题目保证每个顶点都在从初始点到某个标记点的有向路径上，因此环上的顶点能够从初始点到达，也能继续走到标记点。先走到环，绕行任意多圈，再去标记点，就可使边数和字符串长度超过 n。
• D 正确。 初始点能够到达至少一个标记点。删去重复绕行后，存在一条从初始点到该标记点的简单有向路径，长度最多 n−1，必然小于 2n。图中存在环不意味着每一条到达标记点的路线都很长。

题目问错误叙述，因此选 B。若另将“路径”限定为不重复顶点的简单路径，C 就不能成立；本题作答采用上述允许重复绕环的字符串生成约定。

答案：D。

AVL平衡二叉树要求每个结点的左右子树高度差不超过1。高度按层数计，空树高0、叶结点高1。整树高4时，最高子树高3，另一子树高度至少为2。

要让结点数差尽量大，较大子树取高度3的满二叉树，有1+2+4=7个结点；较小子树取高度2的最少结点AVL树，只需一个根带一个叶，共2个结点。因此可达到7−2=5。

也可用最少结点递推N(h)=1+N(h−1)+N(h−2)，其中N(0)=0、N(1)=1，得到N(2)=2。若两个子树都高3，较小子树至少N(3)=4，差至多3，反而小于前面的5。故最大差为5，选D。平衡条件限制的是高度差，而不是结点数差；这正是A、B容易造成的误判。

答案：B。

直接插入排序从第二项开始，把当前元素插入已经有序的前缀。从前缀末端向左比较：比当前值大就后移；遇到不大于当前值的元素停止。这里仅统计关键字之间的比较，检查j是否越界不算。

例如B：插入43比较31一次；插入26依次比较43、31两次；插入55、63、99各比较一次；插入77先比较99，再比较63，共两次。因此B总计1+2+1+1+1+2=8次。

所以选B。某次一直移动到表头时，不应再凭空增加一次“与不存在的前驱比较”；比较次数也不直接等于交换或移动次数。

答案：A。

最终排名有三个层次：先比较总成绩，再比较C1；若两项都相同，还要保留最初相对次序。稳定排序表示等关键字元素的相对次序不改变。

先对次关键字C1降序稳定排序，已保证C1同分者保持原顺序；再对主关键字总成绩降序稳定排序，同总成绩的一组内部保留第一次排序的C1顺序，而两项全相同者仍保留最初顺序。例如甲、乙总成绩都为180，C1分别90、95，第一次让乙在前，第二次必须保留该顺序。

这种从次关键字到主关键字依次稳定处理的方式，正是低位优先的基数排序思想，选A。快速排序、希尔排序、通常的直接选择排序均不保证稳定，可能破坏第一趟已经建立的同总分内部顺序。关键是两趟排序的稳定性及关键字优先级，并非只把两个分数相加后任意排序。

答案：A。

设初始归并段有r个，k路归并每趟把至多k个有序段合成一个，段数按约k倍缩小，归并趟数通常为 $\lceil\log_k r\rceil$。因此增大k可能让趟数减少，I正确；“可能”也考虑了向上取整导致某些k改变后趟数不变的情况。

II错误：初始段越多，通常需要越多趟。例如k=2时，4段需2趟，8段需3趟。

III容易与普通的分块内排序混淆。若一次读满内存再排序，单段长度确实受工作区限制；但初始段还可用置换选择法产生。每输出一个当前最小记录，就读入一个新记录；若新记录不小于刚输出值，仍可进入当前段。输入本来升序时，即使工作区有限，也可持续生成一个很长、甚至覆盖全部输入的有序段。因此内存限制同时驻留的记录数，不限定所有方法所能产生的单段最大长度，III错误。

只有I成立，选A。平均段长与“最大可能长度”也必须区分。

答案：C。

计算机的层次结构从上往下可依次理解为应用、操作系统等软件，指令集体系结构（ISA），微架构，以及逻辑电路、器件和物理封装。各层解释下层能力，并向上提供相应抽象。

ISA规定软件可见的指令及其行为，是软硬件之间的接口；同一ISA可以有不同的微架构实现，例如使用不同流水线、运算单元或Cache组织。微架构描述这些部件的逻辑组织及工作方式，后面还需要电路设计、器件实现和封装，因此不能直接把它归为最下面的物理实现层，C的说法错误。

A给出的最上、最下两端符合该层次；B指出ISA接口作用，正确；D中操作系统通过指令与硬件交互，并把处理器、内存和设备进一步抽象为进程、虚拟地址、文件等服务，也正确。本题考查相邻抽象层之间的区别，并不是否认微架构实现ISA。

答案：A。

本题按 8 位有符号补码机器数计算，字长始终保持 8 位。对负数作算术右移时高位补 1；算术左移时丢弃移出的高位、低位补 0。题面没有另外指明码制，这里明确采用本题的常用补码约定。

原位串为 1010 0110B，最高位是 1，按补码解释为负数。连续算术右移三次：

$$10100110\ \to\ 11010011\ \to\ 11101001\ \to\ 11110100.$$

每次都保留符号，右端被移出的位丢弃。随后算术左移两次：

$$11110100\ \to\ 11101000\ \to\ 11010000.$$

最终结果是 1101 0000B，对应 A。

也可检查真值：原补码表示 $166-256=-90$；右移三位后为 $244-256=-12$；左移两位后为 $208-256=-48$。本次左移没有溢出，但一般固定字长的左移可能丢失有效位，因此逐位计算比直接使用十进制“除 8 再乘 4”更稳妥，特别是负数右移时不能按向零截断的整数除法来代替。

B、D 的低两位为 11，不符合本题补码左移低位补 0 的规则；C 的最高位为 0，与计算得到的位串不符。右移时已经丢弃的低位不能在左移时重新带回。

若改用负数反码等其他编码，算术移位的补位规则可能不同，例如负数反码左移低位补 1 会得到 B；所以 A 的适用前提是本题采用的补码模型。

答案：B。

IEEE 754单精度共32位：1位符号、8位阶码、23位显式尾数，正规化有效数前面的1不存入尾数字段。12.1为正，符号位0；其二进制是1100.000110011…，正规化为 $1.100000110011\cdots\times2^3$，实际指数3，阶码为3+127=130，即10000010B。

用精确分数也能核算尾数及舍入。小数尾数为 $12.1/8-1=0.5125$，乘以 $2^{23}$ 得

$$0.5125\times2^{23}=4299161.6.$$

截断尾数是4299161=419999H，舍弃部分为0.6个最低尾数单位，大于0.5，因此就近舍入为4299162=41999AH。本次不在恰好中间位置，无需用取偶规则处理平局。

把阶码放到位30～23，得到 $(130\ll23)+41999A_H=4141999A_H$，选B。A是未正确进位的截断值；C、D的尾数字段不能表示12.1的正规化小数部分。

答案：A。

每片DRAM宽8位，即每个芯片位置保存一个字节。8片低位交叉编址后，连续8个字节分别放在8片芯片中，可以通过64位总线一次取出这些字节。

按字节地址A编号，芯片号为A mod 8，也就是地址最低3位；余下高位选择片内位置。目标0018001DH末位D=1101B，低3位是101，芯片号5。

只有A与目标同片。C虽是紧邻的字节，却正因交叉编址而落在相邻芯片；地址高位接近不能代替芯片号判断。64位总线决定一次最多传8字节，不表示每个字节地址都要先除8再取最低3位。

答案：D。

ISA规定程序与系统软件能观察到的机器接口，包括指令功能、寄存器、寻址和受保护的控制机制。A中是否存在专门I/O指令，直接决定软件怎样访问设备；B中向量或非向量中断影响中断入口的确定方式；C中分段、分页相关的地址转换机制影响操作系统使用的架构接口，都属于此类规定。

超级流水线把内部处理阶段进一步细分，改变一条指令如何在处理器内部执行。不同处理器可以保持同样的指令、寄存器及可见行为，同时采用不同流水线深度，因此它是微架构实现选择，D正确。

区分方法是检查“软件必须依据这个规定编程或管理硬件吗”，还是“硬件内部可以在不改变接口的情况下换一种实现”。不能因流水线执行的对象也是机器指令，就把流水线划分本身误当作ISA规定。

答案：B（Ⅰ、Ⅳ）。

解题思路。 先弄清 PC，再判断各类指令把程序带到哪里。PC 是程序计数器，用来确定接下来取哪条指令。假设当前指令的地址为 $P$，长度为 $L$，它在存储顺序上的后继地址是 $S=P+L$。普通顺序执行接着取地址 $S$ 的指令；控制转移则把接下来取指的地址改成某个目标地址。

本题采用公开回忆版本的通常考试约定：条件转移按条件决定是否跳转；过程调用与陷入按正常安排转入另一个过程或处理程序的入口，入口不特意设置为当前指令的顺序后继；返回恢复调用方此前保存的正常后继地址。题目中的“程序下一条指令”按程序正常执行流理解，返回计为恢复该执行流。不能把“不改变下一条指令的地址”误读成 PC 寄存器在整个执行过程中完全不更新。

逐项分析。

Ⅰ 的“可能”有明确条件：跳转条件不成立。例如“结果为零才跳转”，而计算结果不为零时，程序就继续执行顺序后继指令。条件跳转并不要求每次都发生跳转。

Ⅱ 的两个动作必须分开看：保存的是“调用方将来回来后执行哪里”，立即执行的是“进入被调用过程”。例如调用指令位于地址 100、长度为 4 字节，子程序入口是 500：CALL 保存返回地址 104，随后使 PC 指向 500。保存了顺序后继 104，并不代表 CALL 执行后立即取地址 104 的指令。

Ⅲ 是主动进入系统处理程序的控制转移，例如通过陷入指令请求系统服务。在题目采用的正常模型中，下一步执行相应处理程序，而不是继续原程序的顺序后继，所以不计入。

Ⅳ 的作用是返回。沿用上例，子程序完成后执行返回指令，将保存的 104 恢复到 PC，原程序便从调用后的那条指令继续。两份公开参考答案把这种“恢复原程序下一条”计为可能不改变程序下一条指令的地址。这里并没有说 RET 不更新 PC：RET 明明把 PC 设置成了保存的返回地址。

选项判断。 按上述约定，符合的是Ⅰ和Ⅳ，即 B。A、C、D 均包含Ⅱ，而正常的过程调用要转到被调用过程入口，因此这三个选项都不符合。D 在所采用的完整公开版本中是“Ⅱ、Ⅳ”，应按这一组合判断。

地址与参照的边界。 “调用指令的下一条”与“返回指令自身在存储顺序上的下一条”不是同一个地址。若把问题严格解释为“执行某条指令后是否取它自身的顺序后继”，RET 是否符合就取决于保存的返回地址 $R$ 是否恰好等于该 RET 的后继地址 $S_{RET}$，不能仅凭“返回”二字直接推出二者相等。

如果进一步允许刻意安排所有目标地址，例如把 CALL 的目标也设为它自身的顺序后继，那么 CALL 同样可能取到该后继；某些体系结构中若处理入口可配置，陷入的目标也可能出现数值重合。这些特殊地址安排超出了本题默认的正常入口模型。B 是本题所采用公开回忆版本及考试约定下的答案，不能推广成“CALL 或陷入在任何地址安排下都必然取不到自身后继”的机器规律。

答案：C。

4路组相联表示每组有4行，并不是整个Cache只有4组。总计1024行，因此组数为1024/4=256。

主存块大小32B，地址1028位于从1024到1055的主存块内：
$\text{块号}=\lfloor1028/32\rfloor=32,\quad \text{组号}=32\bmod256=32.$
数据的块内偏移为1028 mod 32=4，4字节数据占偏移4～7，没有跨块，所以只需这一个组，选C。

A的4是块内偏移而不是组号；B、D也不符合先求块号再对组数取模的映射规则。此处1028为十进制地址，没有十六进制H标记。组内哪一行保存该块由匹配和替换策略决定，不影响组号计算。

答案：A。

页大小256B=$2^8$B，16位虚拟地址分为8位虚页号和8位页内偏移。TLB共有16项、每组4项，所以有4组；虚页号低2位选组，高6位作Tag。

题给页号22是十进制，二进制为00010110：组号10B=2，Tag=000101B=05H。反向验证，组2、Tag05H对应虚页号5×4+2=22。

主存页表中该页装入位P=0，表示页面不在主存；在题设TLB与页表同步后，不能还用有效翻译访问这个页。因此Tag05H、V=1不可能，选A，哪怕A里的PPN与原PPN不同也不能使它合法。

B的Tag06H对应页号26，不是页22，题目没有否定其驻留状态；C、D的V=0表示条目无效，旧Tag和PPN可以残留而不参与翻译。不能把无效表项中的残留位串当成当前有效映射，也不能把虚页号22直接写成Tag16H。

答案：A。

CPI是完成指令所用时钟周期数除以完成的指令数。单周期数据通路规定每条指令在一个时钟周期内完成，题目又排除了额外处理开销，因此I正确。

多周期数据通路把取指、译码、执行等分到多个周期，即使不同指令所需周期不同，在本题通常的多周期结构中每条也都需要多个周期，所以II正确。它的单周期通常较短，CPI更大并不直接意味着总执行时间一定更长。

流水线让多条指令的不同阶段重叠，理想稳定状态可每周期完成一条，CPI趋近1；但仍可能有数据、控制或结构冒险产生停顿，有限指令序列还包括装入、排空。因此不能无条件断言实际CPI恰为1，III错误。

选A。不要把“某条指令经过五个流水阶段”误写成流水线CPI必为5，也不要把理想吞吐率误作所有情况下的精确平均值。

答案：D。

特权指令只能在内核等高特权模式下执行，目的是防止普通程序直接改变设备或机器控制状态。A的I/O指令直接访问设备；B关中断会影响系统响应中断的能力；C中断返回会恢复受保护的程序状态和运行模式，都需要相应权限。

系统调用则是普通用户程序请求内核服务的受控入口，例如应用请求读文件。若系统调用指令本身也只能在内核模式执行，用户程序反而无法借它进入内核，因此D不属于题目所问的特权指令。

执行系统调用时，硬件按规定切换权限并转入内核入口；之后执行的内核操作可以是特权操作。必须区分“用户能执行的入口指令”和“进入之后由内核执行的服务”。题干指出I/O子系统需要一些特权指令，不等于它涉及的所有指令都是特权指令。

答案：C。

中断发生时，处理器需要暂时离开当前程序，去执行中断处理程序，之后还要回到正确位置继续。因此在控制流转入处理入口前，断点，也就是被中断程序应恢复的指令地址，必须由硬件响应过程保存，C正确。否则处理程序一开始就已经失去原来的PC信息。

A开中断可通过软件指令完成；D通用寄存器可以在处理程序入口由保存现场的指令逐个压栈，并在退出时恢复，并非所有寄存器都必须由硬件保存。

B中断判优可以通过硬件优先逻辑实现，也可以结合软件查询决定先服务哪个来源，题目没有限定为只有一种实现，所以不能说必由硬件完成。这里考的是“必须”，并不是“某台机器的硬件能否代做”。保存断点与保存通用寄存器也属于不同内容，不能因两者都叫保存现场而混为一谈。

答案：C。

按本题操作系统模块的语境，装入程序负责把可执行程序放入可运行的环境，建立或调整进程地址空间、映射代码与数据并准备执行入口。这些核心装入操作涉及受保护的进程和内存管理状态，由内核完成，因此选C。

编译程序把源代码翻译为目标代码，链接程序连接目标模块与库，命令解释程序读取并解释用户命令；这些通常作为普通用户程序运行，分别排除A、B、D。它们需要文件读写或创建进程时，可以发起系统调用，由内核代为完成对应操作，但调用内核服务不等于整个程序都在内核模式执行。

题目对“装入程序”的称呼指操作系统的装入功能；实际系统中某些动态链接和装入辅助代码也可位于用户空间，应结合这里的模块定义判断，不能只按程序名称笼统推断所有现实实现。

答案：D。

在一次正常访存中，CPU产生虚拟地址，MMU依据TLB或页表完成地址转换，并检查页表中规定的访问权限；CPU译码等硬件还检测指令编码是否合法。操作系统建立页表和权限规则，但并不为每一条普通指令的软件执行逐项检查，因此A、B、C把硬件检测工作错误地都归给了操作系统。

若硬件发现缺页、非法指令或越权访问等异常，会保存必要状态并转入异常处理入口，由操作系统决定调页、发出错误通知或终止进程等后续动作，D正确。

可以把分工理解为“操作系统设置规则—硬件高频执行检查—操作系统处理异常”。TLB未命中也不一定就是缺页：还可能查内存页表后得到有效映射。不能因页表由操作系统维护，就认为每次虚实地址转换都需要一段操作系统代码参与。

答案：D。

同一进程的线程共享进程虚拟地址空间，其中包括代码、全局数据和堆，所以一个线程在堆中分配的对象，其他线程持有合法指针时也能访问，D正确。共享访问仍可能需要同步，不能把“共享堆”理解成所有并发读写都自动安全。

A错误：用户级线程可以由用户空间的线程库创建和管理，内核不一定直接识别每个用户线程。B把常见映射方向写反了，讨论的是一个或多个用户线程怎样映射到内核调度实体，而不是把多个内核线程映射到一个用户线程。

C错误：不同内核级线程需要分别保存各自在内核中运行的调用链和执行现场，因此各有内核栈；若共用一个栈，会互相破坏现场。线程可以共享进程资源，但程序计数器、寄存器状态和独立执行所需的栈属于每个线程自己的运行上下文。

答案：A。

图中每个进程先wait(S)，再执行Q，最后signal(S)。记录型信号量的wait先把S减1：结果非负就通过，结果为负则阻塞；signal归还许可并在需要时唤醒等待者。

初值5表示最多有5个进程取得许可进入Q。当S=−2时，负值的绝对值2表示有2个进程因wait而等待，故n=2；5个初始许可已经全部被占用，当前进入Q并尚未归还许可的进程有5个，故m=5，选A。

在8个进程中，另一个进程可以尚未申请，也可以处于不占用许可的其他状态；不能仅用8−5就断定阻塞3个。B正是多算了一个阻塞者，C、D则让进入Q的数量超过初始5个许可。信号量负值表示等待进程数，不表示有“负的可用资源”，也不能用5−(−2)=7当作正在执行Q的数量。

答案：C。

本题采用 Bernstein 读写无冲突判定模型：两个进程独立执行，没有额外的同步保护；只根据读集、写集判断是否存在可能改变另一进程输入或覆盖其输出的冲突，不利用具体数据值、相同常量写入等特殊语义。在这个模型中，无冲突条件是三类交集都为空。

因此，需要同时成立的是 I、II、III，选择 C。A 漏掉两类读写冲突；B 漏掉写写冲突；D 额外禁止了安全的共享读取。

这里的“充要条件”是在题目采用的读写集合独立性模型内判断无冲突，并不意味着所有实际程序只要读写集合相交就必然执行错误。若程序使用同步保护，或两次写操作有特殊且已证明安全的语义，即使存在交集也可能得到正确结果；这类情形超出了本题默认模型。

答案：C。

图中一级、二级、三级页号各9位，页内偏移12位。页框大小因此为 $2^{12}=4096$B。一张第三级页表有 $2^9=512$ 项，每项8B，大小512×8=4096B，恰好占1个页框。

题目问整个进程最多有多少第三级页表，而不只是一张表多大。一级页表的512项分别可以指向512张二级页表，每张二级页表的512项又分别可指向512张第三级页表，因此最多有

$$2^9\times2^9=2^{18}=262144=256\mathrm K$$

张第三级页表，也就占256K个页框，选C。

A的512只算某一张二级表能指向的数量，漏掉一级展开；D的128M是三级索引共同可以表示的数据页数 $2^{27}$，不是第三级页表自身数量。64位地址顶部25位为图示保留位，不能再把它们算进页表索引。

答案：D。

平均访存时间不仅包含读内存的时间，还可能包含查页表和极为昂贵的缺页处理。四种技术的作用应分别判断：

I的TLB缓存近期地址翻译，命中后直接得到页框号，减少主存页表访问，能降低平均时间。

III工作集模型尽量保留进程近期需要的页面，并依据内存需求控制运行，减少频繁缺页及抖动；IV页缓冲队列使部分换出页仍暂留在内存，近期再次引用时可能直接恢复，减少外存调页开销。两者都能减少昂贵缺页代价。

II多级页表主要通过按需分配节省页表空间；TLB未命中时，反而可能需要逐级多次访问页表，不能把它本身视为直接降低访存时间的技术。因此选I、III、IV，即D。A、B遗漏缺页控制手段，C还遗漏TLB并错误计入多级页表。查得快和尽量少缺页，是不同的优化方向。

答案：B。

两个进程共享页S，意味着两边访问的是同一个物理页框，而不是各自保留一份内容副本。因此各自的虚拟起始地址VA1、VA2必须映射到相同的物理页框起点，B正确；相同页内偏移也就对应相同物理字节。

A错误：两个进程的虚拟地址空间相互独立，S在其中的位置可以不同。例如一个进程放在虚拟页10，另一个放在虚拟页20，两项都填相同页框号即可共享。

C错误：两份页表项中的页框号需要一致，但权限、访问位等字段不一定相同，例如一方只读、另一方允许写入。D错误：两份页表是不同的管理结构，其表项在各自空间中的位置也没有必须相同的要求。

核心对应关系是“不同虚拟地址→同一物理页”，不能把共享物理存储误解成虚拟地址及整个页表项逐位相同。

答案：D。

设备驱动把内核的抽象I/O请求转换为特定设备可以执行的操作。它需要初始化或启动设备，也需要读写设备寄存器、提交或完成传输等代码，A、B正确；为了使内核能够按统一方式调用不同驱动，还需定义驱动与内核之间的接口，C正确。

块设备把数据组织为可寻址的数据块，常结合块缓冲、请求队列及块传输；字符设备通常按字符流或设备自身事件提供访问，未必具有按任意块定位的功能。因此两类驱动不能被笼统规定为采用完全相同的I/O控制方式，D错误。

“对内核提供统一接口”和“内部以相同方式控制所有设备”不是同一件事：接口可以统一，设备相关实现仍可不同。两类设备都可能使用中断，也不意味着它们的读写单位、缓冲和请求处理机制都相同。题目问错误叙述，选D。

答案：D。

鼠标输入的大致过程是：设备产生数据→控制器把数据放入设备接口的数据寄存器并发中断请求→CPU响应中断、转入内核入口→中断处理程序读取寄存器并把输入保存到内核数据区。最后一步由软件处理程序完成，选D。

B的用户模式到内核模式切换已经在硬件响应中完成，处理程序开始执行时通常就在内核模式；C的设备数据写入接口寄存器是设备或控制器完成的工作，不是中断程序先替设备放进去。

A也错误：鼠标中断并不要求把当前进程阻塞。响应结束后当前进程可以继续执行；处理程序还可能唤醒正在等待输入的进程，这与阻塞被中断进程是不同动作。

判断中断题时，应把“中断请求前的设备动作”“硬件响应”和“随后执行的软件处理”按时间分开，避免将整个过程都归入中断服务程序。

答案：B。

网络分层把大系统分为有明确职责和接口的部分。每层可以通过统一标准与其他实现互通，所以A正确；一层内部改进实现时，只要保持接口和对外行为，其他层通常无需同步重写，C正确；设计者也可以分工处理各层功能，降低整体设计和实现复杂度，D正确。

但每增加一层，都可能增加头部封装、数据传递、复制和处理开销。层次过少不利于职责划分，层次过多也可能降低效率，因此不存在“层次越多效率越高”的普遍关系，B错误。

例如应用数据依次经过传输、网络、链路等层会增加相应首部；这项成本换来了模块化和互通能力，却不能据此推出再增加任意多层都能提升速度。题目问错误叙述，选B。这里讨论分层的工程优点，不是要求以最大层数作为设计目标。

答案：D。

给定带宽和信噪比，要用香农公式求理想最大比特率：

$$C=B\log_2(1+S/N).$$

带宽200kHz=200000Hz，信噪比1023已经是线性比值，没有dB单位，无需再指数换算。于是

$$C=200000\log_2(1024)=200000\times10=2000000\ \mathrm{bit/s}.$$

分组1500B含1500×8=12000bit，最短传输时延是把这些比特送上链路所需时间：

$$T_{\min}=12000/2000000=0.006\ \mathrm s=6\ \mathrm{ms}.$$

因此选D，A、B、C均小于该容量下能实现的最小值。

这里求的是传输时延，不包含传播距离、排队或处理时间。易错点是把1500字节当成1500比特，或直接把200kHz当成200kbit/s；频率带宽要通过容量公式才能转成比特率。

答案：B。

先计算数据帧本身的发送时间：
$T_{\text{data}}=\frac{1500\times8}{300\times10^6} =40\ \mu\mathrm s.$
题目从“开始发送数据帧”计时，因而发送之前争用信道所用的DIFS已经不在计时区间内。

接收方收完数据后，等待短帧间间隔SIFS=28μs，再返回ACK。题目忽略ACK等其他帧传输时间和传播时间，所以发送方最早确认接收成功需要40+28=68μs，选B。

A的40只到数据发送结束，没有等待确认；C的168把发送前DIFS加到数据时间，却漏掉SIFS；D的196把DIFS和SIFS都计入。SIFS较短，使确认能够优先于新一轮竞争得到发送机会，但这里并不需要再等待DIFS。正常CSMA/CA实际还可能有退避等时间；题目问给定条件下的最少时间。

答案：B。

按图中端口分组，H1、H2、H3在VLAN1，H4、H5、H6在VLAN2。VLAN隔离二层广播域，交换机不会只因目的MAC匹配另一VLAN中的主机，就把帧跨VLAN转发。

逐帧判断：

因此仅F1、F3，选B。A误认为只要目的为H3就能跨VLAN，C、D则把另一个VLAN的广播也交给H3。交换机在同一物理机箱内不代表所有端口属于同一个逻辑局域网；跨VLAN通信通常需要三层转发机制，题目没有提供该机制。

答案：B。

先按链路费用重算下一跳，再聚合，不能继续沿用断链前的S1路由。R1—R2断开后：

• 到R3，直接走S2费用6，经R4再到R3费用3+4=7，选S2。
• 到R2，只能经R3继续前往：最短费用6+5=11，第一跳仍为S2。
• R4的两个子网继续走S3，特定主机及Internet出口分别保持S4、S0。

所以199.10.20.0/27和199.10.20.32/27都走S2，可精确合成199.10.20.0/26。S3对应的.64/26及.128/25可用一个更大的/24覆盖，再由前面的/26更具体路由覆盖其不应走S3的部分：

最长前缀匹配使.0～.63选/26，其余.20网内地址选/24，外部地址按具体主机项或默认项处理。四种转发方向需要对应项，充分聚合后共4项，选B。网络挂在R2后面并不等于R1的本地直连网，断开的S1应退出这些目的的转发路径。

答案：A。

OSPF是链路状态内部网关协议，支持把一个自治系统划分为多个Area。每个区域内主要传播本区域的详细链路状态，由区域边界路由器连接，并以骨干区域Area 0组织区域间路由。这样可以减少大网络中每台路由器需要处理的详细拓扑范围，I正确。

RIP是距离向量内部网关协议，按跳数交换路由，没有题目所问的OSPF式Area层次，II不符合。BGP主要负责自治系统之间的路由交换，属于外部网关协议；它有自治系统号等概念，也有自治系统内部的BGP会话，但不能因此把它归作题目描述的区域划分内部网关协议，III不符合。

只有I，选A。C把BGP计入了区域内部协议，B、D则计入RIP。这里要同时满足“内部网关协议”和“可划分Area”，只满足其中一项不能入选。

答案：C。

/22网络有32−22=10位主机位，共 $2^{10}=1024$ 个地址。等分成32=$2^5$个子网，需要再取5位作子网号，因此新前缀为22+5=27；每个子网剩5位主机位，块长32个地址。

123.4.5.211位于原网络覆盖的第三字节4～7范围内。/27的掩码为255.255.255.224，最后一字节211=11010011B，与224=11100000B相与得到11000000B=192，所以其子网为123.4.5.192/27，地址范围.192～.223，选C。

A、B把第三字节错误改成4；B、D使用/28会把1024地址分为64个等大子网，而不是题设32个。这里求网络地址，应保留前27位并清零后5位；不是把整个IP向原网络起点简单截断。

答案：D。

HTTP请求之间不会自动保留上一次请求的用户状态。Cookie允许服务器给客户端保存一个标识，后续符合条件的请求带上该标识，服务器据此关联会话或用户数据。

因此A可以通过标识关联浏览行为，B可以结合历史偏好进行个性化推荐，C可以把多次请求关联到同一个购物车。这些通常由Cookie保存标识、服务器保存具体业务数据，不要求把整辆购物车或全部用户历史都写进Cookie。

D缩短Web对象响应时间，主要依靠缓存、就近部署、连接复用及减少处理开销等技术，并非Cookie的典型用途，选D。Cookie随请求发送还可能增加少量字节；它不是一种自动缓存Web对象的机制。区分Cookie和缓存时，可看前者解决“这些请求属于谁或哪个会话”，后者解决“已有对象能否复用”。

（1）设计思想：沿查找路径找最近值。 二叉搜索树满足左子树关键字小于根、右子树关键字大于根；按这一严格定义，关键字互异。要找与k最接近的值，不必访问整棵树，可沿查找k的路径进行，并维护当前最小绝对差best及达到它的结点。

访问结点p后：

• 若p->data<k，左子树所有值更小，离k都比p更远；先记下p的候选资格，再只向右走。
• 若p->data>k，右子树所有值更大，离k都比p更远；对称地只向左走。
• 若p->data==k，差值0已经是最小值，可以结束。

新差值更小时清除原候选；差值相等时保留并列结果。非零差d最多对应k−d、k+d两个不同关键字，因此两个指针已足够，无需候选数组。

（2）完整C实现。 以下重复给出结点类型，便于单独理解代码。先提升到long long再减法，避免两个int直接相减溢出。

#include <stdio.h>
#include <limits.h>

typedef struct BSTNode {
    int data;
    struct BSTNode *left, *right;
} BinTNode;
typedef BinTNode *BTree;

void searchX(BTree root, int k) {
    BTree p = root, first = NULL, second = NULL;
    long long best = LLONG_MAX;
    while (p != NULL) {
        long long diff = (long long)p->data - (long long)k;
        if (diff < 0) diff = -diff;

        if (diff < best) {
            best = diff;
            first = p;
            second = NULL;  // 更近的值使原来所有候选失效
        } else if (diff == best) {
            second = p;     // 最多另有一个不同的并列值
        }

        if (p->data == k) break;
        p = p->data < k ? p->right : p->left;
    }
    if (first == NULL) return; // 也安全处理空树
    printf("最小绝对差：%lld；关键字：%d", best, first->data);
    if (second != NULL) printf("、%d", second->data);
    printf("\n");
}

过程示例。 设根8，左孩子3，3的右孩子5，5的右孩子7，查k=6。沿8→3→5→7走，差值分别2、3、1、1：5使best更新为1，7与之并列，最终输出差1及关键字5、7。若查k=8，在根处就输出差0、关键字8。

为什么不会漏掉最近结点？ 每次舍弃的子树中，所有值都在当前结点远离k的那一侧，所以其距离严格大于当前距离。当前结点已比较过，它们不可能再改善或并列当前最优结果。按这一理由逐层排除，到达空指针时所有可能最优值均已在查找路径上处理。

复杂度与边界。 每层只访问一个结点，时间O(h)、额外空间O(1)，h为树高；平衡时O(log n)，退化时O(n)。k比全部关键字小或大时，过程分别沿最左或最右路径找到端点。long long能容纳两个int边界值之间的差。若另外允许重复关键字结点，需扩展算法继续找同值结点，不能直接套用本题互异关键字下的“至多两个结点”结论。

（1）逐步模拟两种出栈次序。 栈后进先出，输入1、2、…、9只能按顺序入栈。

第一种2,3,1,6,4,7,5,9,8不能得到。先压1、2弹2，再压3弹3、弹1，随后为了弹6，必须把4、5、6依次压入。弹6后栈顶是5，下面才是4，而下一个要求输出4，无法越过5，故失败。

第二种2,3,1,5,6,7,4,9,8可以得到：

（2）无法实现的三项关系。 若存在i<j<k且

$$P_j<P_k<P_i,$$

则序列不合法。为了先输出最大的P_i，比它小的P_j、P_k已按递增次序入栈，较大的P_k在较小的P_j之上。只要二者还未输出，就必须先弹P_k，不能按位置j、k先弹P_j再弹P_k。第一种序列中的6、4、5就是这种“最大—最小—中间”模式。

（3）n=4、以2开头。 先压1、2并弹2，此时栈底留1，尚可依次压3、4。全部合法结果为2134、2143、2314、2341、2431，共5个。例如2413不合法：为了弹4已经压3，弹4后3挡在1上方。

（4）推广到n=k。 以1开头时，先把1压入再弹出，剩下2～k与k−1项的原问题等价，故有M种。

以2开头时，必须先压1、2并弹2。把剩下的递增元素1、3、…、k重新编号为1、2、…、k−1；最小元素1虽然已在栈底，但任意非空合法操作本来也会先压最小项，剩余可实现次序与k−1项问题一一对应，所以仍有M种。

所有合法出栈序列数为卡特兰数。k次入栈和k次出栈的操作排列共 $\binom{2k}{k}$ 种，排除任何前缀中出栈次数超过入栈次数的非法排列，得到

$$C_k=\frac{1}{k+1}\binom{2k}{k}.$$

已知 $M=C_{k-1}=\binom{2k-2}{k-1}/k$，两式相除得到
$\frac{C_k}{M}=\frac{2k(2k-1)}{k(k+1)} =\frac{4k-2}{k+1},\qquad C_k=\frac{4k-2}{k+1}M.$
以1、2开头只是全部序列的一部分，不能把总数写成2M。代入k=4、M=5，得到总数14，且上述两类各5种，便于核对。

（1）主存单元与寄存器宽度。 按字节编址意味着每一个主存地址对应8位字节，因此主存单元宽8位；“16位计算机”的机器字长为16位，通用寄存器宽16位。指令16位占两个相邻字节，不能因指令字长16位就把编址单元也写成16位。

（2）操作码能否重用。 R型高4位固定0000，译码器先看到这个前缀，再以低4位op1确定具体运算；I型直接以高4位op2识别操作。因此op1和op2可以相同，它们处于不同的译码层级，例如某个低4位值在R型中表示加，而同值放高4位可标识一种I型指令。

I型与M型都用最高4位作直接类型/操作标识。如果op2与op3相同，后面位段又没有额外的类型区分信息，译码器无法唯一选择两种格式，因此二者不能相同。

（3）译码及16位加法。 机器码按四段拆为0000｜0010｜1001｜0001，分别为R型前缀、rt=2、rs=9、op1=加，功能为R2←R2+R9。

$$ABCD_H+F001_H=19BCE_H.$$

寄存器只有16位，保留低4个十六进制位，故R2=9BCEH；源寄存器R9未被写入，仍为F001H。

（4）实现表达式。 R15保存x的地址，x、y各占2B，故y在R15+2。按“取x—乘16—减5—存y”编码：

−5的8位补码为256−5=251=FBH，扩展到16位得到FFFBH，完成减5；左移4位产生乘 $2^4=16$ 的机器操作。注意I2中间8位同时包含目的寄存器号和移位位数，不是8位普通立即数；M型偏移以字节为单位，所以y的偏移是2而不是1。

（1）部件名称。 ①、②都是多路选择器。①从IR.rt与固定寄存器号15中选择读地址ra；②从IR.rs与固定号0中选择读地址rb。输出的是通用寄存器组的读取编号，随后busA、busB才给出相应寄存器数据。

（2）ExtOp位数。 扩展器输入IR低12位，输出16位，需要区分：

1. I型无符号imm8：取低8位，高8位补0。
2. I型有符号imm8：取低8位，用位7的符号补齐高8位。
3. M型有符号offset：取低12位，用位11补齐高4位。

有3种不同扩展动作，1位只能编码2种，至少 $\lceil\log_2 3\rceil=2$ 位。符号扩展是复制符号位，不是给有符号数任意补1。

（3）取指周期。 指令为16位、主存按字节编址，所以取当前指令时用PC作为主存地址，并在本周期计算下一地址PC+2。按图中输入编号：

ALU执行加法、PCin允许更新，内存读出的指令进入IR。ALUBsrc有三个输入，因此使用两位表示，图中编号1应写01。

（4）左移执行周期。 左移用R[rt]作数据、num作位数，ALU A端应取busA；B端取扩展器输出。结果写回rt指定的寄存器：

ExtOp可以采用与M型相同的12位符号扩展。R型的num在IR位7～4；无论这三种扩展怎样处理高位，位7～4都原样保留。左移操作从这四位获取移位位数，不把整个扩展结果当作位数，因此即使高位还含rt或符号扩展位，也不影响num。关键是本题字段位置与ALU对移位字段的使用方式。

（1）先按规则建立时间轴。 优先权越大越先执行，但新来的高优先权进程只能在时钟中断时抢占。每次进入就绪队列都获得新的50ms时间片；时间片用完才降低优先权，因更高优先权抢占则不降低。

10ms时P1、P2到达，先运行优先权4的P2。P3在12ms、P4在14ms到达，P4虽更优先，却不能立刻抢占，要等20ms时钟中断。此时P2已执行10ms，还剩10ms，重新排队但优先权保持4。

所有执行时间合计95+20+40+60=215ms，自10ms起连续运行到225ms，符合表中终点。

计数从10ms开始，10、20、…、220ms共有 $(220-10)/10+1=22$ 次时钟中断。表中7个运行区间各对应一次选定进程执行的调度，故CPU调度7次；同一进程持续运行期间的普通时钟中断不自动算一次重新调度。P1、P3、P4首次执行分别为90、140、20ms。

（2）改变参数。 时间片改100ms后，P4剩余全部60ms可从20到80一次完成，P1全部95ms也可从90到185一次完成，不再因50ms耗尽而两次重新排队。运行次序为P2、P4、P2、P1、P3，共5次调度，所以次数减少。P2的高优先权抢占仍存在，不能误写为只有4次。

时钟间隔从10ms改1ms，会更频繁进入时钟中断并检查计时、调度等状态，因此系统开销增加。更及时地响应不代表中断处理本身没有成本。

（1）三项定位与数量计算。

一盘块4096B，一inode128B，故每块放4096/128=32个inode。编号从0开始，inode1000前面有1000项：

$$1000=31\times32+8.$$

它在inode表的第31个块中，物理盘块号为100+31=131，块内字节偏移为8×128=1024。不能因编号1000就直接访问1000号盘块。

文件偏移从0计，21460所在数据块序号为

$$\lfloor21460/4096\rfloor=5,\qquad21460\bmod4096=980.$$

直接地址5项覆盖序号0～4，序号5开始使用一次间接地址。inode已在内存，若相关块尚未缓存，先读一次间接索引块，从其第0项取得第5号数据块地址，再读这个数据块。因此最多访问2个盘块。索引块保存的是数据块号，不是所要的文件数据；inode本身无需再计一次读取。

inode表共有4096块，每块32项，最多有4096×32=131072=$2^{17}$个inode。每个文件对象需要inode，故空间足够时最多可创建131072个文件；目录也会占其中的inode，不能把目录当成不耗用名额的对象。

（2）删除非空目录及其中文件。 图中dir1包含file，应先处理file，再回收dir1。需要修改的元数据包括：

• 磁盘块位图。 file长30KB=30720B，数据块数为 $\lceil30720/4096\rceil=8$。前5块由直接项指向，后3块由一次间接索引块指向，所以回收8个数据块及1个间接索引块，对应位由1置0。目录dir1自身内容占用的盘块及其实际使用的索引块也须回收；题目未给目录大小，不臆定其具体块数。
• inode位图与对应inode。 把file的inode1000、dir1的inode201标为未占用，回收这两个inode，解除其块地址等有效占用信息。父目录dir的inode100保留。
• 父目录内容。 从dir中删除“dir1→201”的目录项，并更新被修改目录的长度、时间等有关元数据。原来指向dir1的名字不能在回收后继续保留。

仅删名字会泄漏块和inode；仅清位图又会留下指向已释放对象的目录项。目录项、inode分配状态和磁盘块分配状态应共同完成相应更新。

本题采用教材中的常用 TCP 模型：初始拥塞窗口 $cwnd=1MSS$，慢开始阶段每收到一个确认新数据段的 ACK 就增加 1 MSS；文件发送并获得确认后，由 C 主动关闭，服务器的 ACK 与 FIN 分开发送，形成常规四次挥手。 题面所给“初始阈值 8 MSS”是慢开始阈值 $ssthresh$，不是初始 cwnd；两者不能混淆。

（1）三次握手及确认序号。

C 先发 SYN，seq=1000；服务器返回 SYN=1、ACK=1，seq=2000，并确认 C 的 SYN。SYN 消耗一个序号，因此 ack_seq=1001。C 再确认服务器的 SYN，完成 三次握手。双方首个可用数据序号分别为 1001、2001。

（2）由确认号判断已确认的数据与拥塞窗口。

C 首个数据字节的编号是 1001。ack_seq=2001 表示服务器已按序接收编号 1001～2000 的 1000 B，即两个 500 B 数据段。按逐段确认和初始 cwnd=1 MSS：

收到题给确认后，cwnd 为 1500 B，仍低于慢开始阈值 8 MSS。接收窗口始终为 1000 B，发送窗口宽度取两者较小值：

$$\min(cwnd,rwnd)=\min(1500,1000)=\mathbf{1000\ B}.$$

若还有未确认的在途数据，实际新发送额度还要减去在途字节数。服务器 ACK 中的 seq=2001 并不表示它发送过 2001 B 数据，纯 ACK 不消耗数据序号。

（3）四次挥手及最后收到的报文段。

按 C 主动关闭、ACK 和 FIN 分开发送的约定，顺序为 C 发 FIN、服务器确认、服务器发 FIN、C 发最后确认，共 四次挥手。

C 上传的 2000 B 数据占序号 1001～3000；FIN 使用下一个序号 3001，也消耗一个序号，因此服务器确认到 3002。服务器未发送业务数据，SYN 之后的可用序号仍为 2001，纯 ACK 不消耗序号。所以 C 最后收到的服务器 FIN 段中：

$$\boxed{seq=2001,\quad ack\_seq=3002,\quad FIN=1}.$$

C 随后发送最终 ACK，确认服务器 FIN 到 2002。题目问 C“收到”的最后一段，不能误答 C 自己发出的最终 ACK。

若服务器将确认与 FIN 合并，可减少关闭报文数；若由服务器先关闭，C 最后收到的报文性质也会变化。因此本小问按开头声明的常规关闭模型作答。

（4）从请求建连到确认文件已全部收到的时间。

忽略报文段传输时延，C 收到 SYN+ACK 后即可发送第三次握手 ACK，并开始发送数据。初始窗口为 1 MSS，接收窗口为 2 MSS，总文件为 4 MSS，发送批次为 1、2、1 个段：

建立连接需要 1 RTT，数据发送并全部获确认需要 3 RTT，故 C 确认服务器成功接收文件的时间为：

$$T=4RTT=4\times5=\boxed{20\ \text{ms}}.$$

服务器实际收到最后数据的时刻早于 C 收到最后 ACK 的时刻，但题目问的是 C 确认成功的时间。释放连接的时间不计入本小问。

若初始 cwnd 至少为 2 MSS，则同样的 rwnd 下可按 2、2 个段发送，完成确认时间会改变；20 ms 的前提是本题采用的首轮 1 MSS 教材模型。