2017年计算机408真题

答案：B。

每次循环先把i加1，再把新的i加到sum，所以执行t次后i=t，$sum=1+2+\cdots+t=t(t+1)/2$。停止条件为 $t(t+1)/2\ge n$，所需次数约为 $(-1+\sqrt{1+8n})/2$ 向上取整，随√n增长。循环体只有常数次加法和判断，因此时间为 $\Theta(\sqrt n)$，选B。A要求sum按倍数增长才会产生对数次循环；C把sum每轮增加的i误当成固定1；D也没有对应的额外对数工作。虽然i本身每轮只加1，循环条件比较的是累加和sum，关键在于和呈二次增长，而不是看到while就判断O(n)。

答案：C。

逐条判断。I说所有递归改为非递归都“必须”显式用栈，过于绝对：阶乘、简单尾递归等可按规律改成循环，只用少量变量，所以I错。II正确，通常函数调用机制用调用栈保存返回地址、参数及必要现场。III错，入栈次序固定仍可交错进出，例如a、b可先入a即出a再入b，或先入两项再按b、a出，序列不同。IV错，栈只允许在同一端即栈顶压入和弹出；两端都可操作的是双端队列等结构。因此错误项为I、III、IV，选C。A漏两个错误，B、D把正确的II也列为错误。限定“必须”“只要”等绝对词时需要检验反例。

答案：A。

稀疏矩阵大多数元素为0，压缩存储应只记录非零元素及其位置。三元组表用“行号、列号、值”表示每个非零元；十字链表为非零元同时设置行方向和列方向链接，便于按行或列遍历，二者都适合，选A。B、D包含邻接矩阵形式的完整二维存储，需要为大量0保留位置，达不到本题的稀疏压缩目标；C的普通二叉链表主要表示二叉树，没有天然表示矩阵行列关系的这套组织。若非零元数为t，三元组主要空间随t而非总行列乘积增长。压缩不是把0的数值写短一点，而是省去它们占据的大部分存储位置。

答案：B。

先序顺序为根、左、右，中序顺序为左、根、右。对任何结点，只要存在左子树，其中的结点在中序中先于根，在先序中却后于根，两个序列就不可能完全相同。因此每个结点都不能有左子树，非叶结点只能有右子树；此时二者均按根→右孩子→下一级右孩子访问，足以满足，选B。A的全左链恰会使先序和中序方向相反；C只说度为1，但单孩子可能在左侧，不够；D要求双孩子，更必然存在左子树，错误。单结点树没有非叶结点，两个序列都只含根，也符合这一条件。

答案：B。

后序按“左子树、右子树、根”填结点。题图根有左右两条各3结点的支链，所以后序最后f是根；左边3项e、a、c依次填为最底叶e、第三层a、第二层c；右边3项b、d、g依次填为最底叶b、第三层d、第二层g。层次如下：第1层f，第2层c、g，第3层a、d，第4层e、b。因此与a同层的是d，选B。A的c、D的g在第二层，C的f在第一层。不要按后序中相邻位置判断是否同层，遍历次序描述访问先后，层次描述到根的路径长度，必须结合给定树形还原。

答案：D。

哈夫曼码是前缀码，没有一个完整字符码是另一个的前缀，因此从左起累积比特，一旦匹配某个完整码字就输出该字符并重新开始。将题给串切分为 0100 | 011 | 001 | 001 | 011 | 11 | 0101，分别对应a、f、e、e、f、g、d，得到afeefgd，选D。A、B、C按所给字符编码重新拼接，都会与原比特串不符。不要固定每4位截取，因为b、g是2位，e、f是3位，a、c、d、h才是4位；变长码的边界由前缀性质唯一确定。切分后的码长4+3+3+3+3+2+4=22，与原串总位数一致，可用作检查。

答案：B。

无向图每条边给两个端点各贡献1度，故全部顶点度数和为2e=32。已有3个4度和4个3度顶点，共7个，贡献3×4+4×3=24，还需8度。其他顶点度小于3，即至多2，为使顶点数最少应尽量取2度，因此至少再要8/2=4个，总计11，选B。这个下界也可实现：先用一个7顶点的4正则简单图，从中删两条互不相邻边，使4个顶点变3度；再把其中4条边各细分出一个2度新顶点，得到3个4度、4个3度、4个2度，共16条边。A的10个不足补8度，C、D虽可能成立却不是最少。度为0或1只会增加所需顶点数。

答案：A。

折半查找每个结点对应一个当前有序区间，选中点后左右子区间元素数差至多1；若长度为偶数，还必须始终采用相同的上取整或下取整中点规则。A有10个结点，根的左、右子树分别5、4个，可用上取中点：长度10取第6项；左区5项各分为2、2，右区4项分为2、1；所有长度2的区间都取后一个为根，留下左孩子，完全吻合。B中的2结点子树有的仅左孩子、有的仅右孩子，规则矛盾；C的左右4项区间内部切分方向相反；D根需下取中点，却在2项子区间采用上取，仍不一致。因此选A。仅检查树“看起来平衡”不足以证明是折半查找判定树。

答案：B。

关系数据库索引需在大量外存数据中按关键字定位，还常做范围查询。B+树每个结点容纳多个关键字，分支多、树高小，减少磁盘页访问；全部记录定位信息集中在叶层，叶结点顺序链接，方便有序和范围扫描，所以B最合适。A词法分析主要识别字符序列与词法模式，常用有限自动机；C路由表常要最长前缀匹配，不能简单视为普通关键字大小查找；D空闲块管理常用位图或空闲链，核心需求也不是记录的有序索引。其他场景可能设计树结构，但这不改变B+树与数据库索引访问需求的直接对应。

答案：B。

典型数组归并排序把序列递归分为两半并线性合并，时间O(nlogn)；直接插入排序最坏要对大量元素逐个比较和移动，时间O(n²)，对大规模一般无序数据，归并效率更高，所以III可以成立。I关于程序更短没有普遍依据，简单插入排序的代码反而通常更短；II也不成立，数组归并一般需要O(n)辅助数组，插入排序只需O(1)额外空间。因此仅III是合理选择，选B；A、C错误含II，D错误含I。“可能的理由”不表示归并对所有输入都更快，例如小规模或近有序数据插入排序也有优势，要避免把复杂度比较泛化成绝对耗时保证。

答案：D。

希尔排序反复访问相隔某增量的元素，堆排序依靠数组下标i、2i、2i+1快速定位父子结点；数组随机访问O(1)，换成普通链表后这些远距定位往往需要沿链接遍历，时间效率会下降，所以IV、V符合。插入排序可顺序找插入点并修改链接，选择排序可顺序扫描最值，起泡排序比较相邻元素，三者主要所需访问都能沿链完成，不会因失去随机下标直接产生希尔、堆那样的额外定位代价。故选D。A、B、C都含不属于这一关键差别的I、II或III。链表减少了数组元素移动，但它并不适合依赖任意下标定位的所有排序算法。

答案：C。

执行时间公式为 $T=指令数\times CPI/主频$。相同ISA上运行同一个基准程序，按题意指令数N相同，所以 $T_1/T_2=(N\times2/1.5)/(N\times1/1.2)=2\times1.2/1.5=1.6$，选C。M1频率较高，但每条指令平均用2周期，相比M2的1周期抵消了频率优势，运行反而更慢。A的0.4相当于把CPI关系倒置；B的0.625是正确比值的倒数；D的2.5未正确结合两项参数。不能仅比较1.5GHz和1.2GHz就得出M1快，性能取决于主频和每条指令实际周期数的组合。

答案：C。

4个8位芯片配合32位总线，一次最多读一个按4B对齐的32位单元。double占8B，起址804001AH最后两位为10，距其所属对齐单元起点8040018H偏移2B，因此8字节范围为1AH～21H，跨三个对齐单元：18H～1BH取末2B，1CH～1FH取4B，20H～23H取首2B。需要3个存储周期，选C。A的1次总线容量仅4B，不够8B；B的2次仅适用于起点已按4B对齐而不跨第三单元；D的4次没有利用每次可同时读4B。交叉编址提高连续数据读取能力，并不能让一个未对齐8B对象在两次固定字单元读取中完整覆盖。

答案：A。

空间局部性指访问某地址后，很可能访问其附近地址。内层循环j从0逐步增到i，依次读a[0]、a[1]……a[i]，数组相邻元素在内存中相邻，所以具有空间局部性。时间局部性指近期访问过的位置会再次访问；外层i每增1，就再次从a[0]开始乘到新的末项，a[0]等前面的元素短时间内被反复读，所以也有时间局部性，选A。B忽略跨外层的重复访问，C忽略内层的连续地址，D两者都遗漏。局部性描述访问模式，不要求每个元素都被重复同样次数；例如a[9]只读一次，也不妨碍整个程序对数组呈现上述两种性质。

答案：D。

一维数组第i项地址可写为 $基址+i\times元素长度$。变址寻址把固定形式地址与变址寄存器中的变化偏移相加，通过每轮增加一个元素长度，就能依次访问各项，最符合数组下标遍历，选D。A相对寻址通常以PC为基准形成地址，主要适合转移目标等，不直接对应数组基址；B寄存器寻址直接把寄存器内容当作操作数，不是从数组内存取值；C直接寻址把访问地址写在指令中，若数组下标改变则不方便用同一条指令遍历。下标本身未必等于字节偏移，按字节编址时必须乘上每元素的字节数再参与地址计算。

答案：A。

三地址指令的地址字段共3×6=18位，29种操作至少需要 $\lceil\log_2 29\rceil=5$ 位基本操作码，即编码至少23位。按字节组织固定指令，取整到3B为24位，A是最短可行选项。还要验证二地址指令能否装下：用24位时基本操作码有6位，共64个编码，分29个给三地址，剩35个前缀可把第三地址的6位扩展为操作码，提供35×64=2240种二地址操作，足以容纳107条。因此不能错误地把29+107先合并再给所有指令统一操作码，忽略地址数减少后可扩展的空间。B、C、D均比24位更长，不是所求最少长度。

答案：C。

超标量在一个时钟周期内发射多条指令，并配备多个执行通路，让不相互依赖的指令并行执行，II正确。结合动态调度，可以根据操作数是否就绪把独立指令安排到可用部件，减少因个别指令等待造成的空闲，III正确。I所说缩短单个流水线功能段时间不是超标量的定义；把阶段进一步细分、提高时钟频率更接近超流水技术，I错误。因此仅II、III成立，选C。A漏III，B、D错误加入I。多发射并不意味着所有相邻指令都能同时执行，仍受到数据依赖、分支、可用执行部件等约束，需要硬件和调度共同处理。

答案：B。

主存MM通过地址选择单元；微程序控制器中的控制存储器CS同样以微地址访问，微程序计数器或下一地址形成逻辑确定要读哪条微指令，并非用内容联想匹配，因此B错误。A按通常系统结构把主存置于CPU之外、控存置于控制器内部，正确；C中主存保存程序指令与数据，控存保存控制CPU操作的微指令，正确；D描述主存可由RAM和ROM实现、常规控存使用ROM保存微程序，也符合题设模型。可写控存是实现上的扩展，但本题的核心差别不在它是否可更新，而在访问方式。不要把“根据指令操作码找微程序入口”误认为控存本身按内容访问。

答案：A。

按组成划分，数据通路负责数据存储、传送和处理，控制部件负责生成选择、读写、运算类型等控制信号来驱动通路。A把生成信号的控制部件列入数据通路，错误。B的ALU执行算术逻辑运算，属于通路；C的寄存器组保存操作数与结果，取指部件读取指令，也属于通路；D中组合电路进行译码选择和运算，时序电路如寄存器与流水寄存器保存跨周期状态，两类电路共同组成通路，正确。这里说的是概念上的功能划分，即使控制电路和通路物理上都集成在同一CPU芯片中，也不能因此视为同一个功能部分。

答案：D。

PCI Express使用点到点高速串行链路，一条lane有独立的收发通道；×16表示聚合16条串行lane增加吞吐量，而不是传统意义上由16根数据线同步并行传一个16位字，所以D错误。A正确，CPU附近的处理器或存储互连通常要满足较高带宽和较低延迟；B正确，存储器总线可先给地址再突发传多个连续数据；C正确，不同层级总线之间用桥接器衔接，完成时序和协议转换。多条串行链路确实能并发搬运数据，但“多lane并发”与传统并行总线的编码和同步方式不同，不能仅因数字×16就把PCIe归为并行总线。

答案：D。

I/O端口是CPU可读写的设备接口寄存器，例如数据、状态和控制端口。IN、OUT等I/O指令通常把数据在CPU通用寄存器与I/O端口之间传送：输入读端口到寄存器，输出写寄存器到端口，所以选D。A的设备与端口之间传送由设备接口自身完成，不是CPU执行I/O指令的两个直接端点；B跳过了接口端口，误以为CPU直接面对设备内部；C两个端口之间也不是典型IN/OUT的直接传输。端口是软件可见的接口位置，实际磁盘、键盘等设备的数据还需经控制器到达该位置，分清这一层关系即可。

答案：B。

多重中断要求在处理一个中断期间，允许更高处理优先级的请求再次进入，形成嵌套。因此入口保护现场等阶段可先关中断，但在允许嵌套的阶段必须重新开中断，B把整个处理期间都说成关中断，错误。A正确，外部中断通常在当前指令完成的边界响应，避免破坏一条指令的执行；C正确，设备请求产生时刻不由当前指令是否正在执行决定；D正确，CPU通过检测/采样请求信号判断是否有可响应中断。请求产生与CPU实际响应可能有时间间隔。允许嵌套也不代表任何低优先级中断都能抢占，应配合屏蔽设置区分优先级。

答案：D。

只在t=2这一调度时刻判断已到达作业。此时可选J1（0到达、运行3）、J2（1到达、运行3）、J3（1到达、运行2）；J4虽仅运行1，但要t=3才到，不能提前调度。先来先服务按到达先后，选最早的J1；短作业优先在当前候选中按运行时间，选2单位的J3，组合J1、J3，选D。A、C把FCFS首选写成J2，遗漏已更早到达的J1；B、C的SJF选择J4，又预支了未来作业。题目说系统t=2才开始调度，所以不能另假设J1早在t=0已进入运行并从候选中移除。

答案：C。

用户程序先按调用约定把系统调用号、参数放到寄存器、栈或约定内存位置，即③；再执行trap指令，保存必要状态并进入内核，即②；内核根据调用号检查参数并运行对应服务程序，即④；处理完成后恢复用户现场、返回用户态，即①。顺序③→②→④→①，选C。A在参数准备之前陷入，还在服务执行前返回，错；B把参数传递放在服务以后，错；D未陷入内核就先执行内核服务，错。普通函数调用与系统调用的差别在于后者通过受控入口切换特权级，参数准备必须在服务程序取用参数之前完成。

答案：B。

原空闲分区为[20K,60K)、[500K,580K)、[1000K,1100K)、[200K,400K)。回收区从60K长140KB，即[60K,200K)，恰与第一个和最后一个在地址上相邻，三者合为[20K,400K)，大小40+140+200=380KB。原4空闲区去掉两个旧项、加入一个合并项，剩3个，另两个大小80KB、100KB。最佳适应按空闲块大小递增重新排序，首项应是500K处80KB，故选B。A数量对但首项按地址而非大小选择，C、D说4个，未正确完成两侧合并。地址相邻需比较区间端点，不能因为链表中相邻或大小接近就合并。

答案：D。

文件系统以簇为分配单位，簇1KB=1024B，文件1026B比一个簇多2B，所以需要 $\lceil1026/1024\rceil=2$ 簇，分配空间2×1024=2048B，选D。A只算有效数据长度，忽略簇不能只分配一小部分；B的1536B相当于按512B扇区向上取整，而分配单位题目已指定为1KB簇；C的1538B混合了有效字节与扇区大小，也不构成完整簇。第二簇只用2B，余1022B是该文件的内部碎片。扇区是设备读写组织单位，簇是文件系统分配单位，两者虽有关系，不能互换。

答案：B。

时间片耗尽只说明轮到该进程占CPU的配额用完，它仍具备执行条件，应从执行态转到就绪态，重新排队等CPU，而非等待I/O或事件的阻塞态，因此B错误。A正确，片越短单位时间切换越频繁，保存恢复上下文等开销更大；C正确，时钟中断驱动系统扣减剩余片长并判断是否到期；D正确，响应需求、管理开销与就绪进程数会影响合适时间片。进程主动等待输入等才通常阻塞。状态判断应区分“缺CPU但能运行”的就绪与“事件没满足即使有CPU也不能继续”的阻塞。

答案：D。

单道系统中一个程序等待I/O时，CPU可能闲置；多道将多个程序放在内存，可在某程序等I/O时切换到另一就绪程序，提升CPU利用率I，并让CPU与各设备更充分重叠，提高I/O利用率IV。资源利用提高后单位时间完成的作业数通常增加，吞吐量III也提升。另一方面需要调度、上下文切换、内存及资源管理，系统开销并不因此更小，II错误。因此I、III、IV正确，选D。A漏IV，B漏III，C含错误II。多道的收益来自重叠和减少资源空闲，不是删除了管理工作，也不保证每一个具体作业的独立完成时间都缩短。

答案：B。

磁盘使用过程应区分建立扇区结构的物理格式化、划分磁盘区域的分区、以及在分区上建立文件系统的逻辑格式化。逻辑格式化需要创建根目录，并初始化空闲块位图或空闲链等管理结构，所以II、IV正确。I的分区是逻辑格式化前的另一项操作，不应合并为逻辑格式化本身；III的扇区校验码等低层格式属于物理层面的存储结构，不由创建文件系统确定。因此选B。A漏空闲块管理，C错含III，D错含I。日常工具可能把多个步骤包装在一个流程中，但题目按操作系统概念考不同阶段的职责。

答案：D。

对每一类用户，五种权限各可能允许或禁止，需五个独立二进制位，例如一个5位串分别指示完全控制、执行、修改、读取、写入。四类用户的权限可能不同，需要为每类各保存这一组，所以总位数4×5=20，选D。A只足够描述一类用户，B把4和5相加没有表示所有组合，C也少于四组完整权限位。不能用“5种权限只需3位编码”来算，因为同一类用户可以同时拥有多种权限，题目要求位串描述授权集合，而不是只从5种互斥状态中选一种；也未给出可利用的权限包含关系来删减位数。

答案：B。

硬链接是两个目录名指向同一个文件索引结点inode，文件数据和属性共享，II正确。两个进程分别独立open这两个名字，各自文件描述符是其用户打开文件表的下标，指向自己的表项，III正确。每次独立打开建立相应的打开状态，其中读写偏移分别维护；一方seek或读写前移，不要求另一方的偏移同时变化，所以I错误。故选B。A漏II，C、D错含I。共享inode与共享“打开文件描述”不同：若通过dup或fork继承同一个打开描述，偏移可能共享；本题明确两个进程分别打开硬链接，不能套用继承同一打开状态的情形。

答案：B。

DMA先由CPU或驱动设置传送的内存地址、方向、块长度等，并启动磁盘，即②；设备与DMA控制器随后直接把一块数据放入内存缓冲区，即③；传送完成，DMA控制器发结束中断请求通知CPU，即①；CPU响应后运行完成服务程序检查状态、唤醒等待者等，即④。因此②→③→①→④，选B。A在初始化之前先传数据，C未传块就先报完成，D让完成请求发生在启动之前，都倒置了因果顺序。DMA期间CPU可能做其他工作，完成时才需要处理通知，不能把“CPU不逐字搬数据”理解为无需初始化或无需结束中断。

答案：A。

OSI共有7层，排除应用层和物理层后，尚有表示层、会话层、运输层、网络层、数据链路层5层。每层增加20B，附加开销合计5×20=100B，实际传送500B，其中有用应用数据400B，因此效率 $400/(400+100)=0.8=80\%$，选A。B的83%左右相当于只算4层80B，C的87%左右相当于只算3层60B，D的91%左右相当于只算2层40B，均漏层。题中数据无拆分，所以每层只对这一份PDU增加一次开销；不要把物理层也算一个20B头，也不要用有用数据除以附加开销而非总量。

答案：D。

无噪声下奈奎斯特极限 $C_N=2B\log_2 M$，M为信号状态数；有噪声下香农极限 $C_S=B\log_2(1+S/N)$。30dB对应线性S/N=10³=1000，要求 $2B\log_2M\ge B\log_2(1001)$，消去正带宽B得 $M^2\ge1001$，即M≥√1001≈31.64，最小整数32，选D。A、B、C的4、8、16平方均不足1001。不要把30dB直接当线性信噪比，也不能只用一个公式忽略“无噪声极限不少于有噪声极限”的比较条件。因为同一带宽，两公式中的B会消去，无需另外知道带宽数值。

答案：B。

H向分配系统发送的802.11帧为To DS=1、From DS=0。地址1标明当前无线链路接收者，即AP的MAC末字节9b；地址2是无线发送者H，末字节9a；地址3保留接入有线网络后该帧的链路目的，即默认网关R，末字节9c。因此依次9b、9a、9c，对应B。A交换了无线发送和接收方，C把R误作无线发送者，D既把H放成接收者又把R放成发送者。AP是这一步无线跳的接收方，却并非该IP分组通往Internet的路由网关；802.11用多个地址同时表达当前无线跳与分配系统端点，不能照搬只含两个地址的以太网帧头次序。

答案：A。

0.0.0.0表示尚未获知或配置自身IP地址的发送主机，可在初始化等阶段作为源地址，普通IP分组不能以它作为实际目的主机，因此A符合。B的127.0.0.1是本机回环地址，可在本机内作源和目的，只是不在外网转发；C的200.10.10.3是普通单播地址，可表示源主机或目的主机；D的255.255.255.255是受限广播，可作目的地址，却不能作为正常源地址，方向正好相反。题目判断的是IP分组地址字段用途，不是路由表中默认路由0.0.0.0/0的网络前缀；一个看似相同的数字串在不同位置承担的含义不同。

答案：D。

RIP用UDP报文直接承载路由更新，通常使用UDP端口520；OSPF不经TCP或UDP，直接作为IP载荷，由IP协议字段识别；BGP在对等路由器之间建立TCP连接，使用TCP端口179可靠交换路由信息。所以直接封装依次为UDP、IP、TCP，选D。A、B先把RIP写成TCP已错，C虽RIP为UDP，却把OSPF写成TCP、BGP写成IP。三者最终都要经IP网络传送，但题目问“直接封装”的紧邻下层：RIP的外面先是UDP，BGP先是TCP，不能因最终都经IP就把答案全部归成IP。

答案：C。

原前缀/16留下16位主机部分。要划128个等规模子网，需要借 $\log_2 128=7$ 位标识子网，前缀变为16+7=23，剩余主机位32−23=9。每子网共有2⁹=512地址，普通IPv4子网要扣除主机位全0的网络地址和全1的广播地址，可分配512−2=510个，选C。D的512漏扣特殊地址；A的254与B的256是按8位主机位算的，相当于借8位划256个子网，不符合128等分。这里不需把全0、全1子网整体再删掉，只对各子网内部的网络与广播地址作通常扣除。

答案：A。

本题采用经典慢开始的考试默认模型：连接建立成功时拥塞窗口 cwnd=1MSS=1KB；传输过程中没有丢包，慢开始阈值不使窗口在达到32KB之前提前转入拥塞避免。每经过一个RTT，整轮数据得到确认，拥塞窗口约翻倍。

因此拥塞窗口依次为：

发送窗口取拥塞窗口与接收窗口的较小者。乙有64KB接收缓存，在这五轮中不会限制目标32KB窗口：即使应用层暂未取走数据，前五轮累计接收1+2+4+8+16=31KB，仍剩33KB，大于32KB。因此至少经过5个RTT，即5×5ms=25ms，选A。

B的30ms多算了一轮，常见原因是把已经完成的连接建立过程又加进来；C、D把每RTT的窗口增长当成线性增加，或又叠加建连时间。计时起点是“连接建立成功”，所以不再加握手耗时。这里明确采用初始1MSS、无丢包和连续慢开始五轮的约定；若讨论另有初始窗口或门限参数的实现，应按其参数重新计算。

答案：C。

FTP用两个TCP连接分担命令与数据。控制连接由客户端连接服务器的21端口，通常在整个登录会话中保持，所以B、D正确。数据连接用于文件等数据传送，一次传输结束后关闭，下一次可以重新建立，A正确。主动方式中服务器从自己的20端口连接到客户端指定的数据端口，不是连接“客户端TCP20端口”；被动方式还会使用服务器另行告知的端口。因此C的客户端20端口说法错误，应选C。端口号归属于具体通信端点，不能只记“FTP数据用20”而不区分20在哪一方以及主动、被动工作方式。

（1）遍历与加括号思想。 表达式树的叶结点是操作数，内部结点是运算符。二元运算的中缀形式必须先输出左子表达式，再输出运算符，再输出右子表达式，因此使用中序遍历。但裸中序会失去树的计算次序，例如先加后乘会错误输出为a+b*c。

对每个非根、非叶结点，在其整棵子树输出前后加一对括号，使该子表达式作为一个整体参与父结点运算。叶结点不需括号，根也不需最外层括号。题图的一元负号仅有右孩子，中序会先输出负号，再输出右子式，得到(-d)或(-(c-d))，无需另设一元遍历规则。

（2）C实现。

#include <stdio.h>

typedef struct node {
    char data[10];       // 操作数或操作符，须为以\0结束的字符串
    struct node *left, *right;
} BTree;

void printExpression(const BTree *p, int isRoot) {
    if (p == NULL) return;
    int leaf = (p->left == NULL && p->right == NULL);
    if (!leaf && !isRoot) putchar('(');
    printExpression(p->left, 0);
    printf("%s", p->data);
    printExpression(p->right, 0);
    if (!leaf && !isRoot) putchar(')');
}

// 对整棵树调用：printExpression(root, 1);

左图左子树输出(a+b)，右子树输出(c*(-d))，根输出两者之间的*，结果为 (a+b)*(c*(-d))；右图左子树(a*b)，右子树(-(c-d))，根为+，结果 (a*b)+(-(c-d))。

正确性与复杂度。 对叶子，直接输出它即为正确表达式。假设左右子树都正确，中序排列与当前运算符结合，而子树括号保证不会被外部优先级重新组合，所以父表达式正确，逐层归纳到根。算法可能有可省的括号，但题目允许通过括号准确体现树结构。空树不输出，单叶树直接输出操作数；题图的一元运算以右孩子表示。每结点访问一次，data长固定，时间O(n)，递归深度等于树高h，辅助空间O(h)，退化链时为O(n)。

（1）从A执行Prim。 Prim维护已经进入树的顶点集合U，每轮选一条跨越U与其余顶点的最轻边，不形成回路：

依次为AD、DE、EC、CB，总权值4+4+5+4=17。每次选的是连接新顶点的最轻跨边，不是从当前最后加入的顶点任意走一条边，也不是把全图边直接按序取四条。

（2）唯一性。 该MST唯一。割{A}的唯一最轻边是AD=4，割{A,D}的跨边为DE=4、AE=5、AB=6、DC=6，唯一最轻边是DE=4，割{B}的唯一最轻边是BC=4；这些边根据割性质都必须在MST中。三条边构成两个连通部分{A,D,E}与{B,C}，跨越这两部分的边为CE=5、AB=6、CD=6，唯一最轻CE也必选。四条必选边已经连通全部五个顶点，因此没有另一种等价边集。

（3）一般条件。 一个常用充分条件是全图所有边权两两不同，此时每个割的最轻边不会出现同权选择，MST唯一。这不是必要条件，本图AD、DE、BC都权4仍有唯一MST。另一种充分条件是每个环的最大权边都唯一，该条件同样不是唯一MST的必要条件。

若要作准确的充要判定，可先取得一棵MST T：对每条非树边e=(u,v)，比较其权与T中u到v唯一路径上的最大边权。T唯一当且仅当每条非树边的权都严格大于该最大值。若相等，加e形成的环上可删一条等权最大树边，得到另一棵同权MST；若都严格大于，任何这样的替换都会增大代价，就没有等权替代树。对已经是MST的T，非树边不可能比路径最大边更小，否则交换即可使总权下降。

分析口径。 int使用32位补码，unsigned按模2³²运算，float为1位符号、8位指数、23位小数字段，规格化时再含隐含最高1，共24位有效精度。以下整数回绕值按题设机器结果解释；实际ISO C/C++的有符号溢出是未定义行为，不能用原程序在任意实现中保证得到相同回绕结果。

（1）n=0的循环。 n为unsigned，表达式n−1将−1转换为模2³²结果4294967295，即FFFFFFFFH。i也为unsigned，任意值都满足i≤4294967295；到最大值后i++又回0，因此循环条件始终为真。若i、n均改为int，n−1=−1，初始i=0时0≤−1为假，循环一次不做，返回初值1，符合f(0)=1。

（2）n=23的值与编码。 $f(23)=2^{24}-1=16777215$，二进制24个1，int可表示，位模式00FFFFFFH。float有24位有效精度，也能精确表示，规格化为 $1.\underbrace{11\cdots1}_{23位}\times2^{23}$，符号0、指数23+127=150=10010110₂、23位小数全1，机器数4B7FFFFFH。二者返回的数值相等，编码不同；不能因内存位模式不同就认为浮点结果有误差。

（3）n=24的舍入。 真值 $2^{25}-1=33554431$ 有25个有效1，而float只有24位，不能保留最低位。它落在可表示的33554430与33554432之间，距离各1；按就近且同距取偶的舍入规则，选有效尾数最低位为0的一侧33554432.0。int尚未超出2³¹−1，仍准确返回33554431。误差源是浮点有效精度不足，不是指数范围不足。

（4）整数范围。 f(31)的数学值2³²−1为32个1。按32位机器回绕，保存FFFFFFFFH，解释为有符号补码是−1。要求结果非负且准确，必须 $2^{n+1}-1\le2^{31}-1$，得n≤30，所以最大n=30。n=31时power最后一次倍增也已超出有符号正数范围，不能只检查sum最后的赋值。

（5）浮点范围与精度。 7F800000H拆为符号0、指数全1、尾数全0，表示正无穷+∞。最大有限正float为 $(2-2^{-23})2^{127}$。n=126时f2的舍入结果为2¹²⁷，仍有限；n=127时接着增长到2¹²⁸的量级，超过有限范围，成为+∞。故不溢出的最大n=126。要求完全精确时，f(n)有n+1个有效1，必须n+1≤24，所以最大n=23。指数位数限制能有多大，尾数精度限制有多少有效位，这两个上界不可混淆。

（1）识别指令集。 图中push ebp编码55H，占1B；cmp编码39 4D F4，占3B；shl编码D1 E2，占2B，指令长度不固定。cmp还可直接以 dword ptr [ebp-0Ch] 为存储器操作数，不是只有专门Load/Store才访问内存。变长格式与复杂寻址符合CISC，故M为CISC；不能仅由寄存器名字或某条简单移位指令判断RISC。

（2）代码总字节数。 首指令从00401020H开始，最后ret从0040107FH开始，机器码C3为1B，因此代码结束后一地址为00401080H。总长度 $00401080\mathrm H-00401020\mathrm H=60\mathrm H=96$B；也可用末字节减首字节加1：7FH−20H+1=60H。不能用35条指令乘一个固定长度，因为上问已说明长度不同。

（3）CF计算。 调用f1(0)时n=0，unsigned的n−1回绕为FFFFFFFFH。i=0时cmp计算无符号 $00000000\mathrm H-FFFFFFFF\mathrm H$，前者小于后者，需要借位，所以CF=1；低32位结果为1。用加法器看，是 $0+\overline{FFFFFFFF\mathrm H}+1=1$，没有最高位进位输出，减法借位标志对应其取反，仍为1。不能因截断结果1是正数而判断无借位，也不能把加法进位线直接当成减法CF。

（4）float乘2。 f1中的整数位模式整体左移1位可实现低32位意义上的乘2。f2中的float则由符号、指数和尾数构成，整体shl会移动字段边界、破坏编码，不能同样使用。例如1.0编码3F800000H，整体左移会得到7F000000H，不是2.0应有的40000000H。规格化浮点乘2通常相当于调整指数，并须处理特殊值与溢出等情形，应使用浮点运算或等价的合法浮点处理，不能直接对原位串作整数移位。

（1）代码占页数。 页内偏移12位，页大小2¹²=4096B。代码从00401020H到0040107FH，开始和结束的虚页号均为00401H，只有低12位偏移由020H到07FH变化，故只占1页。代码96B小于一页本身还不足以保证只占1页，因为小代码也可能跨页；这里需同时验证起止页号相同。

（2）两级表项编号。 第1条指令地址00401020H按10、10、12位切分。页目录号为 (addr >> 22)=1，页表索引为 ((addr >> 12) & 0x3FF)=1，页内偏移为 (addr & 0xFFF)=0x020。因此先访问页目录中编号1的项，取得二级页表地址，再访问该页表编号1的项，得到页框号，最后加020H偏移形成物理地址。编号从0开始，所以“编号1”是自然顺序的第二项，不能写成编号0。

（3）scanf期间状态与模式。 本题主答案采用实际发起且须等待设备输入的场景。scanf是用户态库函数，获取设备输入时会调用内核的输入系统服务，CPU通过系统调用由用户态进入内核态。输入尚未准备好，进程P由运行态变为阻塞态，调度程序把CPU分配给其他就绪进程。

设备完成输入后产生中断，中断处理程序唤醒P，P由阻塞态变为就绪态。以后调度程序选中P，它才由就绪态变为运行态，完成输入、返回用户程序并继续调用f1。因此进程状态顺序为“运行→阻塞→就绪→运行”。I/O完成只使P具备运行条件，不保证它立即获得CPU。

库函数调用与系统调用需区分。如果所需输入已完整保存在用户态库缓冲区，scanf可直接解析缓冲内容，既不必等待设备，也不必为这次解析再次进入内核；如果数据在内核缓冲区已经就绪，读取它仍可需要系统调用，但可不经历等待设备的阻塞。以上缓冲情形是实现边界，本题按前述等待输入的场景作答。

先识别共享访问。 x、y、z是共享复数，含a、b两个float分量；w和add内部形参、局部s属于各线程自己的调用现场。x只读，无需互斥；thread1、thread2读y，两读之间可并发，但都需与thread3写y互斥；thread2读z需与thread3读改写z互斥。复数读写不应读到一新一旧的两个分量。

用三个初值为1的二元信号量：y13限制thread1与thread3在y上的冲突，y23限制thread2与thread3在y上的冲突，z23限制thread2与thread3在z上的冲突。两个y读取线程用不同信号量，使其能够同时读取。

semaphore y13 = 1, y23 = 1, z23 = 1;

thread1 {
    cnum w;
    P(y13);
    w = add(x, y);
    V(y13);
    ...
}

thread2 {
    cnum w;
    P(y23);
    P(z23);
    w = add(y, z);
    V(z23);
    V(y23);
    ...
}

thread3 {
    cnum w;
    w.a = 1;
    w.b = 1;             // 局部变量初始化无需锁
    P(z23);
    z = add(z, w);
    V(z23);              // 先释放z，再准备更新y
    P(y13);
    P(y23);
    y = add(y, w);
    V(y23);
    V(y13);
    ...
}

互斥与并发理由。 thread3写y前需同时取得两把y锁，任一读y线程在临界操作中都会阻止它；写z则受z23保护。thread1与thread2读y互不持有对方的锁，可并发；thread1读y与thread3更新z也使用不同锁，可并发。两次共享写分别加锁，局部初始化及其余不访问这些共享变量的工作放在锁外，不用一把总锁串行化三个线程。

无死锁理由。 thread2按y23→z23申请。thread3在申请y锁前已经释放z23，不会拿着z23反等thread2所持y23，因此不存在这两把锁的循环等待；thread1只用一把y13，也不能形成等待环。三个锁必须在两条写语句之间正确释放，不能为图省事让thread3一直持有z23直到写y结束。

编号规则。 3位序号按模8循环，GBN发送窗口最多2³−1=7帧。确认号y表示希望收到对方下一帧，因而累计确认此前所有按序到达的数据；数据方向的发送序号x与反向确认y是两套独立状态。

（1）图a已经确认的甲帧。 甲收到R0,1后知道S0,0已收；之后R1,3和R3,3的确认号都为3，说明乙已按序收到甲的0、1、2并期望3。因此能断定正确接收3帧，分别为S0,0、S1,0、S2,0。S3,0与S4,1尚未得到更高累计确认，不能因图画出已发送就认为它们已被乙正确接收。

（2）图a还能新发的帧。 甲已发序号0～4，0～2已确认，窗口当前从3开始，最大7帧，可覆盖3、4、5、6、7、0、1。其中3、4已占两格，余下还可发送5帧：5、6、7、0、1。甲自己收到乙的数据0、1后期望2；随后来的是R3,3，数据序号3越过缺失的2，GBN接收端不能按序接受它，所以甲的捎带确认仍为2。新发5帧为S5,2、S6,2、S7,2、S0,2、S1,2，第一S5,2，最后S1,2。不能把乙帧的确认号3当作甲对乙的接收确认号。

（3）图b的重传。 乙返回的确认号先1后2，随后R2,2仍确认2，说明甲的0、1已确认，2、3、4未确认。t1时序号2超时，GBN须回退重传从2起的所有已发未确认帧，共3帧，即2、3、4。此时甲已按序收到乙的数据0、1、2，期望3，重传时更新捎带确认字段为3，所以重传首帧为S2,3，随后S3,3、S4,3。重发的数据发送序号保持原序号，反向确认号则可使用最新状态。

（4）最大利用率。 一帧1000B，发送时间 $t_f=1000\times8/(100\times10^6)=0.08$ms。按题中往返传播时延RTT=0.96ms计算，首帧从开始发送到收到完整捎带确认，还包括自身帧发送0.08ms以及对方携带确认的数据帧发送0.08ms，总计1.12ms。窗口最大7帧，每轮能连续发送7×0.08=0.56ms，随后等待窗口推进，所以

$$U_{\max}=\min\left(1,\frac{7\times0.08}{0.96+0.08+0.08}\right)=0.5=50\%.$$

捎带确认字段虽短，却要等完整的对方1000B帧传到才能使用，不能把确认传输时间当成0；序号空间8也不等于GBN可开8帧窗口，必须保留一格区分新旧轮次。