2012年计算机408真题

答案：B。

递归时间要看调用了多少次，以及每次额外做多少工作。fact(n)只调用一次fact(n−1)，参数依次为n、n−1、……、1，共n层，每层除递归外只有判断、一次乘法和返回，按常数时间计算。因此 $T(n)=T(n-1)+O(1)$，展开得到 $T(n)=O(n)$，选B。A要求每次把规模按比例缩小，如n/2；C要求每层还有对数等额外工作；D通常对应各层额外工作随规模线性增长，本程序都不具备。n=0、1会立即返回，但渐近复杂度考察n增大的情形；递归栈占O(n)空间，这是空间开销，不能误算成额外时间因子。

答案：A。

中缀转后缀时，操作数直接输出；操作符需按优先级决定弹栈，左括号入栈，右括号把匹配括号之间的操作符弹出。读到a+b后，遇到同优先级的减号，应先弹出此前的+，因此不是把所有已读操作符都留在栈中。继续读 -a*((c+d 时，栈从底到顶为 -、*、(、(、+，共有5个，包括题目计入的括号。遇到第一个右括号后，+和内层左括号出栈，后续 /、- 的处理也不会超过5个，故选A。B、C、D分别多计了已经因优先级或括号匹配出栈的符号。最大深度发生在尚未遇到右括号、且嵌套运算都待定时。

答案：A。

前序的第一个结点和后序的最后一个结点都是根，所以根为a。前序紧接根的e是根的第一个非空子树的根；若a有两个孩子，e子树在后序中应先结束，后面还会有另一个子树，才轮到a。现在后序中e恰好在a之前，且从b到e的4个结点全部属于e子树，说明a只有一个非空子树，孩子就是e，选A。B、C都额外添加了一个根的孩子，与该分段矛盾；D忽略了孩子身份已能确定。前后序未必能确定e是左孩子还是右孩子，也未必唯一确定整棵树，但“不确定左右位置”不等于“不确定有没有这个孩子”。

答案：B。

平衡因子是左子树高度减右子树高度。所有非叶结点因子均为1，意味着高度为h的非叶结点，其左右子树高度分别为h−1、h−2。规定空树高度0、叶结点高度1，令N(h)为结点数，则 $N(h)=1+N(h-1)+N(h-2)$，初值N(0)=0、N(1)=1。逐层计算N(2)=2、N(3)=4、N(4)=7、N(5)=12、N(6)=20，所以选B。A的10少于高度6所需的最少结点数20，C的32与D的33不满足所有非叶结点平衡因子均为1时的递推。不能使用满二叉树的 $2^h-1$，因为本题左右高度一直相差1；题中“平衡”允许高度差为1，并不表示左右子树等高。

答案：C。

邻接表只保存实际存在的边。广度优先遍历把一个未访问顶点标记后入队，出队时扫描它的全部邻接边；借助visited数组，一个顶点最多入队、出队一次，总计O(n)。有向图每条边在其起点的邻接表中出现一次，扫描全部表共O(e)，两部分相加为 $O(n+e)$，选C。A忽略边的扫描，B忽略顶点及无出边顶点的处理，D把顶点和边数量错误地相乘。若图不连通，需从尚未访问的顶点重新启动BFS，仍然每个顶点、边只处理有限次；若改用邻接矩阵，即使边少也要扫描每行n个位置，复杂度才通常为O(n²)。

答案：C。

按本题采用的不含自环的有向图约定，邻接矩阵A[i][j]非零代表边i→j。主对角线以下全0，表示不存在i>j的边；于是每条边都由较小编号指向较大编号，按编号从小到大排列就是一个拓扑序列，必然存在。至于是否唯一，还要看边是否强制每两个顶点的先后：链0→1→2只有一种次序，而只有0→2的图可把1放在多个位置。所以结论是“存在，可能不唯一”，选C。A把唯一性说死，B把不唯一说死，D否认已经能够保证的存在性。无自环的条件不可省略为一般结论：若主对角线上允许表示自环，仅凭下三角为0不足以排除回路。

答案：C。

Dijkstra每轮选未确定顶点中当前距离最小者，选中后用它的出边更新距离。初始由a得到b=2、c=5，其他为∞；确定b后，c=min(5,2+1)=3，d=2+3=5。第二个确定c，经过c的出边得到f=3+1=4，d=min(5,3+3)=5，e=3+4=7。此时最小为f=4，所以第三个确定f；随后d=5，利用d→e权1，把e改成6，最后确定e。后续次序恰为f、d、e，选C。A、B在距离4的f之前选了更远的点，D在距离5的d之前选了e，均违背取最小暂定距离的原则。图中边有方向，不能把反向边自行加入松弛。

答案：A。

最小生成树是连通无向带权图中总权值最小的生成树。I正确：边集可能有多个选择，但“最小总权值”作为一个数必然相同。II错误：设三角形的三边权值都是1，任意两边都是最小生成树，某条最小权边可被舍去。这个例子也说明III错误，Prim从不同起点或对同权边采用不同选择，可能得到不同边集。IV错误：若图的最小生成树唯一，Prim和Kruskal必定得到同一棵；即使不唯一也可能恰好选到同一棵。因此仅I正确，选A；B、D含错误的II，C含错误的III。“树的代价唯一”与“树本身唯一”要分开判断。

答案：D。

3阶B树的非根结点至少有 $\lceil3/2\rceil-1=1$ 个关键字，最多2个。图中最右叶结点只有78，删掉后变空，发生下溢；它的相邻左兄弟为[60,62]，有2个关键字，可以借一个。借关键字不是直接把62放进最右叶，而要经父结点旋转：父结点原分隔关键字65下移到空叶结点，左兄弟最大关键字62上移替换父结点65。于是父结点变成[55,62]，左兄弟变[60]，最右叶变[65]，其余结构不变，选D。A、B错误地把兄弟原内容当作新右叶，C把上移父结点的62也留在右叶。这样调整保持了左侧关键字<62<右叶65的有序关系。

答案：A。

“确定最终位置”要求该元素以后不再需要改变它在整个排序序列中的位置。简单选择排序一趟把当前最小元素放到未排序区的首位，I满足；快速排序一趟划分把枢轴放到左右分区之间的最终位置，III满足；堆排序一趟取出最大元素放到尾部最终位置，IV满足。希尔排序仅让某个增量下的各组有序，后续缩小增量还会调整元素，II不保证；二路归并的中间趟只生成较长的有序段，段内元素仍可能因下一轮归并改变全局位置，V不保证。故只有I、III、IV，选A。B、D错误包含V，C错误包含II；不能把“局部有序”等同于“已有最终位置”。

答案：D。

直接插入排序逐个把第2到第n个元素插进前面的有序区；折半插入仍做同样n−1趟，只是用二分查找定位插入点，而不是从后向前逐个比较。因此A的总趟数相同，C都只需要常数额外空间；对于相同的插入次序和相同的等值处理约定，最终插入位置相同，需后移的元素也相同，B的移动次数不变。真正可能不同的是查找插入点的比较次数，选D：直接法可能比较有序区的多数元素，折半法每次约减半范围。折半插入能减少比较，却不能消除数组中元素后移，因而整体最坏时间仍为O(n²)，不要把“二分查找”直接理解为整个排序O(nlogn)。

答案：D。

原总时间100s，其中CPU90s，I/O时间为100−90=10s。CPU速度“提高50%”表示速度变为原来的1.5倍，同样计算工作的时间应除以1.5，所以新CPU时间 $90/1.5=60$ s；I/O没有加速，仍需10s，总计70s，选D。B的60s只算了CPU部分；A的55s可由错误地把CPU时间减半再加10得到；C的65s也没有使用正确的1.5倍时间关系。速度与时间互为倒数，速度增加50%并不意味着运行时间减少50%。分清可加速与不可加速部分后分别换算，是此类程序性能题的通用计算方法。

答案：B。

16位无符号数最大为65535=FFFFH，65530比它少5，所以x的机器数为FFFAH。赋给32位unsigned int时，需保持无符号数值65530不变，在高16位补0，低16位仍为FFFAH，得到0000FFFAH，选B。A的低位7FFAH不是65530，少了最高位的1；C不仅低位错误，还把高位补成1；D把FFFAH当作负的有符号short做了符号扩展。零扩展还是符号扩展取决于源数的有符号性质，不能仅凭x最高位为1就补1。变量y的数值仍为65530，没有因为类型变宽而改变。

答案：D。

IEEE 754单精度规格化数为 $(-1)^s(1.f)_2\times2^{E-127}$。要取最大有限正值，符号s=0，阶码不能用全1，因为它保留给无穷和NaN，所以最大E=254，实际指数为127；23位小数全1时有效数为 $1+\sum_{i=1}^{23}2^{-i}=2-2^{-23}$。结果为 $(2-2^{-23})2^{127}=2^{128}-2^{104}$，本身是整数，选D。A、B、C的指数或尾数扣除项不对应这些最大字段。题目问“能表示的最大正整数”，不是问“所有整数都能连续精确表示到多大”；后者与24位有效精度有关，不能把两个问题混淆。

答案：D。

先处理数值，再处理布局。273=256+17=00000111H，小端把最低有效字节放在最低地址，所以a从C008开始的4字节依次为11、01、00、00，C008内容为11H。a占C008～C00B，char b紧接着在C00C，占1B；short c需按2字节边界对齐，C00D是奇地址，因此留作填充，c从C00E开始，占C00E～C00F。故选D。A、B错误地把首字节当成高位00，C虽首字节正确却让short从未对齐的C00D开始。结构体内可能有填充字节，不能直接按成员长度相加而忽略对齐；这里也不需要知道b、c的具体数值。

答案：A。

Flash通过半导体存储单元保存信息，掉电后仍保留内容，可用于固态外存。读取可以直接选择地址，而写入需要进行编程操作，改写通常还受块擦除机制约束，读取和写入的过程、耗时都不同，所以A的“读、写速度一样快”错误，应选A。B指出存储元采用MOS结构、属于半导体存储器，正确；C指出非易失性，正确；D指出可按地址访问并用于替代外部存储器，也正确。这里随机访问描述的是可定位访问地址，不表示任意字节都可以像SRAM那样以同样速度直接覆盖写。区分访问定位、读写机制和掉电保持三种属性，就不会因Flash可随机读而误判A。

答案：C。

先明确本题的映射模型。 Cache 有4行，2路组相联表示每组2行，因此共有2组，每组最多保存2个主存块。计算机按字编址，每块为1字，所以主存块号等于字地址，块内地址不占位。本题采用“主存也按每组2个连续块分组，再把主存组映射到Cache组”的组织方式：

$$\text{主存组号}=\lfloor\text{字地址}/2\rfloor,\qquad \text{Cache组号}=\text{主存组号}\bmod2.$$

例如，地址0、1属于主存组0，映射到Cache组0；地址2、3属于主存组1，映射到Cache组1；地址4、5属于主存组2，仍映射到Cache组0。因而题中0、4、8映射到Cache组0，2、6映射到Cache组1。这相当于把地址从高到低划分为区号、Cache组号、组内块号、块内地址，其中组内块号占1位、块内地址占0位。不要把组内块号误说成块内地址。

逐次模拟LRU。 每组只在本组内替换。访问命中时也要更新最近使用次序；访问缺失且本组已满时，淘汰本组最久没有被访问的块。下表各组的块从左到右按“最久未使用→最近使用”排列：

第7、8、10次访问命中，共3次，所以选C。第一次访问某块必然缺失；块曾经出现过也不代表一定命中，还要看它是否已被本组的LRU替换淘汰。

适用边界。 组相联组织还存在直接按“主存块号 mod Cache组数”选组的模型。若改用该模型，本题全部地址都是偶数，会集中到组0，只有第8次访问命中，结果为1次。这个结果对应另一种地址组织；本题计算采用上面明确给出的主存分组模型，不能把两种模型的选组规则与命中次数混合。

答案：C。

字段直接编码把互斥微命令放在同一个字段，用不同二进制编码选择其中一项；不同字段可同时发出命令。每一类除了实际微命令，还要留一种编码表示“本类不发微命令”，所以包含k条命令的字段至少需 $\lceil\log_2(k+1)\rceil$ 位。五类分别需 $\lceil\log_2 8\rceil=3$、$\lceil\log_2 4\rceil=2$、$\lceil\log_2 13\rceil=4$、$\lceil\log_2 6\rceil=3$、$\lceil\log_2 7\rceil=3$ 位，合计15位，选C。A把字段数当作位数；B把33条命令放进一个全局选择字段，无法并行选择不同类；D是每命令一位的直接控制表示，没有利用互斥关系压缩。

答案：C。

总线100MHz对应周期 $1/(100\times10^6)=10$ ns。宽度32位，每次数据传送只能搬32位，128位需要128/32=4个数据周期。地址线和数据线复用，传地址时不能同时传数据，因此先用1周期给出起始地址；突发方式随后连续传4个数据，不必为每个数据再传一次地址。总周期数1+4=5，耗时 $5\times10=50$ ns，选C。A仅20ns不够传4个数据；B的40ns漏掉地址周期；D的80ns相当于4次都单独传地址和数据，未利用突发传输。题目问至少时间，不额外添加未给出的仲裁、等待或应答延迟。

答案：D。

题目所讨论的USB是一种串行通信总线，数据按位依次传输；一对差分信号线用两根线的电压差表示同一个信号，不能解释为每次并行传两个独立比特。因此D的“同时可传输2位数据”错误，选D。A中的即插即用、热拔插是USB支持的外设连接特性；B中通过集线器级联可连接多台外设；C中USB可连接不同种类外设，均正确。串行传输并不等于低速，速率还取决于信号变化速度和协议编码等因素；反过来，数据传输速率高也不能证明它在两根线上并行传两个比特。识别总线的串行性质是本题关键。

答案：D。

总线的“数据线”不只传应用数据，也传可读写寄存器中的编码内容。CPU向I/O接口命令寄存器写入命令字时，命令作为数据在线上传输；读取状态寄存器时，状态字也通过数据线返回。中断响应时，接口提供的中断类型号同样是一个编码数据，可经数据线交给CPU。因此I、II、III都包括在内，选D。A漏掉类型号，B漏掉状态字，C漏掉命令字。必须把“命令字”与“读写控制信号”、把“中断类型号”与“中断请求线”区分开：前者是本次传送的内容，后者用于控制何时发生传送，才属于控制线信号。

答案：B。

中断隐指令不是程序中显式写出的一条指令，而是CPU响应中断时由硬件完成的一组操作。除保存断点外，通常先关中断以保护入口阶段，再形成中断服务程序入口并送入PC，使后续取指转到服务程序，因此I、III正确。服务程序可能使用哪些通用寄存器，要由其软件代码决定并保存相应现场；“保存通用寄存器内容”不是本题规定的中断隐指令职责，II错误。故选B。A、C、D都含II，A、C还分别漏掉入口装入或关中断。保存断点与保存全部现场不同：断点至少涉及恢复原执行位置，通用寄存器保护通常在中断入口的软件中继续完成。

答案：C。

题目问事件能否在CPU正在执行用户态程序时发生。用户程序主动执行系统调用指令，A可以在用户态发起；设备或时钟产生外部中断与当前程序模式无关，B可以在用户态到来；用户程序访问未驻留的虚拟页也可触发缺页，D可以。随后这些事件的处理会进入内核态，但“发生”与“处理”不是同一时刻。进程切换则需由内核保存当前进程上下文、选择另一个进程、恢复其地址空间和执行状态，实际切换操作不在用户态完成，因此选C。不要因为系统调用、缺页的处理程序在内核中，就误认为它们不能从用户态触发。

答案：B。

中断可能在程序没有预先安排的指令边界发生，返回后必须让原程序继续得到相同的条件判断和运行状态，所以一定要保存程序状态字PSW，包括条件码、处理器状态等，选B。普通子程序调用有约定好的调用规则，调用者或被调用者可按约定处理被破坏寄存器，并不要求每次都保存完整PSW。A的PC所代表的返回位置两者都要保留，子程序也必须知道返回何处；C、D的通用数据或地址寄存器则按实际使用和调用约定保存，不具有本题的必然差别。判断的重点是“中断一定保存，而普通调用不必统一保存”，不是说子程序绝不能主动保存状态字。

答案：B。

虚拟存储允许程序只有当前需要的部分驻留内存，其余在后备存储中，并在访问时调入。为给分散驻留的页面或段建立映射，通常采用请求分页、请求分段等非连续分配机制，按本题的存储管理模型应选B。A把它限制为连续分配，无法体现按需调入和灵活映射。C、D把容量限制说成“只受”外存或内存之一约束也不对：虚拟地址宽度决定一个进程可表示的地址范围，可用后备存储及系统实现也限制可支持的容量，虚拟空间可以大于实际内存。虚拟存储扩展的是程序可用的逻辑空间，并不意味着无限容量或物理内存本身变大。

答案：A。

从上到下，用户级I/O软件提供应用使用的库函数或接口；设备无关软件统一处理缓冲、设备分配、命名、通用错误等工作；设备驱动把通用请求转换为某类控制器的具体命令；中断处理程序响应硬件完成事件，是最靠近设备的处理层。因此顺序为“用户级I/O软件→设备无关软件→设备驱动程序→中断处理程序”，选A。B颠倒驱动和中断层，C把设备相关驱动放到了设备无关层之前，D更让用户层直接面对中断处理，都不符合逐层封装的结构。完整I/O可能从上往下启动，又从下往上通知完成；题目考层次位置，而不是把整个执行过程只看成单向调用。

答案：D。

先算可用量。已分配总和为(16,3,19)，总资源为(18,6,22)，故Work=(2,3,3)。各进程尚需量Need=Max−Allocation，P0到P4依次为(2,3,7)、(1,3,3)、(0,0,6)、(2,2,1)、(1,1,0)。按D验证，每步Need≤Work才能完成，完成后只把原已分配量加回Work：

D全程满足。A以P0开头，R3需7而初始只有3；C以P2开头，R3需6，也失败；B虽可先完成P1，但其后Work=(6,3,6)，仍不足P0的7个R3，所以B失败。故选D。

答案：A。

普通阻塞式read读取磁盘文件时，若所需数据不在内核缓冲区，操作系统需发起磁盘I/O，进程等待数据就绪而进入睡眠/阻塞状态，I正确。系统调用是应用请求内核服务的入口，执行read请求会使CPU从用户态切换到核心态，II正确。read通常形如 read(fd, buf, count)，传文件描述符、目标缓冲区和字节数；文件名用于先前的open，由文件描述符识别已打开文件，所以III错误。仅I、II成立，选A。B漏II并含III，C漏I并含III，D也误含III。这里是题设的普通读取流程，不应把异步接口或特意设置的非阻塞方式自行加进题设。

答案：B。

以P1到达为0时刻，安排如下，CPU和I/O可以重叠，但同一CPU一次只能执行一个作业：

P2在5ms已到达，60ms可开始。该安排260ms结束。还需证明不能更短：若P1先完成第一次计算，则P2第一次计算完成前，两个首次计算共60+120=180ms必须已做完，P2再需40ms I/O和40ms计算，结束至少在260ms。若P2先完成第一次计算，则P1首次计算完成也不能早于180ms，其后80ms I/O和20ms计算使结束至少280ms。因此260ms是最少时间，选B。A的240ms仅为CPU工作量，缺少不可全部隐藏的I/O；C、D没有充分重叠两作业。

答案：C。

普通临界区要求其他访问同一共享资源的进程不能同时进入，但不要求当前进程始终占有CPU。持锁进程仍可被抢占，其他就绪进程可执行不需要该锁的工作，因此“进程处于临界区时不能调度”是错误的绝对说法，选C。A中进程结束后当然要选其他就绪进程；B中新进程进入就绪队列可触发调度判断；D中系统调用完成、将返回用户态时也是内核检查是否需要切换的时机，均正确。某些内核关键区段会显式禁止抢占，但不能把这种特殊限制扩大为所有用户临界区。互斥保护资源访问，调度分配CPU，两种机制应分别理解。

答案：A。

进程拥有地址空间、打开文件等资源，是资源分配的基本单位；支持线程后，多个线程共享进程资源，线程通常成为CPU调度和执行的基本单位，所以A正确，B把两者职责反了。内核级线程由内核管理，切换需要内核参与；用户级线程可由进程内线程库保存和恢复现场，内核可能看不到这些线程之间的切换，因此C的“两者都需要”错误。同一进程的线程共享地址空间，虽各有栈、寄存器和PC，不能据此说它们各有不同地址空间，D错误。线程私有执行现场与进程共享资源同时存在，既不是完全独立，也不是一切状态都共享。

答案：B。

机械磁盘访问时间包括寻道、旋转等待和数据传送。A重排I/O请求可减少磁头来回移动；C预读可能提前把将要用的数据送入缓存，滞后写可合并写请求，减少或隐藏访问开销；D把常一起访问的文件块合理放置，可减少跨位置寻道，均能改善性能。B在同一个磁盘上划多个分区只是逻辑划分，仍共享同一磁头机构和传输通道，没有凭空增加并行I/O能力，因此不能单凭分区数改善设备性能，选B。分区可能方便组织管理，但这与优化具体块布局不是一回事；跨分区频繁访问甚至可能增加寻道，不能把“多个分区”当作“多块物理磁盘”。

答案：B。

ICMP用于IP网络中的差错报告和诊断等，其报文作为IP数据报的数据部分直接封装，由IP负责跨网络传送，所以直接提供服务的是IP，选B。A的PPP是点到点链路层协议，可能承载整个IP数据报，但不是ICMP的直接上一层承载关系；C、D的UDP、TCP是运输层协议，ICMP并不先交给它们再发送。判断“直接提供服务”可画出封装顺序：链路帧→IP首部→ICMP报文，中间没有TCP或UDP首部。ICMP虽经常由ping等应用使用，也不能因为应用调用它就把它误归成通过UDP或TCP发送的普通应用协议。

答案：C。

物理层接口规范分四类：机械特性规定接口形状、引脚数及排列等；电气特性规定电压、信号电平、传输速率等；功能特性规定各线或各引脚承担什么用途；过程特性规定完成一次功能时各事件、信号按什么顺序发生，例如先置请求、再等待响应、最后释放。题目强调“事件发生顺序”，对应过程特性，选C。A关注接口长什么样，B关注每个信号做什么，D关注电信号满足哪些数值要求，都没有直接回答先后顺序。功能特性与过程特性尤其易混：知道某线叫请求线只是功能，知道请求与应答如何配合才是过程。

答案：A。

传统以太网MAC发送帧前不与接收方建立逻辑连接，帧携带目的MAC后就可发送，因此是无连接服务。它使用CRC检测帧是否出错，但接收方不会对每个正确帧发送MAC确认，出错或丢失的帧也不由该MAC机制保证恢复，所以是不可靠服务，选A。B把差错检测误当成可靠交付；C、D都增加了以太网MAC没有的建连过程，D还增加了可靠承诺。发送端检测碰撞并重新竞争是介质访问机制的一部分，也不能保证帧最终被目标正确接收。需要端到端可靠性时可由TCP等上层完成，各层的服务性质应分别判断。

答案：B。

发送窗口必须足够大，让最早一帧的确认返回之前仍有新帧可发。要覆盖允许的帧长范围，取128B最短帧，此时传播时延占比最大。数据与等长确认帧的发送时间均为 $T=128\times8/16000=0.064$ s=64ms。第一帧从开始发送到完整收到确认需 $T+2\times270+T=668$ ms，因此窗口需满足 $WT\ge668$，即 $W\ge\lceil668/64\rceil=11$。GBN使用k位序号时最大发送窗口为 $2^k-1$，k=3只能7帧，不够；k=4可15帧，足够，选B。A的5位也够却不是最少，C的3位、D的2位不够。不能忽略确认帧的发送时间，也不能把GBN上限错用成SR的半序号空间规则。

答案：C。

路由器运行路由协议以学习和更新转发所需路由表，I正确；队列拥塞、空间不足等情况下可按策略丢弃IP分组，II正确；依据目的IP地址匹配路由并选择输出接口，IV正确。IPv4首部校验只能检测首部是否发生一定类型的错误，不能保证链路、队列和后续网络都不丢包，IP本来提供尽力而为服务，因此III后半句“确保不丢失”错误。仅I、II、IV成立，选C。A、B、D都含III，A还漏I、II，B漏IV。判断复合语句时需要整条都成立；不能因为路由器确实检查首部，就接受后面的可靠性保证。

答案：A。

IPv4主机在本链路发送帧，需要知道下一跳的MAC地址。ARP以目标IPv4地址发起查询，拥有该地址的设备返回MAC，建立“IP→MAC”的映射，因此选A。B是反向的MAC→IP方向，通常对应RARP这一不同协议的目标；C是域名→IP，由DNS等名称解析机制完成；D是IP→域名，可通过DNS的反向查询完成。若目的主机在同一子网，ARP查它的IP；若在其他子网，则先由路由选择网关，再ARP查网关IP。ARP广播限制在本链路，并不穿过所有路由器去找远端服务器MAC，这有助于理解它承担的地址解析范围。

答案：D。

掩码255.255.252.0的第三字节252为11111100，前22位是网络位，后10位是主机位。先与主机地址按位与：第三字节 $77\,\&\,252=76$，第四字节与0得0，所以网络地址为180.80.76.0。广播地址把全部10位主机位设1，使第三字节最后两位为11，即76+3=79，第四字节为255，得到180.80.79.255，选D。A是网络地址；B只把最后一字节置1，第三字节主机位未全1；C同样未把第三字节的两位全置1。/22子网跨越第三字节76、77、78、79四个取值，不能按默认/24只把原地址末字节改255。

答案：D。

图中①是用户1把邮件提交给自己的邮件服务器，②是发送方服务器把邮件转送到接收方服务器，二者均属于发送邮件，可使用SMTP。③是用户2从自己的邮件服务器取回已收邮件，可使用POP3。因此组合为SMTP、SMTP、POP3，选D。A误把SMTP用于③的取信；B把①的邮件提交错误地改成POP3；C既把①改成POP3，又把③改成SMTP。POP3用于读取邮箱中的邮件，不负责服务器间转投；SMTP负责提交和传送，不是常规的邮箱下载协议。题目问“可以是”，收信还可能采用其他取信协议，但无需因此改变图中这组可行的三阶段组合。

（1）完整合并过程。 两个长度为m、n的升序表用双指针归并：比较当前首元素，取较小者，直到一方为空，余下元素直接接上。最坏情况下两表元素交错，最后只剩一项不需比较，因此比较次数为m+n−1。要减小各元素反复参与合并的次数，应让短表先合并，长表尽量晚参加。

每次从当前各表中选两个最短的，得到：

共5次两两合并，最终395个元素，最坏比较总数 $44+84+109+194+394=825$。

（2）一般策略和理由。 对n个不等长有序表，将当前表长放入小根堆；反复取最短两个表合并，把新表长度放回，直到只剩一个。它与哈夫曼树的构造相同。

把原表看成合并树的叶子，表长是叶权，叶子到根经过几条边，该表全部元素就参加几次合并。因此各次合并后的总长度之和等于带权路径长度WPL；每次比较次数再减1，总比较为 $WPL-(n-1)$，而n−1固定，只需最小化WPL。

可在最优二叉合并树中把最短两个叶子安排为最深层的一对兄弟：把小权值与较深叶子交换不会增加WPL。把这两个叶子缩成权值之和的一个叶子，剩余仍是同类最优问题，所以反复合并两个最短表的贪心策略成立。小根堆管理长度需O(nlogn)时间、O(n)空间；实际数据合并成本还包括逐元素复制，不能只用堆操作时间概括全部合并过程。

（1）设计思想。 单链表一旦指向同一结点，后继next只有一个，后面所有结点就相同，所以共享空间只能表现为共同后缀。要找的是同一个结点的地址，不是两个字符值相同的位置。

设两个表的有效字符结点数为m、n。先遍历求长度，让较长表的指针先走|m−n|步，此后两个指针到表尾的距离相同。再同步各走一步，第一次地址相等的非空结点就是共同后缀起点；若一起走到NULL仍未找到非空相同结点，说明没有共同后缀。带头结点不存单词字符，求长度和比较都从head->next开始。

（2）C实现。

#include <stddef.h>

typedef struct Node {
    char data;
    struct Node *next;
} Node;

/* str1、str2指向两个有效的头结点；链表无环。 */
Node *common_suffix(Node *str1, Node *str2) {
    Node *p = str1->next, *q = str2->next;
    size_t m = 0, n = 0;
    for (Node *t = p; t != NULL; t = t->next) ++m;
    for (Node *t = q; t != NULL; t = t->next) ++n;
    while (m > n) { p = p->next; --m; }
    while (n > m) { q = q->next; --n; }
    while (p != q) {            /* 比较地址而不是data */
        p = p->next;
        q = q->next;
    }
    return p;                  /* 无共享后缀时返回NULL */
}

图中loading长7、being长5，loading指针先走2步，由l来到a；同步比较a与b、d与e，再到同一个i结点时地址相等，返回i的位置p。

正确性和边界。 对齐后两指针剩余长度相等，若存在共同后缀，则必同时到达其首结点；此前不同地址只是各自的私有前缀，因此第一次相等就是所求。若不共享空间，两指针最终同时为NULL，循环退出而不会访问NULL的next。空单词、长度相同、共享整个字符链都可由同一过程处理；字符串内容相同却分别存储时仍应返回NULL。

（3）复杂度。 两次求长度和同步扫描都至多遍历各表常数次，总时间 $O(m+n)$，只用若干指针及计数，额外空间 $O(1)$，也不改变原表结构。

（1）指令速率、Cache缺失和主存带宽。 主频为80×10⁶周期/s，平均每条指令用4周期，所以指令速率 $80\times10^6/4=20\times10^6$ 条/s，MIPS=20。每条指令平均访存1.5次，Cache访问率为 $20\times10^6\times1.5=30\times10^6$ 次/s。命中率99%，缺失率1%，每秒缺失 $30\times10^6\times0.01=300000$ 次。

一次缺失须从主存取完整16B块，而非只取CPU所要的一个字，因此主存最低带宽 $300000\times16=4.8\times10^6$ B/s=4.8MB/s。这里速率单位MB按十进制百万字节解释；没有题设以外的写回或协议附加开销。

（2）缺页和DMA请求。 给出的缺页率是“Cache缺失后访问主存”这一条件下的比例，应乘每秒主存访问300000次，而不能乘全部Cache访问。$0.0005\%=5\times10^{-6}$，故平均每秒缺页 $300000\times5\times10^{-6}=1.5$ 次。

每页4KB=4096B；接口缓冲寄存器32位=4B，周期挪用每搬运一个寄存器量需一次DMA请求，所以每页至少4096/4=1024次。平均请求率 $1.5\times1024=1536$ 次/s。缺页次数1.5是长期平均频率，不要求某个具体1秒内实际发生半次异常。

（3）总线优先级。 DMA控制器应比CPU的访存请求优先。设备持续产生数据时，缓冲寄存器容量有限，迟迟不搬运可能被新数据覆盖；CPU则可等待一个或若干总线周期后继续，通常不会因此丢掉内部数据。这就是周期挪用允许DMA暂时占用存储总线的原因。

（4）四体交叉带宽。 每体存储周期50ns，启动间隔为50/4=12.5ns。顺序交叉访问、流水线进入稳定状态后，每12.5ns可得到一个32位字即4B，最大带宽 $4/(12.5\times10^{-9})=320\times10^6$ B/s=320MB/s。单体仍要50ns才能再次启动同体操作，四体轮流工作使整体输出间隔缩短；不要误把每次字长也乘4又重复计算。

（1）补码算术右移。 16位正数513=0201H，−513的补码为 $10000\mathrm H-0201\mathrm H=FDFF\mathrm H$，二进制 11111101 11111111。算术右移复制最高符号位1，其余位右移一位，得到 11111110 11111111，即FEFFH，按补码为−257。负奇数右移的结果向负无穷取整，不能按向0截断写为−256；逻辑右移补0则是不同运算。

（2）无阻塞流水。 5段流水中第一条指令需5周期通过全部阶段；后续每周期进入一条，每增加一条使整体结束延后一周期。因此4条指令总时间 $5+(4-1)=8$ 周期，不是4×5=20周期。

（3）题图阻塞原因。 I3的ADD在ID阶段读R1和R2，分别由I1、I2的LOAD写回。I1在周期5 WB，I2在周期6 WB；没有转发，且同周期不能读写同一寄存器，所以I3不能在周期6读R2，要等周期7才ID，形成先写后读的真实数据相关（RAW）。题设按序发射，前面的I3滞留在取指之后尚未进入ID时，后面的I4也不能越过它进入取指通路，于是I4的IF推迟到周期7。这是前面数据相关造成的后续流水阻塞，不是指令Cache与数据Cache争用。

（4）实现x=2*x+a及最少周期数。 至少需要两次LOAD取得x、a，一次SHL求2*x，一次ADD以及一次STORE。题设ADD Rs,Rd将结果写入第二操作数，所以以下把和放在R2，随后STORE R2：

I1: LOAD  R1, [x]
I2: LOAD  R2, [a]
I3: SHL   R1
I4: ADD   R1, R2
I5: STORE R2, [x]

先把不依赖彼此的两条LOAD连续发射，可以让读a与等待读x的时段重叠。满足题设的流水图如下；空格表示未执行阶段或停顿，阶段在实际完成的周期标出。

I1最早周期5写R1，I3最早周期6读R1，周期9写回移位结果；I4最早周期10读R1，周期13写回R2；I5最早周期14读R2，周期17通过最后一段。这条不可省的依赖链已经用尽各自最早时刻，因此总计最少17周期。STORE的WB不改通用寄存器，但按题图规定的5段执行模型仍计入完成周期。x、a为无符号数，左移和加法保留16位结果，实现相应的模 $2^{16}$ 运算。

按时间模拟。 驻留集中的页面可直接命中；扫描时只把本轮未访问的页框移到空闲链尾，内容暂时保留。缺页若能在空闲链中找到原页，取回原页框；否则才分配链头并覆盖其旧内容。以下按页1、页3的顺序列出时刻10的回收，交换它们的回收次序也不影响所问结果。

（1） 访问<0,4>时，对应页框21，它是前三次首次调入的第三个链头。

（2） 访问<1,11>时，对应页框32。虽然页1在时刻10被回收，但32尚未分配给别的页，旧内容仍在，所以可直接从空闲链恢复，不必从链头41重新分配或重新读磁盘。

（3） 访问<2,14>时，对应页框41。页2此前从未使用，不满足“曾用且仍在空闲链”的恢复条件，必须取当前链头；41从开始起一直空闲，回收框32、15又只加在链尾，因此链头仍是41。

（4） 适合时间局部性好的程序。这样的程序常在短时间内重复访问最近用过的页：若未被回收，它就在驻留集命中；若刚被回收且尚未被重分配，又可直接恢复原框，省去磁盘读入。该策略通过保留回收页内容利用近期访问规律，并不承诺每次缺页都能免磁盘I/O；若原框已覆盖，仍要重新调入。

（1）仅采用直接索引。 文件系统容量为4TB，即 $4\times2^{40}$ B；每个磁盘块为1KB，即 $2^{10}$ B，所以总块数为

$$\frac{4\times2^{40}}{2^{10}}=2^{32}.$$

给这些块编号需覆盖0到 $2^{32}-1$，块号最少占32位，也就是4B。512B索引区能放 $512/4=128$ 个块号，每个块号直接指向一个1KB数据块，所以最大文件长度为

$$128\times1024=131072\ \mathrm{B}.$$

块号的位数由整个文件系统需要编号的块总数决定；文件的直接索引项数则由FCB索引区的字节预算决定，不能混为同一个限制。

（2）连续预分配区加直接索引区。 前8B描述一段连续空间，后504B使用直接索引。每个直接索引项占6B，所以直接索引部分可指向 $504/6=84$ 个数据块。

本题采用的字段容量约定是：2B块数字段按能够表示65536个连续块计算。要实现1到65536的正块数范围，必须有相应计数编码，例如把0编码约定为65536块。这里明确采用该容量约定，连续区与84个直接索引块不重复，所以最大文件长度为

$$(2^{16}+84)\times2^{10} =2^{26}+84\times1024 =67194880\ \mathrm{B}.$$

起始块号占6B可表示的地址范围虽很大，但连续区大小仍由块数字段限制；不能用起始地址位数替代块数上限。

合理重新分配前8B。 一个合理方案为“起始块号4B、块数4B”。全盘有 $2^{32}$ 个块，4B起始块号已经足以覆盖任意块位置，再多占用地址字节不会增加可用空间。把原来多出的2B转给块数后，4B块数字段在上述容量约定下能描述最多 $2^{32}$ 个连续块，能够达到4TB文件系统的空间上限。实际连续区还须从所选起始块起处于有效磁盘范围内，文件的总数据块也不能超过文件系统可用容量，因此不能将全部连续块和额外索引块相加后宣称文件超过4TB；系统元数据所占空间也会使实际可用容量更小。

普通无符号计数的边界。 若实现把2B字段严格解释成普通无符号整数，不定义上述特殊计数编码，它的最大值就是 $2^{16}-1=65535$，相应最大文件长度为

$$(65535+84)\times1024=67193856\ \mathrm{B}.$$

“有65536种编码”与“普通整数最大值是65536”并不等价。两种数值相差一个1KB块，来自明确不同的计数编码约定；本题主答案使用前面已经写明的字段容量约定。

先定位首部字段。 分组均从IP首部开始，45H表示IPv4、首部长5×4=20B。IP源地址在偏移12～15B，目的地址在16～19B；TCP从第20B开始，首部中的第12字节高4位表示TCP首部的32位字数，紧接的标志字节用于识别SYN、ACK。捕获的字节不包含完整选项或载荷时，仍可从总长度和首部长度求它们的大小。

（1）发送方、握手和填充。 H的IP地址192.168.0.8对应 c0 a8 00 08，因此源IP为该值的分组1、3、4由H发送；分组2、5由S发向H。连接建立三次握手分别为：1的TCP标志02H，仅SYN=1；2的12H，SYN=1、ACK=1；3的10H，ACK=1且SYN=0。所以1、2、3共同完成建连。

以太网最小数据字段46B，承载的完整IP分组不足46B才填充；不是用TCP载荷长度判断。

故需填充的是3、5。填充属于以太网，不计入IP总长度，也不属于TCP应用数据。

（2）S收到的应用数据。 H在分组1中的初始序号为846B41C5H，SYN占用一个序号，因此应用数据的起始序号为846B41C6H，这也与分组4的seq一致。S在分组5发来的累计确认号为846B41D6H，表示这一序号之前的数据已经连续收到，应用数据字节数为 $846B41D6\mathrm H-846B41C6\mathrm H=10\mathrm H=16$ B。分组4的总长减两层首部也得到56−20−20=16B，可互相验证。不能把SYN算作应用数据，多算成17B。

（3）路由器数量。 S发出时与H收到时，IP标识6811H、TCP序号E0599FF0H、确认号846B41D6H一致，可认定题47-b对应分组5。S发出时TTL字段40H=64，H收到时31H=49，每经过一个正常转发路由器TTL减1，所以经过 $64-49=15$ 个路由器。两处目的地址、目的端口不同，是中途地址/端口转换的结果：公网上的CA760106H到达H时成为C0A80008H，A108H端口也变为0BD9H；这些修改和相应校验和更新不改变TTL差的计算方法。