方法一：递归式

这里分析代码需要用到递归式，递归式原则上为超纲内容，详见本题注解。

我们很容易根据算法代码写出递归式：

用递推的方式可以求解递归式： T(n)=T(n−1)+1=T(n−2)+1+1=⋯=n=O(n) 。

本题选B。

方法二：迭代

我们很容易理解代码的含义即求 n!=1×2×⋯×n 。

很容易将递归代码改写为迭代代码。

int fact(int n) {
    int f = 1;
    for (int i = 1; i <= n; i++) {
        f *= i;
    }
    return f;
}

该算法的时间复杂度为 O(n) 。

由于递归相比迭代多了一个压栈过程，所以一般情况下，迭代比递归更加高效。

本题选B。

方法一：模拟

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

转换过程中同时保存在栈中的操作符的最大个数是 5 。

本题选A。

方法二：观察表达式

其实我们没有必要老老实实模拟整个流程，只需要观察表达式即可，保存在栈中的操作符数量最大，则未计算的操作数嵌套最深，即最内层括号中最后一个操作数，很容易找到这个操作数 d ，观察前面与 d 相关的操作，也是没有能够输出的操作，这些操作都暂存在栈中，我们依次分析：

为了区别外层括号和内层括号，外层括号加粗。

• 受 d 直接影响未能输出的操作符为 + ，补充需要和 d 进行 + 计算的操作数 c ；
• 受 c+d 直接影响未能输出的操作符为 ( ；
• 受 (c+d 直接影响未能输出的操作符为 ( ；
• 受 ((c+d 直接影响未能输出的操作符为 ∗ ，补充需要和 ((c+d 进行 ∗ 计算的操作数 a ；
• 受 a∗((c+d 直接影响未能输出的操作符为 − ，此时已经到达最外层。

受 d 直接或间接影响未能输出的操作符在中缀表达式中依次为 −∗((+ ，越靠近栈顶的优先级越高，总计 5 个操作符。

本题选A

参考答案：A

答案解析：考查树的遍历、及由遍历序列确定二叉树的树形。

前序序列和后序序列不能唯一确定一棵二叉树，但可以确定二叉树中结点的祖先关系：当两个结点 的前序序列为 XY 与后序序列为 YX 时，则 X 为 Y 的祖先。考虑前序序列 a,e,b,d,c、后序序列 b,c,d,e,a， 可知 a 为根结点，e 为 a 的孩子结点；此外，a 的孩子结点的前序序列 e,b,d,c、后序序列 b,c,d,e，可知 e 是 bcd 的祖先，故根结点的孩子结点只有 e。本题答案为 A。

已知某二叉树的前序遍历序列和后序遍历序列，能构造的二叉树不一定唯一。

前序遍历是“根左右”遍历，后序遍历是“左右根”遍历。

第一轮递归：从前序遍历序列中取出第一个元素作为二叉树的根结点，从后序遍历序列中取出最后一个元素作为二叉树的根结点，这两个元素一定相同，否则无法构造二叉树，本题均为a。

第二轮递归：从前序遍历序列未处理的子串中取出第一个元素作为二叉树的左子树的根结点，从后序遍历序列未处理的子串中取出最后一个元素作为二叉树的右子树的根结点，这两个元素不一定相同。如果相同，说明有一个子树为空，本题均为e，也就是根结点只有一个孩子结点e，e可以随机分配在左子树或者右子树。

到这里没必要继续递归执行了，本题只要求出根结点的孩子结点即可。

本题选A。

方法一：递推

本题默认叶结点高度为 1 ，采用归纳法思路，从高度为 1 的平衡二叉树进行递推，假设左子树比右子树高。

构造高度为3的平衡二叉树时，左子树为高度为2的平衡二叉树，右子树为高度为1的平衡二叉树。

设高度为 n 的平衡二叉树结点数为 Cn ，可得递推式： Cn=Cn−1+Cn−2+1 。

递推计算出 C6=20 。

本题选B。

参考答案：C

答案解析：考查不同存储结构的图遍历算法的时间复杂度。

广度优先遍历需要借助队列实现。邻接表的结构包括：顶点表；边表（有向图为出边表）。当采用邻接表存储方式时，在对图进行广度优先遍历时每个顶点均需入队一次（顶点表遍历），故时间复杂度为O(n)，在搜索所有顶点的邻接点的过程中，每条边至少访问一次（出边表遍历），故时间复杂度为 O(e)，算法总的时间复杂度为 O(n+e)。

解答：

方法一：推理

用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，若对顶点按照矩阵下标进行编号，也就是只有从编号小的顶点往编号大的顶点的有向边，没有从编号大的顶点往编号小的顶点的有向边，也就是该有向图不可能存在环，既然没有环，也就是一定存在拓扑序列。由于没有具体的有向图，无法判断其拓扑序列是否唯一。

本题选C。

方法二：举例

可以构造如图矩阵，画出有向图。

该有向图有两个拓扑序列，拓扑序列不唯一。

本题选C。

方法一：推理

模拟完整的Dijkstra算法过程，初始点集 S 为空。

本题选C。

方法二：贪心

暴力找最短路径，算出最终的距离数组，如表格中最后一行所示。

按照距离从小到大输出顶点。

本题选C。

参考答案：A

答案解析：考查最小生成树、及最小生成树算法的性质。

对于 I，最小生成树的树形可能不唯一（这是因为可能存在权值相同的边），但是代价一定是唯一的，I 正确。对于 II，如果权值最小的边有多条并且构成环状，则总有权值最小的边将不出现在某棵最小生成树中，II 错误。对于 III，设 N 个结点构成环，N-1 条边权值相等，则从不同的顶点开始普里姆算法会得到 N-1 中不同的最小生成树，III 错误。对于 IV，当最小生成树唯一时（各边的权值不同），普里姆算法和克鲁斯卡尔算法得到的最小生成树相同，IV 错误。

参考答案：D

答案解析：考查 B-树的删除操作。

对于上图所示的 3 阶 B-树，被删关键字 78 所在结点在删除前的关键字个数=1=é3/2ù-1，且其左兄弟结点的关键字个数=2≥é3/2ù，属于“兄弟够借”的情况，则需把该结点的左兄弟结点中最大的关键字上移到双亲结点中，同时把双亲结点中大于上移关键字的关键字下移到要删除关键字的结点中，这样就达到了新的平衡，如下图所示。

参考答案：A

答案解析：考查各种内部排序算法的性质。

对于Ⅰ，简单选择排序每次选择未排序列中的最小元素放入其最终位置。对于Ⅱ，希尔排序每次是对划分的子表进行排序，得到局部有序的结果，所以不能保证每一趟排序结束都能确定一个元素的最终位置。对于Ⅲ，快速排序每一趟排序结束后都将枢轴元素放到最终位置。对于Ⅳ，堆排序属于选择排序，每次都将大根堆的根结点与表尾结点交换，确定其最终位置。对于Ⅴ，二路归并排序每趟对子表进行两两归并从而得到若干个局部有序的结果，但无法确定最终位置。

题目里出现了一个新概念，折半插入排序，本质还是插入排序，遵守插入排序的规则。

折半插入排序插入元素时采用的是折半查找的方式，直接插入排序插入元素时采用的是顺序查找的方式。

折半查找的时间复杂度为 O(log⁡n) ，顺序查找的时间复杂度是 O(n) ，都是基于比较的查找算法。

折半插入排序和直接插入排序元素之间的比较次数可能不同。

插入排序的排序的总趟数、元素的移动次数取决于待排序序列。

插入排序使用辅助空间的数量恒为 O(1) 。

本题选D。

本题为一道小学应用题， 工作量速度时间工作量=速度×时间 ，可以类比 路程速度时间路程=速度×时间 。

设初始时，CPU运行时间为 t1 ，速度为 v1 ，I/O运行时间为 t2 ，速度为 v2 。

提速后，CPU运行时间为 t1′ ，速度为 v1′ ，I/O运行时间为 t2′ ，速度为 v2′ 。

根据题意，初始时，CPU运行时间 t1=90 ，I/O运行时间 t2=100−90=10 。CPU工作量不变，有 v1t1=v1′t1′ ，CPU速度提升50%，有 v1′=1.5v1 。I/O工作量不变，有 v2t2=v2′t2′ ，I/O速度不变，有 v2′=v2 。求 t1′+t2′ 。

本题选D。

参考答案：B

解析：将一个 16 位 unsigned short 转换成一个 32 位的 unsigned int，新表示形式的所有附加位都用 0 进行填充。X 的 16 进制表示为 FFFA，所以 y 的十六进制表示为 0000FFFA。

x=65530=65536−6=216−1−5=FFFFH−5H=FFFAH 。

unsigned short转unsigned int，高位补0，y=x=0000FFFAH。

本题考察float的取值范围，float最大值为 (2−2^−23)×2^127=2^128−2^104 。

如果忘记了float的最大值，首先排除float的特殊表示。

• 当 E=0 且 M=0 时，表示 0 。
• 当 E=0 且 M≠0 时，表示非规格化数（下溢数）。
• 当 E=255 且 M=0 时，表示 ∞ 。
• 当 E=255 且 M≠0 时，表示 NAN。

然后构造出float的最大值，符号位 S=0 ，阶码 E=254 ，尾数 M 所有位全1，float的值为 (−1)^S×1.M×2^(E−127)=(1+1−2^−23)×2^(254−127)=(2−2^−23)×2^127=2^128−2^104 。

本题选D。

这道题考点很多，是一道非常经典的考题。

考点一：编址单位

分为按字编址和按字节编址，在32位和64位计算机中，基本数据类型大小如下

若按字节编址，则一个数据类型占的地址单元数等于其字节数。

考点二：边界对齐

以字节为单位的边界对齐，也称字节对齐，数据在存储时需要被放置在内存地址的倍数上，比如数据类型的大小为4个字节，那么它需要被存放在地址是4的倍数的位置上。数据按边界对齐存储是一种优化技术，通过调整数据在内存中的存储位置，可以提高计算机系统的性能和效率。

边界对齐后，结构体大小为其大小最大成员变量大小的整数倍。

根据边界对齐的定义，record变量的首地址为0xC008，从首地址开始，按顺序从低地址到高地址依次放入a、b和c这3个成员变量，模拟过程如下：

考点三：大端方式和小端方式

大端方式(Big Endian)：数据低位保存在高地址中，数据高位保存在低地址中。大端序和人的书写顺序一致。

小端方式(Little Endian)：数据低位保存在低地址中，数据高位保存在高地址中。

以一个16位（2字节）整数0x1234为例，它在大端方式和小端方式下的存储方式如下：

大端方式存储：高字节0x12存储在低地址，低字节0x34存储在高地址。

小端方式存储：低字节0x34存储在低地址，高字节0x12存储在高地址。

在实际应用中，不同的计算机体系结构和操作系统可能采用不同的字节序。例如，x86架构的计算机一般使用小端方式，而网络传输通常使用大端方式。

record.a=273=0x 00 00 01 11，采用小端方式存放数据，可以画出如下布局：

0xC008中内容为0x11，record.c的地址为0xC00E。

本题选D。

闪存的信息可读可写，但写入操作相对读取操作来说较慢。写入操作需要先擦除整个闪存块的数据，然后再进行写入操作。这个擦除和写入的过程需要一定的时间，所以写入速度较读取速度慢。选项A错误。

闪存是一种基于半导体技术的存储器，其存储单元由MOS（Metal-Oxide-Semiconductor）管组成，也被称为闪存晶体管。选项B正确。

闪存是一种非易失性存储器，意味着即使在失去电源的情况下，存储在闪存中的信息仍然不会丢失。选项C正确。

闪存可以通过随机访问方式进行读取和写入操作，因此可以用作计算机的外部存储器，例如固态硬盘（SSD）和闪存驱动器（USB闪存驱动器）等。选项D正确。

本题选A。

本题考察了Cache映射方式和替换策略。

Cache有4个行，采用2路组相联映射方式，有 4/2=2^1 组，组号占1位，因为计算机按字编址且块大小为1个字，所以主存地址低1位为组号，剩余高位为主存字块标记，这里主存地址最大为 

所有元素都被映射到组0，因为采用2路组相联映射，每组只有2行，组内采用全相联映射，置换算法为LRU，模拟过程如下：

命中次数为1。

本题选A。

答案解析：C，字段直接编码就是把微命令多个段，段的数目等于互斥类的数目。因此这里分为5个段，每段里要留一个离散状态表示自己没命令。所以7个微命令对应3位，3个微命令对应2位，12个微命令对应4位，5个微命令对应3位，6个微命令对应3位，共15位。

操作控制字段釆用字段直接编码法，将微命令字段分成若干个小字段，互斥类微命令可组合在同一字段。根据微命令字段分段的原则：1. 互斥性微命令分在同一段内，相容性字段分在不同段内。2. 每个字段留出一个状态，表示本字段不发出任何微命令。

操作控制字段至少有  位，其中 m 表示互斥类数量， ni 表示第 i 个互斥类的微命令数量，本题有5个互斥类，分别包含7、3、12、5和6个微命令，计算结果为 ⌈log⁡(7+1)⌉+⌈log⁡(3+1)⌉+⌈log⁡(12+1)⌉+⌈log⁡(5+1)⌉+⌈log⁡(6+1)⌉=15 。

本题考察突发（猝发）传输，指在同一行中相邻的存储单元连续进行数据传输的方式，只要指定起始地址和突发长度，控制器就会依次自动对后面相同数量的存储单元进行读/写操作，而不需要控制器连续提供列地址。

总线的时钟频率为100MHz，得时钟周期为10ns，总线宽度为32位。因为每传输一个地址或数据占用一个时钟周期，所以传输起始地址需要10ns，每个时钟周期可传输32位数据，传输128位数据需要128/32×10ns=40ns，总共需要10ns+40ns=50ns。

本题选C。

USB总线支持即插即用和热插拔功能。这意味着外设可以在系统运行时插入或拔出，并且系统会自动检测和配置新插入的设备。A正确。

USB总线可以使用级联方式连接多个外设，通过USB集线器（hub）实现。一个USB集线器可以提供额外的USB端口，使多个外设可以同时连接到计算机或其他主机设备上。B正确。

USB总线是一种通信总线，它使用标准化的连接器和协议，可以连接各种不同类型的外设，例如鼠标、键盘、打印机、摄像头、存储设备等。C正确。

USB总线是一种串行总线，数据位按照顺序一个接一个地传输，不能同时传输2位数据。通过使用串行传输，USB总线可以在相对较低的成本和资源占用情况下提供高速的数据传输。USB总线的数据传输速率可以根据USB设备的版本和类型而有所不同。USB 1.1或更早版本的标准传输速率为1.5 Mbps（低速模式）和12 Mbps（全速模式）。然而，USB 2.0引入了高速模式，其传输速率可达480 Mbps。此外，USB 3.0、USB 3.1和USB 3.2等更高版本的标准可以提供更快的数据传输速率，达到5 Gbps、10 Gbps甚至20 Gbps。因此，USB总线的数据传输率可以是相当高的。D前半句错误，后半句正确，D错误。

本题选D。

I/O接口与CPU之间的I/O总线有数据线、控制线和地址线。控制线和地址线是单向传输的，从CPU传送给I/O接口，数据线用于在计算机系统的CPU和I/O接口之间传输数据和命令。以下是给出的选项的解释：

Ⅰ正确。命令字是一组位模式，用于控制I/O接口和外部设备的操作。它包含指示特定操作（例如读、写、复位）以及相关参数的信息。这些命令字将通过数据线从CPU传输到I/O接口。

Ⅱ正确。状态字是一组位模式，用于指示I/O接口的当前状态和条件。它可以包括设备空闲、数据传输完成、错误状态等信息。这些状态字也通过数据线从I/O接口传输回CPU。

Ⅲ正确。中断类型号是一个用于标识特定中断类型的数值。当外部设备需要处理器的处理或发生了特定的事件时，会触发相应的中断。每个中断类型都对应一个唯一的中断类型号。中断控制器或操作系统会将该中断类型号发送给CPU，以便CPU能够识别并执行相应的中断处理程序。中断类型号也通过数据线传送给CPU。

综上，Ⅰ、Ⅱ、Ⅲ正确。

本题选D。

在响应外部中断的过程中，中断隐指令完成的操作包括：①关中断，②保护断电，③引出中断服务程序（形成中断服务程序入口地址并送PC），所以只有Ⅰ、Ⅲ正确。Ⅱ中的保存通用寄存器的内容是进入中断服务程序后首先进行的操作。

本题选B。

【答案】C

【解析】本题的关键是对“在用户态发生"（与上题的“执行”区分）的理解。对于A，系统调用是操作系统提供给用户程序的接口，系统调用发生在用户态，被调用程序在核心态下执行。对于B，外部中断是用户态到核心态的“门”，也发生在用户态，在核心态完成中断过程。对于C ，进程切换属于系统调用执行过程中的事件，只能发生在核心态；对于D ，缺页产生后，在用户态发生缺页中断，然后进入核心态执行缺页中断服务程序。

本题考察“在用户态发生”，而非“在用户态执行”。

A错误。系统调用是由用户态程序主动发起的请求，用于请求操作系统提供特权操作或资源访问权限。用户态程序可以通过系统调用接口向操作系统发起请求并执行相应的内核函数。

B错误。外部中断是由外部设备或事件触发的中断请求，可能发生在用户态。外部中断通常在内核态进行处理。

C正确。进程切换是操作系统调度器根据调度策略从一个运行的进程切换到另一个进程的操作。用户态程序是无法直接调用进程切换的，程序只能通过系统调用接口向操作系统发送某些请求，如fork、exec、yield等，然后由操作系统内核在内核态中处理这些请求，处理请求的过程中可能需要进行进程切换。进程切换涉及到修改和管理进程的上下文信息，包括保存和恢复寄存器状态、切换页表、更新进程控制块等操作。

D错误。缺页指的是程序访问的内存页不在物理内存中，需要通过页表映射和磁盘交换等机制从磁盘加载到内存中才能继续执行。当用户态程序访问一个缺页时，处理器会触发缺页异常，并由操作系统在内核态进行缺页处理。

本题选C。

【答案】B

【解析】子程序调用只需保存程序断点，即该指令的下一条指令的地址；中断调用子程序不仅要保存断点（PC的内容），还要保存程序状态字寄存器（PSW）的内容。在中断处理中,最重要的两个寄存器是PC和 PSWR。

中断处理需要保存的内容通常包括程序计数器（保存当前指令的地址）、程序状态字寄存器（保存标志位和其他与程序状态相关的信息）和所需保留的通用寄存器（包括一些通用数据寄存器和通用地址寄存器），以保护现场并确保在中断处理完成后能够正确地恢复原来的执行状态。

子程序调用需要保存的内容通常包括程序计数器（保存当前指令的地址）、栈指针（保存当前栈的位置）以及所需保留的通用寄存器（包括一些通用数据寄存器和通用地址寄存器），以确保在子程序执行完毕后能够正确返回到调用者，并保护调用者的数据。

综上，中断处理一定会保存而子程序调用不需要保存其内容的是程序状态字寄存器。

本题选B。

A错误，B正确。非连续分配技术则可以将虚拟地址空间中的不同部分映射到内存或外存的任意位置。根据所用的存储器映像算法，虚拟存储器管理方式主要有段式、页式、和段页式三种。

C和D错误。虚拟存储区的容量与物理主存大小无关，而受限于计算机的地址结构和可用磁盘容量。

本题选B。

用户程序发出磁盘 I/O 请求后，系统的处理流程是用户程序→系统调用处理程序→设备驱动程序→中断处理程序。四个步骤分别对应用户级I/O软件、设备无关软件、设备驱动程序、中断处理程序。

本题选A。

先将表格转化为已分配资源、尚需资源、可用资源三栏的形式。进程Pi尚需资源=进程Pi资源最大需求-进程Pi已分配资源，可用资源=资源总数-所有进程已分配资源之和。

使用银行家算法，保证可用资源大于或等于某进行尚需资源，该进程可以输出到序列，并回收该进程已分配资源。若所有进程均可被输出到序列，则存在安全序列，该输出序列为安全序列，否则不存在安全序列。

这道题安全序列比较多。

方法一：直接推导

根据第一步能够输出到序列的进程分情况讨论。

总共有3×3!+4!+4!=66种安全序列。

将选项逐一和安全序列进行比对，只有D正确。

本题选D。

方法二：用选项模拟

只有D能够模拟成功。

本题选D。

Ⅰ正确。若该文件的数据不在内存中，产生中断，该进程暂时进入睡眠等待状态（阻塞态）。这是因为操作系统需要将磁盘中的数据加载到内存中，这个过程可能需要一定的时间。当数据准备好后，操作系统会通知进程，使其从睡眠状态转变为可执行状态（就绪态），并继续执行读取操作。

Ⅱ正确。请求read系统调用会导致CPU从用户态切换到核心态。

Ⅲ错误。read系统调用的参数应包含文件的描述符 (file descriptor)，而不是文件的名称。read系统调用是用于从文件描述符 (file descriptor) 读取数据的操作。其参数包括：

1. 文件描述符 (file descriptor) ：read系统调用的第一个参数是标识要读取的文件的文件描述符。文件描述符是一个非负整数，由操作系统分配给打开的文件。通常，0表示标准输入 (stdin)，1表示标准输出 (stdout)，2表示标准错误 (stderr)，而其他大于2的整数表示其他打开的文件。
2. 缓冲区 (buffer)：read系统调用的第二个参数是指向用于存储读取数据的缓冲区的指针。读取的数据将被复制到该缓冲区中。缓冲区可以是一个字符数组或者任意类型的指针。
3. 大小 (size)：read系统调用的第三个参数是指定要读取的字节数。它表示缓冲区的大小，read系统调用将尝试从文件中读取指定数量的字节，并将其存储到缓冲区中。

读取操作的返回值是一个整数，表示实际读取的字节数。如果读取成功，返回值将是大于等于0的值；如果达到文件末尾，返回值将是0；而如果发生错误，返回值将是-1，并且错误码会被设置以指示特定的错误类型。

综上，仅Ⅰ、Ⅱ正确。

本题选A。

答案：B

由于P2比P1晚5ms到达，P1先占用CPU，作业运行的甘特图如下：

采用图(a)或图(b)的画法都可以。

选项A、B、D属于可以进行处理机调度的情况。

对于选项C，当进程处于临界区时，说明进程正在占用处理机，只要不破坏临界资源的使用规则，就不会影响处理机的调度。比如，通常访问的临界资源可能是慢速的外设（如打印机），若在进程访问打印机时，不能进行处理机调度，则系统的性能将非常差。

由于单处理器同一时刻只能处理一个进程。所以没有进程占用处理机的情况下进行处理机调度是没有任何问题的，A、B、D正确。

在很多情况下，进程访问临界区并非原子操作，如果要在进程处于临界区时进行处理机调度，执行中断处理即可，C错误。

本题选C。

【答案】A

【解析】在引入线程后，进程依然是资源分配的基本单位，线程是调度的基本单位，同一进程中的各个线程共享进程的地址空间。在用户级线程中，有关线程管理的所有工作都由应用程序完成，无须内核的干预，内核意识不到线程的存在。

A正确。不管系统是否支持线程，进程都是资源分配的基本单位。

B错误。线程是操作系统中调度的基本单位，它是进程内的执行流。线程共享进程的资源，包括内存空间、文件句柄和其他系统资源。正确表述应该是“进程是资源分配的基本单位，线程是调度的基本单位”。

C错误。不同类型的线程切换方式不同。系统级线程是由操作系统内核创建和管理的线程，其切换需要内核的支持。而用户级线程（也称为轻量级线程）是在用户空间实现的线程，其切换由用户级线程库负责，不需要内核的干预。

D错误。同一进程中的各个线程共享相同的地址空间，即它们在同一进程的上下文中执行，并访问相同的内存和其他资源。

A错误。通过对 I/O 请求进行重新排序，可以减少磁盘寻道时间和旋转延迟，以提高磁盘设备的 I/O 性能。

B正确。将磁盘分成多个分区可以在逻辑上组织和管理文件，但并不能直接改善磁盘设备的 I/O 性能。

C错误。预读是指在读取一个块时，预先读取相邻的块到缓存中，以供之后的读取请求使用，从而减少磁盘访问延迟。滞后写是指将写操作先缓存起来，并在合适的时机一次性批量执行，以减少频繁的磁盘写入操作。这些技术可以优化磁盘设备的 I/O 性能。

D错误。通过合理地安排文件的物理块分布，例如将频繁访问的文件块放置在磁盘上相邻的区域，可以减少寻道时间，提高磁盘设备的 I/O 性能。

本题选B。

ICMP (Internet Control Message Protocol) 互联网控制消息协议，是在 IP 层上运行的协议，用于在 IP 网络上发送控制消息。这些消息通常用于诊断和报告有关数据包传输的问题。

A 错误。PPP (Point-to-Point Protocol) 点对点协议，是一种数据链路层协议，用于通过串行连接（例如电话线、光纤等）在两个节点之间进行数据通信。

B 正确。IP (Internet Protocol) 互联网协议，在 TCP/IP 体系结构中为网际层协议。直接为 ICMP 提供服务的协议。ICMP 是建立在 IP 协议之上的，用于发送控制消息。

C 错误。UDP (User Datagram Protocol) 用户数据报协议，在 TCP/IP 体系结构中为传输层协议。提供面向无连接的数据报服务。UDP 通常用于传输不需要可靠数据传输的应用，如 DNS 查询和音视频流媒体。

D 错误。TCP (Transmission Control Protocol) 传输控制协议，在 TCP/IP 体系结构中为传输层协议。提供面向连接的字节流服务。TCP 通常用于传输需要可靠数据传输的应用，如 HTTP 请求。

本题选 B。

A 错误。机械特性：指明接口所用接线器的形状和尺寸、引线数目和排列、固定和锁定装置等。

B 错误。功能特性：规定了接口信号的来源、作用以及其他信号之间的关系。即物理接口上各条信号线的功能分配和确切定义。物理接口信号般分为数据线、控制线、定时线和地线。

C 正确。过程特性：定义了再信号线上进行二进制比特流传输的一组操作过程，包括各信号线的工作顺序和时序，使得比特流传输得以完成。

D 错误。电气特性：指明在接口电缆的各条线上出现的电压的范围。

在物理层接口特性中，用于描述完成每种功能的事件发生顺序的是过程特性。

本题选 C。

有连接需要双方建立连接后才能进行数据交互。有连接的数据传输方式类似于打电话，

无连接不需要双方建立连接后才能进行数据交互。无连接的数据传输方式则类似于发送微信信息，不需要等待对方在线或回复，按下发送键后即可发送数据。

可靠服务是指网络具有纠错、检错、应答机制，能保证数据正确、可靠地传送到目的地。

不可靠服务是指网络只是尽量正确、可靠地传送，而不能保证数据正确、可靠地传送到目的地，是一种尽力而为的服务。

MAC 协议是一种无连接的、不可靠的数据传输服务，它负责处理数据帧在物理介质上传输的细节，但不保证数据的可靠交付。

本题选 A。

在后退 N 帧协议 (GBN) 中，发送方可以发送 N 个帧而无需等待确认。从发送方发送一个数据帧到发送方接收到接收方传来的确认帧为一个周期。

发送方发送一个数据帧的时延为 t1 ，传播时延为 τ=270 ms ，接收方发送一个确认帧的时延为 t2 ，因为接收方总是以与数据帧等长的帧进行确认，所以 t1=t2 ，传播时延为 τ=270 ms 。一个周期 T=t1+τ+t2+τ=2t1+2τ 。因为数据链路层采用后退 N 帧协议 (GBN) 传输数据，为使信道利用率达到最高，在一个周期内，发送方可以连续发送多个数据帧，将位于发送窗口中的帧全部发送出去。

根据题目条件，数据传输速率为 16 kbps，该数据数据传输速率过低，不属于正常的以太网传播速率范围，属于卫星链路数据传输速率范围，卫星链路的数据传输速率通常在几 kbps到 十几 kbps 之间，卫星链路支持全双工通信，即通信双方可以同时发送和接收数据。在 408 真题中，后退 N 帧协议 (GBN) 中默认采用全双工通信，即通信双方可以同时发送和接收数据。

一个周期内能发送的帧数为 T/t1=(2t1+2τ)/t1=2(1+τ/t1) ，题目要求帧序号的比特数至少为多少需要满足所有情况，即满足最坏情况。 在 τ 固定的情况下， t1 越小，可发送的帧数越大。因为 t1=l/C ，其中 l 为数据帧长度，范围是 128~512 字节， C 是数据传输速率，为 16 kbps， l 越小， t1 越小，取 l=128 B ，此时 t1=l/C=128 B/16 kbps=(128×8 bit)/(16×1000 bit/s)=64 ms 。因此一个周期内能发送的最大帧数为 T/t1=(2t1+2τ)/t1=2(1+τ/t1)=2(1+270 ms/64 ms)≈10.4 。

GBN 协议发送窗口大小 WT 满足 1<WT≤2^n−1 ，其中 n 是构成帧序号的比特数量，将 WT=⌈T/t1⌉=11 代入，解得 n=4 ，即帧序号的比特数至少为 4。

本题选 B。

I 正确。路由器负责运行路由协议并设置路由表来指示数据包该如何转发。

II 正确。路由器会根据网络的情况进行流量控制，包括拥塞时的数据包的合理丢弃。

III 错误。IP 路由器会对收到的 IP 分组头进行差错校验，即重新计算该 IP 分组头的校验和，与该 IP 分组头的头部校验和字段进行比对，检查是否一致。如果发现错误则丢弃该分组。III 的前半句正确。IP 路由器工作在 TCP/IP 体系结构中的网际层，该层不负责可靠传输，无法确保传输的 IP 分组不丢失。III 的后半句错误。确保传输的 IP 分组不丢失是端到端的任务，在 TCP/IP 体系结构中通常由传输层的 TCP 协议来完成。

IV 正确。路由器根据目的 IP 地址来决定将数据包转发到哪个输出线路上。

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

本题选 C。

ARP (Address Resolution Protocol) 地址解析协议，是根据 IP 地址获取 MAC 地址的一个 TCP/IP 协议。

A 正确。根据 IP 地址查询 MAC 地址是 ARP 协议的功能。

B 错误。根据 MAC 地址查询 IP 地址是 RARP 协议的功能。RARP (Reverse Address Resolution Protocol) 反向地址解析协议，将局域网中某个主机的 MAC 地址转换为 IP 地址。

C 错误。根据域名查询 IP 地址是 DNS 协议的功能。DNS (Domain Name System) 域名系统，是互联网的一项服务。它作为将域名和 IP 地址相互映射的一个分布式数据库，能够使人更方便地访问互联网。根据域名查询 IP 地址需要进行正向 DNS 查询。

D 错误。根据 IP 地址查询域名是 DNS 协议的功能。反向 DNS 查询 (Reverse DNS lookup) 可以在命令行中使用 nslookup 命令实现。

本题选 A。

要确定向特定子网发送广播分组的目的地址，需要使用该子网的广播地址。子网广播地址为该子网的网络地址加上该子网主机位全部为 1 的情况。

该 IP 地址的子网掩码为 255.255.252.0，写成二进制形式为 1111 1111 1111 1111 1111 1100 0000 0000，前 22 位全 1 为网络号，后 10 位全 0 为主机号。

将 IP 地址 180.80.77.55 和子网掩码 255.255.252.0 按位与运算，得到子网 180.80.76.0/22。

子网 180.80.76.0/22 前 22 位为网络前缀，将 180.80.76.0/22 后 10 位写成二进制形式，其中主机号部分用的位用 x 表示，每个 x 可以取 0 或 1。二进制位用红色表示。得到 180.80.010011xx.xxxxxxx 。将将主机位全取1，得到该子网的广播地址 180.80.01001111.11111111 ，即 180.80.79.255。

本题选 D。

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

POP3 (Post Office Protocol version 3) 邮局协议第3版，它是用于接收电子邮件的标准协议。当你用邮件客户端以从邮件服务器上下载邮件时，它通常会使用 POP3 协议。

根据该过程的描述，

阶段①用户1发送邮件到邮件服务器，可通过 SMTP 协议传输。

阶段②邮件服务器发送邮件到用户2的邮件服务器，可通过 SMTP 协议传输。

阶段③用户2从自己的邮件服务器接收邮件，通常会使用 POP3 或 IMAP 协议。

综上所述，可以选择 SMTP、SMTP、POP3 作为阶段①、②、③分别使用的应用层协议。

本题选 D。

本题同时对多个知识点进行了综合考查。对有序表进行两两合并考查了归并排序中的 Merge()函数；对合并过程的设计考查了哈夫曼树和最佳归并树。外部排序属于大纲新增考点。
1）对于长度分别为 m，n 的两个有序表的合并，最坏情况下是一直比较到两个表尾元素，比较次数为 m+n-1 次。故，最坏情况的比较次数依赖于表长，为了缩短总的比较次数，根据哈夫曼树（最佳归并树）思想的启发，可采用如图所示的合并顺序。 

根据上图中的哈夫曼树，6个序列的合并过程为：
第1次合并：表A与表B合并，生成含有45个元素的表AB；
第2次合并：表AB与表C合并，生成含有85个元素的表ABC；
第3次合并：表D与表E合并，生成含有110个元素的表DE；
第4次合并：表ABC与表DE合并，生成含有195个元素的表ABCDE；
第5次合并：表ABCDE与表F合并，生成含有395个元素的最终表。

由上述分析可知，最坏情况下的比较次数为：第1次合并，最多比较次数=10+35-1=44；第2次合并，最多比较次数=45+40-1=84；第3次合并，最多比较次数=50+60-1=109；第4次合并，最多比较次数=85+110-1=194；第5次合并，最多比较次数=195+200-1=394。
故，比较的总次数最多为：44+84+109+194+394=825 

2）各表的合并策略是：在对多个有序表进行两两合并时，若表长不同，则最坏情况下总的比较次数依赖于表的合并次序。可以借用哈夫曼树的构造思想，依次选择最短的两个表进行合并，可以获得最坏情况下最佳的合并效率。 

【1）2）评分说明】 ①对于用类似哈夫曼树（或最佳归并树）思想进行合并，过程描述正确，给5分。按其他策略进行合并，过程描述正确，给3分。 ②正确算出与合并过程一致的总比较次数，给2分。若计算过程正确，但结果错误，可给1分。 ③考生只要说明采用的是类似哈夫曼树（或最佳归并树）的构造方法作为合并策略，即可给3分。如果采用其他策略，只要能够完成合并，给2分。

1）顺序遍历两个链表到尾结点时，并不能保证两个链表同时到达尾结点。这是因为两个链表的长度不同。假设一个链表比另一个链表长k个结点，我们先在长链表上遍历k个结点，之后同步遍历两个链表，这样就能够保证它们同时到达最后一个结点。由于两个链表从第一个公共结点到链表的尾结点都是重合的，所以它们肯定同时到达第一个公共结点。算法的基本设计思想：
①分别求出str1和str2所指的两个链表的长度m和n；
②将两个链表以表尾对齐：令指针p、q分别指向str1和str2的头结点，若m>=n，则使p指向链表中的第m-n+1个结点；若m<n，则使q指向链表中的第n-m+1个结点，即使指针p和q所指的结点到表尾的长度相等。 
③反复将指针p和q同步向后移动，并判断它们是否指向同一结点。若p和q指向同一结点，则该点即为所求的共同后缀的起始位置。 
2）算法的C语言代码描述： 

LinkNode *Find_1st_Common(LinkList str1,LinkList str2){
    int len1=Length(str1),len2=Length(str2);
    LinkNode *p,*q;
    for(p=str1;len1>len2;len1--)  //使p指向的链表与q指向的链表等长
        p=p->next;
    for(q=str2;len1<len2;len2--)  //使q指向的链表与p指向的链表等长
        q=q->next;
    while(p->next!=NULL&&p->next!=q->next){ //查找共同后缀起始点
        p=p->next;  //两个指针同步向后移动
        q=q->next;
    }
    return p->next;  //返回共同后缀的起始点
}

【1）2）的评分说明】 ①若考生所给算法实现正确，且时间复杂度为O(m + n)，可给12分；若算法正确，但时间复杂度超过O(m + n)，则最高可给9分。
②若在算法的基本设计思想描述中因文字表达没有非常清晰反映出算法思路，但在算法实现中能够清晰看出算法思想且正确的，可参照①的标准给分。
③若算法的基本设计思想描述或算法实现中部分正确，可参照①中各种情况的相应给分标准酌情给分。
④参考答案中只给出了使用C语言的版本，使用C++/JAVA语言的答案视同时用C语言。
3）时间复杂度为：O(len1 + len2)或O(max(len1,len2))，其中len1、len2分别为两个链表的长度。
【3）的评分说明】 若考生所估计的时间复杂度与考生所实现的算法一致，可给1分。 

(1) 第一问，因为CPU主频为80MHz，CPI为4，所以平均每秒CPU执行的指令数为80M/4=20M，即MIPS数是20。

第二问，因为平均每条指令访存1.5次，平均每秒CPU执行的指令数为20M，Cache的命中率为99%，所以平均每秒Cache缺失次数为20M×1.5×(1-99%)=0.3M。

第三问，在Cache缺失的情况下，Cache需要和主存进行块交换，因为主存与Cache之间交换的块大小为16B，平均每秒交换0.3M次，所以为满足CPU的访存要求，主存带宽至少达到16B×0.3M/s=4.8MB/s。

(2) 第一问，因为在Cache缺失的情况下访问主存时，存在0.0005%的缺页率，根据(1)结果，平均每秒Cache缺失次数为0.3M，所以平均每秒产生的缺页中断次数为0.3M×0.0005%=1.5。

第二问，考察周期挪用方式，周期挪用是指利用CPU不访问存储器的那些周期来实现DMA操作，此时DMA可以使用总线而不用通知CPU也不会妨碍CPU的工作。在这种方法中，每当I/O设备发出DMA请求时，I/O设备便挪用或窃取总线占用权一个或几个主存周期，而DMA不请求时，CPU仍继续访问主存。

因为存储器总线宽度为32位，所以每传送32位数据，磁盘控制器发出一次DMA请求，平均每秒产生的缺页中断次数为1.5，页面大小为4KB，所以每秒发出的DMA请求次数至少是1.5×4KB/4B=1.5× 2^10=1536。注意，当K、M、G、T修饰字节或比特时分别表示 2^10 、 2^20 、 2^30 、 2^40 ，当K、M、G、T修饰字节或比特相关的速率时分别表示 10^3 、 10^6 、 10^9 、 10^12 。

(3) 第一问，CPU和DMA控制器同时要求使用存储器总线时，DMA优先级更高。

第二问，因为如果DMA请求得不到及时响应，I/O传输数据可能会丢失。

(4) 因为主存采用四体低位交叉存储模式，四体低位交叉存储为流水线四体并行。又因为存储器总线宽度为32位，工作时每1/4个存储周期启动一个体，则每个存储周期最多（四体并行时）可以传输32bit/(1/4)=16B，又因为每个体的存储周期为50ns，所以最大带宽是16B/50ns=320MB/s。

1）x的机器码为[x]补=1111 1101 1111B，即指令执行前(R1)=FDFFH，右移1位后为1111 1110 1111 1111B，即指令执行后(R1)=FEFFH。（2分）
【评分说明】仅正确写出指令执行前的(R1)可给1分。
2）至少需要4+(5 - 1)=8个时钟周期数。（2分）
3）I₃的ID段被阻塞的原因：因为I₃与I₁和I₂都存在数据相关，需等到I₁和I₂将结果写回寄存器后，I₃才能读寄存器内容，所以I₃的ID段被阻塞。（1分）
I₄的IF段被阻塞的原因：因为I₄的前一条指令I₃在ID段被阻塞，所以I₄的IF段被阻塞。（1分）
4）因2*x操作有左移和加法两种实现方法，故x=x*2+a对应的指令序列为
I1  LOAD  R1，[x]
I2  LOAD  R2，[a]
I3  SHL  R1  //或者  ADD  R1，R1
I4  ADD  R1，R2
I5  STORE  R2，[x]
【评分说明】指令正确给2分；其他正确答案同样给分；部分正确，酌情给分。
这5条指令在流水线中执行过程如下图所示。（3分） 

故执行 x=x*2+a 语句最少需要 17 个时钟周期。（2分）

方法一：增加标记位

为了方便讨论，驻留集的页表中每个记录增加标记位，表示本轮该页面是否被访问，若该页面被访问，则标记位为1，否则标记位为0。这样每次访问某页只需要将该页的页表项中的访问位设为1，每次扫描将访问位为1的页表项的访问位修改为0，将访问位为0的页表项的页框回收。

初始时系统空闲页框链表中页框号依次为32、15、21、41。进程P依次访问的<虚拟页号，访问时刻>是：<1, 1>、<3, 2>、<0, 4>、<0, 6>、<1, 11>、<0, 13>、<2, 14>。模拟完整过程如下：

方法二：仿照LRU算法

仿照LRU算法，通过移动链表结点调整结点访问优先级。用蓝色标记页框链表中本轮被访问过的页框，黄色标记页框链表中本轮未被访问过的页框，所有黄色结点构成空闲页框链表，所有蓝色结点构成驻留集。这样每次访问某页只需要将该页被分配的页框号移动到链表尾，并标记为蓝色，每次扫描将页框链表中所有结点恢复成黄色。

初始时系统空闲页框链表中页框号依次为32、15、21、41。进程P依次访问的<虚拟页号，访问时刻>是：<1, 1>、<3, 2>、<0, 4>、<0, 6>、<1, 11>、<0, 13>、<2, 14>。模拟完整过程如下：

注：题45图(a)和题45图(b)中空闲页框链表中结点的括号内数字表示最近一次页框号被分配的页号。

(1) 访问<0, 4>时，对应的页框号是21。

初始时进程驻留集为空，系统空闲页框链表中页框号依次为32、15、21、41，时刻4是第一轮的第三次访问，且访问的页号与前两次均不同。而0页对应的页框为空闲链表中的第三个空闲页框号是21。

(2) 访问<1, 11>时，对应的页框号是32。

第三轮初始时系统空闲页框链表中页框号依次为41、32(1)、15(3)，括号内数字表示最近一次页框号被分配的页号，时刻11是第三轮的第一次访问，而且访问页面1之前被分配的页框号为32，将页框32重新放入驻留集中。

(3) 访问<2, 14>时，对应的页框号是41。

第三轮初始时系统空闲页框链表中页框号依次为41、32(1)、15(3)，括号内表示最近一次页框号分配的页号，时刻14是第三轮的第三次访问，页面2从来没有被访问过，因此从空闲页框链表中取出链表头的页框41，页框号为41。

(4) 该策略适合于时间局部性好的程序。

如果程序的时间局部性越好，从空闲页框链表中重新取回的机会越大，该策略的优势越明显。

(1) 第一问。因为该文件系统空间的最大容量为4TB，磁盘块大小为1KB，所以该文件系统中所能容纳的磁盘块总数为4TB/1KB= 2^32 。要完全表示所有磁盘块，索引项中的块号最少要占32bit=4B。

第二问。因为文件控制块 (FCB) 包含一个512B的索引表区，根据第一问结果，索引表项中块号最少占4字节，索引表区仅采用直接索引结构，所以索引表区最多能容纳512B/4B=128个索引项。又因为每个索引项对应一个磁盘块，磁盘块大小为1KB，所以该系统可支持的单个文件最大长度是128×1KB=128KB。

(2) 第一问。因为块数占2B=16bit，共可以表示 2^16 个磁盘块，磁盘块大小为1KB，所以预分配的连续存储空间大小为 2^16 ×1KB= 2^16 KB。又因为块号占6B，剩余504字节采用直接索引结构，直接索引区共504B/6B=84个索引项，磁盘块大小为1KB，所以直接索引区存储空间大小为84×1KB=84KB。综上，该系统可支持的单个文件最大长度=预分配的连续存储空间大小+直接索引区存储空间大小= 2^16 KB+84KB=65620KB。

第二问。根据(1)中第一问的结果，块数最少要占4B，才可表示4TB大小的文件长度，此时达到文件系统的空间上限，第0～7字节采用<起始块号，块数>格式表示文件创建时预分配的连续存储空间，总共8B，所以合理的起始块号和块数所占字节数分别为4、4，或3、5，或2、6，或1、7。

1）由于题47 - a表中1、3、4号分组的源IP地址（第13~16字节）均为192.168.0.8（c0a8 0008H），因此可以判定1、3、4号分组是由H发送的。（3分）
题47 - a表中1号分组封装的TCP段的FLAG为02H（即SYN=1，ACK=0），seq=846b 41c5H，2号分组封装的TCP段的FLAG为12H（即SYN=1，ACK=1），seq=e059 9fefH，ack=846b 41c6H，3号分组封装的TCP段的FLAG为10H（即ACK=1），seq=846b 41c6H，ack= e059 9ff0H，所以1、2、3号分组完成了TCP连接建立过程。（1分）
由于快速以太网数据帧有效载荷的最小长度为46字节，表中3、5号分组的总长度为40（28H）字节，小于46字节，其余分组总长度均大于46字节。所以3、5号分组通过快速以太网传输时进行了填充。（1分）
2）由3号分组封装的TCP段可知，发送应用层数据初始序号为seq=846b 41c6H，由5号分组封装的TCP段可知，ack为seq=846b 41d6H，所以5号分组已经收到的应用层数据的字节数为846b 41d6H - 846b 41c6H=10H=16。（2分）
【评分说明】其他正确解答，亦给2分；若解答结果不正确，但分析过程正确给1分；其他情况酌情给分。
3）由于S发出的IP分组的标识=6811H，所以该分组所对应的是题47 - a表中的5号分组。S发出的IP分组的TTL=40H=64，5号分组的TTL=31H=49，64 - 49=15，所以，可以推断该IP分组到达H时经过了15个路由器。（2分）
【评分说明】若解答结果不正确，但分析过程正确给1分；其他情况酌情给分。