2016年计算机408真题

答案：D。

单链表的“地址”是本结点的位置，“链接地址”则保存下一个结点的位置，两者不能混淆。根据表中链接，原逻辑次序为c→a→e→b→d，与各结点在内存中的排列不同。把f插入a与e之间后，应形成a→f→e，所以a的链接地址改成f所在的1014H，f的链接地址保存e所在的1010H；e仍指向b，链接地址维持1004H。按题目a、e、f的次序，得到1014H、1004H、1010H，选D。A、B没有把a的后继改为f，C虽修改a正确，却交换了e和f应保存的后继地址。实际插入宜先令f->next=a->next，再令a->next=f，避免丢失原后继。

答案：D。

设p的前驱为q=p->prev，后继为r=p->next，原链接为q↔p↔r。删除p要把q、r直接相连，所以r->prev=q、q->next=r，对应 p->next->prev=p->prev 和 p->prev->next=p->next，最后free(p)，选D。A第二句让前驱的next指向前驱自己，破坏后向链；B第一句让后继的prev指向后继自己，破坏前向链；C两处都接成自环。带头结点的循环结构使首、尾结点也有有效前驱和后继，可统一处理；但必须先使用p的指针修改相邻结点，再释放p，不能free后继续读p->next或p->prev。

答案：C。

图中列车只能从左往右，不能在轨道内倒退或超车，所以每条轨道是一条先进先出的队列。为了最终按1～9出轨，同轨道上的列车编号必须按进入顺序递增。输入中的8、4、2、1按出现次序严格递减，任意两个若同轨道，较大者都会挡住较小者，因此这4列必须用4条不同轨道，n至少4。另一方面可分配为轨道一[8,9]、二[4,5,6,7]、三[2,3]、四[1]，再依次从相应队头取1～9，确实可实现。所以选C。A、B达不到4条的下界，D虽可行却不是最少。不要将这一单向穿行结构按后进先出的栈来模拟。

答案：B。

三对角矩阵只保存主对角线及左右相邻对角线，即第i行的列i−1、i、i+1，首末行各只有2项，其他行各3项。要找m30,30，先数它之前存了多少项：第1行2项，第2～29行共28×3=84项，所以第30行开始前已存86项。第30行的顺序为m30,29、m30,30、m30,31，第一个下标86，所求为87，选B。A的86是该行第一个元素的下标；C的88是第三个元素；D的89已进入下一行。元素所在第几项与从0开始的数组下标差1，不能在数完前驱项后又多加一次。

答案：C。

一棵具有ni个结点的树恰有ni−1条边，包括只有一个结点、0条边的树。设森林中有k棵互不相交的树，所有结点数之和为25，边数之和为 $\sum( n_i-1)=25-k$。题给15条边，因此 $15=25-k$，得k=10，选C。A、B、D分别代入会得到17、16、14条边，都不等于15。也可理解为先把25个结点看作25棵孤立树，每加一条不形成回路的边就把两棵树合为一棵，15条边后剩25−15=10棵。这个关系依赖森林无环，不能用于任意有回路的图。

答案：D。

有向图DFS访问一个顶点后，必须沿它尚未访问的出边继续深入，只有该顶点的所有可达后续都处理后才回溯。图中V2唯一出边是V2→V5，V5→V4，V4→V3。D从V1到V2后立刻到V3，跳过尚未访问的V5，违反DFS规则。A可先走V1→V5→V4→V3→V2；B先走V1→V3→V2→V5→V4；C先走V1→V2→V5→V4→V3，都与出边方向及深入顺序相符，所以选D。邻接点访问次序不同可以产生不同DFS序列，但不能任意跳到其他分支；线条交叉不表示交叉点是新顶点。

答案：B。

邻接表拓扑排序通常先扫描所有顶点和弧，统计各顶点入度；把入度0的顶点入队，出队一个顶点后扫描它的出边，给终点入度减1，变为0时再入队。每个顶点至多入队、出队一次，共O(n)；每条弧至多在统计及删除时处理常数次，共O(e)，总时间 $O(n+e)$，选B。A忽略处理弧的工作，C把邻接表当作需要扫描全部n²个位置的邻接矩阵，D错误地认为每个顶点都要重新扫描全部弧。若图有环，队列可能提前为空，从已输出顶点数不足n判断无拓扑序，检查仍不改变上述复杂度。

答案：B。

Dijkstra每轮固定当前未确定距离最小的顶点，再松弛其出边。由图的有向边，源1初始到2为5、到5为4，其余∞。先固定5，经5→4得11，经5→6得9，5→2所得10不优于5。再固定2，经2→3得7，2→4所得14不优于11；然后固定3，其到5不会改进已得距离。此时6为9、4为11，先6后4，故顺序为5、2、3、6、4，选B。A把11的4排在9的6之前，C把4排在7的3之前，D把9的6排在7的3之前，都没有选当前最小距离。这里需要比较完整路径长度，而不是只比较最后一条边的权值。

答案：B。

本题按单项选择题中选出“最符合试题要求”的口径，考查跳步顺序查找在哪个位置体现比较次数少的优势。算法依次检查 A[0]、A[3]、A[6]……，遇到不小于 x 的抽查元素后，再补查前面的两项。它每次只把下标增加 3，并没有像折半查找那样把待查范围减半。

若 x 靠近数组开头，例如 x=A[0]，跳步查找只需少量比较即可成功；折半查找一般从中间开始，仍要逐步缩小范围。因此 B 最直接体现该算法的位置优势。若 x 位于中间或结尾，跳步查找的抽查次数约为 n/6 或 n/3，而折半查找为对数数量级；n>1000 时，C、D 所指位置没有这种优势。A 只说关键字不存在，没有指出失败发生的位置，不能稳定描述该算法的优势。

严谨边界。 “有可能”若严格理解为只要存在一个实例，A 也能与靠近开头同时成立。例如 n=1002、A[i]=2i+2、x=3，算法依次判断 A[0]<x、A[3]<x，再判断 A[3]、A[2]、A[1] 是否等于 x，共 5 次元素比较就可失败；通常折半查找约需 10 轮。故考试选 B，不等于在数学意义上否认所有 A 类实例都可能更快。

原伪代码的补查条件还缺少下标下界。若 k=0 且未命中，k−1、k−2 虽满足“小于 n”，却是负数；实际实现应把补查条件写成 0≤k−1<n、0≤k−2<n，并采用短路求值避免越界。这个实现修正不改变本题按位置因素选 B 的考试结论。

答案：A。

B+树将全部数据记录对应的关键字放在叶结点，并把叶结点按关键字次序链接。定位到范围起点后可沿叶链顺序读取后续记录，特别便于顺序和范围查找，这是本题要选的特点，A正确。B树的关键字也存放在结点中，B不是差别；当根不是叶结点时，B树和B+树的根通常都至少有两个分支，C也不是特有性质；二者的叶结点都在同一层，D仍是共同性质。B树也可借助树遍历得到有序结果，但不具有B+树这种统一从叶层顺序链接扫描的结构优势。判断“不同之处”要筛掉两类树共有的性质。

答案：D。

10TB数据通常远超可一次容纳的内存规模，应采用外部排序：先分批读入内存，在内存中排成有序段，再将多个有序段顺序归并，最终形成整个有序文件。归并的读写访问连续，适合磁盘及大文件，并可用多路归并减少外存扫描次数，所以选D。A希尔排序、B堆排序、C快速排序是常见内部排序方法，对整个文件直接应用会涉及大量难以高效进行的随机访问或交换，不适合作为这里的外部排序主方法。生成初始有序段时可以使用这些内部算法，但题目问10TB整体排序的合适方案，主框架仍应是外部归并。

答案：C。

编译程序对高级语言进行词法、语法、语义分析和代码生成，生成机器级目标代码文件，符合题目从高级语言源程序到目标代码的转换，选C。A汇编程序的输入是汇编语言，主要把助记符转换成机器指令，输入层次不同；B链接程序把已经生成的目标文件与库连接，解决跨模块符号引用，形成可执行程序；D解释程序通常边分析边执行源程序，不以生成独立机器级目标代码文件为主要结果。目标文件可能还含待链接的符号和重定位信息，不能因为它尚非最终可执行文件就否认编译器已经产生了机器级代码。

答案：D。

本题采用计算机组成原理考试中常用的模型：short 与 unsigned short 均占 16 位，有符号整数用补码表示。这个位宽是解题约定；C 语言并不保证所有平台的 short 都恰好为 16 位。

16 位 unsigned short 的范围为 0～65535。把 −32767 转换为该无符号类型时，按模 2^16 的规则得到

$$-32767+65536=32769.$$

所以 usi=32769，选 D。用位模式也能理解：−32767 的 16 位补码为 1000 0000 0000 0001B，即 8001H；把它按无符号数解释，最高位不再作符号位，数值为 32768+1=32769。

A 仍把结果当作负数，不符合 unsigned short；B 相当于取绝对值，而类型转换不执行绝对值运算；C 的 32768 对应 8000H，少了最低位的 1。若移到不同位宽的平台，应使用该平台 unsigned short 的实际模数重新计算，不能直接套用 32769。

答案：A。

小端将最低有效字节放在最低地址，题给double位模式共8B，应作为一个完整8B对象按字节存放，不能因机器字长32位就把两个4B部分各自单独倒序后又保留高低顺序。由8040H起依次为：8040→88H、8041→77H、8042→66H、8043→55H、8044→44H、8045→33H、8046→22H、8047→11H。因此所问8046H内容为22H，选A。B的33H在8045，C的77H在8041，D的66H在8042。这里直接使用给出的机器位模式，不需要先按浮点格式计算double对应的十进制数值。

答案：C。

本题按源程序表达的数组读写来统计：每次执行 a[k]=a[k]+32，先读取旧的 a[k]，再把新值写回 a[k]，两次都计入对数组 a 的 Cache 访问；默认循环变量 k 可在寄存器中使用，或其访问不会额外挤掉正在处理的数组块。题目没有给编译后的指令和 k 的地址，因此不另计编译优化或变量布局引起的干扰。

一个 int 占 4B，一个 Cache 块为 16B，故一块包含 4 个连续元素。Cache 初始为空，第一次读取块内首元素时缺失，整块调入；随后的写回及另外 3 个元素的读、写均命中。处理 4 个元素共访问数组 8 次，其中只有 1 次缺失，所以

$$\text{缺失率}\approx\frac{1}{8}=12.5\%.$$

1000 个元素约占 250 块，读写共 2000 次，250/2000 也得到 12.5%，选 C。直接映射且总容量只有 1KB，使后来的数组块替换以前的块，但已处理的元素不再重访，不会因此再产生本程序所需的额外缺失。

D 的 25% 只统计了每元素一次读，漏掉写；A、B 明显低于首次装入各块所必需的比例。若首地址没有恰好对齐 Cache 块，最多多涉及一个边界块，不改变“约为”的结论。真实机器的编译优化、读写合并或 k 与数组的冲突可能改变实际访存序列，测量时须另给这些条件。

答案：C。

先算ROM区大小，地址范围含两端，容量 $5FFF\mathrm H-4000\mathrm H+1=2000\mathrm H=8192$B=8KB；剩余RAM为64−8=56KB。每片8K×4位只有4KB，或者从扩展方法看，两片并联做位扩展才得到8K×8位、即8KB字节存储区。56KB需要7个8KB区，每区2片，共7×2=14片，选C。A的7只做字数扩展而忽略每片仅4位宽；D的16把全部64KB都当作RAM；B的8不符合RAM容量。芯片规格中的8K表示地址数、4表示每地址位数，不能将其直接当成8KB。

答案：C。

括号表示取其中所指寄存器或存储单元的内容。I是变址寄存器编号，本身不是寄存器数值；先变址须取出(I)，再与形式地址D相加，得到中间地址 $(I)+D$。接着间址，访问这个中间地址的存储单元，从中取得真正有效地址，所以 $EA=((I)+D)$，选C。A直接把寄存器编号加D，第一步就错；B仅做到变址，没有间址；D先把(I)进一步间接取内容，再加D，是先间址后变址，次序不同。EA是操作数所在位置，获得EA后还可能再访问它读取操作数，不要把间址取得的“地址”与最终操作数混为一谈。

答案：B。

4GB按字节编址共有 $2^{32}$ 个地址，但32位指令占4B且按字边界对齐，所有合法取指地址的低2位固定为00。因此若只问PC最低需要保存多少信息，可只存高30位的字地址，取指时补回两个0，覆盖 $2^{30}$ 个指令字位置。IR则保存整条指令，32位指令格式仍需32位，故选B。A让IR也缩为30位，会丢失指令内容；C同样缩短IR；D用32位PC当然可实现，但不是利用对齐后的最少位数。压缩PC信息不改变主存的32位字节地址空间，也不是说指令里的两个低位可以丢弃。

答案：B。

五段按序流水的数据冒险重点是后指令读到前指令尚未写回的结果，即RAW。逐条看写入目标：I1写R1，I2写R5，I3读R5并写R4，I4写R5。I2→I3在R5上存在先写后读依赖；无转发时I3的读寄存器阶段可能早于I2写回，必须等待，因此选B。I1与I2都读R2但写不同寄存器，只是共享输入，没有依赖；I2与I4都写R5，属于输出相关，但此基本按序完成流水不会倒置写回顺序；I3先读R5、I4后写R5是反相关，按序读写也不会破坏I3的旧值读取。不能只看到重复寄存器就判断一定有RAW冒险。

答案：A。

单周期处理器需在同一周期内完成取指、读操作数、执行、访存和写回等必要工作。单总线数据通路通常一次只能有一份数据驱动总线，读两个操作数、送运算结果等会争用总线，需要分多个节拍完成，不适合这样的单周期要求，因此A错误。B正确：周期必须覆盖最慢指令的完整组合延迟，时钟频率通常较低。C正确：在该指令周期内控制信号按指令生成并保持稳定，不再用多个微周期依次切换。D正确：每条指令恰用1周期，CPI=1。CPI为1不代表处理器一定快，长时钟周期仍可能导致较长执行时间。

答案：A。

并行总线每次可传多位，但多条线路有串扰、时钟偏斜和布线限制，能达到的工作频率可能较低；高速串行总线可用更高信号速率工作，因此不能无条件断言并行一定比串行快，A错误。B把地址等不同信号在不同时间复用同一组线，可减少引脚与线路，正确；C突发传输只发送一次起始地址后连续传数据，减少重复事务开销，正确；D分离事务把请求和应答拆开，设备准备期间让其他事务使用总线，可提高利用率，正确。总线吞吐量取决于位宽、频率以及协议开销，不能仅凭每次并行传多少位判断快慢。

答案：A。

按题目明确区分，异常是执行当前指令时处理器内部发现的事件，中断是设备等外部来源提出的请求。访存时页表显示所需页面未在内存，由当前访存指令触发缺页异常，A将它称为中断，错误。整数除以0在算术指令执行时检测，B属于异常；DMA传送结束由外部控制器通知CPU，C属于中断；访问不允许的内存区域触发存储保护检查，D属于异常，三项正确。某些教材统称这些控制转移为广义中断，但本题已经指定狭义定义，必须按定义判断，不能再用广义叫法覆盖题设区别。

答案：A。

批处理将作业成批提交后由系统自动组织执行，运行时用户通常不与自己的作业直接交互；允许多个用户及时交互是分时系统的主要特点，所以I错误。批处理按内存中同时安排的作业数，可分为单道和多道，II正确。中断让设备完成I/O后主动通知CPU，CPU不用一直等待查询，可在设备工作期间执行其他就绪作业，III正确。仅II、III成立，选A。B漏III，C、D都含错误的I；“可有多个用户提交作业”不等于“允许多个用户在执行过程中直接交互”。多道安排提高CPU与I/O重叠程度，而不意味着一台CPU真正同时执行多条指令。

答案：B。

输入设备、CPU、输出设备可以并行，但每台设备一次只能服务一个作业，且每个作业必须先输入再计算再输出。可按三个作业依次安排：

最早可开始输出是首个作业输入2ms加计算3ms后的5ms；三个作业输出共需3×4=12ms，所以完工至少5+12=17ms。表中输出从5ms起持续忙碌，达到下界，故选B。A的15ms不足该下界，C的22ms未充分重叠，D的27ms把所有阶段完全串行相加。

答案：C。

死锁需形成循环等待：每个参与进程持有别的参与者所需资源，又等待别人的资源。题中任意两进程的资源需求交集至多一种资源，它们无法各自持有对方所要的另一种资源形成二元等待环；没有自我重复申请的条件，也不会一人死锁。三人则能形成：p1持R1等R2，p2持R2等R3，p3持R3等R1，正好闭环，所以最少3个，选C。A、B不具备上述循环，D虽可能有更多进程等待，却不是最少；p4只申请R2，拿到后即可完成，不需再等另一种资源，不能作为该循环的必要一环。进程被阻塞不一定意味着它本身参与了死锁环。

答案：A。

改进CLOCK同时考虑近期是否访问及淘汰是否需写回。访问位A=0表示近期没有使用，优先于A=1；在同样访问状态下，M=0的页未修改，丢弃即可，优先于需要写回外存的M=1页。因此类别优先次序为(0,0)、(0,1)、(1,0)、(1,1)，选A。B把最近使用但干净的页放在未使用脏页前，改变了主要按访问状况区分的顺序；C把同为已访问的脏页放在干净页前；D同时混淆多个类别。实际CLOCK扫描还会清除访问位，使页面在后续轮次改类；本题问的是给定A、M状态下的淘汰类别次序，而不是说某页永远属于同一类别。

答案：B。

TSL原子地读出锁原值并将其置为TRUE。若锁已被占用，它返回TRUE，进程在while中不断重新测试，这叫忙等或自旋，等待者没有主动进入阻塞态、也没有主动让出CPU，因此B正确。退出者只将lock置FALSE，不执行唤醒阻塞队列的操作，A错误；“让权等待”要求不能进入时让出CPU，这段持续自旋代码不满足，C错误。TSL本身是不可分割的硬件原子指令，不必通过关中断保证测试和置位整体性，D错误。在单CPU中若等待者长期占用CPU还可能阻碍持锁者继续运行，自旋与阻塞式等待的区别应看等待循环实际做了什么。

答案：D。

分段地址由段号和段内偏移组成。先用段号2查表，图中第2段在内存、允许读写，基址4000，段长300；合法偏移应满足 $0\le偏移<300$。所求偏移400超过段长，所以发生越界异常，选D，不能先把4000+400算成4400就认为成功。A的段缺失不符有效状态“在内存”；C的越权不符该段读写权限，且题目没有给出禁止本次操作的权限条件；B只做了基址相加，遗漏边界检查。段长是该段可访问的长度，不是最后一个合法偏移；即使偏移恰等于段长也越界。

答案：A。

工作集W(t,Δ)是时刻t之前最近Δ次访问涉及的不同页面集合，不是这些访问的完整重复序列，也不是未来可能访问的页。图中t箭头位于第二次访问2之后，向左数6次，窗口依次覆盖6、0、3、2、3、2，去掉重复的3、2，得到{6,0,3,2}，选A。B把窗口向右错移，加入尚未纳入本窗口的4并丢失6；C还加入未来访问的9；D把窗口扩到更早的4、5，超过6次访问。集合元素数可以小于窗口长度，因为同一页可能反复出现。应先定位图中的t，再数“访问次数”，不能把6误解成一定要取6个不同页面。

答案：C。

P1的两个线程共享进程级x，P2的两个线程共享另一个进程级x，两个进程的x虽然同名却属于不同地址空间。各函数内声明的a、b则是线程执行栈上的局部变量。A的a=1、a=2操作各自局部a，不冲突；B的a=x、b=x只是读取P2的共享x并写各自局部变量，两次读之间不必互斥；D的x+=1、x+=3修改不同进程的x，也不冲突。C的x+=1与x+=2都对P1同一个x进行读、改、写，若交错可能丢失一次更新，所以需互斥，选C。其他读与写组合可能还需同步，但不能据此说题列的两个纯读取操作必须互斥。

答案：D。

SPOOLing用磁盘上的输入井、输出井暂存各作业数据，再由系统输入/输出服务程序与慢速独占设备进行实际传送。用户作业只面向暂存队列提出请求，不直接控制设备与井之间的传输，因此D错误。A正确，磁盘等外存提供井的存储；B正确，多道程序设计使用户作业与系统服务程序协调工作；C正确，例如多个作业可同时把打印内容提交到输出井，后台按次序实际使用同一打印机，形成逻辑共享。它没有让打印机在物理上同时打印多个作业，而是用排队和缓冲把独占设备虚拟成可供多个用户申请的服务。

答案：A。

管程封装共享数据及访问它们的过程，语言和运行时保证任一时刻只有一个进程在管程中执行，从而实现互斥；还提供条件变量及wait、signal等操作，进程可在条件不满足时等待，在条件满足后继续，所以它也实现同步，A的“只能互斥”错误。B指出语言层面的支持，C指出管程入口的互斥保证，D指出内部变量只通过管程过程访问，均正确。执行wait的进程暂时退出管程并释放进入资格，让其他进程进来改变条件，而不是占着管程睡眠。互斥控制谁能进入，条件同步控制何时能继续，二者都是管程的作用。

答案：C。

OSI自下而上第1层物理层传送比特，第2层数据链路层处理帧及MAC，第3层网络层按网络地址路由分组。R1是路由器，根据目的IP选择下一跳，最高实现网络层3；图中Switch为普通以太网交换机，学习和匹配MAC转发帧，最高第2层；Hub只再生并复制比特流，不识别MAC或IP，最高第1层。因此顺序3、2、1，选C。A、B把路由器降成2层，B、D又让集线器具有它并未实现的链路层功能。设备当然也需要下层功能，“最高层”不表示路由器不涉及物理或数据链路层。

答案：C。

题给频率带宽和信噪比，应使用香农上限 $C=B\log_2(1+S/N)$。30dB是对数单位，先换成线性比：$S/N=10^{30/10}=1000$，B=8kHz=8000Hz。理论最大速率 $8000\log_2(1001)\approx8000\times9.97\approx79.8$kbps。实际为理论值50%，约39.9kbps，即40kbps，选C。D的80kbps只算理论上限而漏乘50%；A、B与正确的信噪比换算和公式不符。不能把30直接放入log₂(1+30)，也不能把8kHz直接当作8kbps；频带宽度和数据比特率属于不同量。

答案：D。

H4的确认帧先到Hub，Hub不查看目的MAC，会把比特流复制到其他端口，因此同Hub上的H3在物理层也能收到；连接交换机的端口也收到。此前H2发送到H4的数据帧使交换机学到H2所在端口，因此返回的单播确认经交换机只送H2端口，不送H1。除H4外能从物理层收到的是H2、H3，选D。A漏H3，B漏目的主机H2，C误加被交换机隔离的H1并漏H3。H3收到电信号不代表其链路层会接受该帧：检查目的MAC后可以丢弃。题目专门说“物理层上收到”，要区分信号到达与上层接收。

答案：B。

Hub连接的共享以太网使用碰撞检测，最短帧还未发送完时，最远处碰撞信号应能往返返回。100Base-T速率为100Mbps，以太网最短帧64B，不计前导码，发送时间 $64\times8/(100\times10^6)=5.12\,\mu s$。设H3与H4线缆总距离d，每方向经过Hub需1.535μs，传播速度200m/μs，则 $2(d/200+1.535)\le5.12$，得 $d\le200(2.56-1.535)=205$m，选B。C、D超出碰撞检测允许的往返时间，A虽小于上限，却不是理论最远值。Hub延迟单程一次、往返两次，不能漏扣或只在总往返中扣一次。

答案：B。

本题采用基础距离向量路由的考试模型：路由器保存各邻居最近通告的距离向量，收到一个邻居的新向量后，将所有邻居提供的候选距离重新比较；未收到更新的邻居信息仍按原值使用。按这个模型计算时，R2 可以使用 R1 尚未更新的旧距离。

RIP 用跳数表示距离，按本题约定直连网络的距离为 1，不可达为 16。网络正常且已收敛时，R3 到直连的 201.1.2.0/25 距离为 1，R1、R2 各经 R3 到该网的距离为 2。

R3 检测到故障后，把自己的距离改为 16 并向 R2 通告。R2 经 R3 的候选路由因此不可达，但 R1 尚未收到这一故障消息，其最近通告的距离仍为 2。R2 经 R1 的候选距离是

$$1+2=3.$$

比较候选后，R2 暂时选择经 R1 的 3 跳路由，选 B。A 的 2 保留了已失效的原距离；在本题模型中 C 忽略了 R1 的旧信息；D 的 17 也不是 RIP 的有效可达度量，超过 15 的情况统一记为 16。

这条“3 跳路由”只是旧信息造成的暂时判断，数据并不能沿它真正到达已断开的网络；R1、R2 的陈旧信息可能导致路由环路和逐步计数到无穷，这就是坏消息传播慢的典型问题。

实现边界。 若实现只保存当前最优路由，并按收到的每条 RIP 通告增量更新，原下一跳 R3 通告 16 后，该项可以先变为 16；等后续收到 R1 的旧通告才会变为 3。是否缓存全部邻居向量、是否启用水平分割或毒性逆转都会影响中间过程。本题的 B 依赖前述基础距离向量模型，不能把它泛化为任何 RIP 实现收到一次故障通告后的必然结果。

答案：D。

图中H3地址192.168.3.251为私有地址，R2执行NAT。去Web服务器130.18.10.1的分组经R2的L0接口向R1转发；该点对点链路为201.1.3.8/30，4个地址中.8是网络地址、.11是广播地址，R1接口已为.9，所以R2外侧接口为201.1.3.10。NAT把源IP改为该出口公网地址，目的IP仍为服务器130.18.10.1，选D。A没有做源地址转换；B既未转换源地址，又把下一跳接口当成IP目的地址；C用了不能分配给接口的网络地址.8。路由下一跳会影响外层链路帧，不会把IP目的服务器地址改成相邻路由器地址。

答案：C。

掩码255.255.255.128为/25，把192.168.3.x分成0～127和128～255两半。H1=.2、H2=.3属于前半，能直接ARP彼此并通信，A错误；H3=.251、H4=.252属于后半，也能直接通信，D错误。H1访问H3时认为对方跨子网，向配置的网关192.168.3.1发送，但图中路由器接口实际为192.168.3.254，并无提供该转发的.1接口，因此H1与H3可能无法正常IP通信，C成立。H4的网关.254在自己的后半子网且是R2真实接口，仍可访问Internet，所以B的“H2与H4均不能”错误。主机物理上接在同一交换网络，不代表错误的逻辑网关配置也能完成跨子网通信。

答案：C。

H4先向默认DNS服务器201.1.1.1请求解析，题问的是这台服务器随后向其他DNS服务器发出的查询次数，不能把H4发给它的请求也计进去。若它缓存中已有可用答案，直接返回，不向外查询，最少0次。最坏缓存没有信息，迭代查询中依次问根DNS、com的DNS、xyz.com的DNS、abc.xyz.com的权威DNS，由最后一层得到www.abc.xyz.com地址，最多4次。因此选C。A、B最多只算3次，漏掉一个实际域层级；B、D又错误地认为本地服务器即使命中缓存也至少外查一次。这里www是待查询主机名，不再单独算一次DNS委派层。

计算约定。 本题按经典教材的慢开始模型：TCP连接建立后初始拥塞窗口 cwnd=1MSS=1KB，每个确认新数据段的ACK使cwnd增加1MSS；忽略段传输时间、丢包及额外确认延迟，按RTT分轮计算。题面给出的32KB是慢开始阈值，不是初始cwnd。实际TCP实现可采用不同的初始窗口，以下窗口与历时结果均按上述考试模型得出。

（1）第二次握手。 S接受连接时既确认H3的SYN，又发自己的SYN，因此SYN=1、ACK=1。H3初始序号100，SYN占一个序号，所以S的确认序号ack=101；这表示下一步期望H3的101号字节。S自己的初始seq独立选择，不能根据H3的100反推。

（2）第8个确认后的窗口。 S从不取出已收数据，每个1KB段占接收缓存1KB，第8个确认表明共收到8KB，通告窗口 $rwnd=20-8=12$KB。发送端拥塞窗口初值为1MSS=1KB，阈值32KB；慢开始每个新的段确认使cwnd加1MSS，8次确认后cwnd=1+8=9KB，仍未到阈值。发送窗口取拥塞和接收窗口的较小值，即min(9,12)=9KB。慢开始“每RTT约翻倍”是多次确认累积的效果，不能误写成每个确认就翻倍。

（3）窗口变0时的序号和平均速率。 缓存装满共收到20×1024=20480B，首个数据字节seq=101，所以下一个待发送段序号 $101+20480=20581$。忽略段传输时间，用RTT分轮模拟如下：

第5轮受剩余缓存5KB限制，收到其确认后发送窗口0。自第一段发出至此经过5RTT=5×200ms=1s，平均速率20480B/s=20KiB/s，按比特换算为163840bit/s=163.84kbps。不能把20KB/s直接写成20kbps，也不能在缓存满后继续按cwnd发送。

（4）S最早释放连接。 正常关闭的单程时延RTT/2=100ms。t时刻H3发FIN，t+100ms到S；通信已结束，S可立即把ACK和自己的FIN一起发出；t+200ms到H3，H3立刻返回最后ACK；t+300ms到S，S获得最终确认并释放连接。所以最短300ms=1.5RTT。等待2MSL的TIME-WAIT由主动关闭方H3承担，不能再加到S释放所需时间上。

（1）由边数推叶结点数。 非叶结点m个，每个都有k个孩子，所以父子边总数km。若叶结点l个，总结点m+l，而非空树的边数总等于结点数减1，即 $km=m+l-1$。整理得 $l=(k-1)m+1$。单根树m=0、l=1也符合，二叉情形k=2退化为l=m+1。

（2）高度h的最大、最小结点数。 最大时从根起每层所有可能孩子都存在，第i层有 $k^{i-1}$ 个结点，故

$$N_{\max}=1+k+\cdots+k^{h-1}=\frac{k^h-1}{k-1}.$$

最少时要有一条从根到第h层的路径，其前h−1个结点必为非叶结点，所以m至少h−1。每个这样的结点仍必须有k个孩子，不能只保留单孩子链。构造方法是在每层选一个孩子继续向下，其余k−1个立即作为叶结点，直到第h层全部为叶，此时恰有m=h−1。由总数N=km+1，得到

$$N_{\min}=k(h-1)+1.$$

例如k=3、h=3，根3个孩子，其中仅一个再生3个孩子，总数1+3+3=7，符合最小式；若第二层3个都继续生孩子，总数1+3+9=13，符合最大式。h=1时两式均为1，说明边界与高度定义一致。

（1）数量约束与和差目标。 n为偶数时，两组各n/2个，数量差最小为0；n为奇数时，只能分别为⌊n/2⌋和⌈n/2⌉个，数量差最小为1。令k=⌊n/2⌋，把最小的k个数给A1，其余给A2。

为什么这样也使绝对和差最大？设总和T，任意k项子集的和s位于最小k项和L与最大k项和U之间，和差为|T−2s|，最大只可能在端点L、U。最小k项和最大k项可以选为不相交，剩余项都是正整数，故L+U≤T；又L≤T/2。因此T−2L≥|T−2U|，选择最小k项的一组已取得最大绝对和差。奇数时尤其不能随意把较大的k项给较少一组而认为同样最优。

不必把各组内部排序，只要把数组划分为前k个最小元素和其余元素。可用随机快速选择确定下标k−1的边界，每轮三路划分成“小于枢轴、等于枢轴、大于枢轴”，只继续包含目标位置的一段。

（2）C++实现。 数组被原地重排，返回两组的和差，划分结果由两个连续区间表示。

#include <random>
#include <utility>

// 前提：n >= 2，a中均为正整数；两组和须在long long范围内。
long long partitionSets(int a[], int n) {
    const int k = n / 2, target = k - 1;
    int lo = 0, hi = n - 1;
    std::mt19937 rng(std::random_device{}());
    while (lo <= hi) {
        std::uniform_int_distribution<int> pick(lo, hi);
        int pivot = a[pick(rng)];
        int lt = lo, i = lo, gt = hi;
        while (i <= gt) {
            if (a[i] < pivot) std::swap(a[lt++], a[i++]);
            else if (a[i] > pivot) std::swap(a[i], a[gt--]);
            else ++i;          // 等值元素留在中间区
        }
        // [lo,lt-1]<pivot，[lt,gt]==pivot，[gt+1,hi]>pivot
        if (target < lt) hi = lt - 1;
        else if (target > gt) lo = gt + 1;
        else break;
    }
    long long small = 0, large = 0;
    for (int i = 0; i < k; ++i) small += a[i];
    for (int i = k; i < n; ++i) large += a[i];
    return large - small; // A1=a[0..k-1]，A2=a[k..n-1]
}

交换一个大于枢轴的元素到右区后，不增加i，因为新换来的a[i]还未分类；这是三路划分的关键。每轮排除不含目标的一侧，外侧已划定的元素仍满足与保留区的大小关系；目标落进等值区时，即使边界切开相等值，也不影响前k项是最小k项。n=2、全部相等和大量重复值都能处理。

例如[8,1,6,2,9]，k=2，A1取1、2，A2取6、8、9，数量差1，和差23−3=20；组内顺序不重要。

（3）复杂度。 随机选择的期望处理量为线性，最后求和也为O(n)，平均时间O(n)，极端枢轴选择时最坏O(n²)。迭代原地划分不建递归栈或额外数组，固定随机数生成器状态及变量占用不随n增加，额外空间O(1)。

（1）串行帧与设备字符率。 异步字符除了7位ASCII数据，还需1位起始、1位奇校验和1位停止，共1+7+1+1=10位。奇校验位根据数据中1的个数决定，并不是额外增加一整个字符。从启动到送到端口用0.5ms，因此若持续接续工作，每秒最多 $1/(0.5\times10^{-3})=2000$ 个字符。这个数由设备工作周期决定；不能用CPU主频直接充当串行字符率。

（2）总历时与CPU占用。 每时钟周期20ns，设备一次输入折算为 $0.5\mathrm{ms}\times50\mathrm{MHz}=25000$ 周期。每个字符中断响应10周期，20条服务指令按CPI=4共80周期，CPU实际处理一个字符需90周期，1000个共90000周期。

计算任务总历时还要考虑下一次启动位置。自某字符送入端口起，先响应10周期，再执行至第15条指令用15×4=60周期，共70周期才启动下一字符。之后服务程序剩余5条即20周期，与设备的下一个25000周期工作重叠，不应重复串行相加。

从首次启动开始，前999次字符之间各有25000+70周期，最后一次还需25000周期及完整末次90周期，故

$$T=1000\times25000+999\times70+90=25070020\ \text{时钟周期},$$

约为2.507×10⁷周期，即0.5014004s。首次启动指令本身的额外开销题目未给出，按图中启动时刻作为计时起点；数量级近似不受它影响。CPU占用仍是9×10⁴周期，即1.8ms，与总历时不同。

中断响应阶段由硬件完成关中断、保存断点及必要程序状态、确定中断服务入口并转入该入口；服务程序随后保存所需通用寄存器、读取字符及再次启动设备等。不能把CPU在设备工作的25000周期也全部计作该输入任务占用CPU。

（1）按图分字段。 页大小8KB=$2^{13}$B，所以页内偏移13位。虚拟地址32位，A为虚页号32−13=19位；全相联TLB没有组号或行索引，其标记B保存完整虚页号，也是19位。物理地址24位，C为物理页框号24−13=11位，D为不变的13位页内偏移。

Cache每块64B=$2^6$B，块内偏移G为6位。64KB数据区共有64KB/64B=1024行，2路组相联使组数为1024/2=512=$2^9$，F组号9位；剩余E标记位数24−9−6=9位。

TLB存页表映射，而Cache存数据块，两者的标记依据不同；不能因为都是相联比较就直接用相同位宽。

（2）块4099的组号和H。 组号为主存块号对组数取模：4099=8×512+3，所以组号3，标记是商8。H就是该行保存的标记字段，宽9位，内容为 000001000。这里输入已是“块号”，无需再除64；若输入字节地址，才应先去掉6位块内偏移再计算。

（3）两种缺失代价。 Cache缺失通常从主存读一个64B块；缺页是整个8KB页不在主存，需要异常处理、分配或置换页框、从磁盘等外存调页及更新页表，若旧页脏还要写回。磁盘比主存慢得多，传输单位也更大，所以缺页处理时间远大于Cache缺失。TLB未命中则可能只是查内存页表，也不能直接等同于缺页。

（4）写策略。 Cache直写让每次修改同时更新主存，方便维持主存最新副本；主存较快且可结合写缓冲，代价可接受。若每次修改页面都立刻写磁盘，频繁小写会产生巨大的外存访问开销。页面因此设置修改位，先把多次修改累积在主存，换出时仅对脏页统一回写；未修改页可直接丢弃。按题目分页管理的策略，回写把昂贵磁盘I/O摊到页面换出时，而不在每条存储指令后访问外存。

（1）静态优先级的饥饿。 优先数越小越先运行。若priority始终等于nice，大nice进程即使一直等待也不会提高优先级；只要较小nice进程不断就绪，调度器每次都选它们，大nice进程就可能长期没有CPU，形成饥饿。饥饿不是该进程缺少某种资源形成死锁，而是调度策略始终不给它执行机会。

（2）动态计算。 一种可行公式是

$$priority=nice+\alpha\,cpuTime-\beta\,waitTime, \qquad \alpha>0,\ \beta>0.$$

例如取α=β=1。进程持续运行时cpuTime增加、waitTime置0，优先数逐渐变大，有利于把CPU让给其他进程；就绪等待时cpuTime置0、waitTime增加，优先数逐渐减小，即优先级持续提高。这种按等待时间提高优先级称为老化。

如nice=10的进程等待12个计时单位，priority=−2，可超过nice=0且刚就绪的进程，说明静态劣势不会永远保留。在nice有界且调度器定期更新和比较优先数的通常实现条件下，等待足够久的进程会得到执行机会，从而避免饥饿。waitTime系数必须带负号，因为本题小数优先；还应避免计数或计算溢出让长期等待者反而失去优先级，并对相同优先数采用合理顺序。

（1）目录文件内容。 目录项保存“名字、首簇号”，不列出该文件的全部簇链。图中dir占簇1，包含一个子目录dir1，首簇48；dir1包含file1、file2，首簇分别100、200。所以所有目录文件的所需内容为：

题目未给特殊的当前目录/父目录项，无需为答案额外假定这些项。

（2）FAT与最大文件。 每项2B可表示16位簇号，至多编号 $2^{16}=65536$ 个簇。每簇对应一项，FAT最大长度 $2^{16}\times2=131072$B=128KiB。按题设不扣除保留簇号、目录簇等实际占用的理论上界，一个文件最多串起全部簇，长度 $2^{16}\times4096=2^{28}$B=256MiB。实际文件系统若用部分编码表示空闲、坏簇或结束标记，可用簇数会少一些；本题未指定这些扣除口径，不能凭空套入某种具体FAT格式的限制。

（3）下一簇号存放位置。 FAT下标是“当前簇号”，表项内容是“下一个簇号”。file1簇链100→106→108，所以106存于FAT[100]，108存于FAT[106]，最后FAT[108]存结束标志；首簇100存于dir1中的目录项。不能把FAT[106]写成106，那样表示自环，无法前进到下一簇。

（4）读第5000个字节。 从1开始计数字节，簇内位置按0开始的偏移为4999；$4999=1\times4096+903$，所以它在文件第二簇、簇内偏移903。dir目录已在内存，先查它得到dir1首簇48，需读簇48查file1首簇100；再从已在内存的FAT读取FAT[100]=106，直接读数据簇106即可。因此实际需访问簇48、106。无需读dir所在簇1，也无需先读数据簇100，因为目录与FAT已经给出定位第二簇的全部信息。