2011年计算机408真题

答案：A。

时间复杂度要数循环执行次数，不能仅看条件中出现了 n。x 初值为2，每执行一次循环就乘2，执行 t 次后为 $x=2^{t+1}$，依次得到2、4、8、16……。退出时满足 $2^{t+1}\ge n/2$，因而 t 随 $\log_2n$ 增长。循环体只有一次乘法和赋值，每次耗时按常数计算，总时间为 $O(\log_2n)$，选A。B对应每次只推进固定距离的线性循环，C通常需要另有一层线性工作，D通常对应二重线性循环，本题都没有这些工作。n较小时循环可能一次也不执行；复杂度讨论的是n增大时的增长趋势。

答案：B。

栈遵循后进先出。要让d首先出栈，必须先依次压入a、b、c、d，并且不能提前弹出a、b、c。弹出d后，栈从底到顶为a、b、c，它们只能按c、b、a的顺序弹出；尚未入栈的e可以在这三次弹出之前、之间或之后入栈并弹出。因此全部序列为 d e c b a、d c e b a、d c b e a、d c b a e，共4种，选B。A的3种漏算了一个插入位置；C、D多计了会改变c、b、a相对顺序的非法序列。注意进栈顺序固定，并不意味着所有元素必须先全部入栈后才能出栈。

答案：B。

先认清指针含义：题中rear指向实际队尾元素，不能套用“rear指向队尾后一格”的实现。入队时，新元素应放在原队尾的下一格，即先计算 $rear=(rear+1)\bmod n$，再写入A[rear]。要求首次写入A[0]，初值就应满足 $(rear+1)\bmod n=0$，所以rear=n−1。front指向队头，首次入队后的队头在A[0]，故初值front=0，选B。A会使首次写入A[1]；C、D的front=n−1与首次队头位置不符。空队列本来没有“实际队尾”，这里的初值是为后续操作设置的约定，判空还可借助计数或标志，不能靠字面含义猜初值。

答案：C。

完全二叉树按层从左到右编号为1到768。编号i的左孩子为2i；有左孩子就不是叶结点，因此非叶结点满足 $2i\le768$，即i≤384，共384个。剩余编号385到768都没有孩子，叶结点数为 $768-384=384$，选C。也可使用完全二叉树公式 $n_0=\lceil n/2\rceil$。A的257、B的258和D的385均与编号计数不符。特别要注意结点384只有左孩子768，没有右孩子769；完全二叉树可以有一个度为1的结点，所以不能直接当作每个内部结点都有两个孩子的满二叉树来算。

答案：C。

前序是“根、左、右”，后序是“左、右、根”。根为1，前序第二个2与后序倒数第二个2相同，说明其余结点都在以2为根的同一子树中；对子树重复判断，得到单孩子链 $1\to2\to3\to4$。每个孩子可在左侧或右侧，中序并不唯一，但每层根只能位于整条子链中序的最前或最后。A可由全右孩子实现；D可由全左孩子实现；B可由1的左孩子为2，而2、3的孩子在右侧实现。对C去掉末尾根1后剩3、2、4，根2却位于其子链中间，要求同时有左右子树，与单孩子链矛盾，因此不会出现C。

答案：D。

普通树转为二叉树用“左孩子、右兄弟”表示：二叉树左指针指向原树的第一个孩子，右指针指向原树的下一个兄弟。因此“无右孩子”是在数原树中没有下一个兄弟的结点，并不是数叶结点。原树非叶结点有 $2011-116=1895$ 个，每个非叶结点对应一组孩子，其中最后一个孩子恰好没有右兄弟，得到1895个。根没有兄弟，也没有右孩子，再加1，结果为1896，选D。A、B只围绕叶数计算，混淆了孩子与兄弟；C漏算了根。不同父结点的孩子组互不重叠，所以以上计数不会重复。

答案：A。

二叉排序树的左子树关键字小于根，右子树关键字大于根；沿查找路径下降时，祖先限定的上下界必须一直保留。A中95→22表示进入95的左子树，22→91又进入22的右子树，可行范围变为(22,95)；91→24后范围缩为(22,91)。随后出现94，大于上界91，已经不在当前子树，故A不可能。B中的后续范围依次收缩到(34,88)，35合法；C收缩到(36,77)，38合法；D收缩到(33,68)，34合法，均可作为查找路径。易错点是只检查相邻两个数是否一大一小，而没有检查全部祖先的约束。

答案：C。

逐条区分概念。I中简单路径要求路径上的顶点不重复，而回路起点与终点相同；按本题采用的定义，回路不能直接称为简单路径，I错，“简单回路”是另一概念。II中邻接矩阵需存 $n^2$ 个位置，空间 $O(n^2)$；邻接表存顶点和实际边，空间 $O(n+e)$。稀疏图的e远小于 $n^2$，邻接表通常更省空间，II错。III中拓扑序要求每条边的起点排在终点之前，若存在有向回路，就会要求某顶点排在自身之前，产生矛盾，故存在拓扑序说明无回路。只有III正确，选C；A、B含错误的II，D含错误的I。

答案：D。

散列表发生冲突时要多做探测或比较，所以提高效率的关键是减少冲突及其连锁影响。装填因子 $\alpha=已存元素数/散列表容量$ 表示拥挤程度，增大它通常会增加冲突、延长查找，I错。好的散列函数把关键字尽量均匀分散到不同地址，避免很多元素集中到少量位置，II对。冲突处理若产生聚集，后续新元素又容易撞进同一区域；采用合适的探测方法等避免聚集，也能改善效率，III对。因此仅II、III成立，选D。A只选了错误措施，B漏掉III，C既包含I又漏掉III。提高装填因子可以节省空槽，但不能据此认为查找更快。

答案：A。

快速排序的一趟划分通常从区间两端扫描元素，以枢轴为界交换不合适的元素，再递归处理左右两个子区间。顺序存储用连续数组保存元素，可以用下标在常数时间访问任意位置，也便于就地交换和表示子区间，因此选A。B的散列存储根据关键字映射位置，不适合维护待排序区间的线性次序；C的链式存储不能直接随机访问或方便地向前扫描，从某个位置寻找另一位置往往需要遍历；D的索引存储额外维护索引，不是常规快速排序最合适的基础存储形式。链表上可以设计其他划分办法，但题目问的是宜采用哪种方式，数组最符合经典算法的访问需求。

答案：B。

大根堆要求每个父结点不小于孩子，但兄弟之间不必有序。用从1开始的数组下标表示原堆：25、13、10、12、9位于1到5。新元素18先放在尾部下标6，其父结点在 $\lfloor6/2\rfloor=3$，值为10。第一次比较18>10，交换后18来到下标3；它的新父结点在下标1，值为25，第二次比较18≤25，停止上滤。调整后的堆为25、13、18、12、9、10，共2次元素比较，选B。A漏掉停止前的第二次比较；C、D把没有发生的兄弟比较、下标判断或交换操作计入了“元素之间比较”。插入上滤只沿祖先链进行。

答案：D。

题目强调“浮点数操作速度”，应寻找单位直接表示浮点运算次数的指标。MFLOPS是每秒百万次浮点运算，即浮点运算次数除以运行秒数，再除以 $10^6$，D符合。A的MIPS是每秒百万条指令，指令可以是整数、访存或控制指令，不能直接等同于浮点运算次数。B的CPI表示平均执行一条指令需要的时钟周期数；C的IPC表示平均每个时钟周期完成的指令数，二者描述指令执行效率，也不是浮点运算速率。因此选D。比较性能时还应注意不同指令可能完成不同数量的浮点操作，本题只考各指标的含义。

答案：A。

IEEE 754单精度由1位符号、8位阶码和23位尾数字段组成，规格化数使用偏置127，最高位的1不保存。先把绝对值转换为二进制：$8.25=1000.01_2=1.00001_2\times2^3$。x为负数，符号位为1；阶码为 $3+127=130=10000010_2$；尾数字段为 00001000000000000000000。拼接为 1 10000010 00001000000000000000000，每4位转十六进制，得到C1040000H，选A。B、C、D的指数或尾数均不符合这组字段。这里−8.25能被二进制精确表示，不需舍入；浮点负数通过符号位表示，不能对正数的整个32位编码求补码。

答案：B。

随机存取的要点是：可直接按地址读写所选单元，访问时间基本不依赖地址位置。EPROM是可擦除可编程只读存储器，虽然写入机制特殊，读取仍可按地址随机访问；DRAM和SRAM也通过地址译码选择存储单元，均属随机存取。CDROM读取光盘信息需光头定位、盘片旋转等机械动作，访问不同位置的时间不同，通常归为直接存取，而不是这里所说的等时间随机存取。因此B符合“不采用随机存取方式”。A、C、D都是半导体随机访问存储器。不要把名称中的ROM误解为只能顺序读取；是否可写与是否随机存取是两个不同分类维度。

答案：D。

MAR保存CPU要访问的主存地址，位数由可寻址的地址空间决定。题设按字节编址，64MB采用 $1\mathrm{MB}=2^{20}\mathrm B$，因此地址空间含 $64\times2^{20}=2^{26}$ 个字节地址，需要26位才能逐一编号，选D。当前只安装32MB，不会把机器的地址空间变成32MB，所以C的25位只够表示当前容量，仍不满足题意。每片 $4\mathrm M\times8$ 位芯片含 $2^{22}$ 个字节，A的22位只够片内选址；B的23位也覆盖不了整个空间。区分芯片地址引脚数、已安装容量和体系结构的主存地址空间，是本题的关键。

答案：A。

形式地址A是指令中给出的地址字段，有效地址EA是最终用来访问操作数的地址。偏移寻址的共同结构为 $EA=寄存器内容+A$。基址寻址用基址寄存器，$EA=(BR)+A$；相对寻址用程序计数器，$EA=(PC)+A$；变址寻址用变址寄存器，$EA=(IX)+A$，所以B、C、D都属于偏移寻址。间接寻址则先到形式地址所指的单元取出另一个地址，即 $EA=(A)$，多了一次取地址的访问，不是上述相加形式，因此选A。不要因间接寻址也要“算地址”就把它归入偏移寻址；判断标准是有效地址具体如何形成。

答案：C。

无符号数比较可通过“被比较数减去另一数”后的标志判断。若前者小于后者，减法发生借位，CF=1；若两数相等，结果为0，ZF=1。要判断严格大于，必须同时满足没有借位CF=0和结果非零ZF=0，即 $\overline{CF}\cdot\overline{ZF}=1$。由德摩根律可写成 $\overline{CF+ZF}=1$，其中加号表示逻辑或，选C。A混入OF，B混入SF且不能排除相等，D也使用了SF并漏掉ZF，都不能正确判断无符号大于。SF、OF主要用于带符号数的大小和溢出判断，不能直接套到无符号比较上。

答案：D。

流水线把不同指令的取指、译码、执行、访存等阶段重叠进行，指令越规整，越容易让各阶段以固定节拍工作。I中统一长度和规整格式使取指边界、操作码位置容易确定，简化译码。II中指令和数据按边界对齐，能减少一次访问跨越多个存储单元的情况，降低取指和访存控制的复杂度。III中只有Load/Store访存，算术指令的操作数来自寄存器，减少各类指令执行路径的差异，也便于安排统一的访存阶段。三项都“有利于”实现流水线，选D。A、B、C各漏掉一项；有利不等于这些特点能消除所有数据相关和分支阻塞。

答案：C。

空操作NOP只是没有有用的运算或访存效果，CPU仍须取到该指令并推进执行位置。例如PC要转到下一条指令，IR也要接收当前指令，故“任何寄存器的内容都不会改变”过于绝对，C错误。A中题设排除Cache和预取，取指至少要访问一次内存，因此正确。B中指令周期由若干CPU时钟周期组成，不会短于一个时钟周期，因此正确。D中机器开中断，CPU在每条指令结束时可能检测到可响应的外部中断，因而可能转入服务程序，也正确。“可能被打断”并不表示每条指令执行完都必定发生中断。

答案：C。

总线按用途分地址线、数据线和控制线。数据线传输的是一次总线事务的数据内容，所以从内存取指时可传指令，读写内存或设备时可传操作数，中断响应时也可传中断类型号，A、B、D都可能。握手信号表示“请求已收到”“数据已就绪”等事务控制状态，需要让双方协同完成传输，属于控制信号，应走控制线，因此选C。中断类型号与中断请求信号要区分：前者是说明哪个中断的编码数据，后者是提出中断请求的控制信号。同样，存放在寄存器中的状态字属于可读取的数据，也不能与专用握手线混为一谈。

答案：D。

响应优先级决定多个请求同时出现时先响应谁；处理优先级决定服务某中断时，哪些中断允许嵌套进入。这里正在处理L1，应允许处理优先级比它高的L4、L0、L2，而屏蔽自身L1及比它低的L3。题设Mi=1表示屏蔽，按M4、M3、M2、M1、M0逐位写出：0、1、0、1、0，即01010，选D。A会屏蔽多个应允许的高优先级中断；B未正确屏蔽自身L1；C虽然M1=1屏蔽了自身，却把M3置0放行低优先级L3，同时把M0置1屏蔽高优先级L0，仍不符合嵌套条件。计算屏蔽字时必须使用题目给出的“处理优先级”顺序，不能直接照抄硬件响应优先级。

答案：C。

主频50MHz表示每秒可运行 $50\times10^6$ 个时钟周期。查询一次至少消耗500周期，每秒至少查询200次，所以设备查询每秒至少占用 $500\times200=100000$ 周期。占CPU总时间的比例可直接用周期数之比：$100000/(50\times10^6)=0.002=0.20\%$，选C。也可先算每次查询 $500/(50\times10^6)=10\,\mu s$，每秒总耗时2ms，仍为0.20%。A、B低估了必须的查询开销，D高于算出的最小值。注意小数0.002转换成百分数要乘100，不能写成0.002%。

答案：B。

高响应比优先的响应比为 $R=(等待时间+服务时间)/服务时间=1+等待时间/服务时间$。当等待时间相同时，服务时间越短，R越大，所以偏向短任务；长任务虽初始响应比可能较小，但等待越久R越大，能逐渐获得执行机会，避免一直被新到的短任务压住，因此B同时满足两个要求。A的先来先服务主要按到达顺序，不体现短任务优先；C的时间片轮转使任务轮流使用CPU，但也不按短任务优先排序；D的非抢占式短任务优先只比较服务时间，连续到来的短任务可能使长任务饥饿。题目要求两种性质同时成立，不能只抓其中一种。

答案：A。

用户态执行普通应用代码，内核态才能操作关键系统资源和执行特权操作。命令解释程序如Shell负责读取用户命令、组织参数并请求操作系统服务，通常作为用户态程序运行，所以选A。它调用系统调用时CPU会暂时进入内核，并不意味着解释程序整体运行在内核态。B的缺页处理要修改页表、调入页面，C的进程调度要保存和恢复运行现场，D的时钟中断处理要维护系统计时及调度信息，都是内核的工作。判断时应看该程序承担的职责，而不是它能否发起系统调用；大多数用户程序都能通过系统调用获得服务。

答案：D。

同一进程的线程共享进程所拥有的资源，因此代码段、全局变量和打开文件通常可由各线程共同使用，A、B、C都是可共享项。每个线程还需独立的执行现场，包括PC、通用寄存器、栈及栈指针。栈记录该线程的函数调用、局部变量和返回地址；若多个线程使用同一个当前栈指针，彼此调用和返回就会破坏现场，因此D不能作为共同的线程执行状态共享。这里“不能共享栈指针”是说各线程有各自的栈指针值；在同一地址空间中，线程仍可能通过明确传递地址访问另一线程栈上的数据，但这不改变各自栈和栈指针独立的事实。

答案：B。

磁盘I/O先由用户程序通过系统调用提出请求，系统调用处理程序检查参数、权限等，并把操作交给对应设备的驱动。驱动程序设置控制器寄存器、启动磁盘读写，设备完成或发生需要处理的事件后，再通过中断进入中断处理程序，记录结果并唤醒等待进程。按启动到完成的顺序为“用户程序→系统调用处理程序→设备驱动程序→中断处理程序”，选B。A把完成时的中断处理放在启动设备之前；C、D都让用户程序在进入系统调用处理之前直接调用驱动，越过了用户态与内核态的接口。设备驱动与中断处理可能合作，但职责和发生顺序不同。

答案：D。

安全性检查是假设依次让某进程获得全部尚需资源并完成，再把其已分配资源释放到Work；每一类资源都必须分别够用。初始Work=(0,2,1)，仅P1的Need=(0,0,1)满足。P1完成后释放(2,0,0)，Work=(2,2,1)，此时仅P4的Need=(2,0,0)可满足；P4再释放(0,0,1)，Work=(2,2,2)。P2尚需(1,3,2)，P3尚需(1,3,1)，二者均缺R2：需要3个而只有2个，因此不能把所有进程排成安全序列。A、B在P1后直接安排P2或P3已失败；C到P3也失败，故选D。“不安全”表示无法保证全部完成，并不等同于当前已发生死锁。

答案：D。

缺页表示要访问的虚拟页当前不在主存，CPU产生缺页异常，操作系统需要补上该映射。首先需取得一个页框，可能从空闲列表分配，也可能通过页面置换腾出，因此III可能发生。为把所需页的内容放入该页框，通常要从磁盘等后备存储读入，有脏页被换出时还可能写磁盘，II可能发生。调入后要把页框号、有效位等写入页表，必要时更新TLB，因此I也可能发生。三项都可能，选D。A漏掉页框分配，B只考虑磁盘，C只考虑页框。题目问的是“可能”，不要求任何一种缺页场景都机械地执行同一套磁盘操作。

答案：A。

抖动是进程频繁缺页、系统大部分时间忙于页面换入换出而难以有效计算的状态，常见原因是多道程序过多，每个进程实际获得的页框不足以容纳工作集。撤销部分进程可以释放主存，使其余进程获得更多页框，减少缺页，I有效。增大磁盘交换区只是增加后备存储容量，并没有增加主存页框，不能解决工作集装不下的问题，II无效。提高用户进程优先级只能改变调度机会，不能补足驻留页面，也可能让缺页更集中的进程运行，III无效。仅I成立，选A；B、C未解决内存不足，D还包含错误的II。

答案：C。

本题要区分编译、链接和装载形成的地址。编辑阶段产生源代码；编译把各源模块转换为目标模块，模块中的地址通常是相对该模块起点的相对地址。链接器把多个目标模块、库函数合为可执行程序，确定各段在统一程序地址空间中的位置，并调整跨模块引用，形成完整的逻辑地址空间，因此选C。装载阶段把程序放入内存或建立运行映射；虚拟存储系统中CPU随后发出的逻辑地址由地址变换机构换成物理地址。A尚未生成机器程序，B只完成单个模块的翻译，D是加载已有程序。不要把运行时地址转换与链接阶段的地址形成混为一谈。

答案：B。

记磁盘读入T=100μs、缓冲区送用户区M=50μs、分析C=50μs。单缓冲时，缓冲区被读入或传送占用，下一块读入必须等上一块传送结束；但上一块在用户区分析时，下一块可读入。由于T≥C，每块推进节拍为T+M=150μs，最后一块传送后还要分析50μs，总计 $10\times150+50=1550\,\mu s$。双缓冲时，读入一块可与另一块的传送及分析重叠，且 $T=M+C=100\,\mu s$，10块读入用1000μs，最后传送、分析再用100μs，总计1100μs。故选B；A漏了尾部工作，C未体现双缓冲重叠，D把各阶段完全串行相加。

答案：C。

加1与减1各包含load、算术、store三条指令，整个操作不是原子的。若一方三条全部完成后另一方再做，x先变2再变1，或先变0再变1，最终均为1。若两方都先load到初值1，各自在寄存器中得到R1=2、R2=0，最终值取决于谁最后store：P1最后写回得2，P2最后写回得0。因此可能结果恰为0、1、2，选C。A的−1或3要求某一加减操作额外多执行一次，本题不会出现；B假定了整个加减原子执行，忽略交错；D多列了不可能的−1。丢失更新发生在两个进程都基于同一个旧值进行运算时。

答案：A。

TCP/IP网络层的核心协议是IP，提供尽力而为的数据报传送。发送前不先建立网络层连接，各分组带目的IP地址，路由器独立选择转发方向，因此是无连接。IP也不保证数据报必定到达、按序到达或不重复；需要可靠传输时由TCP等上层机制补充，所以是不可靠服务，选A。B虽然无连接正确，但把可靠性加给了IP；C、D的“虚电路”属于先建立连接再沿既定逻辑通路传输的网络服务，不是IP采用的模式。“不可靠”是指协议不提供可靠交付承诺，不是说IP完全不做首部校验或只能传错数据。

答案：B。

bps是每秒传送的比特数，波特率是每秒发送的码元数，两者只有每码元携带1bit时才相等。4相位调制有4种可区分状态，每个码元可编码 $\log_2 4=2$ bit，因此 $码元速率=比特率/每码元比特数=2400/2=1200$ Baud，选B。A的600相当于误认为每码元携带4bit，而4bit需要16种状态；C的4800把关系反过来乘2，D的9600又错误地按相位数乘4。识别调制状态数后应先取以2为底的对数，再换算速率，不能直接用状态数充当每码元的比特数。

答案：B。

选择重传SR为各帧单独维护确认状态和超时计时器。某帧超时，只重传该帧；已被正确确认的帧无需随它重传。题中1号帧已确认，0号和2号依次超时，故分别重传0、2，共2帧，选B。3号虽尚未收到确认，但题目没有说它超时，不能提前把它也算为必需重传。A漏掉一个超时帧，C多计3号，D连已确认的1号也重传。若是后退N帧GBN，重传范围可能包含从最早未确认帧起的后续帧；本题明说SR，不能套用GBN的回退逻辑。

答案：D。

无线局域网中发送方难以在发送的同时可靠地检测碰撞，CSMA/CA通过避免碰撞并由接收方在正确接收数据帧后返回ACK，来帮助发送方判断该次传送是否成功，符合题意，选D。A的CSMA只是先侦听载波再竞争发送，并不因此规定逐帧确认；B的CDMA是码分多址方法，用不同码区分用户，也不是本题所问的确认机制；C的CSMA/CD依靠发送端碰撞检测处理冲突，传统以太网MAC不对正确收到的每一帧发送确认。这里判断的是MAC层确认，不能把TCP确认等上层机制当成以太网MAC本身的服务。

答案：D。

图中两个远端子网是192.168.2.0/25和192.168.2.128/25，分别覆盖最后一字节0～127和128～255。它们具有相同的前24位，可用一条192.168.2.0/24聚合路由同时覆盖，掩码为255.255.255.0。R1要把分组送给直连网段上的R2，下一跳应是R2面向R1的接口192.168.1.2，而不是R1自己的192.168.1.1，因此选D。A同时用了过窄的/25掩码和自身地址；B掩码正确但下一跳错误；C下一跳正确却只能覆盖前一半子网。路由表下一跳填写相邻路由器的可达接口地址，不是最终目的主机或本机接口地址。

答案：C。

前缀/30表示32位地址中有30位网络位，留下2位主机位，共 $2^2=4$ 个地址。子网192.168.4.0/30中的四个地址依次是.0、.1、.2、.3，其中主机位全0的.0是网络地址，全1的.3是该子网的定向广播地址；可分配给普通主机的是.1和.2。目的地址.3代表向本子网全部主机广播，因此最多由2台主机接收，选C。A把广播地址误认为无接收者，B只算一个接收者，D把网络地址和广播地址也当成可配置的主机。题目只问子网内最多能接收的主机数，不是在问路由器是否允许跨网广播。

答案：C。

TCP三次握手的第二步既要接受对方请求又要提出自己的连接请求，因此乙的报文应为SYN=1、ACK=1。SYN虽不带普通应用数据，也占用一个序号；甲的初始seq=11220，所以乙确认的下一个序号应为ack=11221。乙自己的seq由乙独立选择，不必等于甲的初始序号，也可以恰好选11221，故C是一种可能。A、D没有设置SYN和ACK，不能完成第二次握手；B虽然标志正确，但ack=11220没有确认甲的SYN。注意seq描述本方向发送序列，ack确认相反方向，不能因为两字段在选项C中相等就认为它们具有相同含义。

答案：B。

TCP按字节编号，一个段的序号是该段第一个数据字节的序号。第三段seq=900，第二段长400B，因此第二段起始序号 $900-400=500$；第一段又长300B，起始序号为200。各段字节范围分别为200～499、500～899、900～1399。乙收到第一、第三段，但500开始的连续数据缺失；累计确认只能确认已连续收到的前缀，所以ack=500，表示下一步期望500号字节，选B。A把长度300当作确认号，C的1200既不对应缺口也不对应连续边界，D的1400只有第二段也收到时才能累计确认。乱序收到第三段不会越过中间缺口更新累计确认。

（1）由压缩数组恢复邻接矩阵。 6个顶点的严格上三角部分有 $6\times5/2=15$ 项，正好等于数组长度，所以数组只存对角线以上的元素。按行依次填入A[0][1]到A[0][5]、A[1][2]到A[1][5]等位置。对角线按自身距离记0；下三角没有边，记∞，∞也表示上三角中无边的情形：

$$A=\begin{pmatrix} 0&4&6&\infty&\infty&\infty\\ \infty&0&5&\infty&\infty&\infty\\ \infty&\infty&0&4&3&\infty\\ \infty&\infty&\infty&0&\infty&3\\ \infty&\infty&\infty&\infty&0&3\\ \infty&\infty&\infty&\infty&\infty&0 \end{pmatrix}.$$

（2）由矩阵画图。 每个有限且非对角的A[i][j]对应有向边i→j，权值为A[i][j]，因此共有7条边：

（3）求关键路径。 将顶点看作事件、边看作活动。事件发生需等全部前驱活动结束，所以最早时间取最大值：$ve(j)=\max\{ve(i)+w(i,j)\}$。从ve(0)=0开始，ve(1)=4，$ve(2)=\max(6,4+5)=9$，ve(3)=13，ve(4)=12，$ve(5)=\max(13+3,12+3)=16$。总工期为16。

最迟时间从终点vl(5)=16逆推，$vl(i)=\min\{vl(j)-w(i,j)\}$，结果如下：

活动i→j的最早开始e=ve(i)，最迟开始l=vl(j)−w；二者相等就是关键活动。

所以关键路径为 $0\to1\to2\to3\to5$，长度 $4+5+4+3=16$。关键路径求的是决定工期的最长活动路径，不能把0→2→4→5这样的较短路径当作答案。

（1）设计思想。 两个长度均为n的升序序列合并后有2n项，题目规定中位数位置为 $\lceil2n/2\rceil=n$，即取第n小的数，而不是对中间两项求平均。若真的合并要O(n)时间和可能的额外数组，可以改为二分寻找“左侧恰有n项”的划分。

设A左侧取前i项，B左侧取前j=n−i项。由于各自已升序，只需比较四个边界：A左侧最后一项al、右侧第一项ar，B对应bl、br。若 $al\le br$ 且 $bl\le ar$，左侧所有项都不大于右侧所有项，左侧最大值max(al,bl)就是第n小。若al>br，说明A取多了，减小i；否则bl>ar，说明A取少了，增大i。i的候选范围0～n可以二分。

（2）C实现。 空的左部分用负无穷、空的右部分用正无穷处理。使用long long哨兵，使int数组即使含INT_MIN或INT_MAX也能正确比较，不修改输入。

#include <limits.h>

/* 前提：a、b均按升序排列，各有n项，n >= 1。 */
int median_two(const int a[], const int b[], int n) {
    int lo = 0, hi = n;
    while (lo <= hi) {
        int i = lo + (hi - lo) / 2;
        int j = n - i;
        long long al = i ? a[i - 1] : LLONG_MIN;
        long long ar = i < n ? a[i] : LLONG_MAX;
        long long bl = j ? b[j - 1] : LLONG_MIN;
        long long br = j < n ? b[j] : LLONG_MAX;
        if (al <= br && bl <= ar)
            return (int)(al > bl ? al : bl);
        if (al > br) hi = i - 1; /* A左侧取多了 */
        else lo = i + 1;        /* A左侧取少了 */
    }
    return 0; /* 满足前提时不会执行到此处 */
}

例如A=(11,13,15,17,19)、B=(2,4,6,8,20)，n=5。先试i=2、j=3，有al=13>br=8，应减小i；最终i=1、j=4，此时al=11≤br=20、bl=8≤ar=13，中位数为max(11,8)=11。

正确性与边界。 每次保留能满足边界顺序的划分范围：al>br时进一步增加i只会使al更大、br更小，因此必须向左；bl>ar时同理必须向右。找到合法划分时左侧恰有n项，最大项的秩为n，结论成立。n=1时返回两项中较小者；重复元素允许等号，某一数组左部分为空或全满也由哨兵处理。

（3）复杂度。 二分范围每次约减半，每轮仅常数次比较，时间 $O(\log n)$；只使用固定数量的变量，额外空间 $O(1)$。

先区分位模式与数值。 8位寄存器只有256种位模式。无符号数范围0～255，补码有符号数范围−128～127；相同位模式按不同类型解释，数值可能不同。按题设8位机器模型，转换为有符号变量时保留低8位，不套用实际C实现的更宽int规则。

（1）R1、R5、R6。 x=134，$134=128+6$，8位模式为10000110，故R1=86H。R5存z1=x−y，$134-246=-112$，保留8位等价于模256：$-112+256=144=90\mathrm H$。R6存z2=x+y，$134+246=380$，低8位为 $380-256=124=7C\mathrm H$。答案依次为86H、90H、7CH。

（2）m和k1的十进制值。 m保留86H，最高位为1，补码数值 $134-256=-122$；n保留F6H，数值 $246-256=-10$。因此 $k1=m-n=-122-(-10)=-112$，在8位有符号范围内，位模式90H。

（3）共用加法器。 可以。无符号加法与补码加法都做同一组二进制位相加并保存低8位；减法都可变为 $a+\overline b+1$。辅助电路用控制信号选择b是否取反以及最低位进位是否置1，同一加法器即可完成四种操作。差别在于结果的解释和标志判定：无符号运算关注进位/借位，带符号运算关注是否超出补码范围。

（4）带符号溢出。 加法中“同号相加得到异号”才溢出；减法中“异号相减且结果符号不同于被减数”才溢出。也可用符号位进位与符号位输出进位异或判断，即 $OF=C_{进入符号位}\oplus C_{离开符号位}$。

k2的真值−132小于−128，两负数相加却产生正的保存结果，所以只有 int k2=m+n; 这一带符号加减语句溢出。赋值m=x、n=y是位模式的类型解释，不能与加减法溢出混为一谈。

（1）虚拟地址和物理地址。 按字节编址，虚拟空间 $16\mathrm{MB}=2^{24}\mathrm B$，虚拟地址为24位；主存空间 $1\mathrm{MB}=2^{20}\mathrm B$，物理地址为20位。页大小 $4\mathrm{KB}=2^{12}\mathrm B$，页内偏移均为12位，且地址转换时不变。因此虚拟地址23～12位是12位虚页号，11～0位是页内偏移；物理地址19～12位是8位页框号，11～0位仍是页内偏移。

（2）访问Cache的物理地址字段。 每块32B=$2^5$B，需要最低5位选择块内字节；直接映射8行=$2^3$行，再用3位选择行；其余20−5−3=12位是标记：

页内偏移和块内偏移不能混淆：一个4KB页面包含很多32B的Cache块。

（3）001C60H的访问。 将虚拟地址按12位偏移切开，得到虚页号001H和偏移C60H。页表中页1有效位为1，说明页面在主存，页框号04H，所以物理地址为 $(04\mathrm H\ll12)+C60\mathrm H=04C60\mathrm H$。用物理地址拆Cache字段：行号 $\lfloor04C60\mathrm H/32\rfloor\bmod8=3$，标记为 $04C60\mathrm H\gg8=04C\mathrm H$，块内偏移为0。Cache行3虽有效，其标记却为105H，与04CH不同，故Cache未命中。页面在主存和Cache命中是两层不同的判断。

（4）通过TLB判断024BACH。 TLB是页表项的高速缓存，8项、4路组相联意味着共有8/4=2组，需要虚页号的低1位作为组号。该地址的虚页号为024H=36，偏移BACH；组号 $36\bmod2=0$，TLB标记为 $\lfloor36/2\rfloor=18=012\mathrm H$。在组0找到有效位1、标记012H、页框号1FH的项，TLB命中，直接说明所需页面已驻留主存。对应物理地址还可得到1FBACH。题目给出的部分普通页表未列出页36，并不妨碍根据有效TLB项判断。

同步关系。 座位是10个有限资源，取号机及号码队列要互斥访问；营业员没有等待顾客时不能空叫号，顾客没有被叫到时不能开始服务。P操作申请资源或等待事件，V操作归还资源或通知事件。还要按具体号码唤醒顾客，否则用一个公共叫号信号量可能让未被叫到的顾客抢先服务。

设seats=10表示可占用座位数，ticketMutex=1保护取号机和等待队列，waiting=0计数已经入队的顾客。每个新号码t有独立的called[t]，初值0；Q初始为空，按取号顺序保存号码。以下“获取服务”和“为号码t的顾客服务至结束”描述同一次窗口服务。

semaphore seats = 10;
semaphore ticketMutex = 1;
semaphore waiting = 0;
queue Q = empty;
// 每个领取的号码t分配一个called[t]，其初值为0。

顾客 i:
    P(seats);                  // 无空座位时在进入等待区前等待
    P(ticketMutex);
    t = 从取号机获取号码;
    初始化 called[t] = 0;
    Q.enqueue(t);
    V(ticketMutex);
    V(waiting);                // 发布一位可叫号的顾客
    P(called[t]);               // 只能由营业员叫本号码时通过
    V(seats);                  // 起身前往窗口，释放等待座位
    获取服务;

营业员:
    while (true) {
        P(waiting);            // 无顾客时阻塞
        P(ticketMutex);
        t = Q.dequeue();
        V(ticketMutex);
        叫号码 t;
        V(called[t]);
        为号码 t 的顾客服务至结束;
    }

为什么满足要求。 P(seats)保证占用等待座位的顾客不超过10人，离座时V(seats)，服务中的顾客不继续占用等待座位。ticketMutex保证取号及入队不会交错破坏顺序；waiting只在入队后增加，营业员获得它后必有号码可取。即使营业员先V(called[t])而顾客尚未P，该通知也会保留，不会丢失。等待叫号时不持有ticketMutex，不会阻止其他人取号。一个营业员每次完整服务后才进入下一轮，保证窗口一次只服务一个号码。无座位时的等待发生在取号之前，不能把它解释为又占了第11个等待座位。

（1）连续分配及FCB字段。 更适合连续分配。文件一次写入后不可修改，创建时可按其最终长度分配连续磁盘块，不存在以后扩展时找不到相邻空闲块的主要困难。连续块便于顺序读取，定位第i个块只需“起始块号+i”；与链式分配相比不用逐个追踪指针，与索引分配相比不用额外索引块。链式和索引方式适合灵活增长等需求，但本题的不可修改条件削弱了这些优势。连续分配仍可能产生外部碎片，这是其代价，不会使本题理由失效。

FCB至少记录起始磁盘块号和文件长度，长度可用字节数保存；由块大小B计算占用块数 $\lceil文件长度/B\rceil$，并识别末块有效字节。若仅保存占用块数，还需记录末块的有效长度才能知道精确文件大小。

（2）集中存放FCB。 一级目录中的文件名与FCB对应。查找文件时，主要任务是按名称定位FCB；将FCB集中放在目录区域，便于连续扫描或统一建立检索结构，所需磁盘访问较少。若每个FCB跟自己的数据块放在一起，虽然找到它后读取数据方便，但查找一个未知位置的文件名就可能在磁盘多个分散位置移动磁头，开销较大。因此为快速找文件应集中存储FCB。目录负责定位文件，数据块负责存内容，两者的访问需求不同。

（1）解析服务器IP地址和网关MAC地址。 以太网首部依次为目的MAC地址6B、源MAC地址6B、类型2B，共14B。帧中类型字段为 08 00，表示其数据部分承载IPv4分组。因此IPv4首部从帧偏移0EH开始；首字节45H中高4位为版本4，低4位为首部长度5，即首部长为 $5\times4=20$ B。

目的IP地址位于IPv4首部偏移16～19处，对应帧偏移1EH～21H，四个字节为 40 aa 62 20。转换为十进制分别是64、170、98、32，所以Web服务器的IP地址为 64.170.98.32。

帧最前6B为 00 21 27 21 51 ee，即目的MAC地址 00-21-27-21-51-EE。服务器位于外网，主机先把以太网帧交给同一链路上的默认网关，因此这个MAC是默认网关的MAC地址。后6B为本机的MAC地址00-15-C5-C1-5E-28，可用来核对帧头起点。最左边的0000、0010等数值是字节偏移标签，不属于帧内容。

（2）ARP请求。 主机按路由选择默认网关10.2.128.1作为下一跳，再通过 ARP 获取该网关IP地址所对应的MAC地址。请求时尚不知道网关MAC，因此封装ARP请求的以太网帧使用广播目的地址 FF-FF-FF-FF-FF-FF。网关回复后，主机才使用获得的MAC封装当前Web请求。ARP解析的是本链路下一跳的地址，不能跨Internet直接查询远端服务器的MAC地址。

（3）所需RTT数。 本题按页面和5幅图像复用题中这一条持续TCP连接的通常考试模型计算；题目已经把一次请求—响应时间定义为1RTT。持续连接允许后续请求继续使用该连接，非流水线要求在这条连接上收到前一次响应后才发下一次请求。

计时从题中的GET请求发出开始，不再计入建立TCP连接的时间。取得rfc.html需要1RTT；收到页面后才能得到其中5幅JPEG图像的引用，随后逐个请求图像，每幅再用1RTT。因此共需 $1+5=\boxed{6\mathrm{RTT}}$。这里没有另建多个并行连接；“非流水线”描述的是单条连接上的请求顺序，不能单凭这个词推断浏览器在所有场景下都禁止并行连接。

（4）路由转发时改变的IPv4首部字段。 本题采用图中R为私网主机执行NAT的默认模型：主机源IP为10.2.128.100，R的公网侧地址为101.12.123.15。因此源IP字段由10.2.128.100改为 101.12.123.15。路由器每转发一次分组，TTL减1；本帧中TTL为80H=128，转发后为7FH=127。源IP及TTL改变后，还应重新计算或增量更新 IPv4首部校验和。所以本题需修改的IPv4首部字段是 源IP地址、TTL、首部校验和。

本分组的总长度为01EFH=495B，小于图中出口MTU1500B；标志及片偏移字段4000H表明DF=1，所以本次没有分片，不需修改总长度、片偏移或目的IP。NAT引起的TCP校验和等变化属于TCP首部，出口以太网MAC地址及CRC变化属于链路层，均不计入本问要求的IPv4首部字段。NAT源地址变化依赖这里采用的NAT转发模型；普通IPv4路由转发的基本变化是TTL及相应首部校验和。