本题选B。

解答：

将一棵树T转化为对应的二叉树BT，用的是“左孩子右兄弟”规则，即每个结点的左指针指向它的第一个孩子，右指针指向它在树中相邻的右兄弟。

方法一：推理

树T的后序遍历是先孩子后根，是一个自底向上的遍历顺序，对应二叉树BT中的一个从左到右的遍历顺序，即中序遍历。如果不能理解中序遍历是从左到右的，将二叉树中所有结点都向下进行投影，投影得到的序列就是中序遍历序列。

本题选B。

方法二：画图举例

当然方法一比较抽象，比较难想。我们可以直接画出一棵树，写出其后根遍历序列，将他转化为二叉树，观察这个后根遍历序列与二叉树的哪个遍历序列一致。

但是这个举例又非常有讲究，要具有区分度又不能太复杂，我们先尝试构造出一棵高度为2的满三叉树。

很明显，这里BT的中序遍历序列与T的后根遍历序列相同。

本题选B。

方法二：画图举例

如果记不得哈夫曼树和二叉树的性质怎么办？还是画图和举例，直接构造一棵哈夫曼树。

构造的哈夫曼树越简单越好。

很明显，新构造出的结点有 n−1 个， n+n−1=115 ，解得 n=58 。

本题选C。

解答：

方法一：推理

AVL树首先是二叉搜索树，遵循二叉搜索树的性质。

如果从 T1 中删除一个结点 z ，不考虑平衡调整。

从二叉搜索树 T1 中删除结点 z 分三种情况：

• 情况一：如果 z 没有孩子结点，直接删除， z 的父结点指向 z 的指针置为NIL。如图(a)所示。
• 情况二：如果 z 只有一个孩子结点，将这个孩子结点提升到 z 的位置，z 的父结点指向 z 的指针改为指向这个孩子结点。如图(b)所示。
• 情况三：如果 z 有两个孩子结点，找出 z 的后继 y ，让 y 占据 z 的位置， z 的右子树变为 y 的右子树，z 的左子树变为 y 的左子树。由于 y 是 z 的后继，所以 y 不可能有左孩子。
  • 如果 y 是 z 的右孩子，用 y 替换 z 。
  • 如果 y 在 z 的右子树中且 y 不是 z 的右孩子，先用 y 的右孩子结点替换 y ，然后用 y 替换 z 。

下面具体分情况讨论。

• 情况一：如果 z 没有孩子结点，直接删除。再插入 z 后， T1 与 T3 可能相同也可能不相同。
  • 如果删除 z 后仍为AVL树，不需要进行旋转调整，再插入 z 后， z 还在原来位置，此时 T3 与 T1 相同。
  • 如果删除 z 后仍为AVL树不平衡，需要进行旋转调整，此时AVL树结构发生变化，子树根结点发生变化，重新插入 z 的路径发生变化，插入后 z 所在子树不需要进行旋转调整，推理过程如下：删除 z 前最下面叶结点的深度为 2 ， z 的深度为 1 ， z 的父结点深度为 0 ，删除 z 后进行调整， z 的父结点和另一侧叶结点深度相同均为 1 ，再插入 z ，此时 z 的深度为 2 ，原先最下面叶结点深度为 1 ，符合AVL树性质，不需要进行旋转调整。此时 T3 与 T1 不相同。
• 情况二：如果 z 只有一个孩子结点，将这个孩子结点提升到 z 的位置，z 的父结点指向 z 的指针改为指向这个孩子结点。
  • 如果删除 z 后仍为AVL树且左右高度差为 0 ，不需要进行旋转调整，再重新插入 z 后， z 变为叶结点。T1 与 T3 一定不相同。
  • 如果删除 z 后仍为AVL树且左右高度差为 1 且 z 的父结点位于较高的一侧，再重新插入 z 后，仍为AVL树，不需要进行旋转调整， z 变为叶结点。T1 与 T3 一定不相同。
  • 如果删除 z 后仍为AVL树且左右高度差为 1 且 z 的父结点位于较低的一侧，再重新插入 z 后，AVL树不平衡，需要进行旋转调整，调整后 T1 与 T3 可能相同。

分析到情况二结果已经出来了，且情况三更加复杂，不需要进行继续分析。I正确，II错误，III错误。

本题选A。

方法二：画图举例

可以发现，严格按照性质分析结果过于复杂，还是画图举例：

I正确，II错误，III错误。

本题选A。

方法三：断言

下面提供秒题解法：

看到绝对词排除，II、III都有一定，太绝对，错误。

为什么敢玩的这么大胆，因为这里涉及AVL树的插入删除，其中包含二叉搜索树的插入和删除以及AVL树的旋转，情况非常复杂多变，过于绝对的选项大概率能够举出反例。

I正确，II错误，III错误。

本题选A。

本题选C。

方法二：贪心

下面提供秒题解法：

观察选项，B和C中都有12，二选一。

B和C的区别在哪里呢，B选项最早开始时间和最晚开始时间相等，C选项最早开始时间和最晚开始时间不相等。意味着什么？B选项表示的边在关键路径上，C选项表示的边在不关键路径上。

这里图中关键路径很容易找出来。即和  ，很明显，活动 d 不在关键路径上。

本题选C。

解答：

这道题就是考察知识点的联想与转化，想到了就很好做。

方法一：推理

第一步：将表达式转化为二叉树。

第二步：合并二叉树中的重复结点转化为图。

本题选A。

方法二：贪心

假设所有元素都可以复用，只需要统计表达式中有几种不同的元素和操作， �,�,+,×,÷ 总共5种。

本题选A。

方法三：选项排序 + 贪心

下面提供秒题解法：

题目要求“至少”，四个选项中A最小。

本题选A。

方法一：推理

我们依次分析每个选项：

数据规模肯定要考虑啊，一般情况下，数据规模小的时候用插入排序，数据规模大的时候用快速排序。

数据的存储方式肯定要考虑啊，数据用数组存还是用链表存，适用的排序算法完全不一样。

算法的稳定性肯定要考虑啊，一般情况下，要求稳定的排序用归并排序，没有要求稳定的排序用归并排序或用快速排序均可，优先考虑用快速排序。

数据的初始状态肯定要考虑啊，一般情况下，数据基本有序用直接插入排序。

本题选D。

方法二：断言

下面提供秒题解法：

这道题需要考虑吗？直接全选。

本题选D。

方法一：推理

我们先构造出插入所有元素后的散列表。

一般我们说计算成功查找长度需要统计的情况数量为散列表中元素数量。计算失败查找长度需要统计的情况数量为散列表中槽位数量。

但是这里命题组挖坑了，散列函数式模7的，但是散列表的长度为11，实际上剩下的4个槽位是永远不可能散列到的。也就是这里计算失败查找长度需要统计的情况数量为散列函数中是模数。

可以计算出0-6号槽位的失败需要探测的次数，如下图所示。

本题选C。

方法二：观察选项

下面提供秒题解法：

观察选项，C和D中整数部分均为6，二选一，正确概率50%。

个人偏向凑整，因为命题组编写题目的时候数字都是凑好的，算出小数点你不慌吗？

本题选C。

本题选B。

解答：

方法一：计算 next 数组

第一步：计算出模式串的next数组。默认next数组是优化后的next数组。

本人自编口诀优化前的next数组：第一格负一，第二格零，前缀等于后缀取最长。

当然实际代码中很多人习惯用优化前的next数组求解，优化后的next数组中每个值为优化前的next数组中每个值加一。

本人自编口诀优化后的next数组：第一格零，第二格一，前缀等于后缀取最长再加一。

移动位数 = 已匹配字符数 - 失配位置对应的匹配值（优化前next数组） = 5 - 2 = 3。模式串向后移动3格，重新进行匹配，这次匹配成功。

移动位数 = 失配位置 - 失配位置对应的匹配值（优化后next数组） = 6 - 3 = 3。模式串向后移动3格，重新进行匹配，这次匹配成功。

或 j 指针跳转指向模式串第 next[j] 个字符重新与主串第 i 个字符进行比较，next[6] = 3 ， j 指针跳转到模式串第3个字符的位置。

第二步：遍历主串对模式串进行匹配。

第一次匹配在主串第六个位置出现失配，找到之前匹配的子串为abaab，最长相同前缀与后缀为ab，将前缀的ab移动到后缀ab的位置。

或者查表next数组失配字符c，其next值为3，c位于模式串中第6位，移动位数 = 失配位置 - 失配位置对应的匹配值 （优化后next数组）= 6 - 3 = 3。模式串向后移动3格，重新进行匹配，这次匹配成功。

匹配9次，失配1次，总比较次数：9+1=10。

本题选B。

方法二：模拟

以下以 T = bacbababaabcbab 和 P = ababaca 为例。P 中绿色（含浅绿色和深绿色）表示对应字符匹配，红色表示对应字符失配，灰色表示未比较，浅绿色表示已匹配部分的最长的相等的前缀，深绿色表示已匹配部分的最长的相等的后缀。T 中黄色表示对应字符已经比较过，灰色表示未比较。

若已匹配部分为空，则 P 继续偏移一个位置，即偏移 s 增加 1。如图中第 1 趟、第 3 趟和第 4 趟匹配。

若已匹配部分不为空，已匹配长度为 x = i - 1，找出已匹配部分的最长的相等的前缀和后缀，（寻找已匹配部分的最长的相等的前缀和后缀时，从长度为 x - 1 的前缀和后缀开始判断更好。）该长度为 y，则下一次匹配从后缀开始位置开始，即偏移 s 增加 x - y。如图中第 2 趟和第 5 趟匹配。这步跳转用到了等式的传递性，因为 且  ，所以  。KMP 算法强大的地方就在这里，相比朴素字符串匹配算法，偏移 s 不仅实现了跳跃式增长，而且下一趟匹配中当前这趟的前缀部分的无需重新比较。

接下来进入下一轮匹配，从 P 中未比较的灰色部分开始继续比较，重复上述过程直到找到一个匹配或者比较超出 T 的范围为止。

该模拟方法无需计算 next 数组，next 数组本质就是基于这个原理进行计算的。此外，由于 next 数组有多种计算方式，不同计算方式结果不同，并不方便真题进行考察。

假设已经比较了 k 趟。

这里有个注意点，第 i 趟比较后匹配次数不是第 i 趟所有匹配的字符数，例如第 2 趟匹配中，前缀 ab 是无需重新比较的，所以第 2 趟比较后匹配次数 = 4，而不是 6，这一点一定要细心。

还有一种更快捷的计算方法：

后一种计算方式更为简便。

本题选B。

方法三：贪心

贪心找到最多匹配的情况，同样画出上图。虽然这个方法不严谨，好在本题足够简单，只有开始头指针对齐的一次和完全匹配的一次，总共出现一次失配。

匹配9次，失配1次，总比较次数：9+1=10。

本题选B。

解答：

这道题关键的难点在于理解一“趟”，就是递归的一轮，画出递归树，就是递归树中的一层。

第一步：

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

我们求出排好序后的序列为：2, 5, 12, 16, 28, 32, 60, 72，然后依次和四个选项进行比对，看有没有不符合要求的。

A中有两个落位。

B中有两个落位。

C中有三个落位。

D中有两个落位。

均符合。

第二步：

检查枢轴左边的元素是否都小于枢轴，右边元素是否都大于枢轴。

均符合。

到这里一般人就卡住了，找不到正确答案吗？

第三步：

画出递归树，明显选项D无法构造。

如果第一趟枢轴为12，第二趟左右两段分别递归产生新的枢轴，明显左边段枢轴缺失。

如果第一趟枢轴为32，第二趟左右两段分别递归产生新的枢轴，明显右边段枢轴缺失。

无法构造出递归树。

本题选D。

解答：

冯·诺依曼结构计算机的功能部件包括输入设备、输出设备、存储器、运算器和控制器，程序的功能都通过中央处理器（运算器和控制器）执行指令，A正确。

指令和数据以同等地位存于存储器内，形式上无差别，只在程序执行时具有不同的含义，B正确。

指令在地址访问，数据由指令的地址码指出，除立即寻址，数据均存放在存储器内，C错误。

在程序执行前，指令和数据需预先存放在存储器中，中央处理器可以从存储器存取代码，D正确。

本题选C。

解答：

方法一：二进制计算

unsigned short为16位无符号短整型，表示范围为0~65535，usi = 65535 = 1111 1111 1111 1111B。short为16位有符号短整型，表示范围为-32768~32767，用补码表示，[si]补=1111 1111 1111 1111B，[si]原=1000 0000 0000 0001B=-1。

本题选A。

方法二：十进制计算

unsigned short为16位无符号短整型，表示范围为0~65535，short为16位有符号短整型，表示范围为-32768~32767，两者表示范围大小均为65536，65535强转为short后溢出，负向偏移65536得65535-65536=-1。

本题选A。

解答：

当CPU执行指令时，如果需要访问的页面不在内存中，就会发生缺页。缺页是一种由CPU检测到的异常情况。A正确。

当发生缺页时，CPU会通过异常机制将控制权转移到操作系统提供的缺页处理程序。B正确。

缺页处理程序负责处理缺页异常，根据需要从外存（如磁盘）中读取缺失的页面到内存中，并更新相关的页表以反映新的页面位置。这个过程涉及到磁盘IO等相对较慢的操作。C正确。

当缺页处理完成后，控制权会从缺页处理程序返回给引发缺页的指令之后的指令，而不是直接回到下一条指令。CPU会重新执行引发缺页的指令，从而完成之前由于缺页而被中断的指令执行流程。D错误。

本题选D。

解答：

操作数采用基址寻址方式，EA=(BR)+A，基址寄存器BR的内容(BR)为F0000000H，形式地址A用补码表示为FF12H=1111 1111 0001 0010B，符号位为1，补齐至32位为FFFFFF12H，有效地址EA=(BR)+A=F000 0000H+FFFF FF12H=EFFF FF12H。因为计算机按字节编址，机器数1234 FF00H占4字节，所以1234 FF00H占4个地址单元；因为计算机采用大端方式编址，所以低位字节存放在字的高地址处。可以画出1234 FF00H的内存布局如下：

红色表示该操作数的LSB（最低有效字节），所在的地址是EFFF FF15H。

本题选D。

解答：

时钟脉冲信号通常由机器脉冲源发出，并经过整形和分频等处理形成规整的时钟信号。A正确。

时钟脉冲信号的宽度称为时钟周期，时钟周期的倒数为机器主频（即每秒钟发生的时钟周期数）。B正确。

时钟周期的确定通常以相邻状态单元之间的组合逻辑电路的最大延迟为基准，确保信号能够在时钟周期内稳定传播。C正确。

处理器的执行是由时钟信号驱动的，但处理器不一定在每个时钟脉冲信号到来时执行一条新的指令。处理器的指令执行需要考虑多个因素，包括指令的类型、操作数的取得、操作的完成等。处理器可能需要多个时钟周期才能完成一条指令的执行。因此，处理器的指令执行与时钟脉冲信号并不是一一对应的。D错误。

本题选D。

解答：

由于源操作数R[r1]采用寄存器寻址方式，源操作数M[R[r0]]采用寄存器间接寻址方式，因此在取数阶段需要用到通用寄存器组（包括寄存器r0和r1）和存储器。即需要I和III。

在执行阶段，两个源操作数相加需要用到算术逻辑单元，即需要II。

而指令译码器用于操作码字段进行译码，向控制器提供特定的操作信号，在取指阶段需要，在取数及执行阶段用不到。

综上，该指令在取数及执行过程中需要用到的是Ⅰ、Ⅱ和Ⅲ。

本题选B。

解答：

常考的数据冒险有：写后读（read after write, RAW）数据冒险、写后写（write after write, WAW）数据冒险、读后写（write after read, WRA）数据冒险、装入-使用（load-use）数据冒险等。

在按序发射，按序流动的流水线中，可能出现写后读（RAW）数据冒险和装入-使用（load-use）数据冒险。

A错误。I1和I3存在写后读数据冒险（read after write Data Hazard, RAW Data Hazard）：读取某数据操作必须在写入该数据操作之后执行，否则可能产生错误。这里I3读取R[s2]必须在I1写回R[s2]后执行，可以使用数据旁路解决。

B错误。I2和I3之间存在数据冒险，属于装入-使用数据冒险（load-use Data Hazard）：LOAD指令和随后使用LOAD指令所加载数据的后续指令之间存在的依赖关系，即使用某数据操作必须在装入该数据之后执行，否则可能产生错误。仅用转发线路无法解决I2和I3之间的数据相关问题，需要用转发技术结合装入-使用阻塞解决。原因在于I2的功能是从内存中取数，只有在M段结束时才能从主存中得到R[s3]的新值，即先装入后使用，但I3的EX段就要用到R[s3]，I3需要阻塞1个时钟周期，等到I2的M段结束之后，从I2的M→WB流水段寄存器中取到R[s3]的新值。

C正确。

D错误。I3和I4存在写后读数据冒险（read after write Data Hazard, RAW Data Hazard）：读取某数据操作必须在写入该数据操作之后执行，否则可能产生错误。这里I4读取R[s2]必须在I3写回R[s2]后执行，可以使用数据旁路解决。

采用硬件阻塞方式进行阻塞，并采用数据旁路技术，指令的执行过程如图(a)所示。仅采用硬件阻塞方式进行阻塞，指令的执行过程如图(b)所示。

本题选C。

解答：

计算机采用3通道存储器总线，存储器总线的工作频率为1333MHz，即1秒内传送1333M次数据，总线宽度为64位，即单条总线工作一次可传输8字节，因此存储器总线的总带宽为3×8B×1333MHz=31992MB/s≈32GB/s。

本题选B。

解答：

磁盘存储数据之前需进行格式化，将磁盘分成扇区，并写入信息，因此磁盘的格式化容量比非格式化容量小。A正确。

磁盘扇区中包含数据、地址和校验等信息。B正确。

磁盘存储器的最小读写单位为一个扇区，即磁盘按块存取。C错误。

磁盘存储器由磁盘控制器、磁盘驱动器和盘片组成。D正确。

本题选C。

解答：

方法一：通过时间计算

CPU主频为1GHz，所以CPU时钟周期为1ns，设备接口中的数据缓冲寄存器为32位，即一次中断可以传输4B数据，设备数据传输率为50KBps，每秒需要50KB/4B=12.5K次中断，每次中断开销为1000个时钟周期，即每次中断开销为1000×1ns=1μs，每秒中断需要的时间为12.5K×1μs=12.5ms，因此CPU用于该设备输入/输出的时间占整个CPU时间的百分比最多是12.5ms/1s=1.25%。

方法二：通过频率计算

设备接口中的数据缓冲寄存器为32位，即一次中断可以传输4B数据，设备数据传输率为50KBps，每秒需要50KB/4B=12.5K次中断，每次中断开销为1000个时钟周期，每秒中断需要的时钟周期数为12.5K×1000=12.5M，CPU主频为1GHz，即每秒的时钟周期数为1G，因此CPU用于该设备输入/输出的时间占整个CPU时间的百分比最多是12.5M/1G=1.25%。

本题选A。

解答：

Ⅰ正确。DMA传送前由设备驱动程序设置传送参数：在进行DMA传送之前，设备驱动程序负责设置传送参数，例如源地址、目标地址和传输长度等。这些参数将指导DMA控制器进行数据传送。

Ⅱ正确。数据传送前由DMA控制器请求总线使用权：在进行DMA传送之前，DMA控制器会向总线控制器（如总线控制器或内存控制器）请求总线的使用权。一旦获得总线使用权，DMA控制器将能够直接控制总线进行数据传输，而无需主处理器的干预。

Ⅲ正确。数据传送由DMA控制器直接控制总线完成：DMA控制器在获得总线使用权后，可以直接控制总线进行数据传输。它负责管理传输的数据、地址和传输方向，并在传输结束后释放总线的控制权。

Ⅳ正确。DMA传送结束后的处理由中断服务程序完成：一旦DMA传送完成，通常会触发一个DMA传输完成的中断。DMA控制器向CPU 发送中断请求，CPU执行中断服务程序做DMA结束处理。

综上，Ⅰ、Ⅱ、Ⅲ、Ⅳ都正确。

本题选D。

【答案】B

【解析】应用程序没有进行线程管理的代码，只有一个到内核级线程的编程接口，内核为进程及其内部的每个线程维护上下文信息，调度也是在内核中由操作系统完成的，A 正确。在多线程模型中，用户级线程和内核级线程的连接方式分为多对一、一对一、多对多， “操作系统为每个用户线程建立一个线程控制块”属于一对一模型，B 错误。用户级线程的切换可以在用户空间完成，内核级线程的切换需要操作系统帮助进行调度，因此用户级线程的切换效率更高，C 正确。用户级线程的管理工作可以只在用户空间中进行，因此可以在不支持内核级线程的操作系统上实现，D 正确。

【答案】C

【解析】当被阻塞进程等待的某资源（不包括处理机）可用时，进程将会被唤醒。I/O结束后，等待该I/O结束而被阻塞的有关进程会被唤醒，即 I 正确；
某进程退出临界区后，之前会因需要进入该临界区而被阻塞的有关进程会被唤醒，即 II 正确；
当前时间片用完后进入就绪队列等待重新调度，即由运行态变为就绪态，即 III 错误。

【答案】C

【解析】用户可以在用户态调用操作系统的服务，但执行具体的系统调用服务程序是处于内核态的，Ⅰ正确；设备管理属于操作系统的职能之一，包括对输入/输出设备的分配、初始化、维护等，用户程序需要通过系统调用使用操作系统的设备管理服务，II正确；操作系统不同，底层逻辑、实现方式均不相同，为应用程序提供的系统调用接口也不同，III错误；系统调用是用户在程序中调用操作系统提供的子功能，IV正确。

解答：

Ⅰ正确。位图是一种使用位表示磁盘块分配情况的数据结构。每个位对应一个磁盘块，位的值表示该磁盘块的分配状态（已分配或未分配）。

II错误。索引节点是在文件系统中用于表示和管理文件或目录的索引数据结构。

Ⅲ正确。空闲磁盘块链是一种使用链表来管理磁盘块分配的数据结构。链表中的每个节点表示一个空闲磁盘块，通过链接在一起形成一个链表，可以按顺序或随机方式分配空闲磁盘块。

Ⅳ正确。文件分配表是一种表格形式的数据结构，用于记录和管理文件在磁盘上的分配情况。每个表项对应一个磁盘块，表项的值表示所指向的下一个磁盘块的位置。

综上，仅Ⅰ、Ⅲ、Ⅳ正确。

本题选B。

答案：C
进程P1，P2依次创建后进入队列Q1 ，根据时间片调度算法的规则，进程P1，P2将依次被分配10ms的CPU时间，两个进程分别执行完一个时间片后都会被转入队列Q2，就绪队列Q2采用短进程优先调度算法，此时P1还需要20ms的CPU时间，P2还需要10ms的CPU时间，所以P2会被优先调度执行，10ms后进程P2执行完成，之后P1再调度执行，再过20ms后P1也执行完成。运行图表如下所示。

进程P1，P2的等待时间分别为图中的虚横线部分，平均等待时间=(P1等待时间+P2等待时间)/2=(20+10)/2，因此答案选C。

解答：

分段存储管理系统是一种操作系统中的内存管理方式，通过将程序和数据划分为不同大小的段 (segment)，并分配给它们特定的内存区域，来管理内存的使用。每个段都代表了程序或数据的逻辑单元，有自己的起始地址和长度。分段系统的一个突出优点，是易于实现段的共享，即允许若干个进程共享一个或多个分段，且对段的保护也十分简单易行。

A正确。当多个进程共享同一个段时，为了节省内存空间，物理内存中只需要保存一份该段的内容，而不是为每个进程都保存一份。

B错误。在分段存储管理系统中，每个进程都有自己的段表，段表中的段号是由该进程自己管理的。如果进程P1和P2共享段S，它们可以分别在它们的段表中有不同的段号来表示段S。实际上，共享段的段号可以不同，只要在段表中的其他属性（例如段的基地址、段的长度等）相同即可。这样可以确保进程通过不同的段号访问同一个共享段。

C正确。共享段表中的段表项会记录共享段S的相关信息，比如段号、段长度、共享权限等。P1和P2可以通过共享段表中的段表项来获取段S的描述信息，以便访问和使用共享段S。

D正确。当进程P1和P2都结束运行或者显式释放共享段S时，操作系统会检查共享段S的使用计数器或引用计数器。如果计数器的值为零，表示没有任何进程在使用该共享段，操作系统会将该段的内存空间回收。

本题选B。

解答：

LRU是Least Recently Used的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。

根据题意，模拟过程如下（红色表示未命中，蓝色表示未命中且置换，绿色表示命中）：

产生页置换的总次数是5。

本题选C。

解答：

Ⅰ正确。从一个或多个进程中抢占足够数量的资源，然后将他们分配给死锁进程，解除其死锁状态。

II正确。死锁的预防方法能确保系统不发生死锁。死锁的预防方法是在系统设计阶段采取措施，通过破坏死锁发生的四个必要条件（互斥条件、请求和保持条件、不剥夺条件和循环等待条件），来确保系统不会进入死锁状态。

Ⅲ错误。银行家算法是一种死锁避免算法，可以判断系统是否存在安全序列，无法判断系统是否处于死锁状态。

Ⅳ正确。在死锁状态下，存在循环依赖关系，每个进程都在等待其他进程释放资源，因此至少有两个或两个以上的进程处于阻塞状态，无法继续执行。

综上，仅Ⅰ、Ⅱ、Ⅳ正确。

本题选B。

解答：

虚拟地址20501225H= ，对应的页目录号是0010000001B=081H，页号是01 0000 0001B=101H。

本题选A。

解答：

首次适应算法：从空闲分区表的第一个表目起查找该表，把最先能够满足要求的空闲区分配给作业，这种方法的目的在于减少查找时间。

最佳适应算法：从全部空闲区中找出能满足作业要求的，且大小最小的空闲分区，这种方法能使碎片尽量小。

最差适应算法：它从全部空闲区中找出能满足作业要求的、且大小最大的空闲分区，从而使空闲链表中的结点大小趋于均匀。

循环首次适用算法：每次查找的起始位置是从上次查找位置的下一个位置开始，把最先能够满足要求的空闲区分配给作业。

当系统中存在多个不同大小的空闲分区时，如果选择最佳适应的方式去分配内存，会导致许多小的空闲分区被保留下来，而较大的分区被分割成较小的部分，从而增加了内存碎片的数量和总碎片的大小。相比而言，首次适应算法、最坏适应算法和循环首次适应算法相对来说更容易获得较大的连续空闲区，减少了内存碎片的发生。因此，最容易产生内存碎片的算法是最佳适应算法。

本题选C。

C

A

B

B

B

C

D

B

解答：

注意：题目中单链表带头结点，头结点不存储关键字。

思路一：开辟一个长度为 n 的辅助数组，将所有结点存入，然后直接操作数组下标，重新构建链表。该算法空间复杂度为 O(n) ，但是这里题目已经明确要求设计一个空间复杂度为 O(1) 的算法，所以不能使用。

所以本题只能使用一个原地算法。目前主流的解法如下：

寻找链表中点 + 反转链表 + 合并链表

目标链表即为将原链表的左半端和反转后的右半端合并后的结果。这样可以分为三步。

第一步：找到原链表的中点，本题为下中位数点  ，即第  个结点，为什么是找下中位数点，这道题将链表分成两段，左半段为  ，右半段为  ，这样能够满足当 n 为偶数时，左半段结点个数和右半段结点个数相等，当 n 为奇数时，左半段结点个数比右半段结点个数多 1。为什么要求当 n 为奇数时左半段结点个数比右半段结点个数多 1，因为第一个元素 a1 是左半段元素，这样交替后最后一个元素一定是左半段的元素，恰巧比右半段多出一个。

使用快慢指针可以方便找出链表中位于中位数位置的结点，该步时间复杂度 O(n) 。

第二步：将原链表的右半段反转。

反转链表有三种方法，递归法，迭代法，头插法。这三种方法中，迭代法是最优解。

这里使用迭代法实现链表的反转，该步时间复杂度 O(n) 。

第三步：将两条链表合并。

因为两链表长度相差不超过一，交叉合并，该步时间复杂度 O(n) 。

综上，该算法的时间复杂度为 O(n)+O(n)+O(n)=O(n) 。

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

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

typedef struct node {
    int data;
    struct node *next;
} NODE;

void reorderList(NODE* h) {
    NODE *p, *q, *r, *s;
    // 第一步：寻找h中间结点
    p = q = h;
    while (q->next != NULL) {
        p = p->next;
        q = q->next;
        if (q->next != NULL) {
            q = q->next;
        }
    }
    q = p->next;
    p->next = NULL;
    // 第二步：将链表后半段反转
    while (q != NULL) {
        r = q->next;
        q->next = p->next;
        p->next = q;
        q = r;
    }
    // 第三步：合并链表
    s = h->next;
    q = p->next;
    p->next = NULL;
    while (q != NULL) {
        r = q->next;
        q->next = s->next;
        s->next = q;
        s = q->next;
        q = r;
    }
}

NODE* createLinkedList(int *a, int n) {
    NODE* head = (NODE *)malloc(sizeof(struct node));
    NODE* tail = head;
    for (int i = 0; i < n; i++) {
        NODE* p = (NODE *)malloc(sizeof(struct node));
        p->data = a[i];
        p->next = NULL;
        tail->next = p;
        tail = tail->next;
    }
    return head;
}

int main() {
    int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    NODE* head = createLinkedList(a, 9);
    reorderList(head);
    NODE* curr = head;
    printf("head");
    while (curr != NULL) {
        printf("->%d", curr->data);
        curr = curr->next;
    }
    return 0;
}

说实话，标准答案的指针利用率非常高，缺点也很明显，可读性很差。

这道题实际上是三个基础算法的组合，本人把三段代码拆分三个方法。

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

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

typedef struct node {
    int data;
    struct node *next;
} NODE;

NODE* middleNode(NODE* head) {
    NODE* slow = head;
    NODE* fast = head;
    while (fast->next != NULL && fast->next->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

NODE* reverseList(NODE* head) {
    NODE* prev = NULL;
    NODE* curr = head;
    while (curr != NULL) {
        NODE* nextTemp = curr->next;
        curr->next = prev;
        prev = curr;
        curr = nextTemp;
    }
    return prev;
}

void mergeList(NODE* l1, NODE* l2) {
    NODE* l1_tmp;
    NODE* l2_tmp;
    while (l1 != NULL && l2 != NULL) {
        l1_tmp = l1->next;
        l2_tmp = l2->next;
        l1->next = l2;
        l1 = l1_tmp;
        l2->next = l1;
        l2 = l2_tmp;
    }
}

void reorderList(NODE* head) {
    if (head == NULL || head->next == NULL) {
        return;
    }
    NODE* mid = middleNode(head->next);
    NODE* l1 = head->next;
    NODE* l2 = mid->next;
    mid->next = NULL;
    l2 = reverseList(l2);
    mergeList(l1, l2);
}

NODE* createLinkedList(int *a, int n) {
    NODE* head = (NODE *)malloc(sizeof(struct node));
    NODE* tail = head;
    for (int i = 0; i < n; i++) {
        NODE* p = (NODE *)malloc(sizeof(struct node));
        p->data = a[i];
        p->next = NULL;
        tail->next = p;
        tail = tail->next;
    }
    return head;
}

int main() {
    int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    NODE* head = createLinkedList(a, 9);
    reorderList(head);
    NODE* curr = head;
    printf("head");
    while (curr != NULL) {
        printf("->%d", curr->data);
        curr = curr->next;
    }
    return 0;
}

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

#include <iostream>
using namespace std;

typedef struct node {
    int data;
    struct node *next;
} NODE;

NODE* middleNode(NODE* head) {
    NODE* slow = head;
    NODE* fast = head;
    while (fast->next != nullptr && fast->next->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

NODE* reverseList(NODE* head) {
    NODE* prev = nullptr;
    NODE* curr = head;
    while (curr != nullptr) {
        NODE* nextTemp = curr->next;
        curr->next = prev;
        prev = curr;
        curr = nextTemp;
    }
    return prev;
}

void mergeList(NODE* l1, NODE* l2) {
    NODE* l1_tmp;
    NODE* l2_tmp;
    while (l1 != nullptr && l2 != nullptr) {
        l1_tmp = l1->next;
        l2_tmp = l2->next;
        l1->next = l2;
        l1 = l1_tmp;
        l2->next = l1;
        l2 = l2_tmp;
    }
}

void reorderList(NODE* head) {
    if (head == nullptr || head->next == nullptr) {
        return;
    }
    NODE* mid = middleNode(head->next);
    NODE* l1 = head->next;
    NODE* l2 = mid->next;
    mid->next = nullptr;
    l2 = reverseList(l2);
    mergeList(l1, l2);
}

NODE* createLinkedList(int *a, int n) {
    NODE* head = new NODE();
    NODE* tail = head;
    for (int i = 0; i < n; i++) {
        NODE* p = new NODE();
        p->data = a[i];
        p->next = nullptr;
        tail->next = p;
        tail = tail->next;
    }
    return head;
}

int main() {
    int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    NODE* head = createLinkedList(a, 9);
    reorderList(head);
    NODE* curr = head;
    cout << "head";
    while (curr != nullptr) {
        cout << "->"<< curr->data;
        curr = curr->next;
    }
    return 0;
}

复杂度分析

• 时间复杂度： O(n) 。
• 空间复杂度： O(1) 。

解答：

⑴ 该队列应选择链式存储结构。由于入队时，允许增加队列占用空间，出队后，整个队列所占用的空间只增不减，链式存储方便开辟新的空间。出队元素所占用的空间可重复使用，所以构造成循环链表。只需要维护队头指针和队尾指针，同时每个结点维护属性 key记录该结点的关键字，就能保证入队操作和出队操作的时间复杂度始终保持为 O(1) 。

方法一： Q.front 指向结点存储队列中的关键字。

⑵ 设队列 Q 头指针为 Q.front ，队尾指针为 Q.rear 。

初始状态： Q.front 和 Q.rear 均指向一个空结点。如图(a)所示。

判断队空 IS-EMPTY 伪代码如下：

IS-EMPTY(Q)
    if Q.front == Q.rear
        return TRUE
    else return FALSE

判断队满 IS-FULL 伪代码如下：

IS-FULL(Q)
    if Q.front == Q.rear->next
        return TRUE
    else return FALSE

⑶ 第一个元素 1 入队后：如图(b)所示。

⑷ 入队操作和出队操作的基本过程：

入队操作 ENQUEUE 伪代码如下：

ENQUEUE(Q, x)
    Q.rear.key = x   // 加入x
    if IS-FULL(Q) == TRUE    // 如果队满，需要增加新空结点
        create a new node p
        Q.rear->next = p
        p->next = Q.front
    Q.rear = Q.rear->next

第二个元素 2 入队后：如图(c)所示。

出队操作 DEQUEUE 伪代码如下：

DEQUEUE(Q)
    if IS-EMPTY(Q) == TRUE
        error "queue is empty"    // 如果队空，报错
    else    
        p = Q.front
        Q.front = Q.front->next;
        return p.key;

队头元素 1 出队后：如图(d)所示。

方法二： Q.rear 指向结点存储队列中的关键字。

⑵ 设队列 Q 头指针为 Q.front ，队尾指针为 Q.rear 。

初始状态： Q.front 和 Q.rear 均指向一个空结点。如图(a)所示。

判断队空 IS-EMPTY 伪代码如下：

IS-EMPTY(Q)
    if Q.front == Q.rear
        return TRUE
    else return FALSE

判断队满 IS-FULL 伪代码如下：

IS-FULL(Q)
    if Q.front == Q.rear->next
        return TRUE
    else return FALSE

⑶ 第一个元素 1 入队后：如图(b)所示。

⑷ 入队操作和出队操作的基本过程：

入队操作 ENQUEUE 伪代码如下：

ENQUEUE(Q, x)
    if IS-FULL(Q) == TRUE    // 如果队满，需要增加新空结点
        create a new node p
        Q.rear->next = p
        p->next = Q.front
    Q.rear = Q.rear->next
    Q.rear.key = x   // 加入x

第二个元素 2 入队后：如图(c)所示。

出队操作 DEQUEUE 伪代码如下：

DEQUEUE(Q)
    if IS-EMPTY(Q) == TRUE
        error "queue is empty"    // 如果队空，报错
    else    
        Q.front = Q.front->next;
        return Q.front.key;

队头元素 1 出队后：如图(d)所示。

解答：

哲学家进餐问题有多种解决方案，主要有

方法一：至多只允许有n-1位哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够进餐，并在用毕时能释放出他用过的两只筷子，从而使更多的哲学家能够进餐。

semaphore count = n-1;    // 可进餐名额数量
semaphore chopsticks[n];   // 所有筷子资源的信号量
for (int i=0; i<n; i++) {
    chopsticks[i] = 1;
}
CoBegin
Process 哲学家i() {
    while (true) {
        思考;
        P(count);
        P(chopsticks[i]);    // 取左边筷子
        P(chopsticks[(i+1)%n]);    // 取右边筷子
        进餐;
        V(chopsticks[i]);    // 放回左边筷子
        V(chopsticks[(i+1)%n]);    // 放回右边筷子
        V(count);
    }
}
CoEnd

方法二：仅当哲学家的左、右两只筷子均可用时，才允许他拿起筷子进餐。

semaphore mutex = 1;   // 保证每个时刻只有一个哲学家取筷子的互斥信号量
semaphore chopsticks[n];   // 所有筷子资源的信号量
for (int i=0; i<n; i++) {
    chopsticks[i] = 1;
}
CoBegin
Process 哲学家i() {
    while (true) {
        思考;
        P(mutex);
        P(chopsticks[i]);    // 取左边筷子
        P(chopsticks[(i+1)%n]);    // 取右边筷子
        V(mutex);
        进餐;
        V(chopsticks[i]);    // 放回左边筷子
        V(chopsticks[(i+1)%n]);    // 放回右边筷子
    }
}
CoEnd

方法三：规定奇数号哲学家先拿他左边的筷子，然后再去拿右边的筷子，而偶数号哲学家则相反。

semaphore chopsticks[n];   // 所有筷子资源的信号量
for (int i=0; i<n; i++) {
    chopsticks[i] = 1;
}
CoBegin
Process 哲学家i() {
    while (true) {
        思考;
        if (i%2==1) {
            P(chopsticks[i]);    // 取左边筷子
            P(chopsticks[(i+1)%n]);    // 取右边筷子
        } else {
            P(chopsticks[(i+1)%n]);    // 取右边筷子
            P(chopsticks[i]);    // 取左边筷子
        }
        进餐;
        V(chopsticks[i]);    // 放回左边筷子
        V(chopsticks[(i+1)%n]);    // 放回右边筷子
    }
}
CoEnd

由于本题引入了新资源碗，每位哲学家必须取到一个碗和两侧的筷子后，才能就餐。

方法一

使用哲学家进餐问题的模板一：综合考虑碗的数量m和最大可进餐名额数量n-1，限制碗的数量为 min{m, n-1}，得到新的最大可进餐名额数量。本题适合采用方法一，伪代码如下：

semaphore bowls = min(n-1, m);    // 可用碗数量即可进餐名额数量
semaphore chopsticks[n];   // 所有筷子资源的信号量
for (int i=0; i<n; i++) {
    chopsticks[i] = 1;
}
CoBegin
Process 哲学家i() {
    while (true) {
        思考;
        P(bowls);
        P(chopsticks[i]);    // 取左边筷子
        P(chopsticks[(i+1)%n]);    // 取右边筷子
        进餐;
        V(chopsticks[i]);    // 放回左边筷子
        V(chopsticks[(i+1)%n]);    // 放回右边筷子
        V(bowls);
    }
}
CoEnd

方法二

使用哲学家进餐问题的模板二：仅当哲学家的左、右两只筷子和碗均可用时，才允许他拿起筷子进餐。这里需要引入互斥信号量，保证进餐请求能够按照顺序执行，根据银行家算法，对于任意一个请求序列，均存在安全序列，不会产生死锁。这里拿左、右两只筷子和碗的顺序不会影响结果的正确性。

semaphore bowls = m;    // 所有碗资源的信号量
semaphore mutex = 1;   // 保证每个时刻只有一个哲学家取筷子的互斥信号量
semaphore chopsticks[n];   // 所有筷子资源的信号量
for (int i=0; i<n; i++) {
    chopsticks[i] = 1;
}
CoBegin
Process 哲学家i() {
    while (true) {
        思考;
        P(mutex);
        P(bowls);    // 取碗
        P(chopsticks[i]);    // 取左边筷子
        P(chopsticks[(i+1)%n]);    // 取右边筷子
        V(mutex);
        进餐;
        V(chopsticks[i]);    // 放回左边筷子
        V(chopsticks[(i+1)%n]);    // 放回右边筷子
        V(bowls);    // 放回碗
    }
}
CoEnd

由于方法二会限制进餐请求的顺序，相比方法一降低了并行度。

方法三

使用哲学家进餐问题的模板三：规定奇数号哲学家先拿他左边的筷子，然后再去拿右边的筷子，而偶数号哲学家则相反。若 m≥n ，每个哲学家一定都能拿到碗，若 m<n ，则会对同时进餐的名额产生限制，要求拿到碗的哲学家才能去拿筷子。

semaphore bowls = m;    // 所有碗资源的信号量
semaphore chopsticks[n];   // 所有筷子资源的信号量
for (int i=0; i<n; i++) {
    chopsticks[i] = 1;
}
CoBegin
Process 哲学家i() {
    while (true) {
        思考;
        P(bowls);    // 取碗
        if (i%2==1) {
            P(chopsticks[i]);    // 取左边筷子
            P(chopsticks[(i+1)%n]);    // 取右边筷子
        } else {
            P(chopsticks[(i+1)%n]);    // 取右边筷子
            P(chopsticks[i]);    // 取左边筷子
        }
        进餐;
        V(chopsticks[i]);    // 放回左边筷子
        V(chopsticks[(i+1)%n]);    // 放回右边筷子
        V(bowls);    // 放回碗
    }
}
CoEnd

如果不使用上述方法，可能会产生死锁，在碗资源数不足的情况下，可能会出现一部分哲学家拿到筷子但拿不到碗，一部分哲学家拿到碗但拿不到筷子，举个例子，有A、B、C、D共4个哲学家，依次围坐在一张圆桌边，有4根筷子，2个碗，A、C各拿到2根筷子，B、D各拿到1个碗，4人均无法进餐，处于死锁状态。

解答：

(1) 因为该计算机系统中的磁盘有300个柱面，每个柱面有10个磁道，每个磁道有200个扇区，扇区大小为512B，所以磁盘的容量是300×10×200×512B= 3×10^5KB 。

(2) 因为每个柱面有10个磁道，每个磁道有200个扇区，每个簇包含2个扇区，所以每个柱面有10×200/2=1000个簇，柱面号默认从0开始编号，100260号簇位于⌊100260/1000⌋=100号柱面，60005号簇位于⌊60005/1000⌋=60号柱面，101660号簇位于⌊101660/1000⌋=101号柱面，110560号簇位于⌊110560/1000⌋=110号柱面。磁头在85号柱面上，最短寻道时间优先 (SSTF) 调度算法，总是访问距离当前柱面最近的柱面。模拟过程如下：

访问柱面的先后次序是100、101、110、60，对应访问簇的先后次序是100260、101660、110560、60005。

(3) 第一问。第 100530 簇在磁盘上的物理地址由其所在的柱面号、磁道号、扇区号构成。柱面号、磁道号、扇区号默认从0开始编号。

柱面号 = ⌊ 簇号/每个柱面的簇数 ⌋ = ⌊100530/1000⌋=100；

磁道号 = ⌊ (簇号 mod 每个柱面的簇数) / 每个磁道的簇数 ⌋ = ⌊(100530 mod 1000)/100⌋ = 5；

扇区号 = (簇号 mod 每个磁道的簇数) × 每个簇包含扇区数 = (100530 mod 100) × 2 = 60。

第二问。将簇号转换成磁盘物理地址的过程由磁盘驱动程序完成。

解答：

(1) 第一问。观察f1的C语言代码，可知f1(n)用递归方法计算n!，计算f(10)需要调用函数f1共10次。

第二问。执行第16行的指令会递归调用f1。

方法一：观察f1的汇编代码，第16行call f1，表示递归调用f1。

方法二：观察f1的指令地址，第16行跳转到第1行的地址00401000执行，表示从头开始执行f1。

(2) 第一问。观察f1的汇编语言代码，可知第12行jle (jump when less or equal) 指令是条件转移指令。结合f1的C语言代码分析可知，n<=1为真时跳转到else分支，n>1为真时执行if的第一个分支。因为n<=1不一定为真，所以该条件转移指令不一定会使程序跳转执行。

第二问。观察f1的汇编语言代码，可知

• 第16行call指令为递归调用f1，对应代码f1(n-1)，一定会使程序跳转执行。
• 第20行jmp (jump) 指令为无条件跳转指令，一定会使程序跳转执行。
• 第30行ret (return) 指令为返回指令，一定会使程序跳转执行。

(3) 第一问。第17行指令为第16行指令的下一条指令，第16行指令的虚拟地址为00401025H，指令内容为”E8 D6 FF FF FF“（从左到右为从低字节到高字节的内容），占5个字节，计算机M按字节编址，第16行指令占5个地址单元，所以第17行指令的虚拟地址为00401025H+5H=0040102AH。

第二问。已知第16行的call指令采用相对寻址方式，即目标地址=(PC)+偏移量，call指令的目标地址为00401000H，(PC)为第16行指令的下一条指令的虚拟地址，即17行指令的虚拟地址，根据第一问的结果，(PC)=0040102AH，所以偏移量=目标地址-(PC)=00401000H-0040102AH=FFFFFFD6H。

第三问。已知第16行的call指令的后4字节为偏移量，偏移量字段为“D6 FF FF FF”（从左到右为从低字节到高字节的内容），偏移量内容为FFFFFFD6H，低字节内容存储在低地址，可确定M采用小端方式。

(4) 第一问。因为f1返回值类型为int，int型数据占32位，int的表示范围为 −2^31∼2^31−1 ，即-2147483648~2147483647，f(13)=6 227 020 800大于32位int型数据可表示的最大值，因而f1(13)的返回值是一个发生了溢出的结果。

第二问。为使f1(13)能返可正确结果，可将函数f1的返回值类型改为具有更大表示范围的long long（或double或long double或float）。一般数值用int表示溢出情况下改为long long，因为int和long long都是整型。

注：6227020800= 1 0111 0011 0010 1000 1100 1100 0000 0000B，如果用浮点数表示，则二进制有效数值位至少有23位。因为float最多可以表示24位二进制有效数值位，所以转float不会出现精度丢失。

(5) 第一问，若乘积的高33位为非全0或非全1，则OF=1。C语言整型用补码表示，imul指令（带符号整数乘）使用的是补码一位乘法（Booth乘法）。补码一位乘法需要两个寄存器，按照题意，乘法器分为高32位和低32位，其中高32位存储在累加器 (Accumulator, ACC) 中，低32位存储在乘商寄存器 (Multiplier-Quotient Register, MQ) 中，初始时ACC存储部分积，部分积初始为0，MQ存储32位的乘数。执行Booth乘法结束后，高位和低位拼接起来为最终的64位乘积，但int只能表示32位，若不溢出，低31位为数值位，剩余高33位为1位符号位和32位符合扩展位，若乘积的高33位全0或全1，即32位符合扩展位与符号位相同，则不溢出，OF=0；反之，若乘积的高33位为非全0或非全1，即32位符合扩展位中存在某一位与符号位不同，则溢出，OF=1。

第二问。编译器应该在imul指令后加一条“溢出自陷指令”，使得CPU自动查询溢出标志OF，当OF=1时调出“溢出异常处理程序”。

溢出自陷指令 (Overflow Trap Instruction) 是一种处理整数运算溢出的机器指令。它通常由处理器提供，并用于捕捉和处理算术运算中发生的溢出错误。当执行一条溢出自陷指令时，处理器会检测当前的算术运算结果是否发生了溢出。如果发生了溢出，处理器会触发一个异常或中断，将控制权转移到相应的异常处理程序中。溢出自陷指令的目的是提供一种机制，用于检测和处理数值运算的溢出。当进行加法、减法、乘法等算术运算时，如果结果超过了数据类型能够表示的范围，就会发生溢出。溢出可能导致错误的计算结果和无效的程序行为，因此通过溢出自陷指令可以及时地进行检测和处理。

解答：

第一问。第1行指令和第30行指令的代码在同一页。

因为计算机M的主存地址为32位，釆用分页存储管理方式，虚拟地址格式为 虚页号|页内地址，页大小为4KB= 2^12B，根据上题，计算机M按字节编址，所以页内地址占低12位，虚页号占高32-12=20位。第1行指令地址为  ，第30行指令地址为  ，两者虚页号均为00401H，因此两条指令在同一页中。

第二、三、四问。组相联映射格式为  。若指令Cache有64行，采用4路组相联映射方式，Cache组数为64/4=16= 2^4 ，组号占中间4位，主存块大小为64B= 2^6B，根据题45，计算机M按字节编址，所以块内地址占低6位，在32位主存地址中，物理地址占32位，主存字块标记占高32-4-6=22位。所以物理地址0~5位为块内地址，6~9位为组号，10~31位为标记（tag）信息。

第五问。读取第16行call指令时，只可能在指令Cache第0组中命中。因为第16行指令地址为  ，页大小为4KB，虚拟地址和物理地址的最低12位完全相同，块内地址占6位，组号占4位，两者组合在一起占低10位，所以页内地址包含组号和块内地址。页内地址025H=  ，所以对应Cache组号为0000B=0。

【答案要点】

(1)设备1:路由器，设备2:以太网交换机，设备3:以太网交换机

(2)设备1的接口需要配置IP地址;设备1的IFI、IF2和IF3接口的IP地址分别是:192.168.1.254、192.168.1.1和192.168.1.65。

(3)R需要提供NAT服务

(4)主机H4会接收该数据报。