B
第一次：3+2= 5，S1：5，8，5（栈顶）；S2：*，-（栈顶）
第二次：8-5= 3，S1：5，3（栈顶）；S2：*（栈顶）
第三次：5*3= 15，S1：15；S2：空

这道题很简单，模拟计算过程就行，唯一要注意的是先弹出的是a，后弹出的b，且计算时b op a，b在前，a在后。审题务必仔细。

C
队列先进先出，按次序出队，按次序入栈，即按1,2,3,4,5,6依次入栈。C选项：3先出栈，则2比1先出栈。

方法一：模拟

A的操作顺序为①①②②①①③③。

B的操作顺序为②①①①①①③。

C无法找到合适的操作序列。

D的操作顺序为②②②②②①③③③③③。

本题选C。

方法二：单调性

由于只能通过栈改变序列中某子串单调性一次，所以输出序列中没有按照先进先出顺序出队的子串一定通过栈要被反转。

A中子串3, 4没有按序出队，被反转成4, 3，正确。

B中子串1没有按序出队，被反转成1，正确。

C中子串1, 2没有按序出队，但没有被反转，错误。

D中子串1, 2, 3, 4, 5, 6没有按序出队，被反转成6, 5, 4, 3, 2, 1，正确。

本题选C。

如果本题加大难度，输入序列为乱序，需要进行元素值和元素下标的一对一映射，写代码需要建立两个键值哈希表，一个键为元素值，值为元素下标，另一个键为元素下标，值为元素值。

C语言下标为0，按行优先存储。

方法一：画图

本题选A。

方法二：计算

也可以直接计算：

第一步：计算 m1,1 到 m6,6 的元素个数。

12+11+10+9+8+1=51

第二步：修正下标从0开始，需要减一。

51−1=50

本题选A。

A

方法一：推理

因为每个非叶结点都有2个子结点，所以二叉树T只有度为0和度为2的结点，可得：

n0=k

n0=n2+1

n=n0+n2

解得 n=2k−1 。

本题选A。

方法二：画图举例

一棵非空完全二叉树T的所有叶结点均位于同一层，且每个非叶结点都有2个子结点。可得这棵二叉树为满二叉树。

直接画出一个高度为3的满二叉树。

k=4,n=7 可得 n=2k−1 。

本题选A。

方法一：构造

按照题目条件构造哈夫曼树。

每次取最小的两个子树的根结点合并。过程如下图所示：

左指针标0，右指针标1，从根结点到叶结点的路径即为该字符的哈夫曼编码。

本题选A。

方法二：代入选项

从选项构造哈夫曼树，检查是否符合哈夫曼编码性质。

选项B中a的编码是d的编码的前缀，错误。

选项C中a的编码是b的编码的前缀，错误。

选项D构造出的哈夫曼树不符合WPL最小规则，错误。

但其实这样做可能更加麻烦，需要画出4棵哈夫曼树依次进行检查。

检查后只有A符合要求。

本题选A。

二叉排序树中序遍历序列单调递增序列。

中序遍历有两种方法，本人分别命名为投影法和环线法。

有 x1<x3<x5<x4<x2 。

本题选C。

补充一下二叉树前序遍历、中序遍历、后序遍历递归版的特征：

• 前序遍历顺序为“根左右”，在第一次访问某结点时输出该结点的关键字。
• 中序遍历顺序为“左根右”，在第二次访问某结点时输出该结点的关键字。
• 后序遍历顺序为“左右根”，在第三次访问某结点时输出该结点的关键字。

D

方法一：枚举

枚举所可能的拓扑序列。

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

总共有4种可能的输出序列。

A、B、C均能够找到对应的输出序列。

本题选D。

方法二：代入选项

带入选项中的拓扑序列检查是否符合题目中的有向图。

A、B、C均符合。

本题选D。

B

本题考察B树的基本性质。

方法一：公式法

方法二：构造法

C

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

可以计算出查找关键字22, 43, 15成功需要探测的次数，如下图所示。

查找22的探测次数为1：

查找43的探测次数为2：

查找15的探测次数为3：

平均查找长度为求查找长度的数学期望：

ASL_成功=(3+2+1)/3=2

D

先看第一趟，1从最开始的5号位移动到0号位，说明第一趟步长是5，直接排除A,B；再看第二趟，2从第一趟排序结果的第4位移动到1号位，说明第二趟步长是3

void shellsort(int[] arr, int length) {
    int index = 0;
    int value = 0;
    for(int flag = length/2; flag>0; flag /= 2;) {
        for(int i=flag; i<length; i++) {
            index = i;
            value = arr[index];
            if(value < arr[index-flag]) {
                while((index-flag > 0 ||index-flag == 0) && value < arr[index-flag]) {
                    arr[index] = arr[index-flag];
                    index = index - flag;
                }
                arr[index] = value;
            }
        }
    }
}

这道题考察希尔排序的特征，希尔排序中间过程是间隔有序的。

需要考察的间隔很多，我们可以直接参考选项，第一趟排序的间隔只有3和5，我们先考察3，从数组第一个元素开始为1, 5, 4, ...到这里就没必要查下去了，数组已经不单调了。直接排除A和B。

下面考察C和D，只需要观察第二题排序的间隔。我们先考察2，从数组第一个元素开始为1, 6, 3, ...到这里就没必要查下去了，数组已经不单调了。直接排除C。

现在A、B和C都被排除，只能选D，当然不放心的话你也可以验证一下D，完全符合希尔排序的特征。

A

画出建堆过程：

对应Python测试代码：

array = [-6,-1,-5,-9,-8,-4,-7]
heapq.heapify(array)
print(array)

建堆的时间复杂度 O(n) 。

对于I，二进制由千只有0和1两种数值，运算规则较简单，都是通过ALU部件转换成加法运算。I正确。

对于II，二进制只需要高电平和低电平两个状态就可以表示，这样的物理器件很容易制造。II正确。

对于III，二进制与逻辑量相吻合。二进制的0和1正好与逻辑量的真和假相对应，因此用二进制数表示二值逻辑显得十分自然，采用逻辑门电路很容易实现运算。III正确。

综上，I、II和III都正确。

本题选D。

[x]补=FFFF FFDFH=1111 1111 1111 1111 1111 1111 1101 1111B，

[x]原=1000 0000 0000 0000 0000 0000 0010 0001B= −(2^5+1) =-33。

[y]补=0000 0041H，[y]原=0000 0041H=4×16+1=65。

关于计算x-y。

方法一：十进制计算

用十进制计算x-y，再转二进制补码。

x-y=-33-65=-98，[x-y]原=1000 0000 0000 0000 0000 0000 0110 0010B，[x-y]补=1111 1111 1111 1111 1111 1111 1001 1110B=FFFF FF9EH。

方法二：二进制计算

二进制计算x-y补码。

[y]补=0000 0041H=0000 0000 0000 0000 0000 0000 0100 0001B，[-y]补=1111 1111 1111 1111 1111 1111 1011 1111B。

[x-y]补=[x]补+[-y]补=1111 1111 1111 1111 1111 1111 1101 1111B+1111 1111 1111 1111 1111 1111 1011 1111B=(1)1111 1111 1111 1111 1111 1111 1001 1110B=FFFF FF9EH。

本题选C。

本题考察float的取值范围，float最小的规格化正数是 \(1.0 \times 2^{-126}\)。

如果忘记了float的最大值，首先排除float的特殊表示。
- 当 \(E = 0\) 且 \(M = 0\) 时，表示 0。
- 当 \(E = 0\) 且 \(M \neq 0\) 时，表示非规格化数（下溢数），通常被视为0。
- 当 \(E = 255\) 且 \(M = 0\) 时，表示 \(\infty\)。
- 当 \(E = 255\) 且 \(M \neq 0\) 时，表示 NAN。

然后构造出float的最小的规格化正数，符号位 \(S = 0\)，阶码 \(E = 1\)，尾数 \(M\) 所有位全0，float的值为 \((-1)^S \times 1.M \times 2^{E-127} = (-1)^0 \times 1.0 \times 2^{1-127} = 1.0 \times 2^{-126}\)。

本题选A。

计算机按字节编址，采用小端方式，低位的数据存储在低地址位、高位的数据存储在高地址位。在32位计算机中，int占32位，i=0=00000000H，按照小端方式，从低地址到高地址依次为00H、00H、00H、00H。“int i=0”的指令内容为”C7 45 FC 00 00 00 00“（从左到右为从低字节到高字节的内容），显然后32位存储的是i，现在i=-64，用补码表示，[i]原=1000 0000 0000 0000 0000 0000 0100 0000B，[i]补=1111 1111 1111 1111 1111 1111 1100 0000B=FFFF FFC0H，按照小端方式，从低地址到高地址依次为C0H、FFH、FFH、FFH，前面拼接上指令的剩余部分，得到“int i=-64”的指令内容为”C7 45 FC C0 FF FF FF“（从左到右为从低字节到高字节的内容）。

本题选A。

逻辑移位：

左移和右移空位都补0，并且所有数字参与移动。

算术移位：符号位不参与移动，右移空位补符号位，左移空位补0。

对x进行逻辑右移1位得到的机器数是01101100。

对x进行逻算术右移1位得到的机器数是11101100。

本题选B。

假定DRAM芯片中存储阵列的行数为r、列数为c，对于一个2K×1位的DRAM芯片，r×c=2K，四个选项均满足。

首先，根据DRAM采用的是行列地址线复用技术，地址引脚数为 max{log2⁡r,log2⁡c} ，为保证其地址引脚数最少，我们尽量选行列最大值小的，排除A和D。

其次，为了减小刷新开销，而DRAM一般是按行刷新的，所以应选行数值较少的，C比B更优。

本题选C。

double占64位，计算机按字节编址，double占8个地址单元，sizeof(double)=8。某double型数组A的首地址为2000H，使用变址寻址和循环结构访问数组A，变址寄存器保存数组下标，根据变址寻址的公式，有效地址EA的计算公式为：EA=8(IX)+A，其中A为指令格式中的形式地址。

初始时，EA=2000H，变址寄存器初值为0，即(IX)=0，代入EA的计算公式，解得A=2000H。

某次循环所取元素的地址为2100H，即EA=2100H，此时(IX)发生改变，A=2000H不变，代入EA的计算公式，解得(IX)=32。

本题选B。

因为(R1)-(R2)→R3，(R1)=FFFFFFFFH，(R2)=FFFFFFF0H，(R3)=(R1)-(R2)=FFFFFFFFH-FFFFFFF0H=0000000FH，被减数和减数都视为无符号数，FFFFFFFFH显然够减FFFFFFF0H，无借位，CF=0，结果没有超出表示范围，无溢出，OF=0。

本题选A。

指令流水线的每个流水段时间单位为时钟周期，题中指令流水线的指令需要用到A~E五个部件，所以每个流水段时间应取最大部件时间，即80ps，此外还有寄存器延时为20ps，则CPU时钟周期至少是100ps。

本题选D。

总线数据传输率也称总线带宽，为总线上每秒钟传输的字节数。

总线数据传输率=总线工作频率×总线宽度/8，I和II正确。

采用突发传输方式，在一个总线周期内传输存储地址连续的多个数据字，提高了传输效率，进而提高了总线数据提高传输率。III正确。

采用地址/数据线复用只是减少了线的数量，节省了成本，并不能提高总线数据提高传输率。Ⅳ错误。

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

本题选B。

中断控制器通常会按照中断请求的响应优先级进行排队，该优先级一般都由硬件设置，而不是根据请求的先后次序。A错误。

中断隐指令完成的工作有：①关中断；②保存断点；③引出中断服务程序，通用寄存器的保护由中断服务程序完成。B错误。

CPU在处理中断请求之前必须处于中断允许（开中断）状态。如果CPU处于中断禁止（关中断）状态，它将无法响应外部设备的中断请求。C正确。

有中断请求时，先要由中断隐指令完成中断前程序的状态保存。D错误。

本题选C。

【答案】C

【解析】多任务操作系统可在同一时间内运行多个应用程序，因此I 正确。多个任务必须互斥地访问共享资源，为达到这一目标必须对共享资源进行必要的保护，因此II正确。现代操作系统都是多任务的（主要特点是并发和并行），并不一定需要运行在多CPU的硬件上，单个CPU也可满足要求，Ⅲ错误。综上所述，Ⅰ、Ⅱ正确，Ⅲ错误，因此选C。

答案：D
由优先权可知，进程的执行顺序为P2 > P3 > P1 

P2的周转时间为1+15+24=40us；P3的周转时间为18+1+24+1+36=80us；P1 的周转时间为30+1+24+1+36+1+12=105us；平均周转时间为(40+80+105)/3=225/3=75us，因此选D。
 

答案：B

通过阅读两个线程代码可知，thread1和thread2均是对x进行加1操作，x的初始值为0，若要使得最终x=2，只能先执行完thread1再执行thread2，或先执行完thread2再执行thread1，因此仅有两种可能，选B。

答案：A
由题意可知，仅剩最后一个同类资源，若将其分给P1或P2，则均无法正常执行；若分给P3，则P3正常执行完成后，释放的这一个资源仍无法使P1,P2正常执行，因此不存在安全序列。

方法一：资源分配图

资源分配图：一种描述系统当前状态的图，图中有进程结点、资源结点以及两种不同结点之间的有向边。

资源分配图化简方法：从资源分配图中找既非孤立又非阻塞的进程结点，将该结点直接有关的有向边全删去，重复上述过程直到图中找不到既非孤立又非阻塞的进程结点为止。

根据题意，设资源为R，画出资源分配图，如图(a)所示，化简后如图(b)所示。

死锁检测中的数据结构类似于银行家算法中的数据结构：

• 可用资源向量 Available，它表示了 m 类资源中每一类资源的可用数目。
• 把不占用资源的进程（Available_i = 0）记入输出表中。
• 从进程集合中找到一个 Request_i ≤ Work 的进程，做如下处理：①将其资源分配图简化，释放出资源，增加工作向量 Work 增加为 Work + Allocation_i。② 将它记入输出表中。
• 若不能把所有进程都记入 L 表中，便表明系统状态的资源分配图是不可完全简化的。因此，该系统状态将发生死锁。

很明显，不存在安全序列。

本题选A。

方法二：资源分配表

根据题意，设资源为R，画出资源分配表，如图(c)所示，在将表格转化为已分配资源、尚需资源、可用资源三栏的形式。进程Pi尚需资源=进程Pi资源最大需求-进程Pi已分配资源，可用资源=资源总数-所有进程已分配资源之和，如图(d)所示。

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

很明显，不存在安全序列。

本题选A。

【答案】C

【解析】进程等待某资源为可用（不包括处理机）或等待输入/输出完成均会进入阻塞态，因此I、II正确；Ⅲ中情况发生时，进程进入就绪态，因此Ⅲ错误，答案选C。

管程 (Monitor) 是一种同步机制，用于解决多个进程或线程对共享资源的并发访问问题。管程通常包含共享数据和对该数据进行操作的方法集合。

条件变量 (Condition Variable) 是管程内的一种机制，用于实现进程或线程之间的等待和唤醒操作。条件变量提供了一种方式，允许进程（线程）在某个条件满足之前进行等待，以避免忙等。当条件满足时，其他进程（线程）可以通过唤醒操作通知等待中的进程（线程）继续执行。

在管程中，条件变量的操作通常包括以下两个方法：

wait()：当一个进程（线程）调用条件变量的wait()方法时，它会被放入条件变量的等待队列，并且会被阻塞（暂停执行），直到其他进程（线程）通过信号 (signal) 或广播 (broadcast) 操作唤醒它。

signal() / broadcast()：当某个进程（线程）通过条件判断发现条件变量的某个条件满足时，它可以通过signal()方法向条件变量发送一个信号，唤醒等待在该条件变量上的一个进程（线程）；或者通过broadcast()方法唤醒等待在该条件变量上的所有进程（线程）。

当进程执行 x.wait() 时，所做的工作是阻塞该进程，并将其插入 x 的阻塞队列中。进程会主动阻塞自己，并排队等待被唤醒。

本题选D。

【答案】D

【解析】时钟中断的主要工作是处理和时间有关的信息及决定是否执行调度程序。和时间有关的所有信息包括系统时间、进程的时间片、延时、使 用 CPU的时间、各种定时器，因此I、II、III均正确。

磁臂黏着原因是有源源不断的对某个磁道的访问请求到来，导致对其他磁道的请求无法被响应，导致饥饿，或者某个磁道频繁被请求导致磁头长时间停留在该磁道上。

选项 A：先来先服务 (FCFS) 算法按照磁道请求到达的顺序进行服务。由于它不考虑磁道间的距离，只是简单地按照请求到达的顺序来处理，因此不会长时间停留在某个磁道上处理连续到来的对该磁道的请求。因此，FCFS 算法不会导致磁臂黏着。

选项 B：最短寻道时间优先 (SSTF) 算法选择与当前磁头距离最近的磁道进行范围，以使每次寻道时间最短。如果某个磁道频繁被请求，且其位置与磁头当前位置较近，磁头可能会长时间停留在该磁道上，导致磁臂黏着。因此，SSTF 算法有可能导致磁臂黏着。

选项 C：扫描算法 (SCAN) 也称为电梯算法，当磁头正在由里向外移动时，它会选择最近的外部磁道进行处理。完成外部磁道的处理后，磁头会反向移动，处理内部的磁道。如果在某个磁道频繁被请求，磁头可能会长时间停留在该磁道上，导致磁臂黏着。因此，SCAN 算法有可能导致磁臂黏着。

选项 D：循环扫描算法 (CSCAN) 算法与 SCAN 算法类似，但规定磁头只能单向访问磁道，若只是自里向外移动，当磁头移到最外的磁道并访问后，磁头立即返回到最里的欲访问磁道，进行循环扫描。如果在某个磁道频繁被请求，磁头可能会长时间停留在该磁道上，导致磁臂黏着。因此，CSCAN 算法有可能导致磁臂黏着。

上述选项中只有选项 A 的调度与时间顺序有关，和位置顺序无关，因此 FCFS 不会导致磁臂粘着。

本题选 A。

Ⅰ正确。提前读是指在文件被请求访问之前，预先将文件的内容加载到内存或高速缓存中。通过提前读取文件的数据，可以减少后续对磁盘的实际读取次数，从而提高文件的访问速度。

Ⅱ正确。文件系统通常将文件划分为簇(cluster)或块(block)进行存储。如果文件的簇是连续的，就可以实现更高效的顺序读取，从而提高文件的访问速度。因为连续簇的读取可以最小化磁头的移动，并允许连续的数据传输。

Ⅲ正确。延迟写是一种延迟文件写入操作的策略，主要用于提高系统性能和响应速度。在延迟写策略中，当应用程序执行写操作时，操作系统并不立即将数据写入存储设备（如磁盘），而是将数据缓存在内存中或者延迟到后续合适的时机再进行写入。延迟写的优点在于可以将多个写操作合并为一个较大的写操作，从而减少了磁盘写入的次数。这样可以提高磁盘的效率和整体系统的性能，特别是当有大量小型写操作发生时。通过延迟写，可以积极利用系统内存进行缓存，并减少对磁盘的频繁访问，从而降低了写操作的延迟和系统负载。

Ⅳ正确。磁盘高速缓存是一种位于内存中的缓存区域，用于存储最常访问的数据块或文件。当文件被访问时，先检查缓存中是否有对应的数据，如果存在，就可以直接从缓存中获取，避免了访问慢速的磁盘。磁盘高速缓存可以显著加快对常用文件的访问速度。

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

本题选D。

让权等待是指当一个进程需要访问共享资源或进入临界区时，如果该资源或临界区已经被占用，该进程会主动放弃执行权，让其他进程先执行。这种机制可以避免进程过多地忙等待资源或临界区，提高系统的效率和公平性。

在多进程或多线程环境下，实现让权等待的方式通常有以下几种：

1. 睡眠/唤醒机制：当一个进程发现资源或临界区被占用时，它可以放弃执行权，主动进入睡眠状态，等待资源可用或临界区解锁时被唤醒。这样可以让其他进程有机会执行。
2. 条件变量：条件变量是一种同步原语，可以与互斥锁结合使用。当一个进程发现条件不满足时，它可以通过条件变量进入等待状态，同时释放互斥锁，让其他进程有机会执行。当条件满足时，其他进程可以通过条件变量进行通知，唤醒等待的进程。
3. 信号量：信号量是一种计数器，用于控制对共享资源的访问。当进程需要访问资源时，它会尝试获取信号量。如果信号量的值为0，表示资源已被占用，则进程会被阻塞，放弃执行权。当资源可用时，其他进程可能会释放信号量，唤醒等待的进程，使其可以继续执行。

A错误。Peterson方法是一种经典的软件同步机制，用于实现两个进程之间的互斥访问。该方法通过使用共享的bool型变量和一个turn变量来控制进程的执行顺序，从而实现有限等待的效果。当一个进程需要进入临界区时，它会标记自己希望进入的意向，并将执行权交给另一个进程。如果两个进程都希望进入临界区，而且轮到另一个进程执行的话，当前进程将会等待。通过不断交替执行和等待，最终可以实现进程的互斥执行。

B错误。swap指令通常用于原子操作，可以交换两个变量的值。它无法实现让权等待。

C正确。记录型信号量由于引入阻塞机制，消除了不让权等待的情况。

D错误。TestAndSet指令是一种原子操作，用于检查一个变量的值并设置新值。它可以用于实现其他同步机制，如自旋锁和互斥量，但并不能直接实现让权等待。

本题选C。

方法一：判断基于 TCP 还是 UDP

TCP/IP 体系中，TCP 在传输层提供有连接的可靠的传输服务。UDP 在传输层提供无连接的不可靠的传输服务。

A 错误。FTP (File Transfer Protocol) 文件传输协议。FTP 在传输层使用 TCP 传输，端口号 20/21。

B 正确。DNS (Domain Name System) 域名系统。DNS 在传输层使用 UDP 传输，端口号 53。

C 错误。SMTP (Simple Mail Transfer Protocol) 简单邮件传输协议，是用于在网络上发送电子邮件的标准协议。FTP 在传输层使用 TCP 传输，端口号 25。

D 错误。HTTP (Hypertext Transfer Protocol) 超文本传输协议。HTTP 在传输层使用 TCP 传输，端口号 80。

本题选 B。

方法二：判断是否需要可靠传输

如果记不住这些应用层协议是基于 TCP 还是 UDP，那么可以借助常识进行判断。

一般情况下，无连接服务提供的是不可靠传输，是尽力交付的传输。要保证实现可靠传输需要建立连接。

A 错误。FTP (File Transfer Protocol) 文件传输协议。文件传输必须可靠，不能出现丢包或者乱序，所以需要需要建立连接以保证可靠传输。

B 正确。DNS (Domain Name System) 域名系统。DNS 服务器通常需要处理大量的查询，建立连接开销较大，所以使用无连接服务比较合理。

C 错误。SMTP (Simple Mail Transfer Protocol) 简单邮件传输协议。邮件传输必须可靠，不能出现丢包或者乱序，所以需要需要建立连接以保证可靠传输。

D 错误。HTTP (Hypertext Transfer Protocol) 超文本传输协议。HTTP 通常用于访问 Internet 上的网站，访问网站很多服务都需要保证信息传输可靠，最常见的比如登录和注册操作，登录一般需要输入用户名和密码，注册一般需要输入用户名、登录密码以及其他重要信息，这些信息传输必须可靠，不能出现丢包或者乱序，所以需要需要建立连接以保证可靠传输。

B 选项比较难分析，可以先分析 A、C、D，然后通过排除法选出 B。

实际上，DNS 使用 UDP 协议的主要原因包括以下几点：

1. 简单快速的交互：UDP是无连接的协议，相比TCP，UDP交互的开销更小，不需要建立连接和维护状态，适合对速度有要求的DNS查询。

2. 较小的开销和资源消耗：DNS通常涉及较小的数据包，而UDP相比TCP具有更小的头部开销和较少的状态管理，这使得它更适合用于快速的、短小的交互。

3. 效率和灵活性：UDP协议在处理高负载情况下更为高效，DNS服务器通常需要处理大量的查询，而UDP更适合这种高负载的情况。

本题选 B。

物理层规定：为传输数据所需要的物理链路创建、维持、拆除，而提供具有机械的，电子的，功能的和规范的特性。

物理层主要包含以下四种特性。

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

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

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

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

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

A 属于物理层接口规范定义范畴。接口形状属于机械特性。

B 属于物理层接口规范定义范畴。引脚功能属于功能特性。

C 不属于物理层接口规范定义范畴。物理地址通常是数据链路层的概念，在 OSI 模型中用于定义网络设备的唯一地址，也被称为 MAC 地址。

D 属于物理层接口规范定义范畴。信号电平属于电气特性。

本题选 C。

CSMA/CA 协议使用 RTS (Request to Send) 和CTS (Clear to Send) 帧来预约传输信道，这有助于避免碰撞和提高效率。CSMA/CA中的信道预约过程如下：

1. 发送节点发送RTS帧来请求对方节点信道的使用。
2. 接收节点如果空闲，将发送CTS帧向发送节点确认信道的可用性。
3. 发送节点收到CTS帧后，开始发送数据帧。
4. 其他节点在监听到CTS帧后，将暂时禁止发送，等待一段随机的时间间隔 (Distributed Interframe Space, DIFS) 后再尝试发送。

本题选 D。

从发送方发送一个数据帧到发送方接收到接收方传来的确认帧为一个周期。信道利用率为一个周期内发生数据的时间占该周期的比例。

主机甲发生一个数据帧的时延为 t1 ，传播时延为 τ=200 ms ，主机乙发送一个确认帧的时延为 t2 ，因为乙每收到一个数据帧立即利用一个短帧（忽略其传输延迟）进行确认，所以 t2=0 ，传播时延为 τ=200 ms 。一个周期 T=t1+τ+t2+τ=t1+2τ 。因为主机甲采用停-等协议向主机乙发送数据，一个周期内只能发送一个数据帧，直到主机甲接收到确认帧，才能于下个周期开始发送下一个数据帧，信道利用率  ，将 τ=200 ms 和 U=40% 代入计算出 t1=800/3 ms ， t1=L/C ，其中 L 为数据帧长， C 为数据传输率， L=Ct1 ，将 t1=800/3 ms 和 C=3 kbps 代入得， L=800 bit 。

本题选 D。

IP 分组在整个传输过程中，封装 IP 分组的以太网帧的源 MAC 地址和目的 MAC 地址逐段链路改变。

根据图可分析出，主机H1和H2不在一个网络中，若H1向H2发送一个IP分组P，则主机H1先把以太网帧发送给其默认网关，即路由器R，此时该以太网帧的源 MAC 地址为主机H1的MAC地址00-1a-2b-3c-4d-52，目的MAC地址为R位于主机H1所在子网的接口的MAC地址00-1a-2b-3c-4d-51。因此，H1发出的封装P的以太网帧的目的MAC地址为00-1a-2b-3c-4d-51。

最后由主机H2的默认网关，即路由器R，将该以太网帧发送给主机H2，此时该以太网帧的源 MAC 地址为R位于主机H2所在子网的接口的MAC地址00-1a-2b-3c-4d-61，目的 MAC 地址为主机H2的MAC地址00-1a-2b-3c-4d-62。因此，H2收到的封装P的以太网帧的源MAC地址为00-1a-2b-3c-4d-61。

本题选 D。

为了对这些路由进行聚合，我们需要对它们进行最长公共前缀匹配。

观察这4个网络地址，前两个十进制数相同，将其后 16 位写成二进制形式，其中主机号的位用 x 表示，每个 x 可以取 0 或 1。二进制位用红色表示。得到

显然此时只有后 16 位的前3位相同，即前19位相同，得到聚合后的网络为 

前19位为网络号，将主机号位全部取 0 得到网络地址  ，即 35.230.32.0。

因此，聚合后的网络为即 35.230.32.0/19。

本题选 C。

复用指发送方在不同的应用进程都可以使用同一个运输层协议来传输数据。

分用是指接收方的应用层实体收到数据后，再分配到不同的进程中去。

传输层协议实现复用和分用都是依靠端口号来实现的。分用是接收方的行为，接收方对应“目的”。因此，UDP 在接收数据包时会根据数据包头部中的目的端口号将数据包分配给相应的应用程序或进程进行处理。

本题选 B。

SMTP (Simple Mail Transfer Protocol) 简单邮件传输协议。SMTP 传输的文本只能使用 7 位 ASCII 字符。SMTP 通常不用于传输二进制文件，因此像 JPEG 图形、MPEG 视频和 EXE 文件这样的二进制文件通常需要通过其他方式（比如MIME附件）进行传输。

本题选 D。

方法一：哈希表

本方法为暴力解。

哈希表是一个可以支持快速查找的数据结构：给定一个元素，我们可以在 O(1) 的时间查找该元素是否在哈希表中。

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

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

struct hashTable {
    int key;
    int val;
    UT_hash_handle hh;
};

struct hashTable* hashtable;

struct hashTable* find(int ikey) {
    struct hashTable* tmp;
    HASH_FIND_INT(hashtable, &ikey, tmp);
    return tmp;
}

void insert(int ikey, int ival) {
    struct hashTable* it = find(ikey);
    if (it == NULL) {
        struct hashTable* tmp = malloc(sizeof(struct hashTable));
        tmp->key = ikey;
        tmp->val = ival;
        HASH_ADD_INT(hashtable, key, tmp);
    } else {
        it->val = ival;
    }
}

int firstMissingPositive(int* nums, int numsSize) {
    for (int i = 0; i < numsSize; i++) {
        insert(nums[i], 1);
    }
    for (int i = 1; i <= numsSize; i++) {
        struct hashTable* it = find(i);
        if (it == NULL) {
            return i;
        }
    }
    return numsSize + 1;
}

int main() {
    int a[] = {-5, 3, 2, 3};
    int miss = firstMissingPositive(a, 4);
    printf("%d", miss);
    return 0;
}

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

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

int firstMissingPositive(vector<int>& nums) {
    int n = nums.size();
    unordered_set<int> st;
    for (int num : nums) {
        st.insert(num);
    }
    for (int i = 1; i <= n; ++i) {
        if (!st.count(i)){
            return i;
        }
    }
    return n + 1;
}

int main(int argc, const char * argv[]) {
    vector<int> a = {-5, 3, 2, 3};
    int miss = firstMissingPositive(a);
    cout << miss;
    return 0;
}

这里可以用数组作为哈希表进行优化，由于结果 x 一定满足 1≤x≤n+1 ，所以只需要记录值在这个范围中的元素，修改如下：

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

#include <stdio.h>
#include <string.h>

int firstMissingPositive(int* a, int n){
    int f[n + 1];
    memset(f, 0, sizeof(f));
    for (int i = 0; i < n; i++) {
        if (a[i] > 0 && a[i] <= n) {
            f[a[i]] = 1;
        }
    }
    for (int i = 1; i <= n; i++) {
        if (f[i] == 0) {
            return i;
        }
    }
    return n + 1;
}

int main() {
    int a[] = {-5, 3, 2, 3};
    int miss = firstMissingPositive(a, 4);
    printf("%d", miss);
    return 0;
}

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

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

int firstMissingPositive(vector<int>& nums) {
    int n = (int) nums.size();
    vector<bool> flag(n + 1, false);
    for (int num: nums) {
        if (num > 0 && num <= n) {
            flag[num] = true;
        }
    }
    for (int i = 1; i <= n; i++) { // 从1开始遍历flag数组
        if (!flag[i]) {
            return i; // 第一个位置为false的就是缺失的最小正整数
        }
    }
    return n + 1; // 位置均为true，没有缺失正数返回n+1
}

int main(int argc, const char * argv[]) {
    vector<int> a = {-5, 3, 2, 3};
    int miss = firstMissingPositive(a);
    cout << miss;
    return 0;
}

复杂度分析

• 时间复杂度： O(n) 。
• 空间复杂度： O(n) ，需要开辟大小为 O(n) 的辅助哈希表。

方法二：原地哈希

这个思路非常巧妙，用负号标记元素存在。将数组的下标假想为哈希表的键。

算法的流程如下：

• 我们将数组中所有小于或等于 0 的数修改为 n+1 ；
• 我们遍历数组中的每一个数 x ，它可能已经被打了标记，因此原本对应的数为 |x| 。如果 |x|∈[1,n] ，那么我们给数组中的第 |x|−1 个位置的数添加一个负号。注意如果它已经有负号，不需要重复添加；
• 在遍历完成之后，如果数组中的每一个数都是负数，那么答案是 n+1 ，否则答案是第一个正数的位置加 1 。

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

#include <stdio.h>

int firstMissingPositive(int* nums, int numsSize) {
    for (int i = 0; i < numsSize; ++i) {
        if (nums[i] <= 0) {
            nums[i] = numsSize + 1;
        }
    }
    for (int i = 0; i < numsSize; ++i) {
        int num = abs(nums[i]);
        if (num <= numsSize) {
            nums[num - 1] = -abs(nums[num - 1]);
        }
    }
    for (int i = 0; i < numsSize; ++i) {
        if (nums[i] > 0) {
            return i + 1;
        }
    }
    return numsSize + 1;
}

int main() {
    int a[] = {-5, 3, 2, 3};
    int miss = firstMissingPositive(a, 4);
    printf("%d", miss);
    return 0;
}

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

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

int firstMissingPositive(vector<int>& nums) {
    int n = (int)nums.size();
    for (int& num : nums) {
        if (num <= 0) {
            num = n + 1; //越界数字处理
        }
    }
    for (int i = 0; i < n; ++i) {
        int num = abs(nums[i]);
        if (num <= n) { //合格的数字
            nums[num - 1] = -abs(nums[num - 1]); //-标记,正确数字对应的位置
        }
    }
    for (int i = 0; i < n; ++i) { //找到第一个为正数的位置
        if (nums[i] > 0) {
            return i + 1; //位置下标+1为缺失数
        }
    }
    return n+1;
}

int main(int argc, const char * argv[]) {
    vector<int> a = {-5, 3, 2, 3};
    int miss = firstMissingPositive(a);
    cout << miss;
    return 0;
}

复杂度分析

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

方法三：置换

除了打标记以外，我们还可以使用置换的方法。

在恢复后，数组应当有{1, 2, ..., n}的形式，但其中有若干个位置上的数是错误的，每一个错误的位置就代表了一个缺失的正数。以{3, 4, -1, 1}为例，恢复后的数组应当为{1, -1, 3, 4}，我们就可以知道缺失的数为2。

由于每次的交换操作都会使得某一个数交换到正确的位置，因此交换的次数最多为 n ，整个方法的时间复杂度为 O(n) 。

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

#include <stdio.h>

int firstMissingPositive(int* nums, int numsSize) {
    for (int i = 0; i < numsSize; ++i) {
        while (nums[i] > 0 && nums[i] <= numsSize &&
               nums[nums[i] - 1] != nums[i]) {
            int t = nums[nums[i] - 1];
            nums[nums[i] - 1] = nums[i], nums[i] = t;
        }
    }
    for (int i = 0; i < numsSize; ++i) {
        if (nums[i] != i + 1) {
            return i + 1;
        }
    }
    return numsSize + 1;
}

int main() {
    int a[] = {-5, 3, 2, 3};
    int miss = firstMissingPositive(a, 4);
    printf("%d", miss);
    return 0;
}

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

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

int firstMissingPositive(vector<int>& nums) {
    int n = nums.size();
    for (int i = 0; i < n; ++i) {
        while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
            swap(nums[nums[i] - 1], nums[i]);
        }
    }
    for (int i = 0; i < n; ++i) {
        if (nums[i] != i + 1) {
            return i + 1;
        }
    }
    return n + 1;
}

int main(int argc, const char * argv[]) {
    vector<int> a = {-5, 3, 2, 3};
    int miss = firstMissingPositive(a);
    cout << miss;
    return 0;
}

复杂度分析

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

⑴ 用最小生成树算法，Prim或Kruskal，本题个人偏向用Kruskal，先添加5条长度为2的边，再补上2条长度为3的边。

可以得到两种方案，如下图所示，总费用均为16。

⑵ 题42图可以采用邻接矩阵或邻接表存储。求解问题⑴所使用的算法名称为Prim或Kruskal。

⑶ IP分组每经过一个路由器的转发，其头部中的生存时间TTL字段的值减1，当TTL字段的值减少到0时路由器会丢弃该IP分组并给源主机发送“时间超过”类型的ICMP差错报告报文。

对于方案一，主机H1给H2发送IP分组，IP分组的转发路径为 H1→TL→JN→QD→WH→XA→BJ→H2 ，

IP分组从H1发出时其TTL=5，每经过一个路由器的转发，其头部中的生存时间TTL字段的值减1，当该分组转发进入BJ的路由器时，其TTL=0，该分组会被BJ的路由器丢弃，因此H2不能收到该IP分组。

对于方案二，主机H1给H2发送IP分组，IP分组的转发路径为 H1→TL→BJ→H2 ，

IP分组从H1发出时其TTL=5，每经过一个路由器的转发，其头部中的生存时间TTL字段的值减1，到达主机H2时TTL=3，主机H2可以收到该IP分组。

(1) 第一问。程序定时向缓存端口查询数据，由于缓存端口大小有限，必须在传输完端口大小的数据时访问端口，以防止部分数据没有被及时读取而丢失。设备A的数据传输率为2MBps，设备A准备32位数据所用时间为32bit/2MBps=4B/2MBps=2μs，所以最多每隔2μs必须查询一次。

第二问。

方法一：通过时间计算

因为计算机的主频为500MHz，时钟周期为2ns，CPI为4，平均执行一条指令需要2ns×4=8ns，每次输入/输出都至少执行10条指令，所以每次输入/输出需要CPU时间为8ns×10=80ns，又因为根据第一问，设备A最多每隔2μs必须查询一次，所以CPU用于设备A输入输出的时间占CPU总时间的百分比至少是80ns/2μs=4%。

方法二：通过频率计算

因为计算机CPI为4，每次输入/输出都至少执行10条指令，所以每次输入/输出都至少需要4×10=40个时钟周期，又因为根据第一问，设备A最多每隔2μs必须查询一次，即每秒的查询次数至少是1s/2μs=0.5M，所以CPU每秒用于设备A输入/输出的时钟周期数至少为40×0.5M=20M，又因为计算机的主频为500MHz，即每秒有500M个时钟周期，所以CPU用于设备A输入输出的时间占CPU总时间的百分比至少是20M/500M=4%。

(2) 方法一：通过时间计算

因为计算机的主频为500MHz，时钟周期为2ns，在中断I/O方式下，若每次中断响应和中断处理的总时钟周期数至少为400，则每次中断响应和中断处理的时间至少为2ns×400=800ns。这时只需判断设备B准备32位数据要多久，如果准备数据的时间小于中断响应和中断处理的时间，那么数据就会被刷新、造成丢失。设备B的数据传输率为40MBps，设备B准备32位数据所用时间为32bit/40MBps=4B/40MBps=100ns<800ns。因此，设备B不适合采用中断I/O方式。

方法二：通过频率计算

因为计算机的主频为500MHz，即每秒有500M个时钟周期，在中断I/O方式下，若每次中断响应和中断处理的总时钟周期数至少为400，计算机的处理中断的频率至多为500MHz/400=1.25MHz。这时只需计算设备B可以多少次将数据送入32位数据缓冲寄存器的频率。如果设备B可以多少次将数据送入32位数据缓冲寄存器的频率大于计算机的处理中断的频率，那么数据就会被刷新、造成丢失。设备B的数据传输率为40MBps，设备B可以多少次将数据送入32位数据缓冲寄存器的频率为40MBps/32bit=40MBps/4B=10MHz>1.25MHz。因此，设备B不适合采用中断I/O方式。

(3) 在DMA方式中，只有预处理和后处理需要CPU处理，数据的传送过程是由DMA控制。

方法一：通过时间计算

因为计算机的主频为500MHz，时钟周期为2ns，CPU用于DMA预处理和后处理的总时钟周期数为500，所以每次DMA预处理和后处理的时间为2ns×500=1μs。设备B每次DMA传送的数据块大小1000B，设备B的数据传输率为40MBps，设备每次DMA传送的时间（包含DMA预处理和后处理的时间）为1000B/40MBps=25μs，CPU用于设备B输入/输出的时间占CPU总时间的百分比最大是1μs/25μs=4%。

方法二：通过频率计算

设备B每次DMA传送的数据块大小1000B，设备B的数据传输率为40MBps，设备B每秒DMA次数至多为40MB/1000B=0.04M，CPU用于DMA预处理和后处理的总时钟周期数为500，CPU每秒用于设备B输入/输出的时钟周期至多为0.04M×500=20M，因为计算机的主频为500MHz，即每秒有500M个时钟周期，CPU用于设备B输入/输出的时间占CPU总时间的百分比最大是20M/500M=4%。

(1) 方法一：观察TLB和虚拟地址

观察TLB中实页号项，例如F800H=1111 1000 0000 0000B，最高位为1，没有填充0，可知实页号占16位，观察虚拟地址中页内地址项，可知页内地址占12位，物理地址格式为  ，可得物理地址占16+12=28位。为了防止实页号项高位被填充0，采用下面一种方法更加合适。

方法二：观察物理地址映射到Cache后的地址

物理地址映射到Cache后的地址位数不变，观察映射到Cache后的地址结构，可得物理地址占20+3+5=28位。

(2) 第一问。TLB采用全相联映射，可以把页表内容调入任一块空TLB项中，TLB中每项都有一个比较器，没有映射规则，只要空闲就行。

第二问。TLB采用静态存储器SRAM，读写速度快，但成本高，多用于容量较小的高速缓冲存储器。可以用Cache类比TLB，Cache是主存的缓存，TLB是页表的缓存，两者都要求读写速度快，Cache采用静态存储器SRAM，因此TLB采用静态存储器SRAM。

(3) 第一问。根据题44图，Cache中每组有两行，采用2路组相联映射方式。

第二问。若Cache采用LRU替换算法和回写（Write Back）策略，则Cache每行中除数据（Data）、Tag和有效位外，还应有替换算法控制位和一致性维护位。

考虑 n 路组相联并采用LRU替换算法，需要记录若某组不命中时，则按照LRU替换算法规则查找该组中最久未被访问的一行进行替换，组内每一行都需要记录一个和组内其它行不同的秩，用来表示该行的未被访问的时间排名，每组最多有 n 个秩，范围为 0∼n−1 ，需要 log⁡n 位来表示，所以LRU需要的替换算法控制位数为 ⌈log⁡n⌉ ，本题为2路组相连，所以每行需要 ⌈log⁡2⌉=1 位替换算法控制位。

不同替换算法需要的替换算法控制位总结如下：

因为采用回写策略，所以每行有1位脏位，根据脏位判断数据是否被更新，如果脏位为1则需要写回内存。

不同写策略需要的脏位位数总结如下：

第三问。Cache组相联映射的地址结构中，主存字块标记占20位，组号占3位，Cache中有 2^3=8 组，每组有两行，Cache中有8×2=16行，块内地址占5位，计算机按字节编址，Cache块大小为 2^5×1B=32B。

Cache每行标记位数=主存字块标记位数+有效位位数+替换算法控制位位数+脏位位数=(20+1+1+1)bit=23bit。

Cache每行数据位数=32B=32×8bit=256bit。

Cache总容量=(Cache每行标记位数+Cache每行数据位数)×Cache行数=(23bit+256bit)×16=558B。

Cache总容量是558字节。

第四问。Cache中有效位用来指出所在Cache行中的信息是否有效。即用于指示Cache行中的数据是否有效或者说是为了标识Cache行是否包含了当前正在被请求的数据。当有效位被设置为有效（即设置为1）时，表示Cache行中的数据是最新的、有效的，并且可用于响应对应的读取请求。相反，当有效位被设置为无效（即设置为0）时，表示Cache行中的数据无效，无法被使用，需要重新从主存或其他更低层级的缓存中获取最新的数据。

(4) 第一问。虚拟地址格式为  ，物理地址格式为  ，利用虚拟地址的虚页号部分去查找TLB表（缺失时从页表调入），将实页号取出后和虚拟地址的页内地址拼接，就形成了物理地址。

虚拟地址  ，查找TLB表中Tag为0008CH的项，有效位为1，实页号为0040H，得到0008C040H所在的物理地址为  。

第二问。Cache组相联映射的地址格式为  ，物理地址高20位对应主存字块标记，所以物理地址 ，查Cache表表中Tag为00400H的项，左边一个存在Tag为00400H的项，但有效位为0，右边一个不存在Tag为00400H的项，所以访问Cache不命中。

第三问。因为物理地址的低12位与虚拟地址低12位相同，对于虚拟地址为0007C260H，低12位为260H=0010 0110 0000B 。根据物理地址的结构，物理地址的后八位01100000B的前三位011B是组号，因此该地址所在的主存映射到Cache组号为011B=3。

(1) 根据题44图，地址总长度为32位，高20位为虚页号，低12位为页内地址。且虚页号高10位为页目录号，低10位为页表索引。某虚拟地址对应的页目录号为6=0000000110B，在相应的页表中对应的页表索引为6=0000000110B，页内偏移量为8=000000001000B，拼接得到虚拟地址  B = 0180 6008H。

(2) 第一问。寄存器PDBR用于保存当前进程的页目录起始地址是物理地址。每个进程都有自己的地址空间和页目录 (Page Directory Table, PDT)，页目录的物理地址由页目录基址地址寄存器PDBR (Page Directory Base Register) 指定，每个进程的地址空间、页目录和PDBR的内容存在一一对应关系。

第二问。进程切换时，进程和地址空间和页目录发生变化，对应的PDBR的内容也会变化。

第三问。同一进程的线程切换时，进程和地址空间和页目录没有变化，PDBR的内容也不会变化。

(3) 改进型 CLOCK 置换算法需要用到使用位和修改位，故需要设置访问字段（使用位）和修改字段（脏位）。

(1) 因为簇大小为\( 4\mathrm{KB} \)，每个地址项长度为\( 4\mathrm{B} \)，所以每簇有\( \frac{4\mathrm{KB}}{4\mathrm{B}} = 1024 \)个地址项。又因为有11个地址项，其中直接地址项8个，一级、二级和三级间接地址项各1个，所以最大文件长度为
\[
(8 + 1 \times 1024 + 1 \times 1024^2 + 1 \times 1024^3) \times 4\mathrm{KB} = 32\mathrm{KB} + 4\mathrm{MB} + 4\mathrm{GB} + 4\mathrm{TB}
\]

(2) 文件系统用\( 1\mathrm{M} \)（\( 1\mathrm{M}=2^{20} \)）个簇存放文件索引节点，每个簇大小为\( 4\mathrm{KB} \)，每个文件索引节点占\( 64\mathrm{B} \)，文件索引节点总个数为\( 1\mathrm{M} \times 4\mathrm{KB} / 64\mathrm{B} = 64\mathrm{M} \)。

文件系统通常将文件划分为簇进行存储，5600B的图像文件占\( \lceil \frac{5600\mathrm{B}}{4\mathrm{KB}} \rceil = 2 \)个簇，用512M个簇存放文件数据，该文件系统最多能存放\( 512\mathrm{M} / 2 = 256\mathrm{M} \)个这样的图像文件。

综上，因为可表示的文件总个数受限于文件索引节点总个数，所以该文件系统最多能存放\( \min(64\mathrm{M}, 256\mathrm{M}) = 64\mathrm{M} \)个大小为5600B的图像文件。

(3) 直接地址项最大能表示的文件大小为\( 4\mathrm{KB} \times 8 = 32\mathrm{KB} \)，文件F1大小为6KB，\( 6\mathrm{KB} \leq 32\mathrm{KB} \)，所以获取文件F1的最后一个簇的簇号只需要访问索引节点的直接地址项。

直接地址项和一级地址项最大能表示的文件大小为
\[
(8 + 1 \times 1024) \times 4\mathrm{KB} = 32\mathrm{KB} + 4\mathrm{MB}
\]
文件F2大小为40KB，\( 32\mathrm{KB} < 40\mathrm{KB} \leq 32\mathrm{KB} + 4\mathrm{MB} \)，所以获取F2的最后一个簇的簇号需要读一级索引表。

访问一级索引表比访问直接地址项需要多一次访问磁盘，所以该文件系统获取F1和F2最后一个簇的簇号需要的时间不相同。

(1) IP地址空间192.168.1.0/24被均分给销售部和技术部两个子网，将192.168.1.0/24后32-24=8位写成二进制形式，其中主机号的位用 x 表示，每个 x 可以取 0 或 1。二进制位用红色表示。得到 192.168.1.xxxxxxxx ，因为要均匀划分给两个子网，取出其中 ⌈log2⁡2⌉=1 位作为子网号，得到两个子网：

192.168.1.0xxxxxxx

192.168.1.1xxxxxxx

对于 192.168.1.0xxxxxxx ，即192.168.1.0/25，

将其主机号位全取0，得到其网络地址：192.168.1.0

将其主机号位全取1，得到其广播地址：192.168.1.127

其余为其可分配的主机号，192.168.1.1~192.168.1.126

对于 192.168.1.1xxxxxxx ，即192.168.1.128/25，

将其主机号位全取0，得到其网络地址：192.168.1.128

将其主机号位全取1，得到其广播地址：192.168.1.255

其余为其可分配的主机号，192.168.1.129~192.168.1.254

观察销售部分配的地址为192.168.1.1~192.168.1.20，属于192.168.1.1~192.168.1.126，即其所在子网为192.168.1.0/25。

观察技术部分配的地址为192.168.1.129~192.168.1.208，属于192.168.1.129~192.168.1.254，即其所在子网为192.168.1.128/25。

第一问。销售部子网的广播地址即192.168.1.0/25的广播地址，为192.168.1.127。

第二问。技术部子网的子网地址即192.168.1.128/25的网络地址，为192.168.1.128。

第三问。技术部子网可分配的主机号为192.168.1.129~192.168.1.254，共计254-129+1=126个。已经分配的主机号为192.168.1.129~192.168.1.208和路由器接口F1的地址192.168.1.254，共计208-129+1+1=81个，因此还可以分配的主机号有126-81=45，即若每个主机仅分配一个IP地址，则技术部子网还可以连接45台主机。

(2) 假设主机192.168.1.1向主机192.168.1.208发送一个总长度为1500 B的IP分组，IP分组的头部长度为20 B，路由器在通过接口F1转发该IP分组时进行了分配。若分片时尽可能分为最大片，则一个最大IP分片封装数据的字节数是多少？至少需要分为几个分片？每个分片的片偏移量是多少？

主机192.168.1.1向主机192.168.1.208发送一个总长度为 1500 B的IP分组，销售部子网的MTU=1500 B，技术部子网的MTU=800 B。因此，该IP分组能够顺利在销售部子网中进行传输，1500 B > 800 B，进入技术部子网时要进行分片。

分片先去除原来的IP分组的头的 20 B，对数据载荷1500 B - 20 B = 1480 B 进行分片，分片后每个分片的数据载荷不能超过 800 B -20 B = 780 B，且要求是 8 B 的整数倍（片偏移字段以 8 B 为单位）。

第一问。最大IP分片封装数据的字节数为 ⌊780 B/8⌋×8=776 B 。

第二问。至少需要分为 ⌈1480 B/776 B⌉=2 个分片。

第三问。第一个分片的片偏移量是 0 B / 8 B = 0，第二个分片的片偏移量是 776 B / 8 B = 97。

分片效果如下图所示：