方法一：定义法

本题为多层循环，用定义法求解 ：

本题选C。

方法二：公式法

本题为多层循环中嵌套循环指针无关类型题。

外层循环时间复杂度为 O(log⁡n) ，内层循环时间复杂度为 O(n) 。

由公式

可得总时间复杂度为  。

本题选C。

方法一：模拟

本题考察中缀表达式转后缀表达式，需要利用栈作为辅助。

没有必要扫描完整个表达式，只需要扫描到 f 即可，过程模拟如下：

本题选B。

方法二：观察表达式

其实我们没有必要老老实实模拟整个流程，只需要观察中缀表达式即可， a/b+(c∗d−e∗f)/g 扫描到 f 时，此时 f 还没有被输出，观察前面与 f 相关的操作，也是没有能够输出的操作，这些操作都暂存在栈中，依次为 +(−∗ ，越靠近栈顶的优先级越高，显然在括号中 ∗ 比 − 的优先级高，栈顶的是 ∗ 。

本题选B。

循环队列中区分队空和队满，有三种处理方式：

① 牺牲一个单元来区分队空和队满，入队时少用一个队列单元，这是一个较为普遍的做法，约定以“队头指针在队尾指针的下一个位置作为队满的标志”。

队满条件：(Q.rear + 1) % MaxSize == Q.front

队空条件：Q.front == Q.rear

队列中元素的个数：(Q.rear - Q.front + MaxSize) % MaxSize

② 类型中增设表示元素个数的数据成员size：

队满条件：Q.size == MaxSize

队空条件：Q.size == 0

队列中元素的个数：Q.size

③ 类型中增设用于区分队满还是队空的数据成员tag，入队标记tag = 1，出队标记tag = 0：

队满条件：Q.front == Q.rear && tag == 1

队空条件：Q.front == Q.rear && tag == 0

队列中元素的个数：(Q.rear - Q.front + MaxSize) % MaxSize

以上三种方法本人简记为：

① 空一法（空格法）

② 计数法

③ 标记法（标志法）

A[0..M-1]数组的容量为M，队列中最多能容纳 M-1 个元素，很明显采用了空一法。

把变量名对着题目改一遍，很明显A选项符合条件。

本题选A。

中序线索化先进行中序遍历， x 左线索指向中序序列中 x 的前驱，x 右线索指向中序序列中 x 的后继。

中序遍历可以用投影法或者环线法。

得到中序遍历序列为d, e, b, x, a, c。

本题选D。

方法一：性质

将森林F转换为对应的二叉树T，即二叉树T用左孩子右兄弟法表示森林。森林F中的叶结点一定没有孩子结点，转化为二叉树T没有左孩子，所以F中叶子的个数等于T中左孩子指针为空的结点个数。

本题选C。

方法二：画图

如果仅仅利用性质分析觉得过于抽象，直接画图举例：

F中叶子的个数为5。

A选项，T中叶结点的个数为3，错误。

B选项，T中度为1的结点个数为2，错误。

C选项，T中左孩子指针为空的结点个数为5，正确。

D选项，T中右孩子指针为空的结点个数为3，错误。

本题选C。

方法一：观察选项

D选项中110是1100的前缀，不是前缀编码。

本题选D。

方法二：哈夫曼树

直接画出每种编码方案对应的哈夫曼树，遵循路径左0右1的规则。

最后检查所有编码必须存储在叶结点。

下图用黄色结点标记存储编码。

本题选D。

参考答案：D

答案解析：按照拓扑排序的算法，每次都选择入度为 0 的结点从图中删去，此图中一开始只有 结点 3 的入度为 0；删掉 3 结点后，只有结点 1 的入度为 0；删掉结点 1 后，只有结点 4 的 入度为 0；删掉 4 结点后，结点 2 和结点 6 的入度都为 0，此时选择删去不同的结点，会得出不同的拓扑序列，分别处理完毕后可知可能的拓扑序列为 314265 和 314625，选 D。

每次找入度为0的点依次剥离，如下图所示：

参考答案：D

答案解析：产生堆积现象，即产生了冲突，它对存储效率、散列函数和装填因子均不会有影响，而平均查找长度会因为堆积现象而增大，选 D。

用线性探测法为例，处理冲突（碰撞）时可能出现堆积（聚焦）现象，平均查找长度会变长。

A、B和C选项均与处理冲突无关。

本题选D。

方法一：性质 + 贪心

本题选D。

方法二：公式法

本题选D。

方法三：选项排序 + 贪心

本题选D。

参考答案：B

答案解析：首先，第二个元素为1，是整个序列中的最小元素，所以可知该希尔排序为从小到大排序。然后考虑增量问题，若增量为2，第 1+2 个元素4明显比第1个元素9要大，A 排除；若增量为3，第 i、i+3、i+6 个元素都为有序序列(i=1,2,3)，符合希尔排序的定义；若增量为4，第1个元素9比第1+4个元素7要大，C排除；若增量为5，第1个元素9比第1+5个元素8要大，D排除，选B。

我们依次检查每个增量，每个增量序列必须单调递增。

A错误。间隔2的序列为：9, 4, ... ，非单调递增，错误。

B正确。间隔3的序列为：9, 13, 20、 1, 7, 23、4, 8, 15，全部单调递增。

C错误。间隔4的序列为：9, 7, ...，非单调递增。

D错误。间隔5的序列为：9, 8, ...，非单调递增。

本题选B。

参考答案：C

答案解析：快排的阶段性排序结果的特点是，第 i 趟完成时，会有 i 个以上的数出现在它最终将要出现的位置，即它左边的数都比它小，它右边的数都比它大。题目问第二趟排序的结果，即要找不存在 2 个这样的数的选项。A 选项中 2、3、6、7、9 均符合，所以 A 排除；B选项中，2、9 均符合，所以 B 排除；D 选项中 5、9 均符合，所以D选项排除；最后看C选项，只有9一个数符合，所以C不可能是快速排序第二趟的结果。

其它方法

第一步：

检查快速排序，首先利用快速排序的性质，快速排序每一趟至少能够保证一个元素落在最终位置，即枢轴一定落在最终位置。这里进行了两趟快速排序，至少两个元素落在最终位置。

我们求出排好序后的序列为：2, 3, 4, 5, 6, 7, 9，然后依次和四个选项进行比对，看有没有不符合要求的。

A中有5个落位，待定。

B中有2个落位，待定。

C中有1个落位，错误。

D中有2个落位，待定。

由于这里C选项已经确定错误，无需进行第二步。

第二步是判断枢轴左边元素是否都小于枢轴，右边元素是否都大于枢轴。

第三步是画出序列对应的递归树，判断是否为快速排序的递归树。

本题过于简单，到第一步就结束了。

本题选C。

参考答案: D

解析：不妨设原来指令条数为 x，那么原 CPI 就为 20/x，经过编译优化后，指令条数减少

到原来的 70%，即指令条数为 0.7x，而 CPI 增加到原来的 1.2 倍，即 24/x，那么现在 P 在 M上的执行时间就为指令条数*CPI=0.7x*24/x=24*0.7=16.8 秒，选 D。

解析：8 位定点补码表示的数据范围为-128~127，若运算结果超出这个范围则会溢出，A

选项 x+y=103-25=78，符合范围，A 排除；B 选项-x+y=-103-25=-128，符合范围，B 排除；

D 选项-x-y=-103+25=-78，符合范围，D 排除；C 选项 x-y=103+25=128，超过了 127，选 C。

方法一：十进制计算

8位定点补码表示的数据范围为-128~127，若运算结果超出这个范围则会溢出。

一般发生正溢出，需要考虑 x-y，即选项C，或者负溢出，需要考虑 -x+y，即选项B，

B选项-x+y=-103-25=-128，符合范围，B排除。

C选项x-y=103+25=128>127，溢出。

本题选C。

方法二：二进制计算

[x]补 = 01100111B，[-x]补 = 10011001B，[y]补 = 11100111B，[-y]补 = 00011001B

B选项 [-x+y]补 =[-x]补 + [y]补 = (1) 1000 0000B。括号内为最高位进位，最高位符号位和最高位进位相同，无溢出。

C选项 [x-y]补 = [x]补 + [-y]补 = 01100111B = 00011001B = (1) 0000 0000B。括号内为最高位进位，最高位符号位和最高位进位不相同，溢出。

本题选C。

参考答案：A

解析：(f1)和(f2)对应的二进制分别是(110011001001……)2 和(101100001100……)2，根据

IEEE754 浮点数标准，可知(f1)的数符为 1，阶码为 10011001，尾数为 1.001，而(f2)的数符为 1，阶码为 01100001，尾数为 1.1，则可知两数均为负数，符号相同，B、D 排除，(f1)的绝对值为 1.001×226，(f2)的绝对值为 1.1×2-30，则(f1)的绝对值比(f2)的绝对值大，而符号为负，真值大小相反，即(f1)的真值比(f2)的真值小，即 x<y，选 A。

此题还有更为简便的算法，(f1)与(f2)的前 4 位为 1100 与 1011,可以看出两数均为负数，

而阶码用移码表示，两数的阶码头三位分别为 100 和 011，可知(f1)的阶码大于(f2)的阶码，

又因为是 IEEE754 规格化的数，尾数部分均为 1.xxx，则阶码大的数，真值的绝对值必然大，

可知(f1)真值的绝对值大于(f2)真值的绝对值，因为都为负数，则(f1)<(f2)，即 x<y。

4M×8位的芯片数据线应为8根，地址线应为 log⁡4M=log⁡(2^2*2^20)=22 根，而DRAM采用地址复用技术，地址线是原来的1/2，且地址信号分行、列两次传送。地址线数为22/2=11根，所以地址引脚与数据引脚的总数为11+8=19根。

本题选A。

分离指令存储和数据存储是哈佛结构的思想。把指令Cache与数据Cache分离后，取指和取数分别到不同的Cache中寻找，那么指令流水线中取指部分和取数部分就可以很好地避免冲突，即减少了指令流水线的冲突。

本题选D。

采用32位定长指令字，其中操作码为8位，剩余32-8=24位，而Store指令的源操作数和目的操作数分别采用寄存器直接寻址和基址寻址，机器中共有16个通用寄存器，则寻址一个寄存器需要log16=4位，源操作数中的寄存器直接寻址用掉4位，而目的操作数采用基址寻址也要指定一个寄存器，同样用掉4位，则留给偏移址的位数为24-4-4=16位，而偏移址用补码表示，16位补码的表示范围为 −2^15∼2^15−1 ，即-32768~+32767。

该指令格式如下：

计算机共有32条指令，各个指令对应的微程序平均为4条，则指令对应的微指令为32×4=128条，而公共微指令还有2条，整个系统中微指令的条数一共为128+2=130条，所以需要 ⌈log⁡130⌉=8 位才能寻址到130条微指令。

本题选C。

数据线有32根，也就是一次可以传送32bit/8=4B的数据，66MHz意味着每秒有66M个时钟周期，而每个时钟周期传送两次数据，总线的最大数据传输率4B×66MHz×2=528MB/s。

本题选C。

参考答案: C

解析：猝发(突发)传输是在一个总线周期中，可以传输多个存储地址连续的数据，即一次传输一个地址和一批地址连续的数据，并行传输是在传输中有多个数据位同时在设备之间进行的传输，串行传输是指数据的二进制代码在一条物理信道上以位为单位按时间顺序逐位传输的方式，同步传输是指传输过程由统一的时钟控制，选 C。

独立编址是将I/O端口单独编排地址，独立于存储器地址。C陈述正确。

统一编址是将I/O端口与存储器地址统一编排，共享一个地址空间。CPU访存和访问I/O端口用的是一样的指令，所以访存指令可以访问I/O端口。D陈述错误。

本题选D。

每400ns发出一次中断请求，而响应和处理时间为100ns，其中中断响应所允许的最长延迟时间为50ns必须包含在400ns内，否则处理一次中断的时间将超过400ns，从而导致部分中断请求得不到及时响应，进而产生数据丢失等错误。所以该设备的I/O时间占整个CPU时间的百分比为100ns/400ns=25%。

本题选B。

饥饿现象是指一个进程或任务由于得不到执行的机会而无法完成的情况。调度算法的设计应该避免饥饿现象的发生，确保公平地分配处理器时间给各个进程或任务。

A正确。时间片轮转调度算法是一种循环调度算法，在每个时间片内，每个进程或任务都有机会执行一段时间。因为时间片是有限的，所以没有一个进程会长时间占用处理器，从而避免饥饿现象的发生。

B错误。静态优先数调度算法根据每个进程或任务的静态优先级进行调度。属于优先级调度算法，饥饿现象可能发生在优先级较低的进程，只要有源源不断的优先级比该进程高的进程在其执行前到来，则该进程将一直被推迟，可能导致饥饿现象。

C错误。非抢占式短作业优先调度算法将优先执行估计运行时间短的作业。属于短作业优先调度算法。饥饿现象可能发生在运行时间较长的作业，只要有源源不断的运行时间比该作业短的作业在其执行前到来，则该作业将一直被推迟，可能导致饥饿现象。

D错误。抢占式短作业优先调度算法中，运行时间相对较短的作业可以抢占正在执行的剩余运行时间相对较长的作业。属于短作业优先调度算法。饥饿现象可能发生在运行时间较长的作业，只要有源源不断的运行时间比该作业短的作业在其执行前到来，则该作业将一直被推迟，可能导致饥饿现象。

本题选A。

各种进程调度算法的优缺点总结如下：

答案：B
三个并发进程分别需要3，4，5台设备，当系统只有(3-1)+(4-1)+(5-1)=9台设备时，第一个进程分配2台，第二个进程分配3台，第三个进程分配4台。这种情况下，三个进程均无法继续执行下去，发生死锁。当系统中再增加1台设备，即10台设备时，最后1台设备分配给任意一个进程都可以顺利执行完成，因此保证系统不发生死锁的最小设备数为10。

【答案】D

【解析】trap指令、跳转指令和压栈指令均可以在用户态执行, 其中trap指令负责由用户态转换为内 核态。关中断指令为特权指令，必须在核心态才能执行，选 D。注意，在操作系统中，关中断指令是权限非常大的指令，因为中断是现代操作系统正常运行的核心保障之一，能把它关掉，说明执行这条指令的一定是权限非常大的机构（管态）。

在用户态执行的指令是受限制的，通常只能执行非特权操作。

A错误。trap指令一般指陷阱指令。陷阱指令是处理陷阱的指令。陷阱是指计算机系统在运行中的一种意外事故，例如电源电压不稳、存储器检验出错、存储器校验出错、输入输出设备出现故障、用户使用了未定义的指令或特权指令等意外情况，使得计算机系统不能正常工作。在一般的计算机中，陷阱指令作为隐含指令不提供给用户使用，只有在出现故障时，才由CPU自动产生并执行。在一些系统中，用户态程序可以通过trap指令请求操作系统的服务，从用户态向内核态（特权态）转移执行。因此，用户态程序可以执行trap指令。

B错误。跳转指令用于在程序中无条件或有条件地跳转到指定的地址。跳转指令通常是用户态程序的一部分，因此可以在用户态执行。

C错误。压栈指令是将数据压入栈中的指令，用于保存当前执行环境和数据。在用户态程序中，可以使用压栈指令来维护局部变量、函数调用的返回地址等，因此可以在用户态执行。

D正确。关中断指令用于在处理器中禁用中断请求。这个指令是一种特权操作，只有处于内核态（特权态）的代码才能执行。用户态程序没有权限执行关中断指令。

本题选D。

【答案】A

【解析】进程申请读磁盘操作的时候，因为要等待I/O操作完成，会把自身阻塞，此时进 程就变为了阻塞状态，当 I/O操作完成后，进程得到了想要的资源，就会从阻塞态转换到就绪态(这是操作系统的行为)。而降低进程优先级、分配用户内存空间和增加进程的时间片大小都不一定会发生，选A。

A正确。当一个进程的读磁盘操作完成后，该进程以具备执行进程需要的系统资源。操作系统将其状态从阻塞态修改为就绪态，等待处理机的调度。这样，进程将具备执行的条件，并可以在调度算法的允许下被选中执行。

B错误。读磁盘操作的完成并不一定要导致进程优先级的降低。进程优先级的调整通常是基于一些策略和调度算法，并不是读磁盘操作完成后必做的操作。

C错误。分配用户内存空间通常是在进程创建时进行，而不是在读磁盘操作完成后。读磁盘操作完成后，操作系统更关注进程状态的切换和调度，而不是重新分配用户内存空间。

D错误。进程的时间片大小通常是由调度算法和操作系统决定的，读磁盘操作完成后并不会直接增加进程的时间片大小。

本题选A。

因为该磁盘容量为10GB，每个簇大小为4KB，所以总共有10GB/4KB= 5×2^19 个簇，又采用位图法管理该分区的空闲空间，每个簇需要1位标识，总共需要 5×2^19×1bit=5×2^19bit 空间，每个簇大小为4KB，需要 5×2^19bit/4KB=5×2^19bit/(4×2^10×8bit)=80 个簇存储位图。

本题选A。

快表 (Translation Lookaside Buffer, TLB) 是缓存页表项的高速缓存，用于加速虚实地址的转换。

I正确。通过增大TLB的容量，可以存储更多的页表项，减少了需要访问内存的次数，从而提高虚实地址转换的速度。

II正确。将页表常驻内存是指将页表始终保留在内存中，而不将其置换到磁盘上的交换区。当页表在内存中时，虚实地址转换的速度更快，因为访问内存比访问磁盘要快得多。通过确保页表常驻内存，可以加快虚实地址转换的速度。

III错误。增大交换区的容量并不直接加快虚实地址转换的速度。交换区是用于将内存中不活跃的页调出到磁盘的区域。增大交换区可以提供更多的存储空间，以便支持更多的进程运行，但它并不直接影响虚实地址转换的速度。

综上所述，能加快虚实地址转换的措施是仅 I、II。

本题选C。

在一个文件被用户进程首次打开的过程中，操作系统需要完成以下几个关键步骤：

1. 文件查找：操作系统首先需要根据用户进程提供的文件路径或文件描述符来查找文件。这通常涉及检查文件系统以确定文件是否存在以及用户对文件的访问权限。
2. 分配文件描述符：一旦文件被找到并且用户进程有合适的权限来打开该文件，操作系统需要为该文件分配一个文件描述符。文件描述符是一个抽象的概念，用来代表已打开文件的引用，使得用户进程可以通过该文件描述符来进行后续的 I/O 操作。
3. 建立文件表项：操作系统需要在内部的文件表中建立一个文件表项，其中包含有关该文件的元数据信息，如当前文件偏移量、文件状态等。
4. 权限检查：在用户进程进行文件打开操作时，操作系统通常会对需要访问的文件进行权限检查，以确保用户拥有足够的权限来进行所需的操作。
5. 为文件分配资源：当文件被打开时，操作系统可能还需要分配其他资源，如内存缓冲区或其他控制结构，以便在用户进程执行读取和写入操作时使用。

A错误。在文件首次打开时，操作系统通常不会立即将整个文件内容读入内存。相反，操作系统会在需要读取文件内容时进行逐块或按需加载。

B正确。文件控制块 (File Control Block, FCB) 是操作系统用于管理文件的数据结构，包含有关文件的元数据和指示符等信息。在用户进程首次打开文件时，操作系统需要将文件控制块读取到内存中，以便后续对文件进行管理和操作。

C错误。文件的读写权限通常是在文件创建或修改的过程中进行设置，并不是在用户进程首次打开文件时修改的。因此，在文件首次打开的过程中不需要修改文件控制块中的读写权限。

D错误。在一个文件被用户进程首次打开的过程中，操作系统会为该文件分配相应的文件描述符和数据缓冲区。然而，操作系统并不会直接将文件的数据缓冲区首指针返回给用户进程。用户进程无需直接获取数据缓冲区的首指针，而是通过系统调用来进行文件读写操作，让操作系统处理数据缓冲区的传输和管理。这样的设计可以提高系统的安全性、可靠性和效率。

• 文件读取：当用户进程调用读取操作（如read()）时，操作系统会将文件描述符与对应的数据缓冲区关联起来，并将数据从文件缓冲区复制到用户进程提供的缓冲区中。在这个过程中，操作系统会使用数据缓冲区的首指针来指示数据的位置，并将读取的数据从文件缓冲区复制到用户进程的缓冲区中。
• 文件写入：当用户进程调用写入操作（如write()）时，操作系统会将文件描述符与对应的数据缓冲区关联起来，并将用户进程提供的数据写入文件缓冲区。在这个过程中，操作系统使用数据缓冲区的首指针来指示写入的位置，并将用户进程提供的数据复制到文件缓冲区中。

本题选B。

Belady异常现象指的是在某些情况下，使用某些页面置换算法，当进程的物理页框（页面框）数目增加时，缺页次数反而会增加。换句话说，当为进程分配更多的物理页框时，它的缺页率反而会增加，这是不符合直觉的现象。

在解决页面置换问题时，经典的页面置换算法包括LRU算法（最近最少使用算法）、FIFO算法（先进先出算法）和OPT算法（最佳置换算法）等。

I错误。LRU算法是根据页面的历史访问记录来决定置换哪个页面，选择最近最少被使用的页面进行置换。相对于FIFO算法来说，LRU算法通常能够更好地反映出进程的局部性，因此缺页次数较少。在一般情况下，LRU算法不会出现Belady异常现象。

II正确。FIFO算法是按页面调入内存的顺序进行置换，最早进入内存的页面将被置换出去。FIFO算法在一般情况下不能完美地反映进程的访问模式，但它具有简单和易于实现的优点。与LRU算法相比，FIFO算法可能更容易出现Belady异常现象。

III错误。OPT算法是一种理想的页面置换算法，它能够看到未来的访问模式，总是选择能够在未来最远的时间被访问到的页面进行置换。然而，由于OPT算法需要事先知道进程的完整访问序列，而实际中无法预知未来的访问模式，因此OPT算法很难实现。在实践中，OPT算法很少被使用。

综上，仅 II 正确。

本题选A。

【答案】C

【解析】管道实际上是一种固定大小的缓冲区，管道对于管道两端的进程而言，就是一个文件，但它不是普通的文件，它不属于某种文件系统，而是自立门户、单独构成的一种文件系统，并且只存在于内存中。它类似于通信中半双工信道的进程通信机制，一个管道可以实现双向的数据传输，而同一时刻只能最多有一个方向的传输，不能两个方向同时进行。管道的容量大小通常为内存上的一页，它的大小并不受磁盘容量大小的限制。当管道满时，进程在写管道会被阻塞，而当管道空时，进程在读管道会被阻塞，因此选C。

A错误。管道通信是一种半双工的通信方式，意味着数据只能在一个方向上传输。管道具有一个读端和一个写端，只能单向传输数据。

B错误。管道的容量是受操作系统的限制的，与磁盘容量无关。通常，管道的容量是固定的，取决于操作系统的实现。

C正确。管道的读写操作都是阻塞的。如果管道为空，读取操作将被阻塞，直到有数据可读。同样，如果管道已满，写入操作将被阻塞，直到有空间可写。

D错误。管道通常被设计成允许多个进程进行读写操作。多个进程可以共享同一个管道实例，一个进程可以写入数据到管道，而另一个进程可以从管道读取数据。

本题选C。

A错误。多级页表并不能直接加快地址变换的速度。事实上，由于多级页表需要多次间接查表，地址变换的速度可能会稍微变慢。

B错误。多级页表与缺页中断没有直接关系。缺页中断是由于页面不在内存中，需要进行页面调度和置换的过程中产生的。多级页表在页表管理方面有一些优势，但并不直接减少缺页中断次数。

C错误。因为多级页表需要更多的页表项，而页表项大小是固定的，所以级页表会增加页表项所占的字节数。

D正确。。多级页表的一个显著优点是减少页表所占用的连续内存空间。传统的单级页表需要一次性分配整个页表，因此需要连续的内存空间。而多级页表可以将页表分为多个级别，每个级别只需要分配一部分页表，从而减少了连续内存空间的需求。

本题选D。

OSI 参考模型 (Open System Interconnection Reference Model) 是一个由国际标准化组织提出的概念模型，旨在为各种计算机互连构成网络提供标准框架。该模型将通信系统划分为七层，从下到上依次为物理层、数据链路层、网络层、传输层、会话层、表示层和应用层。

其中，下层为上层提供服务。

会话层下一层是传输层，所以直接为会话层提供服务的是传输层。

本题选 C。

本题考察交换机自学习和转发帧的相关知识，其一般步骤如下：

自学习：以太网收到一帧后先进行自学习。查找转发表最后与收到帧的源地址有无匹配的项。如果没有，就在转发表中增加一个项（包括源地址，进入端口的口和时间）；如果有，就把原来的项进行更新。

转发帧：查找转发表中与收到帧的目的地址有无想匹配的项。如果没有，则通过除进入交换机的端口外的所有其他端口进行转发；如果有，则按照转发表中给出的端口进行转发，但要注意，如果转发表在给出的端口就是该帧进入交换机的端口，则应该丢弃该帧（因为此时无需经过交换机进行转发）。

下面对本题进行逐步分析：

初始时，交换机的转发表为：

主机 00-e1-d5-00-23-a1 向主机 00-e1-d5-00-23-c1 发送 1 个数据帧，数据帧进入交换机后，交换机通过自学习记录该帧的源 MAC 地址进入交换机的端口号，更新转发表后如下：

查找目的地址为 00-e1-d5-00-23-c1 的项发现不存在，此时将该帧通过除进入交换机的端口（这里为端口 1）外的所有其他端口进行转发，即通过端口 2 和端口 3 进行转发。

主机 00-e1-d5-00-23-b1 收到该帧后，发现该帧目的 MAC 地址与自身 MAC 地址不一致，丢弃该帧。主机 00-e1-d5-00-23-c1 收到该帧后，发现该帧目的 MAC 地址与自身 MAC 地址一致，给主机 00-e1-d5-00-23-a1 发送确认帧，确认帧进入交换机后，交换机通过自学习记录该确认帧的源 MAC 地址进入交换机的端口号，更新转发表后如下：

查找目的地址为 00-e1-d5-00-23-a1 的项发现存在，于是交换机根据该项端口 1 进行明确转发。

综上所述，交换机对着两个帧的转发端口分别是 {2,3} 和 {1}。

本题选 B。

根据香农公式，在被高斯白噪声干扰的信道中，信道的最大数据传输速率为

C=Wlog₂⁡(1+S/N) （单位：比特每秒 (bits per second)）

其中 W 是信道带宽，单位 Hz，S 是信号功率，单位瓦，N 是噪声功率，单位瓦。 S/N 为信号与噪声的功率之比，简称信噪比。

因此， A. 信噪比和 B. 频率宽带会影响信道数据传输速率。

根据奈奎斯特定理，无噪声情况下可获得的最大数据传输速率为

C=2W （单位：波特 (Baud)，即码元/秒）

其中 W 为带宽。每个码元可携带比特数量为 log₂⁡M ，其中 M 为调制技术中可利用的符号数量。奈奎斯特定理表达式可修改如下：

C=2Wlog_2⁡M （单位：比特每秒 (bits per second, bps)）

如果采用更好的调制方法，使得每个码元可携带更多比特数量，比如提高调制速度，可提高信道的最大数据传输速率。

因此，C. 调制速度会影响信道数据传输速率。

综上所述，可排除选项 A、B、C。

本题选 D。

在后退 N 帧协议 (GBN) 中，发送方可以发送 N 个帧而无需等待确认。从发送方发送一个数据帧到发送方接收到接收方传来的确认帧为一个周期。信道利用率为一个周期内发生数据的时间占该周期的比例。

信道带宽为 100 Mbps，该信道为高速以太网，高速以太网默认采用全双工模式，允许数据在两个方向上同时传输。

主机甲发送一个数据帧的时延为  ，传播时延为 50 ms ，主机乙发送一个确认帧的时延为 t2 ，因为乙每收到一个数据帧立即利用一个短帧（忽略其传输延迟）进行确认，所以 t2=0 ，传播时延为 50 ms 。一个周期 T=0.08 ms+50 ms+0 ms+50 ms=100.08 ms 。因为数据链路层采用后退 N 帧协议 (GBN) 传输数据，为使信道利用率达到最高，在一个周期内，发送方可以连续发送多个数据帧，将位于发送窗口中的帧全部发送出去。甲的发送窗口尺寸为1000，1000个帧的发送时延为 1000t1=80 ms<T ，满足要求。

最大信道利用率是 

甲可以达到的最大平均数据传输速率 = 信道带宽 × 最大信道利用率 ≈100 Mbps×80%=80 Mbps 。

本题选 C。

在 CDMA 系统中，接收端通过与发送端相同的码片序列进行相关运算来解码特定发送端的数据。本题中，C 想要解码 A 发送的数据，需要将 C 收到的序列与 A 的码片序列进行内积运算。为了方便，我们习惯将码片中的0记作-1，将1记作+1。

C 从链路上收到的序列是 (2,0,2,0,0,-2,0,-2,0,2,0,2)可以拆分为部分 (2,0,2,0), (0,-2,0,-2), (0,2,0,2)。

要判断 C 收到 A 发送的数据，将 A 的码片序列 (1,1,1,1) 分别与上面三个部分进行内积运算

因此 C 收到 A 发送的数据是 101。

本题选 B。

发送方维持一个拥塞窗口 (congestion window, cwnd)，拥塞窗口的大小取决于网络的拥塞程度，并且动态地变化。发送方让自己的发送窗口等于拥塞窗口。

发送方控制拥塞窗口的原则是：只要网络没有出现拥塞，拥塞窗口就再增大一些，以便把更多的分组发送出去。但只要网络出现拥塞，拥塞窗口就减小一些，以减少注入到网络中的分组数。

最大报文段长度 (maximum segment size, MSS) 是 TCP 协议的一个选项，用于在TCP连接建立时，收发双方协商通信时每一个报文段所能承载的最大数据长度（不包括报文段头）。

慢开始算法

开始时，将拥塞窗口设置为一个 MSS 的数值，每收到一个对新的报文段的确认后，把拥塞窗口增加至多一个 MSS 的数值。可以分析出，每经过一个传输轮次 (transmission round)，拥塞窗口大小加倍，逐渐增大到拥塞窗口的数值，一个传输轮次所经历的时间就是一个往返时间 RTT。

拥塞避免算法

每经过一个往返时间将发送方的窗口加 1。只要发送方判断网络出现拥塞，就将慢开始门限 ssthresh 设置为出现拥塞时发送方窗口值的一半，然后执行慢开始算法。

在本题中，在 cwnd = 8 MSS 时出现超时，发送方判断网络出现拥塞，就将慢开始门限 ssthresh 设置为 cwnd/2 = 4 MSS，然后执行慢开始算法。重新设置 cwnd = 1 MSS。

• 第一个 RTT 发送方得到肯定应答后，调整当前拥塞窗口大小为上一轮次拥塞窗口大小的两倍，即调整 cwnd = 2 MSS。
• 第二个 RTT 发送方得到肯定应答后，调整当前拥塞窗口大小为上一轮次拥塞窗口大小的两倍，即调整 cwnd = 4 MSS。此时 cwnd 到达慢开始门限 ssthresh 值，转而是使用拥塞避免算法。
• 第三个 RTT 发送方得到肯定应答后，调整当前拥塞窗口大小为上一轮次拥塞窗口大小加 1，即调整 cwnd = 5 MSS。
• 第四个 RTT 发送方得到肯定应答后，调整当前拥塞窗口大小为上一轮次拥塞窗口大小加 1，即调整 cwnd = 6 MSS。
• 第五个 RTT 发送方得到肯定应答后，调整当前拥塞窗口大小为上一轮次拥塞窗口大小加 1，即调整 cwnd = 7 MSS。
• 第六个 RTT 发送方得到肯定应答后，调整当前拥塞窗口大小为上一轮次拥塞窗口大小加 1，即调整 cwnd = 8 MSS。
• 第七个 RTT 发送方得到肯定应答后，调整当前拥塞窗口大小为上一轮次拥塞窗口大小加 1，即调整 cwnd = 9 MSS。
• 第八个 RTT 发送方得到肯定应答后，调整当前拥塞窗口大小为上一轮次拥塞窗口大小加 1，即调整 cwnd = 10 MSS。
• 第九个 RTT 发送方得到肯定应答后，调整当前拥塞窗口大小为上一轮次拥塞窗口大小加 1，即调整 cwnd = 11 MSS。
• 第十个 RTT 发送方得到肯定应答后，调整当前拥塞窗口大小为上一轮次拥塞窗口大小加 1，即调整 cwnd = 12 MSS。

乙每收到一个数据段都会发出一个接收窗口为 10 KB 的确认段，即乙的接收窗口为 10 MSS。

该过程示意图如下：

甲的发送窗口 = min {乙的接收窗口, 拥塞窗口} = min{10 MSS, 12 MSS} = 10 MSS = 10 KB。

当然，本题可以无需计算拥塞窗口，甲的发送窗口不可能超过乙的接收窗口，即 10 KB，观察选项，只有选项 A 符合要求。

本题选 A。

关于UDP协议的叙述：

I 正确。UDP 是无连接的传输协议，不需要在发送数据之前先建立连接。

II 正确。UDP 通过端口号来区分不同进程，进而提供复用/分用服务。

III 错误。UDP 提供差错检测，仅检查数据在传输过程中是否出现误码，出现误码的数据会被直接丢弃，没有重传机制，不能保证可靠传输。

综上所述，仅 I、II 正确。

本题选 B。

A 可能被使用。PPP (Point-to-Point Protocol) 点对点协议，是一种数据链路层协议，用于通过串行连接（例如电话线、光纤等）在两个节点之间进行数据通信。若用户主机所在局域网和Internet服务提供商之间使用点对点链路，则会用到 PPP 协议。

B 可能被使用。ARP (Address Resolution Protocol) 地址解析协议，可根据 IP 地址查询 MAC 地址若用户主机不知道所在局域网的默认网关 MAC 地址，可通过 ARP 根据默认网关的 IP 地址获取默认网关 MAC 地址。

C 可能被使用。若其 DNS 缓存没有某大学Web网站主页的 IP 地址，可通过 DNS 根据大学Web网站主页的域名地址如 www.hdu.edu.cn （杭州电子科技大学官网）查询其 IP 地址，DNS 是基于 UDP 的协议。所以可能用到 UDP。

D 不可能被使用。SMTP (Simple Mail Transfer Protocol) 简单邮件传输协议，是用于在网络上发送电子邮件的标准协议。SMTP 可以实现将邮件从你的一台主机的用户代理发送到一个邮件服务器。该邮件服务器会查找接收者的邮件服务器，并使用 SMTP 将邮件转发到接收者的邮件服务器。简单访问 Web 网站不可能用到 SMTP。

本题选 D。

本题为一道简单难度的考察搜索的算法题，考研只需要掌握深度优先搜索和广度优先搜索即可。

这道题要注意的是题目要求“二叉树中所有叶结点的带权路径长度之和”，也就是只有“叶结点”才需要计算WPL。

构造测试用例如下图所示：

方法一：深度优先搜索

C代码如下（含测试用例）：

#include <stdio.h>
#include <stdlib.h>

struct TreeNode {
    int weight;
    struct TreeNode *left;
    struct TreeNode *right;
};

int dfs(struct TreeNode* root, int depth) {
    if (root == NULL) {
        return 0;
    }
    if (root->left == NULL && root->right == NULL) {
        return root->weight * depth;
    }
    return dfs(root->left, depth + 1) + dfs(root->right, depth + 1);
}

int pathSum(struct TreeNode* root) {
    return dfs(root, 0);
}

struct TreeNode *createBinaryTree(int *a, int n) {
    if (a[0] == -1) {
        return NULL;
    }
    int i = 0;
    struct TreeNode *root = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    root->weight = a[i++];
    root->left = NULL;
    root->right = NULL;
    struct TreeNode** que = (struct TreeNode**)malloc(sizeof(struct TreeNode*));
    int front = 0, rear = 0;
    struct TreeNode *curr = root;
    que[rear++] = curr;
    while (front < rear && i < n) {
        curr = que[front++];
        for (int j = 0; j < 2 && i < n; j++, i++) {
            if (a[i] != -1) {
                if (j == 0) {
                    curr->left = (struct TreeNode *)malloc(sizeof(struct TreeNode));
                    curr->left->weight = a[i];
                    curr->left->left = NULL;
                    curr->left->right = NULL;
                    que[rear++] = curr->left;
                } else {
                    curr->right = (struct TreeNode *)malloc(sizeof(struct TreeNode));
                    curr->right->weight = a[i];
                    curr->right->left = NULL;
                    curr->right->right = NULL;
                    que[rear++] = curr->right;
                }
            }
        }
    }
    return root;
}

int main() {
    int W[] = {1, -1, 2, 3};
    printf("%d", pathSum(createBinaryTree(W, 4)));
    return 0;
}

C++代码如下（含测试用例）：

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct TreeNode {
    int weight;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : weight(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : weight(x), left(nullptr), right(nullptr) {}
};

int dfs(TreeNode* root, int depth) {
    if (root == nullptr) {
        return 0;
    }
    if (root->left == nullptr && root->right == nullptr) {
        return root->weight * depth;
    }
    return dfs(root->left, depth + 1) + dfs(root->right, depth + 1);
}

int pathSum(TreeNode* root) {
    return dfs(root, 0);
}

TreeNode *createBinaryTree(vector<int> weights) {
    if (weights[0] == -1) {
        return nullptr;
    }
    const int n = weights.size();
    int i = 0;
    TreeNode *root = new TreeNode(weights[i++]);
    queue<TreeNode *> Q;
    Q.push(root);
    while (!Q.empty() && i < n) {
        TreeNode *node = Q.front();
        Q.pop();
        for (int j = 0; j < 2 && i < n; j++, i++) {
            if (weights[i] != -1) {
                if (j == 0) {
                    node->left = new TreeNode(weights[i]);
                    Q.push(node->left);
                } else {
                    node->right = new TreeNode(weights[i]);
                    Q.push(node->right);
                }
            }
        }
    }
    return root;
}

int main() {
    vector<int> W = {1, -1, 2, 3};
    cout << pathSum(createBinaryTree(W));
    return 0;
}

复杂度分析

• 时间复杂度： O(n) ，其中 n 是二叉树的结点数。
• 空间复杂度： O(n) ，为递归过程中栈的开销，平均情况下为 O(log⁡n) ，最坏情况下树呈现链状，为 O(n) 。

方法二：广度优先搜索

C代码如下（含测试用例）：

#include <stdio.h>
#include <stdlib.h>

struct TreeNode {
    int weight;
    struct TreeNode *left;
    struct TreeNode *right;
};

int pathSum(struct TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    struct TreeNode *curr = root;
    struct TreeNode** que = (struct TreeNode**)malloc(sizeof(struct TreeNode*));
    int front = 0, rear = 0;
    que[rear++] = curr;
    int wpl = 0;
    int depth = 0;
    while (front < rear) {
        int sz = rear - front;
        while (sz > 0) {
            curr = que[front++];
            if (curr->left == NULL && curr->right == NULL) {
                wpl += curr->weight * depth;
            }
            if (curr->left) {
                que[rear++] = curr->left;
            }
            if (curr->right) {
                que[rear++] = curr->right;
            }
            sz--;
        }
        depth++;
    }
    return wpl;
}

struct TreeNode *createBinaryTree(int *a, int n) {
    if (a[0] == -1) {
        return NULL;
    }
    int i = 0;
    struct TreeNode *root = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    root->weight = a[i++];
    root->left = NULL;
    root->right = NULL;
    struct TreeNode** que = (struct TreeNode**)malloc(sizeof(struct TreeNode*));
    int front = 0, rear = 0;
    struct TreeNode *curr = root;
    que[rear++] = curr;
    while (front < rear && i < n) {
        curr = que[front++];
        for (int j = 0; j < 2 && i < n; j++, i++) {
            if (a[i] != -1) {
                if (j == 0) {
                    curr->left = (struct TreeNode *)malloc(sizeof(struct TreeNode));
                    curr->left->weight = a[i];
                    curr->left->left = NULL;
                    curr->left->right = NULL;
                    que[rear++] = curr->left;
                } else {
                    curr->right = (struct TreeNode *)malloc(sizeof(struct TreeNode));
                    curr->right->weight = a[i];
                    curr->right->left = NULL;
                    curr->right->right = NULL;
                    que[rear++] = curr->right;
                }
            }
        }
    }
    return root;
}

int main() {
    int W[] = {1, -1, 2, 3};
    printf("%d", pathSum(createBinaryTree(W, 4)));
    return 0;
}

C++代码如下（含测试用例）：

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct TreeNode {
    int weight;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : weight(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : weight(x), left(nullptr), right(nullptr) {}
};

int pathSum(TreeNode* root) {
    if (root == nullptr) {
        return 0;
    }
    queue<TreeNode *>Q;
    TreeNode *curr = root;
    Q.push(curr);
    int wpl = 0;
    int depth = 0;
    while (!Q.empty()) {
        int sz = (int)Q.size();
        while (sz > 0) {
            curr = Q.front();
            Q.pop();
            if (curr->left == nullptr && curr->right == nullptr) {
                wpl += curr->weight * depth;
            }
            if (curr->left) {
                Q.push(curr->left);
            }
            if (curr->right) {
                Q.push(curr->right);
            }
            sz--;
        }
        depth++;
    }
    return wpl;
}

TreeNode *createBinaryTree(vector<int> weights) {
    if (weights[0] == -1) {
        return nullptr;
    }
    const int n = weights.size();
    int i = 0;
    TreeNode *root = new TreeNode(weights[i++]);
    queue<TreeNode *> Q;
    Q.push(root);
    while (!Q.empty() && i < n) {
        TreeNode *node = Q.front();
        Q.pop();
        for (int j = 0; j < 2 && i < n; j++, i++) {
            if (weights[i] != -1) {
                if (j == 0) {
                    node->left = new TreeNode(weights[i]);
                    Q.push(node->left);
                } else {
                    node->right = new TreeNode(weights[i]);
                    Q.push(node->right);
                }
            }
        }
    }
    return root;
}

int main() {
    vector<int> W = {1, -1, 2, 3};
    cout << pathSum(createBinaryTree(W));
    return 0;
}

复杂度分析

• 时间复杂度： O(n) ，其中 n 是二叉树的结点数。
• 空间复杂度： O(n) ，队列中的元素不超过 n 个。

考察在给出具体模型时，数据结构的应用。该题很多考生乍看之下以为是网络的题目，其实题本身并没有涉及太多的网络知识点，只是应用了网络的模型，实际上考察的还是数据结构的内容。 

(1)图中给出的是一个简单的网络拓扑图，可以抽象为无向图。
【评分说明】
只要考生的答案中给出与图含义相似的描述，例如“网状结构”、“非线性结构”等，同样给分。
(2)链式存储结构的如下图所示

其数据类型定义如下：(3 分)

typedef struct{
    unsigned int ID, IP;
}LinkNode;  //Link 的结构
typedef struct{
    unsigned int Prefix, Mask;
}NetNode;  //Net 的结构
typedef struct Node{
    int Flag;  //Flag=1 为 Link;Flag=2 为 Net
    union{
        LinkNode Lnode;
        NetNode Nnode
    }LinkORNet;
    unsigned int Metric;
    struct Node *next;
}ArcNode;  //弧结点
typedef struct HNode{
    unsigned int RouterID;
    ArcNode *LN_link;
    Struct HNode *next;
}HNODE;  //表头结点

对应题 42 表的链式存储结构示意图如下。(2 分) 

【评分说明】
①若考生给出的答案是将链表中的表头结点保存在一个一维数组中 (即采用邻接表形式)，同样给分。
②若考生给出的答案中，弧结点没有使用 union 定义，而是采用两种不同的结构分别表示 Link 和 Net，同时在表头结点中定义了两个指针，分别指向由这两种类型的结点构成的两个链表，同样给分。
③考生所给答案的弧结点中，可以在单独定义的域中保存各直连网络 IP 地址的前缀长度，也可以与网络地址保存在同一个域中。
④数据类型定义中，只要采用了可行的链式存储结构，并保存了题目中所给的 LSI 信息，例如将网络抽象为一类结点，写出含 8 个表头结点的链式存储结构，均可参照①~③的标准给分。
⑤若考生给出的答案中，图示部分应与其数据类型定义部分一致，图示只要能够体现链式存储结构及题 42 图中的网络连接关系（可以不给出结点内细节信息），即可给分。

(3)计算结果如下表所示。(4 分)

【评分说明】
①若考生给出的各条最短路径的结果部分正确，可酌情给分。
②若考生给出的从 R1 到达子网 192.1.x.x 的最短路径及代价正确，但不完全符合代价不减的次序，可酌情给分。 

(1) 根据题 42 图，可以分析R1到达各个子网的路由

目的网络 192.1.1.0/24，为 R1 的直连网络，通过接口 E0 进行转发。

目的网络 192.1.5.0/24，使用 OSPF 路由选择协议，选择费用最短的路径，即 R1→R3→192.1.5.0/24，下一跳为 R3 地址为 10.1.1.10 的接口，通过接口 L1 进行转发。

目的网络 192.1.6.0/24，使用 OSPF 路由选择协议，选择费用最短的路径，即 R1→R2→192.1.6.0/24，下一跳为 R2 地址为 10.1.1.2 的接口，通过接口 L0 进行转发。

目的网络 192.1.7.0/24，使用 OSPF 路由选择协议，选择费用最短的路径，即 R1→R2→192.1.7.0/24，下一跳为 R2 地址为 10.1.1.2 的接口，通过接口 L0 进行转发。

可写出 R1 的路由表如下：

由于路由表中的路由项尽可能少，需要进行路由聚合，将下一跳地址相同的项进行聚合，即表中最后两项，将子网 192.1.6.0/24 和 192.1.7.0/24 进行聚合。

路由聚合可以找出需要聚合的网络的最长公共网络前缀。

将 192.1.6.0/24 和 192.1.7.0/24 低 16 位写成二进制形式，其中主机号部分用的位用 x 表示，每个 x 可以取 0 或 1。二进制位用红色表示。得到 192.1.00000110.xxxxxxxx 和 192.1.00000111.xxxxxxxx 。聚合后得到子网为 192.1.0000011x.xxxxxxxx 。前 23 位为网络号，主机号位全部取 0 得到网络地址 192.1.00000110.00000000 ，即 192.1.6.0。

因此，聚合后的网络为即 192.1.6.0/23。

最终可写出 R1 的路由表如下：

(2) 第一问。主机 192.1.1.130 属于子网 192.1.1.0/24，主机192.1.7.211 属于子网 192.1.7.0/24，当主机192.1.1.130向主机192.1.7.211发送一个TTL=64的IP分组时，使用 OSPF 路由选择协议，选择费用最短的路径，即192.1.1.130→R1→R2→R4→192.1.7.211，R1通过L0转发该IP分组。

第二问。每经过一个路由器，TTL 值就会减 1，该传输路径中要经过 3 个路由器，所以主机192.1.7.211 收到该 IP 分组时，TTL = 64 - 3 = 61。

(3) R1 连接 Internet 需要增加一条默认路由，即 0.0.0.0/0。所以题 42 表中 R1 的 LSI 需要增加一项的网络前缀 Prefix 为 0.0.0.0/0，度量 Metric 为 10。

(1) 计算机M采用32位定长指令字，即一条指令占4B，观察表中各指令的地址可知，每条指令的地址差为4个地址单位，指令1的地址为08048100H，指令2的地址为08048104H，指令长度和编址单位的比值为08048104H-08048100H=4H=4，所以M的存储器编址单位是4B/4=1B，即该计算机按字节编址。

(2) 根据题目条件，编译时变量sum和i分别分配在寄存器R1和R2中。常量N在寄存器R6中，数组A的首地址在寄存器R3中，数组中元素在内内存空间中连续存储。设初始时 sum = 0，N = 2，设A的首地址为08050000H，A数组元素类型大小为x字节，数组存放在堆空间中，数组元素在堆空间中按地址从小到大连续存储，所以A[0]首地址为08050000H，A[1]首地址为08050000H+x，A[2]首地址为08050000H+2x，以此类推。红色表示指令执行后写入寄存器的值。模拟代码段P的指令执行过程如下：

通过该过程的模拟，推出R4的内容为A[i]首地址或A[i]首地址距离A首地址的偏移，R5的内容为A[i]的值，根据R4的A[i]首地址的计算式，即 首地址首地址A[i]首地址=A首地址+4i ，等价于 首地址首地址A[i]首地址=A首地址+xi ，解得 x=4 ，即A数组元素类型大小为4字节。数组A中每个元素占4B=32bit。

这个推导过程非常麻烦，如果考场上没时间进行推理，由于这里是进行加法运算，常用的数据类型有 char、short、int、float和double，char用于字符串，剩余均可用于四则运算，short和double在408中出现通常与类型转换相关，只有int和float最常考，所以直接猜A中元素类型为int或float，在32位或64位计算机中，int或float大小为4B，数组A中每个元素占4B=32bit。

(3) 第一问。由表可知，bne (branch when not equal) 指令的机器代码为1446FFFAH，根据题目给出的指令格式，低16位的为OFFSET字段，所以该指令的OFFSET内容为FFFAH，用补码表示，[OFFSET]补=FFFAH=1111 1111 1111 1010B，[OFFSET]原= 1000 0000 0000 0110B= -6。

第二问。指令跳转PC自增一个指令字长的字长数，本题为4，从指令6的地址跳转到指令1的地址，08048100H = 08048114H + 4H + k×OFFSET，所以 ×OFFSET = -18H=-16-8=-24，OFFSET=-6，所以k=4，bne指令的转移目标地址计算公式为(PC)+4+4×OFFSET。

本题为2013年题44的变体，将该题的转移目标地址计算公式(PC)+2+2×OFFSET中的2修改为4，得到(PC)+4+4×OFFSET，即为这一问的答案。

(4) 第一问。因为指令2、3、4、6都与各自前一条指令发生数据相关，所以由于数据相关而发生阻塞的指令为指令2、3、4、6。

数据冒险：在一个程序中，下一条指令会用到当前指令计算的结果，此时这两条指令发生数据冲突。指令1和指令2，指令2和指令3，指令3和指令4，指令5和指令6均为写后读相关。由于M采用如下“按序发射、按序完成”的5级指令流水线，且硬件不采取任何转发措施，对于写后读相关，当前指令将数据写入寄存器后，下一条指令才能从该寄存器中读取数据；否则，先读后写，读取到的就是错误（旧）数据。因此只能进行阻塞，需要阻塞3个时钟周期。所以由于数据相关而发生阻塞的指令为指令2、3、4、6。

第二问。指令6进行分支预测，会发生控制冒险。

控制冒险：指令通常是顺序执行，但是遇到改变指令执行顺序的情况，例如执行转移、调用或返回指令时，会改变PC值，从而造成断流，引起控制冒险。指令6进行分支预测，判断结果为真就跳转指令1继续执行，指令6和指令1存在控制相关。由于M采用如下“按序发射、按序完成”的5级指令流水线，若不采用分支预测或其他任何优化方法，则对于分支预测指令，当前指令执行并访存后，下一条指令才能开始执行，因此只能进行阻塞，需要阻塞3个时钟周期。指令6进行分支预测，会发生控制冒险。

第三问。当前循环的指令5与下次循环的指令1虽然有数据相关，但由于

1. 指令5和指令6存在数据相关。由于M采用如下“按序发射、按序完成”的5级指令流水线，且硬件不采取任何转发措施，因此引起3个时钟周期阻塞；

2. 指令6是分支指令，指令6和指令1存在控制相关。分支指令的执行均引起3个时钟周期阻塞。

因而消除了该数据相关。

用NOP指令进行阻塞，模拟指令流水线如下：

(1) R2里装的是i的值，循环条件是i<N，N在寄存器R6中，(R6)=1000，即循环条件是i<1000，当i自增到不满足这个条件时跳出循环，程序结束，所以此时i的值为1000。

(2) Cache共有16块，每块32字节，所以Cache数据区的容量为16×32B=512B。根据题44(1)的结论，计算机按字节编址，Cache块占32B= 2^5B，块内偏移占5位。P共有6条指令，一条指令占4B，6条指令占6×4=24B，小于一个主存块大小32B，且程序段P起始地址为08048100H，指令1起始地址为08048100H，低5位全0，块内偏移为0，对应一个主存块的起始位置，6条指令连续存放，由此可知所有指令都在一个主存块内。读取指令1时会发生Cache缺失，所以将P所在的主存块调入Cache某一块，以后每次读取指令时，都能在指令Cache中命中。因此在1000次循环中，只会发生1次指令访问缺失，所以指令Cache的命中率为(1000×6-1)/(1000×6)=99.98%。

(3) 第一问。指令4为加法指令，即对应sum+=A[i]，当数组A中元素的值过大时，则会导致这条加法指令发生溢出异常；而指令2、5虽然都是加法指令，但它们分别为数组地址的计算指令和存储变量i的寄存器进行自增的指令，而i最大到达1000，所以它们都不会产生溢出异常。

第二问。只有访存指令可能产生缺页异常，因为数组A未调入主存，即第一次调用指令3时访问A[0]时产生缺页异常。需要访问磁盘一次。

第三问。因为数组A未调入主存，且数组A所有元素在同一页，并存储在磁盘同一个扇区。所以该程序仅需访盘一次，此后数组A的元素都在内存中，则不会导致访盘。每访问一次内存数据就会查TLB一次，第一次访问A[0]会先查一次TLB，然后产生缺页，处理完缺页中断后，会重新访问A[0]，此时又查TLB一次。所以A[0]需要访问两次TLB才能从TLB中获得，剩余元素A[1], A[2], ..., A[999]均可从TLB中获得，共访问TLB的次数是2×1+1×999=1001次。或每个元素均需要访问TLB一次，考虑第一次访问TLB但TLB缺失需要多要多访问TLB的一次，共访问TLB的次数是1×1000+1=1001次。

参考2009年题46，在带有TLB的请求分页管理系统中通过虚地址访问其对应的主存中的数据的过程总结如下：

文件物理结构就是典型的数据结构的应用。

(1) 第一问。若文件系统采用连续分配方式，则插入记录可能需要移动其他的记录块。文件F共有200条记录，要插入新记录作为第30条，而存储区前后均有足够的磁盘空间，且题目要求最少的访问磁盘块数（原因是访问磁盘块非常耗时），若移动第30条记录后面的记录，则需要移动170条记录，若移动第30条记录前面的记录，则需要移动29条记录，显然后一种策略是最优策略。第一步，将文件前29条记录依次前移一个位置，移动一条记录读取和写回磁盘各需访问一次磁盘块，这步操作需要访问磁盘块29×(1+1)=58次。第二步，插入新记录作为第30条，写入磁盘需要访问一次磁盘块，这步操作需要访问磁盘块1次。综上，完成上述插入操作最少需要访问58+1=59次磁盘块。

第二问。文件控制块一般应包括下列的文件属性信息：

• 文件标志和控制信息：包括指示标识一个文件的符号名（操作系统可以进行按名存取）、文件状态标志、文件引用计数等等。
• 文件逻辑结构信息：指示文件是流式文件还是记录式文件，是定长记录还是变长记录，记录数等。
• 文件物理结构信息：指示文件在外存上的存储位置，包括存放文件的设备名、文件在外存的起始盘块号、指示文件所占用的盘块数或字节数的文件长度。
• 文件使用信息：包括文件创建时间、上次一修改时间、当前使用信息等。
• 文件管理信息：包括文件的访问权限和保护级别等。

因为文件F的首个磁盘块发生移动，所以F的文件控制区的起始块号发生改变。因为文件F增加了一个磁盘块，所以F的文件控制区的文件长度发生改变。

(2) 第一问。若文件系统采用链接分配方式，插入记录并不用移动其他记录，只需要找到插入记录的直接前驱并修改该磁盘块的链接指针即可。第一步，找到第30条记录的直接前驱磁盘块即第29条记录所在的磁盘块，需要读文件的前29块的链接指针，每次读取需要访问一次磁盘块，这步要访问29×1=29次，第二步，修改该磁盘块的链接指针指向给第30条记录分配的磁盘块，每次写入需要访问一次磁盘块，这步要访问1次，第三步，插入新记录作为第30条，写入磁盘需要访问一次磁盘块，这步操作需要访问磁盘块1次。综上，完成上述插入操作需要访问29+1+1次磁盘块。

第二问。若每个存储块大小为1KB，其中链接指针占4B=32bit，则最多可以表示 2^32 个磁盘块位置，每个存储块除链接指针外可存放数据1KB-4B=1024B-4B=1020B，推出该文件系统支持的文件最大长度是1020B× 2^32 =4080GB。

这是典型的生产者和消费者问题，只对典型问题加了一个条件，只需在标准模型上新加一个信号量，即可完成指定要求。
设置四个变量mutex1、mutex2、empty和full，mutex1，用于一个控制一个消费者进程一个周期(10次)内对于缓冲区的控制，初值为1，mutex2用于进程单次互斥的访问缓冲区，初值为1，empty代表缓冲区的空位数，初值为0，full代表缓冲区的产品数，初值为1000，具体进程的描述如下：

semaphore mutex1=1;
semaphore mutex2=1;
semaphore empty=0;
semaphore full=0;
producer(){
    while(1){
        生产一个产品;
        P(empty);             //判断缓冲区是否有空位
        P(mutex2);            //互斥访问缓冲区
        把产品放入缓冲区;
        V(mutex2);            //互斥访问缓冲区
        V(full);              //产品的数量加1
    }
}

consumer(){
    while(1){
        P(mutex1)                    //连续取10次
        for(int i = 0; i <= 10; ++i){
            P(full);                //判断缓冲区是否有产品
            P(mutex2);              //互斥访问缓冲区
            从缓冲区取出一件产品;
            V(mutex2);              //互斥访问缓冲区
            V(empty);               //腾出一个空位
            消费这件产品;
        }
        V(mutex1)
    }
}

【评分说明】
①信号量的初值和含义都正确给2分。
②生产者之间的互斥操作正确给1分；生产者与消费者之间的同步操作正确给2分；消费者之间互斥操作正确给1分。
③控制消费者连续取产品数量正确给2分。
④仅给出经典生产者-消费者问题的信号量定义和伪代码描述最多给3分。
⑤若考生将题意理解成缓冲区至少有10件产品，消费者才能开始取，其他均正确，得6分。
⑥部分完全正确，酌情给分。