2013年计算机408真题

答案：D。

**思路：**两个原链表已经升序，可以各用一个指针指向尚未处理的首结点。每次取出两指针中较小的结点，用头插法放入结果链表；取出的值越来越大，放在表头后恰好得到降序。某表用完后，继续把另一表剩余结点依次头插。

每个结点只被取出、改链一次，时间为 $O(m+n)$。令 $M=\max(m,n)$，有 $M\le m+n\le2M$，所以也可写成 $O(\max(m,n))$。A 的 $O(n)$ 忽略了可能更长的 m 表；B 的乘积没有必要；C 只计算较短表，遗漏剩余结点；D 正确。反转输出顺序改变的是插入位置，不会使合并变成乘积时间。

答案：C。

栈遵守后进先出，但入栈和出栈可以交替进行。题目只固定第二次弹出的是 3，不能据此认为第三次只能弹出 2。3 已经弹出，先排除它，再证明其余值均可实现。

若希望 $p_3=1$，先压入 1、2，弹出 2 作为 $p_1$，再压入并弹出 3，此时栈顶是 1。若希望 $p_3=2$，先弹出 1，再压入 2、3，弹出 3 后弹出 2。若希望 $p_3=k\ge4$，先弹出 1，再压入 2、3 并弹出 3，接着压入 4 至 k，便可弹出 k。所以共有 $1,2,4,\ldots,n$，计 $n-1$ 种；A、B 少计，D 错在该个数可确定。

答案：D。

平衡因子是左、右子树高度之差，绝对值超过 1 时要旋转。依次插入递增关键字会产生右右失衡，需要左旋，不能把最终树当成普通二叉排序树的单链。

插入 1、2、3 后，对 1 左旋，根变为 2。插入 4、5 后，结点 3 失衡，左旋后其子树根为 4；插入 6 后，根 2 失衡，左旋后整树根为 4；插入 7 后，对结点 5 左旋。最终根 4 的左子树为 2 带孩子 1、3，右子树为 6 带孩子 5、7。分支结点只有 4、2、6，三个结点左右等高，平衡因子均为 0，故计数为 3。A、B、C 均少计；叶结点虽也平衡，但本题不计叶结点。

答案：B。

带权路径长度 $WPL=\sum w_i l_i$，其中 $l_i$ 是根到叶的边数。最小值由三叉哈夫曼构造求出，每轮合并三个最小权。满三叉树的叶数满足 L-1 能被 2 整除；6 个叶不满足，补一个权为 0 的虚叶，其 WPL 贡献为零。

依次合并：$0+2+3=5$；剩余权为 4、5、5、6、7，合并 $4+5+5=14$；最后 $6+7+14=27$。每次合并使参与子树的叶深度加 1，因此 $WPL=5+14+27=46$。也可验算 $2\times3+3\times3+4\times2+5\times2+6+7=46$。A 的 27 只是总权，C、D 都大于最优值，故选 B。

答案：A。

线索指针利用空孩子指针存放遍历序列中的前驱或后继，右线索指向后继。后序遍历次序为“左子树、右子树、根”。X 存在左兄弟 Y，说明 X 是父结点的右孩子；又因为 X 是叶，访问这个右子树时只访问 X 本身。

局部后序序列必为“以 Y 为根的整棵子树、X、X 的父结点”，紧接 X 的就是父结点，故 A 正确。B、D 所指结点均在左子树内，早于 X 被访问；C 的 Y 是左子树最后访问的结点，也在 X 之前。注意“右线索”不是“指向右侧的结点”，其含义由遍历后继决定，不能套用中序遍历的后继规则。

答案：C。

二叉排序树插入时，从根按关键字大小查找，最终总是在空孩子位置插入一个叶结点。若删除的 $\nu$ 原本是叶，删除只把父结点的一条链接置空，其余比较路径不变。再插入相同关键字会沿原路径恢复原位置，故 II 正确、I 错误。

若 $\nu$ 原本不是叶，删除时要让孩子接替它，或用前驱、后继替换并调整链接；重新插入 $\nu$ 时，它将作为叶出现。而原树中同一关键字对应的是非叶，带关键字的树结构不可能相同，故 III 正确、IV 错误。A 含 I，B 含 I、IV，D 含 IV，都应排除，只有 C 的 II、III 均成立。三棵树的关键字集合相同不代表树结构相同。

答案：C。

无向图的邻接矩阵关于主对角线对称；题中 $A_{12}=1$、$A_{21}=0$，所以是有向图。$A_{ij}=1$ 表示从 i 到 j 有弧，行和为出度，列和为入度，有向图的度为二者之和。

因此选 C。A 仅列入度，B 仅列出度，D 与统计不符。矩阵共有 6 个 1，即 6 条弧；每条弧在起点贡献出度、终点贡献入度，总度应为 12，也可用来检验。

答案：D。

广度优先遍历使用队列，先访问起点的所有邻点，再访问距离起点为 2 的点。同层先后可随邻点枚举顺序改变，但不能越过尚未完成的前一层。

按图核对：A 从 h 开始，第一层 c、a，随后可依次发现 b、d、e，最后 g、f；B 从 e 开始，第一层 a、f、g，第二层 b、h，最后 c、d；C 从 d 开始，第一层 b、c，第二层 a、h，最后 e、f、g，均可用相应邻点顺序得到。D 从 a 开始时，邻点 b、e、h 应全部先于 c、d、f、g 出现，却在 e、h 之前访问 c、d，违反层次次序。因此 D 不是 BFS 序列；不能仅因同层点顺序不同而否定 A、B、C。

答案：C。

AOE 网的弧代表活动，工程工期由起点到终点的最长路径决定。有多条关键路径时，必须使每一条都缩短，才能缩短总工期。

图中三条最长路径为 $b\to d\to c\to g$，长度 $8+4+9+6=27$；$b\to d\to e\to h$，长度 $8+4+6+9=27$；$b\to f\to h$，长度 $8+10+9=27$。经 a 的两条路径均为 18。A 加快 c、e，第三条仍为 27；B 加快 d、c，第三条仍不变；D 加快 f、h，第一条仍不变。C 的 d 覆盖前两条，f 覆盖第三条，同时缩短它们可使所有原关键路径变短。关键活动不能只看是否位于某一条最长路径，还要检查其他路径。

答案：A。

5 阶 B 树的结点最多有 5 个孩子、4 个关键字；非根结点至少有 $\lceil5/2\rceil-1=2$ 个关键字。非叶根结点是例外，最少只有 1 个关键字和 2 个孩子，不能把非根下限直接套到根上。

本题高度 2 按结点层数计算，即根一层、叶一层。令根取最小规模：1 个关键字和 2 个叶孩子；每个叶孩子再各取 2 个关键字。总数为 $1+2\times2=5$，且这种结构满足所有约束，下限可达到。A 正确；B、C、D 都不是最小值。若把高度误当成根到叶有两条边，就会多算一层；“阶”限制的是最大孩子数，也不是每个结点必须含 5 个关键字。

答案：C。

低位优先基数排序先按个位分配到 0～9 桶并收集，再按十位重复。每趟必须稳定，即同桶内保持进入次序，才能保留低位已排好的关系。

第一趟个位为 0、9、7、1、4、0、2，收集得到 110、120、911、122、114、007、119。第二趟十位为 1、2、1、2、1、0、1：0 桶是 007，1 桶依次是 110、911、114、119，2 桶是 120、122。因此结果为 007、110、911、114、119、120、122，选 C。A、B 的十位相同组没有保持个位顺序，B 还颠倒 120、122；D 是第一趟结果，尚未完成第二趟。

答案：C。

CPI 表示每条指令平均需要的时钟周期。程序含不同类型指令，应按指令数量比例加权，不能把四类 CPI 直接算术平均：

$$\overline{CPI}=0.50\times2+0.20\times3+0.10\times4+0.20\times5=3.$$

主频 $1.2\,\mathrm{GHz}=1200\,\mathrm{MHz}$，每秒周期数除以每条指令的周期数，得到每秒指令数；再以百万条为单位，$MIPS=1200/3=400$，选 C。A、B 都低于给定权重算出的速度；D 的 600 相当于误把所有指令都按 CPI=2 处理。GHz 为每秒十亿周期，MIPS 为每秒百万指令，必须先统一单位。

答案：A。

IEEE 754 单精度的 32 位分为 1 位符号、8 位阶码、23 位小数尾数。C6400000H 按字段展开为 $1\mid10001100\mid10000000000000000000000$。符号位为 1，数值为负；阶码 $10001100_2=140$，减偏置 127 后真实指数为 13。

阶码既非全 0 也非全 1，是规格化数，尾数最高位隐含 1。小数字段为 $.100\ldots_2=0.5$，所以有效数为 $1.5$。结果为 $-1.5\times2^{13}$，A 正确。B 把指数少算 1；C 漏掉隐含整数位 1；D 同时犯这两个错误。十六进制只是位串的紧凑表示，不能把整个位串按补码整数解释。

答案：A。

8 位补码最高位为 1 表示负数，可把无符号值减去 $2^8=256$ 得到真值。因此 $x=244-256=-12$，$y=176-256=-80$。按题意 $z=2x+y/2=-24-40=-64$，中间值及结果都在 8 位有符号整数范围 $[-128,127]$ 内，无溢出。

转回补码：$256-64=192=11000000_2$，选 A。B 的 00100100 是正数 36，C 的 10101010 是 -86，均不符；D 被范围检查排除。也可用算术移位验证：x 左移一位得 11101000（-24），y 右移时补符号位 1，得 11011000（-40），相加保留低 8 位即 11000000。负数除以 2 不能采用补零的逻辑右移。

答案：C。

海明码要定位一位错误，r 个校验位产生的 $2^r$ 种校验结果必须能区分“无错误”以及编码中每一位出错。8 位数据加 r 位校验，共 $8+r$ 个可能出错位置，所以 $2^r\ge8+r+1$。

逐个试最小值：r=2 时 $4<11$，r=3 时 $8<12$，都不够；r=4 时 $16\ge13$，第一次成立，所以至少 4 位，选 C。A、B 无法为每种状态分配不同校验结果；D 的 5 位虽足够，却不是最小值。校验位自身也可能出错，因此右边不能只写数据位数 8。本题要求纠正一位错，未额外要求扩展海明码的双错检测，无需再加总奇偶校验位。

答案：A。

页面为 $4\,\mathrm{KB}=2^{12}$ B，虚拟地址低 12 位为偏移，高 20 位为虚页号。每个十六进制数字表示 4 位，因此 03FFF180H 可直接分出虚页号 03FFFH、偏移 180H。

全相联 TLB 以完整虚页号作标记，同时检查有效位。标记 03FFFH 的项有效位为 1，页框号为 0153H，物理地址为 $(0153\mathrm H\ll12)+180\mathrm H=0153180\mathrm H$，选 A。B 误用了标记 3FFF1H 的页框 0035H；C 错在本次命中有效项；D 的缺页不能仅由地址形式判断，本题已由有效 TLB 项完成转换。页内偏移保持不变，只替换高位的页号。

答案：D。

变址寻址的有效地址为“指令形式地址加变址寄存器内容”，即 $EA=A+(R)$。题中 $A=2000\mathrm H$、$(R)=1000\mathrm H$，故 $EA=3000\mathrm H$。题目问操作数，还需到该地址读取：$M[3000\mathrm H]=4000\mathrm H$，所以 D 正确。

A 的 1000H 是寄存器内容，B 的 2000H 是形式地址，C 的 3000H 是有效地址，都不是最终数据。地址 1000H、2000H 中的内容不参与此次有效地址形成；不能因为题目给了多处内存内容就逐次间接访问。把“计算访问地址”和“取出地址中的操作数”分为两步，可避免变址、直接、间接寻址之间的混淆。

答案：C。

理想 k 级流水线执行 n 条指令需要 $k+n-1$ 周期：第一条需经过全部 k 段，此后每周期再完成一条。本题 k=4、n=100，共 $4+100-1=103$ 周期。

总时间 $T=103/(1.03\times10^9)=100\times10^{-9}\,\mathrm s=100\,\mathrm{ns}$，实际吞吐率为 $100/T=1.0\times10^9$ 条/秒，选 C。A 近似把每条都按四段串行执行，忽略重叠；B 不是给定频率下的结果；D 的 $1.03\times10^9$ 是稳态极限，忽略这 100 条指令的装入和排空开销。有限批次吞吐率必须用实际完成的总指令数除以完整总耗时。

答案：B。

要区分互连位置：系统内部总线连接处理器、主存、扩展控制器等部件，外设接口连接设备和设备控制器。USB 是通用串行总线，典型用途是把键盘、鼠标、移动存储等接到 USB 主机控制器，符合“设备与设备控制器之间互连”，B 正确。

A 的 PCI 是系统内部扩展总线，可连接网卡、声卡等接口卡；C 的 AGP 用于图形适配器的内部连接；D 的 PCI-Express 也是系统内部高速扩展互连。它们与 USB 都涉及数据传送，但连接对象不同，不符合本题所问的位置。判断接口标准不能只看是否叫“总线”，应关注其位于系统结构的哪一侧。

答案：B。

RAID 的可靠性来自冗余：磁盘失效后仍能用其他信息恢复数据。I 镜像保存相同数据的副本，一份失效仍有另一份；III 奇偶校验保存数据块之间的校验关系，在相应容错范围内可重建丢失数据，二者均提高可靠性。

II 条带化把数据分散到多盘并行读写，主要提高吞吐；单纯条带化无副本或校验，磁盘失效仍会丢数据。IV 普通 Cache 主要降低访问延迟，并不自动提供磁盘故障恢复能力；题中未给备份、断电保护等条件，不能把它当成冗余。因此只有 I、III，选 B。A、D 错含 II，C 错含 IV。性能提高与可靠性提高是不同目标。

答案：B。

一次磁盘读操作要加上寻道、旋转等待、数据传输和控制器开销。转速 10000 转/分，转一圈为 $60/10000\,\mathrm s=6\,\mathrm{ms}$；到达磁道后目标扇区平均需等半圈，故平均旋转等待 3 ms。

4 KB 的传输时间约为 $4\,\mathrm{KB}/(20\,\mathrm{MB/s})\approx0.2\,\mathrm{ms}$。合计 $6+3+0.2+0.2\approx9.4\,\mathrm{ms}$，B 正确；二进制 KB 与十进制 MB 的细微换算不影响“约为”的选项。A 的 9 ms 漏传输和控制器时间，C 的 12 ms 把等候算成整圈且漏其他开销，D 的 12.4 ms 把平均旋转等待误算为整圈。读一个扇区无需等待扇区再次转回原位置。

答案：D。

中断 I/O 由 CPU 执行服务程序搬运数据，DMA 由控制器在设备与主存间直接传送，CPU 主要参与初始化及完成处理。A 正确：前者申请 CPU 服务，后者申请总线使用权。B 正确：可屏蔽中断通常在指令结束处响应，DMA 可在当前总线事务完成后取得总线，不必等整条指令结束。C 正确：两种搬运分别依靠软件指令与硬件控制。

D 把“中断 I/O 适用于所有外设”说得过于绝对。极高速连续数据若逐次中断，服务和现场切换开销可能使 CPU 来不及处理，通常要用 DMA 等方式。DMA 适于高速批量传送，并不意味着中断就适于所有设备，所以该项整体错误。

答案：A。

目录保存文件名与文件控制信息之间的对应关系。删除一个文件与删除容纳它的整个目录是不同操作：删除文件时应撤去对应目录项；满足回收条件时，还可回收文件控制块、释放数据块以及相关内存缓冲区。因此 B、C、D 都是可能步骤。

A 删除“此文件所在的目录”会影响目录自身及其中其他文件，不能作为只删除该文件的处理，故选 A。注意“可能”不等于“每次立即发生”：有其他硬链接或文件仍被打开时，控制块和数据块回收可以推迟，但不影响 C 属于可能操作。目录项是目录中的一条记录，删除这条记录不等于删除其所在目录。

答案：A。

视频随机播放需要迅速定位指定偏移的数据块，并连续读取后续内容。连续结构使文件数据块相邻存放，知道首块号与逻辑块号 i 后，可直接求物理块号“首块+i”，不必逐块追踪指针，且后续读取减少寻道，故 A 性能最好。

B 链式结构的随机访问通常要从前面沿链走，定位慢。C 直接索引支持随机访问，但可能先读索引块，数据也未必相邻。D 多级索引经过更多索引层次，额外访问更明显。连续分配通常有扩展不便、外部碎片等缺点，但 CD-ROM 中视频写成后不动态增长，本题目标是播放性能，这些缺点不改变选择。不能把“支持随机访问”直接等同于“随机播放性能最好”。

答案：C。

磁盘请求从抽象到具体逐层处理。用户程序按文件及偏移提出需求；系统调用处理程序检查参数、权限并进入内核服务；设备驱动了解具体磁盘寻址和控制方式，负责把逻辑块请求转换为柱面号、磁头号、扇区号等设备位置，并发出硬件控制命令，因此 C 正确。

A 用户程序不应依赖磁盘物理几何信息；B 系统调用处理程序提供统一服务入口，题中这种设备相关计算属于驱动层；D 中断处理程序主要在设备完成或出错后响应中断、记录状态、唤醒等待者，不承担启动请求前的地址转换。定位软件层次时，抓住“涉及具体硬件特性”就能判断应由设备驱动处理。

答案：A。

一个文件可有多长，取决于它自身索引节点里的地址项能覆盖多少数据块。设块大小 B 字节、每个地址占 a 字节，则一个间接索引块能放 $B/a$ 个地址；一级间接覆盖这么多块，二级间接覆盖 $(B/a)^2$ 块，级数增加会扩大寻址范围。

所以 B 间接级数、C 地址项数量、D 块大小都会影响单个文件的长度上限；块大小还决定每个块能保存多少数据。A 索引节点总数主要限制整个文件系统能建立多少个文件，不会增加某一个索引节点的寻址能力，因此与单个文件长度无关。整个文件系统的文件数量限制与一个文件的容量限制应分别考虑。

答案：C。

单系统缓冲只有一块空间，读入后必须搬走才能读下一块；单用户工作区在分析结束前也不能被覆盖。但外设读第二块时，CPU 可以分析第一块，两者能够重叠。

第二块读完时用户区已经空闲，随即搬运、分析，总时间 300，选 C。A 只算读取，B 的 295 误让第二块在 100 时开始读，忽略搬运期间缓冲仍占用；D 的 390 将操作全串行相加，漏掉可并行阶段。

答案：B。

用户态进入内核态的常见原因是系统调用、异常或中断。I 整数除以零是处理器检测到的异常，处理器转入异常处理程序，切换内核态。III read 是系统调用，用户程序通过陷入机制请求操作系统读取数据，也进入内核态。

II 的 sin() 通常是数学库函数，执行用户空间中的计算代码，函数调用本身只改变控制流，不需要特权，不会必然切换内核态。正确集合为 I、III，选 B。A 错含 II、漏 III，C 错含 II、漏 I，D 多列 II。应区分普通函数与系统调用；题目未给 sin() 内部触发异常等额外情形，不能用假设的异常去判断普通函数调用。

答案：D。

CPU 执行操作系统时，内核运行代码与数据需要驻留主存。开机先执行固件中的引导代码，再由引导过程把磁盘等启动介质上的操作系统加载到 RAM，最后转交控制权，因此最终加载位置是 D。

A BIOS 是固件提供的基本输入输出及启动功能，不是操作系统运行时的目标内存。B ROM、C EPROM 是非易失性存储器，可保存固件或特定程序，不是此题通常计算机把操作系统动态装入的主存。RAM 掉电后内容消失不影响开机运行，因为启动时可重新加载。要区分“引导代码原先在哪里保存”和“操作系统加载后在哪里执行”，不能因 ROM 中有启动程序就把它当成操作系统加载位置。

答案：B。

缺页表示访问的是合法虚拟页面，但该页当前不在主存；越界表示地址超出进程允许范围，是另一类地址合法性错误。对合法缺页，内核需把所需页装入主存：有空闲页框时可分配内存；无合适空闲页框时可选择页面置换，必要时将脏页写回，再读入所需页并更新页表。

因此 II 置换页、III 分配内存都可能发生；I 处理越界错不属于本题合法缺页处理，选 B。A、C、D 都含 I，应排除。这里“可能”不等于“必须”：有空闲页框时无需置换。缺页处理完成后通常重新执行引起异常的访存指令，而不是把合法缺页当作地址越界直接终止程序。

答案：B。

题目目标是提高 CPU 与 I/O 设备的综合利用率。I/O 密集进程占用 CPU 较短，运行后很快提交 I/O 并阻塞；此时设备工作，CPU 可运行其他进程，二者更容易重叠。若长期优先计算密集进程，I/O 进程迟迟发不出请求，设备可能空闲。

P3 的 I/O 比例 85%，最偏向 I/O；P2 为 50%，居中；P1 只有 10%，最偏向计算。故优先级为 $P_3>P_2>P_1$，选 B。A 恰好反向；C 将负载差异最大的两者等同；D 提高计算密集的 P1 且未区分 P2、P3。此处采用促进资源并行的调度原则，题目未给公平性、截止时间等其他目标。

答案：B。

安全状态意味着存在安全序列：按该次序，即使进程提出声明的最大资源需求，系统仍能让它们依次完成并释放资源。所以安全状态不可能已经有死锁进程，B 正确。

A 错在术语：银行家算法属于“避免死锁”，在分配前试算，拒绝导致不安全状态的请求；“预防死锁”则从机制上破坏某个必要条件。C 错：不安全表示不能保证所有最大需求均满足，实际请求较少或较早释放时仍可能完成，并不等于死锁。D 错：银行家允许进程保留已有资源再申请其他资源，没有破坏“请求和保持”。安全必无死锁，不安全则可能有死锁，也可能没有，应区分这三个概念。

答案：B。

OSI 七层自上而下为应用、表示、会话、传输、网络、数据链路、物理。应用层紧邻的下一层是表示层，解决不同系统对数据表示的差异，如字符编码、数据格式转换，以及表示相关的压缩、加密等功能，故 B 正确。

A 对话管理属于会话层，负责会话建立与对话控制，与应用层之间隔着表示层。C 路由选择属于网络层，负责分组跨网络转发。D 可靠数据传输通常属于传输层的端到端服务。题目问的是模型中哪层承担功能，不是哪些功能可能被应用程序使用；先定位应用层相邻层，再匹配职责，不能把会话层误当成直接相邻层。

答案：A。

10BaseT 采用曼彻斯特编码，每比特中间必有跳变；按本题以太网约定，中点由低到高表示 0，由高到低表示 1。图中虚线划分各比特边界，应观察相邻两虚线之间的中点，不能把边界处的跳变也算成一个数据位。

从左到右八个中点方向依次为上升、上升、下降、下降、上升、下降、下降、上升，得到 0011 0110，选 A。B 的 1010 1101、C 的 0101 0010、D 的 1100 0101 均与逐位中点方向不符。曼彻斯特编码用一个比特内的跳变方向判位，不是用电平高低直接判位；同时必须采用题目对应的以太网 0、1 约定。

答案：D。

存储转发要求路由器收完整个交换单位才转发。报文交换以整个 8 Mbit 为单位，单段发送需 $8\times10^6/(10\times10^6)=0.8\,\mathrm s$；两段依次完成，共 1600 ms。

分组数为 $8\times10^6/(10\times10^3)=800$，每组单段发送需 1 ms。第一组到乙要 2 ms，此后甲发送后组与路由器转发前组重叠，乙每隔 1 ms 收完一组，故总时间 $(800+2-1)\times1=801\,\mathrm{ms}$。A、B 把两种方式的大小关系颠倒；C 的 800 ms 漏了最后一组过第二段的时间；D 正确。题设已忽略传播、组头与拆装开销，不能额外添加。

答案：B。

CSMA 是载波侦听多路访问，站点发现信道空闲才发送。但信号传播需要时间，两个站点可能在彼此信号尚未到达时都判断空闲，随后同时发送，信号在共享介质上叠加形成冲突。因此先听后发能降低冲突概率，不能完全消除冲突，B 正确。

A CDMA 按码字区分用户，C TDMA 按不同时隙分配，D FDMA 按不同频段分配。在题目采用的理想信道划分模型中，各用户已分配不同资源，不发生 CSMA 那种竞争碰撞，所以不选 A、C、D。应区分随机争用和预先划分资源，也不能把一般噪声、码间干扰等传输问题都称作本题的介质访问冲突。

答案：A。

HDLC 的帧标志是 01111110，为避免数据出现相同模式，发送端进行零比特填充：连续遇到五个 1，立即插入一个 0；接收端按相反规则去掉填充位。原有 0 不能删除，遇到六个连续 1 时也要在第 5 个后插 0。

第一段 01111100 变为 011111000；第二段 01111110 变为 011111010。两段间本来有 0，连续 1 的计数已清零，拼接后为 011111000011111010，按选项分组就是 01111100 00111110 10，选 A。C 只得到 17 位，少填一位；B、D 不是本数据填充结果，长度也不等于原 16 位加 2 位。选项比较的是填充后的数据部分。

答案：B。

直通交换尚未收完整帧就开始转发，但至少要读到目的 MAC 地址，才能查表确定输出端口。不含前导码的以太网帧最前面就是 6 B 目的地址，因此最早也要接收 $6\times8=48$ bit。

速率为 $100\,\mathrm{Mbps}=10^8$ bit/s，这段接收时间 $48/10^8\,\mathrm s=0.48\,\mu\mathrm s$，故 B 正确。A 的 0 漏了目的地址识别；C 的 5.12 μs 是传输 64 B 最小帧的时间；D 的 121.44 μs 是传输 1518 B 帧的时间，后二者等待更多乃至全部帧，超过直通方式最低延迟。题设无排队，无需加等待输出端口的时间。

答案：B（2046，2013）。

TCP 的序号按字节编号。数据段的序号是该段第一个数据字节的序号，确认序号则表示接收方下一次期望收到的字节序号。

乙发来的数据段序号为 1913，有效载荷为 100 B，因此该段携带字节 1913～2012：最后一个字节的序号为 $1913+100-1=2012$。按本题正常、连续接收的考试模型，甲接收后已收到乙截至 2012 的数据，下一次期望乙发送的字节是 $1913+100=2013$，所以甲回复段的确认序号为 2013。

乙段的确认序号 2046 表示乙已累计确认甲截至 2045 的数据，下一次期望收到甲的字节 2046。本题采用的默认约定是：甲在立即回复前没有另行发送超过该已确认范围的数据，其下一待发字节就是 2046。因此甲回复段的序号为 2046，选择 B。

A、C 把确认序号误写成最后一个收到的字节号 2012；C、D 又把甲的发送序号多加了 1。普通 ACK 不占用序号空间，不能因为发出确认而把发送序号额外加 1。

**适用边界：**实际 TCP 中，“最早尚未被确认的序号”和“下一待发序号”是不同状态；若甲已经另发了尚未被乙确认的数据，乙报出的 ACK=2046 本身不能唯一确定甲下一次发送的序号。本题按上述未另发未确认数据、双方连续接收的考试约定求解，不能把“收到的确认号永远等于下一段发送序号”当成一般协议规则。

答案：A。

按本题采用的基础 SMTP 模型，SMTP 是发信协议，传统内容以 7 bit ASCII 表示，所以 I 成立。非 ASCII 文本、附件可以先经 MIME 等编码转换；现代 SMTP 扩展另有能力，但不将额外规则代入这道基础模型题。

用户代理向发送服务器提交邮件用 SMTP，对应 III；服务器向接收方服务器中继邮件也用 SMTP，对应 II。用户代理从邮箱服务器获取邮件通常用 POP3 或 IMAP，IV 的收信过程不由 SMTP 完成。因此 I、II、III 正确，选 A。B、C 错含 IV，且漏一个发送环节；D 虽含 II、III，仍错含 IV、漏题目范围内的 I。应区分发信提交、中继和收信三个环节。

**（1）设计思想。**主元素的出现次数严格大于 $n/2$，所以至多存在一个。使用 Boyer–Moore 投票法，逐步抵消一对不同值。若主元素存在，抵消后它仍比其他所有值合起来多，不会被全部消去。candidate 保存当前候选，votes 保存尚未抵消的候选数量；遇相同值加 1，遇不同值减 1，votes 归零后让下个元素成为新候选。

第一遍只得到可能的主元素，没有主元素的数组也可能留下候选。因此第二遍必须重新统计候选的实际次数，超过 $n/2$ 才输出，否则输出 -1。

（2）C 实现。

int majority(const int a[], int n) {
    if (n <= 0) return -1;
    int candidate = 0, votes = 0;
    for (int i = 0; i < n; ++i) {
        if (votes == 0) { candidate = a[i]; votes = 1; } // 建立新候选
        else if (a[i] == candidate) ++votes;
        else --votes;  // 消去一对不同值
    }
    int count = 0;
    for (int i = 0; i < n; ++i)
        if (a[i] == candidate) ++count;
    return count > n / 2 ? candidate : -1;
}

题中第一个数组可留下候选 5，第二遍计数为 5，满足 $5>8/2$，输出 5；第二个数组的 5 出现 4 次，只等于一半，输出 -1。n=1 时唯一元素就是主元素；空数组由入口检查返回 -1。题设合法元素非负，所以 -1 不会与合法值混淆。

**（3）正确性与复杂度。**若抵消一对涉及主元素，主元素与非主元素各减少一个，数量优势不变；若抵消两个非主元素，主元素优势增大。因此存在主元素时最终候选必为它，第二遍计数保证不会误报。两遍均扫描 n 个元素，时间 $O(n)$；只用固定几个变量，额外空间 $O(1)$。虽然值域为 0～n-1，可以另建计数数组，但投票法无需 $O(n)$ 额外空间。

**基础：**成功平均查找长度 $ASL=\sum p_i c_i$，其中 $c_i$ 是找到元素 i 的关键字比较次数。高概率元素应尽量分配较少比较次数，不同结构可以选择不同查找方法。

**（1）顺序存储。**按概率递减排列，如 do、while、for、repeat，使用顺序查找。第 i 个元素需 i 次比较，所以

$$ASL=0.35\times1+0.35\times2+0.15\times3+0.15\times4=2.1<2.2.$$

do 与 while 可互换，for 与 repeat 也可互换。若较大概率 p 放在较后位置 j，较小概率 q 放在较前位置 i，交换后 ASL 减少 $(p-q)(j-i)>0$，说明概率递减是合理次序。该排列不是字典序，应采用顺序查找，不能再直接按关键字进行折半查找。

**（2）链式存储。**可采用二叉链表构造二叉排序树：for 为根，do 为左孩子，while 为右孩子，repeat 为 while 的左孩子。字典序为 $do<for<repeat<while$，该树满足左小右大，查找时逐个比较并选择左右分支。

所以 $ASL=0.15+0.35\times2+0.35\times2+0.15\times3=2.0$，比 2.2 短。也可取 repeat 为根，do 为左孩子且带右孩子 for，while 为右孩子，ASL 同为 2.0。链式存储不必等同于单链表；若限定单链表，则用第（1）问的概率次序连接并顺序查找，也能得到 2.1，二叉链表可进一步改善到 2.0。

**（1）周期与带宽。**周期为频率的倒数：CPU 周期 $T_C=1/(800\times10^6)=1.25\,\mathrm{ns}$；总线周期 $T_B=1/(200\times10^6)=5\,\mathrm{ns}$。总线每周期最多传 32 bit=4 B，最大数据带宽 $4\times200\times10^6=800\times10^6\,\mathrm{B/s}=800\,\mathrm{MB/s}$。这里 MB 按带宽常用十进制单位计；32 位不能直接当成 32 字节。

**（2）事务个数。**填充一个 Cache 块需 32 B，每次突发事务正好传 32 B，故需要 $32/32=1$ 个读突发事务。总线宽 4 B 是每拍的数据量，不表示一个事务只有 4 B。

**（3）事务时间。**一次事务包括三阶段：首地址及命令占 1 拍，5 ns；存储器准备数据占 40 ns；32 B 分成 8 个 32 位字传送，占 $8\times5=40$ ns。8 体交叉存储让连续 8 个字分布在不同存储体，可交叠准备，后续各字不必重新等待一个完整的 40 ns。因此一次事务为 $5+40+40=85\,\mathrm{ns}$。

**（4）CPU 执行时间。**命中情况下基础时间 $100\times4\times1.25=500\,\mathrm{ns}$。总访存数为 $100\times1.2=120$，缺失数为 $120\times0.05=6$。不计替换等开销，每次缺失额外等待 85 ns，损失 $6\times85=510\,\mathrm{ns}$，总时间为 $500+510=1010\,\mathrm{ns}=1.01\,\mu\mathrm s$。基础 CPI 已含命中开销，不能再为每次命中重复加访存时间；主频和总线频率也不能混用。

**（1）编址与反向范围。**指令长 16 bit=2 B，顺序执行 PC 增加 2，说明每个地址对应 1 B，即按字节编址。8 位 OFFSET 补码范围是 -128～127，乘 2 将指令条数转换为字节偏移。最小目标为 $PC+2+2\times(-128)=PC-254$，从当前指令算起，反向距离为 $254/2=127$ 条指令。-128 是相对下一条指令 $PC+2$ 的偏移，不是相对当前指令的条数。

**（2）先判条件，再算 PC。**指令 C=0、Z=1、N=1，条件为 $ZF\lor NF$，CF 不参与。OFFSET=11100011B=E3H，无符号值 227，补码值 $227-256=-29$。

当 CF=0、ZF=0、NF=1 时，NF 满足检测，发生转移，$PC'=200C\mathrm H+2+2\times(-29)=200E\mathrm H-003A\mathrm H=1FD4\mathrm H$。当 CF=1、ZF=0、NF=0 时，被检测的两位都为 0，CF 为 1 也不触发，顺序执行，$PC'=200C\mathrm H+2=200E\mathrm H$。

**（3）无符号小于等于。**比较无符号 A、B 可由 A-B 设置标志。A<B 时发生借位，CF=1；A=B 时结果为零，ZF=1。因此所需条件是 $CF\lor ZF$，应设 C=1、Z=1、N=0。NF 表示结果符号，不能用于判断无符号大小。

**（4）数据通路。**①保存 OP、C、Z、N、OFFSET，是指令寄存器 IR。②把符号扩展后的 OFFSET 左移一位，产生 $2\times OFFSET$；先扩展使负偏移仍保持正确符号。③有来自②及 $PC+2$ 的两路输入，是加法器，输出转移目标。左侧三个与门分别计算 C·CF、Z·ZF、N·NF，再经或门控制多路选择器：条件真选择③的目标，条件假选择 $PC+2$，送回 PC。检测位为 0 时，相应标志不会影响转移决定。

馆内人数上限与门口一次一人是两种约束。计数信号量 capacity=500 表示还可预留的参观名额；互斥信号量 gate=1 保护同一个出入口，进入和离开都必须使用。P 申请资源，不足时阻塞；V 释放资源并可能唤醒等待者。

semaphore capacity = 500, gate = 1;

参观者 i:
    P(capacity);       // 先取得入馆名额
    P(gate);
    进门;
    V(gate);
    参观;
    P(gate);
    出门;
    V(gate);
    V(capacity);       // 完全出门后归还名额

每个参观者成功取得一个名额后才进馆，出馆后归还，因此馆内人数不会超过 500。gate 的临界区只包住进门或出门动作，保证同一时刻最多一人通过；参观时释放 gate，使其他人仍能进出。

进入前必须先 P(capacity) 再 P(gate)。若先占门再等名额，馆满时入馆者持有 gate 阻塞；馆内参观者又必须取得 gate 才能出门、释放名额，会死锁。先等名额的人不占门，出口可持续供馆内的人使用。归还名额应在实际离开后，不能提前允许新参观者进入。

**（1）页面和页表大小。**按字节编址，12 位页内偏移表示 $2^{12}=4096$ 个字节位置，所以页大小为 4096 B=4 KB。20 位页号表示最多 $2^{20}$ 个逻辑页，每页一个 4 B 页表项，完整一级页表最大为 $2^{20}\times4=2^{22}=4194304$ B=4 MB。页表项大小和页面大小是不同参数。

**（2）提取字段。**32 位 LA 的位 31～22 是页目录号，21～12 是页表索引，11～0 是页内偏移。使用无符号 32 位 LA：

unsigned directory = (LA >> 22) & 0x3FFu;
unsigned index = (LA >> 12) & 0x3FFu;

0x3FF 的低 10 位为 1，保留所需字段。尤其 index 在右移 12 位后还夹带目录号，不能省掉掩码。数学表达式分别为 $\lfloor LA/2^{22}\rfloor$ 与 $\lfloor LA/2^{12}\rfloor\bmod2^{10}$。

**（3）两页映射。**代码起点 00008000H 页对齐，8 KB 恰占两页；逻辑页号是 $8000\mathrm H/1000\mathrm H=8$ 及 9。第 p 项地址为“页表基址+p×4”，页框号为页面物理起点除以 1000H。

第二页连续装载，故起点 $00900000\mathrm H+1000\mathrm H=00901000\mathrm H$。表项存放地址、表项中的页框号、页框起始字节地址需分别计算，不能把 00200020H 当作代码页地址。

**（1）聚合与路由表。**AS1 的 153.14.5.0/25 和 153.14.5.128/25 覆盖同一 /24 的上下半区，且都经 R1，可精确合并为 153.14.5.0/24。R3 后面的 194.17.20.0/25 与 194.17.21.0/25 共同前缀为 /23：第三字节 20=00010100、21=00010101，共同前 7 位，加上前两字节的 16 位得到 23 位。

/23 比两个远端 /25 的覆盖范围更大，还包含本地 194.17.20.128/25，因此本地直连项必须保留，由最长前缀匹配覆盖本地部分。按图中五个所标子网，三种转发方向至少分别需要一个有效路由项，上表三项即可。图中串行互连链路只给邻端地址、未给子网前缀，不另臆造其路由项。

**（2）转发接口。**194.17.20.200 落在本地 /25 的 194.17.20.128～194.17.20.255 范围，同时匹配 /23 汇总项。路由器选匹配位数最多的项，25>23，所以通过 E0 直接交付。不能因 /23 项列在表中较前就先选它，路由不是按任意列出次序匹配。

**（3）协议及封装。**R1 属于 AS1，R2 属于 AS2，跨自治系统交换路由使用 BGP/BGP-4，该外部会话为 eBGP。BGP 报文封装在 TCP 段内，经可靠 TCP 连接传输，TCP 段再由 IP 承载。题问承载 BGP 报文的协议，应答 TCP；RIP、OSPF 属于自治系统内部常用协议，不适合这条跨 AS 会话。