解答：

方法一：逐步分析法

该过程主要代价为while循环，其中 x=2*x 的代价为 O(1) ，需要计算while循环的迭代次数。

初始时有 x=2=2^1 ；

while循环第 1 次迭代后有 x=2⋅2=2^(1+1) ；

归纳得while循环第 i 次迭代后有 x=2^(i+1) ；

假设第 k 次迭代后，恰有 ，此时跳出循环时，解得  。

while循环迭代次，所以该过程时间复杂度为  。

本题选A。

方法二：综合分析法

本题为单层循环类型题， x 呈指数增长，上限一定，对应循环次数为对数。

本题选A。

方法一：枚举

元素d开头的序列有：

• d, e, c, b, a
• d, c, e, b, a
• d, c, b, e, a
• d, c, b, a, e

本题选B。

方法二：推理

栈为先进后出的数据结构，已知d在出栈序列中为第一个元素，出栈子序列的子序列一定有d, c, b, a和d, e，考虑将e插入到子序列c, b, a中，有4个位置可以插入。

本题选B。

方法一：指针法

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端 front 进行删除操作，而在表的后端 rear 进行插入操作。

要求第一个进入队列的元素储存在 A[0] ，即队头位于 0 ，设此时队头指针和队尾指针分别为 front′ 和 rear′ 。

A[0] 入队后，front′ 为 0 ，入队元素增加在队尾，队尾指针 +1 ，rear′ 指向 0 ，即 (rear+1)modn=rear′ ，解得 rear=n−1 ，由于没有出队操作，队头指针不变，即 front=front′=0 。

本题选B。

方法二：开闭区间法

指针操作通常难度比较大，我们有没有更好的办法来解决这个问题，我们可以不从过程出发，直接从结果出发。

首先，先引入开闭区间的相关知识。

对于表示一段连续整数，通常有两种表示方法，假设  ，表示从 a 到 b 的所有整数，包括 a 和 b 。

方案一：枚举 x=a,a+1,a+2,…,b−1,b 。

方案二：区间  ，或者 。

通常第二种写法更加简洁，除了闭区间，还有开区间，下面默认 ，有四种写法：

闭区间： 

左闭右开：

左开右闭：

开区间： 

四种表示方法各有优劣，一般具体问题具体分析。

我们把开闭区间模型套用在队列上，队列中元素下标为一连串整数，设队头为区间左端点，队尾为区间右端点，教科书上的循环队列中队头指针指向队头元素位置，队尾指针指向队尾元素位置的下一个位置，是一个左闭右开模型，有位置  ，当 front=rear 时，显然有  ，即 。

现在回到本题，题目要求队列非空时， front 和 rear 分别指向队头元素和队尾元素。明显套用闭区间模型，有位置  ，初始时队列为空，有 ，推出 rear=front−1=0−1=−1 ，由于循环队列位置非负，将 −1 修改为 (−1+n)modn=n−1 即可。

本题选B。

解答：C。叶结点数为n，则度为2的结点数为n-1,度为1的结点数为0或1，本题中为1（总结点数为偶数），故而即2n=768。 

方法一：构造

设完全二叉树高度为 h ，有不等式 2^h−1≤768≤2^h−1 ，解得 h=10 ，倒数第二层结点数为 28=256 ，倒数第一层结点数为 768−(29−1)=257 ，需要占用倒数第二层 ⌈257⌉=129 个结点作为父结点，叶结点只会出现在倒数第二层和倒数第一层，所以该二叉树中叶结点的个数是 257+(256−129)=384 。

方法二：性质

叶结点个数为 n0 ，度为 2 的非叶结点数为 n2=n0−1 ，该树为完全二叉树，  。

又 n0+n1+n2=768 ，解得 n0=384 。

解答：C。由前序和后序遍历序列可知3为根结点，故（1,2）为左子树，（4）为右子树，

C不可能。或画图即可得出结果。

方法一：构造

利用前序遍历序列和后序遍历序列构造所有可能的二叉树。

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

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

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

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

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

结点2、3和4均可能在其父结点的左子树或者右子树，根据乘法原理，总共有 2×2×2=8 种可能。

画出所以

对比选项，中序遍历序列不可能为3, 2, 4, 1。

本题选C。

方法二：利用选项构造

方法一是利用前序遍历序列和后序遍历序列构造二叉树。

我们知道前序遍历序列和中序遍历序列可以唯一确定一棵二叉树，我们可以利用题目的前序遍历序列和选项的中序遍历序列构造二叉树，最后检查该二叉树的后序遍历序列是否和题目的后序遍历序列一致。

检查得，用题目的前序遍历序列和C选项的中序遍历序列构造出的二叉树的后序遍历序列和题目的后序遍历序列不一致。

本题选C。

方法一：性质

树转换为二叉树，用的是“左孩子右兄弟”表示法。

树的根结点一定没有兄弟结点，在对应的二叉树中的结点无右孩子。根结点数量为 1 。

树中每一个分支结点（非叶结点）的所有孩子结点中最右孩子结点在对应的二叉树中的结点无右孩子。分支结点数为 2011−116=1895 。

总计 1+1895=1896 。

本题选D。

方法二：举例

构造一棵树，叶结点全部在最后一层。

所有蓝色的非叶结点在对应的二叉树中的结点都没有右孩子，最右边一个叶结点在对应的二叉树中的结点没有右孩子。

总计 1895+1=1896 。

本题选D。

方法一：二分查找 + 双指针

折半查找就是二分查找，是一个双指针夹逼的过程，搜索区间不断缩小。

A选项： (−∞,95]→[22,95]→[22,91]→[24,91] ， 94 越界，错误。

B选项： [21,+∞)→[21,98]→[21,77]→[29,77]→[36,77]→[38,77] ，正确。

C选项： (−∞,92]→[20,92]→[20,91]→[34,91]→[34,88]→[35,88] ，正确。

D选项： [12,+∞)→[25,+∞)→[25,71]→[25,68]→[33,68]→[34,68] ，正确。

本题选A。

方法二：二叉搜索树 + 中序遍历

折半查找过程对应一棵二叉搜索树，其中序遍历序列单调递增。

解答：C。Ⅰ.回路对应于路径，简单回路对应于简单路径；Ⅱ．刚好相反；Ⅲ．拓扑有序的必要条件。故选C。 

回路也称环，是起点和终点相同的路径。简单路径是没有顶点重复的路径。回路最后有顶点重复，不可能是回路，I错误。

稀疏图是边相对于顶点少很多的情况，设顶点数为 n ，边数为 e ，用邻接矩阵存储空间为 O(n^2) ，用邻接表存储有向图存储空间为 O(n+e) ，无向图存储空间为 O(n+2e) ，明显存储稀疏图，用邻接表比邻接矩阵更省空间。II错误。

若有向图存在回路，则不存在拓扑序列，拓扑序列必须包含有向图中所有元素。III正确。

本题选C。

本题有争议

减小装填因子可以提高散列表的查找效率；处理冲突（碰撞）时可以减少，但不能“避免”产生聚集（堆积）现象，故选 B

III错在“避免”二字。

本题选B。

散列表查找效率取决于散列函数、冲突处理方法和装填因子。

装填因子越大说明散列表填的越满，越容易发生冲突。I错误。

合理的散列函数能够提高查找效率，最理想的情况是没有冲突发生，每个元素的查找长度均为 1 。II正确。

元素聚集会增大查找长度，所以尽量避免。III正确。

本题选D。

解答：A。快速排序需要对元素按下标进行随机访问，只有顺序存储满足。。

解答：B。首先与10比较，交换位置，再与25比较，不交换位置。比较了二次。 

调整过程中比较 2 次，交换 1 次。

审题要仔细，题目问的是调整过程中元素之间进行的比较次数，不是交换次数。

本题选B。

方法一：概念定义

MIPS是Million Instructions Per Second的缩写，即每秒处理的百万级的机器语言指令数，用于说明单字长定点指令平均执行速度。

CPI是Cycle Per Instruction的缩写，表示计算机执行一条指令所需的时钟周期数。

IPC是Instructions per Clock Cycle的缩写，是CPI的倒数，表示CPU每一时钟周期内所执行的指令数量。

MFLOPS是Million Floating-point Operations per Second的缩写，即每秒百万个浮点操作数，衡量计算机系统的技术指标，不能反映整体情况，只能反映浮点运算情况。

本题选D。

方法二：观察选项

如果完全不知道这些缩写，没关系，只要知道浮的英文或者拼音就行，因为很多高级编程语言中浮点数用float表示，浮点数(Floating Point)缩写首字母为F，所以描述浮点数操作速度指标中一定包含字母F，浮为音译，浮的拼音为Fu，观察选项，只有D选项包含字母F。

本题选D。

IEEE754单精度浮点数的格式如下：

本题选A。

EPROM是Erasable Programmable Read-Only Memory的缩写，即可擦除可编程只读存储器。通过在存储器芯片中设计的窗口照射强紫外线，可以擦除数据并对芯片进行重新编程，这个过程被称为烧录。

CDROM是Compact Disk Read-Only Memory的缩写，即小型光盘只读存储，简称光盘。

DRAM是Dynamic Random Access Memory的缩写，即动态随机存取存储器。

SRAM是Static Random-Access Memory的缩写，即静态随机存取存储器。

所谓“随机存取”，类比数据结构数组，指的是当存储器中的消息被读取或写入时，所需要的时间与这段信息所在的位置无关。相对的，读取或写入顺序访问存储设备中的信息时，其所需要的时间与位置就会有关系（如磁带），类比数据结构链表。随机存取存储器（RAM）是计算机存储器中最为人熟知的一种，包括SRAM、DRAM、FPM DRAM、EDO DRAM、SDRAM、DDR SDRAM、RDRAM等。

随机存取即随机访问，英文为Random Access，缩写为RA，很容易排除选项C和D。

选项A和B都属于ROM，但是EPROM可以通过编程器写入数据，可以理解为伪随机存取，写入时间比读取时间慢得多，EEPROM (Electrically Erasable Programmable read only memory) 本质上是 EPROM 的更新。CDROM一定不能进行随机存取，只能顺序存取。相比之下，选项B更适合作为正确选项。

本题选B。

按字节编址，主存地址空间大小为64MB，MAR寻址范围为 64M=226 ，MAR的位数至少是26位。这里实际的主存容量32MB为干扰条件，因为主存是可以扩展的。

本题选D。

间接寻址：不需要寄存器，有效地址EA=(A)。

基址寻址：需要基址寄存器BR，有效地址EA=(BR)+A。

相对寻址：需要程序计数器PC，有效地址EA=(PC)+A。

变址寻址：需要变址寄存器IX，有效地址EA=(IX)+A。

本题选A。

解答：C。无符号整数比较，如A>B，则A-B无进位/借位，也不为0。故而CF和ZF均为0。

本题考察布尔运算(Boolean operations)，A 或 B 记为 A+B 或 A∨B ，A 与 B 记为 AB 或 A∧B ，非A记为 或 ¬A 。

常用布尔运算：

或(disjunction or OR)： ∨

0∨0=0

0∨1=1

1∨0=1

1∨1=1

与(conjunction or AND)： ∧

0∧0=0

0∧1=0

1∧0=0

1∧1=1

非(negation or NOT)： ¬

¬0=1

¬1=0

异或(exclusive or or XOR)： ⊕

0⊕0=0

0⊕1=1

1⊕0=1

1⊕1=0

CF、ZF、SF和OF是计算机体系结构和汇编语言编程中常用的缩写。

• CF：进位标志(Carry Flag)。它是处理器状态寄存器中的一个标志位，指示算术操作是否产生了进位或借位。例如，在加法操作中，如果结果太大而无法放入目标寄存器，就会设置进位标志。
• ZF：零标志(Zero Flag)。该标志表示操作结果是否为零。如果结果为零，则设置零标志，否则清除。
• SF：符号标志(Sign Flag)。它指示算术操作的结果的符号。具体而言，如果结果为负数，则设置符号标志；如果结果为正数或零，则清除。
• OF：溢出标志(Overflow Flag)。当算术操作产生的结果超出了可用位数的表示范围时，设置该标志。它表示在操作过程中发生了溢出。

这些标志对于在汇编语言编程中进行分支和条件执行非常重要。它们允许程序根据先前操作的结果做出决策。

由于本题考察无符号整数运算，不涉及SF，排除选项B和D。

bgt是Branch on Greater Than的缩写，表示大于时分支。

设无符号整数 a>b 为真，移项得 a−b>0 为真，所以 a 够减 b ，所以 a−b 无借位且 a−b≠0 ，所以 CF=0 且 ZF=0 为真，即 ¬CF=1 且 ¬ZF=1 为真，即 ¬CF∧¬ZF=1 ，根据德摩根律（口诀：短杠变长杠或长杠变短杠，开口换方向）有 ¬(CF∨ZF)=1 ，即 ¬(CF+ZF)=1 。

本题选C。

解答：D。指令定长、对齐、仅Load/Store指令访存，以上三个都是RISC的特征。均能够有效的简化流水线的复杂度。

RISC利于实现指令流水线，I、II、III都是RISC的特征。

解答：C。会自动加1，A取指令要访存、B时钟周期对指令不可分割。

由于不采用指令预取技术，每个指令周期都需要取指令，而不采用Cache技术，则每次取指令都至少要访问内存一次（当指令字长与存储字长相等且按边界对齐时），A正确。

时钟周期是CPU的最小时间单位，每个指令周期一定大于或等于一个CPU时钟周期，B正确。

即使是空操作指令，在取指操作后，PC也会自动加1，即自动指向下一条指令所在地址，C错误。

由于机器处于“开中断”状态，在每条指令执行结束时都可能被外部中断而打断，D正确。

在取指令时，指令便是在数据线上传输的。A正确。

操作数显然在数据线上传输。B正确。

握手（应答）信号属于通信联络控制信号，应在通信总线上传输。C错误。

中断类型号用以指出中断向量的地址，CPU响应中断请求后，将中断应答信号（INTR）发回到数据总线上，CPU从数据总线上读取中断类型号后，查找中断向量表，找到相应的中断处理程序入口。D正确。

本题选C。

中断屏蔽字(Interrupt Mask Register)是用于控制和管理中断系统的一个寄存器。它通常是在计算机的控制器或处理器中的一个专门寄存器，用于控制中断信号的屏蔽（禁止）和允许。

1表示屏蔽，0表示允许。一个中断需要屏蔽自身和处理优先级比其低的中断。

因为中断处理优先级从高到低的顺序是 L4→L0→L2→L1→L3 ，所以 L1 能够屏蔽 L1 和 L3 ，所以 M1 和 M3 为1，其它位为0，所以 M4M3M2M1M0=01010 。

本题选D。

因为每秒需对其查询至少200次且查询程序运行一次所用的时钟周期数至少为500，所以每秒查询至少需要200×500=100000=0.1M个周期，又因为CPU主频为50MHz，所以CPU用于设备A的I/O的时间占整个CPU时间的百分比至少为0.1M/50M=0.20%。

本题选C。

A错误。先来先服务调度算法不会发生发生饥饿现象，但不一定满足短任务优先。

B正确。高响应比优先调度算法兼具先来先服务调度算法和短任务优先调度算法的有点。响应比=作业响应时间/作业执行时间 = (作业执行时间+作业等待时间)/作业执行时间。高响应比算法，在等待时间相同情况下，作业执行时间越少，响应比越高，优先执行，满足短任务优先。随着等待时间增加，响应比也会变大，执行机会就增大，所以不会产生饥饿现象。

C错误。时间片轮转调度算法不会发生发生饥饿现象，但不一定满足短任务优先。

D错误。非抢占式短任务优先调度算法满足短任务优先，但可能发生饥饿现象。

本题选B。

【答案】A

【解析】缺页处理和时钟中断都属于中断，在核心态执行；进程调度是操作系统内核进程，无须用户干预，在核心态执行；命令解释程序属于命令接口，是4个选项中唯一能面对用户的，它在用户态执行。

A正确。命令解释程序 (Command Interpreter) 是运行在用户态的应用程序，也称为shell。它接收用户输入的命令，并将其解释和执行。命令解释程序负责解析命令行参数、调用相应的系统调用和应用程序来执行命令，以及显示结果给用户。

B、C、D错误。进程调度程序、缺页处理程序和时钟中断处理程序通常是在内核态（也称为特权态）下执行的。这些程序涉及到底层的操作系统功能，需要更高的权限才能执行。

【答案】D

【解析】进程中的线程共享进程内的全部资源，但进程中某线程的栈指针对其他线程是透明的，不能与其他线程共享。

在多线程的系统中，不同线程共享进程P的代码段、全局变量和打开的文件。这意味着它们可以访问和修改相同的代码和数据。然而，每个线程都有自己的栈空间，用于存储局部变量和函数调用信息。每个线程的栈指针指向其自己的栈空间，而不是共享的。因此，不同线程之间的栈空间是独立的，无法直接共享。

用户程序发出磁盘 I/O 请求后，系统的正确处理流程是用户程序→系统调用处理程序→设备驱动程序→中断处理程序。下面是各个步骤的说明：

1. 用户程序：用户程序首先发出磁盘 I/O 请求，例如读取或写入文件。
2. 系统调用处理程序：当用户程序发出系统调用请求时，控制权会传递给系统调用处理程序。系统调用处理程序是操作系统的一部分，负责接收和处理来自用户程序的系统调用请求。
3. 设备驱动程序：在系统调用处理程序确定磁盘 I/O 请求后，控制权会传递给相应的设备驱动程序。设备驱动程序是操作系统中负责管理和控制硬件设备的一部分。它会将磁盘 I/O 请求转换成与硬件设备通信的命令和操作。
4. 中断处理程序：设备驱动程序发出磁盘 I/O 请求后，硬盘控制器开始执行相应的操作。在操作完成后，硬盘控制器会产生一个中断信号，通知操作系统完成了磁盘 I/O 操作。中断处理程序负责接收和处理这个中断信号，并将控制权返回给系统调用处理程序。

本题选B。

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

模拟过程如下：

依次输出P1和P4后，R2的可用资源数为2，但P2和P3均需要3个R2资源才能够继续执行，系统无法继续分配资源。不存在安全序列。

本题选D。

在缺页处理过程中，当访问的页面不在主存中，会触发缺页异常。为了处理该异常，操作系统需要进行以下操作：

分配页框：当页面缺失时，操作系统需要为该页面分配一个合适的物理页框，以供页面调入主存。这包括从空闲页框池中选择一个可用页框。III正确。

磁盘 I/O：由于缺失的页面不在内存中，操作系统需要通过磁盘 I/O 将该页面读取到主存中。这涉及到磁盘读取操作，将页面从磁盘加载到主存。II正确。

修改页表：操作系统需要修改页表，将缺失页面映射到主存中的合适页框。这样，当页面再次被访问时，就可以直接从主存中获取而不触发缺页异常。I正确。

综上，Ⅰ、Ⅱ和Ⅲ正确。

本题选D。

答案：A

在具有对换功能的操作系统中，通常把外存分为文件区和对换区。前者用于存放文件，后者用于存放从内存换出的进程。

抖动现象是指刚刚被换出的页很快又要被访问，为此又要换出其他页，而该页又很快被访问，如此频繁地置换页面，以致大部分时间都花在页面置换上，导致系统性能下降。

撤销部分进程可以减少所要用到的页面数，防止抖动。对换区大小和进程优先级都与抖动无关。

“抖动”现象是指刚刚被换出的页很快又要被访问，为此，又要换出其他页，而该页又很快被访问，必须换入，如此频繁地置换页面，以致操作系统的大部分时间都花在页面置换上，引起系统性能下降甚至崩溃。

引起系统抖动现象的原因是对换的信息量过大，内存容量不足，置换算法选择不当。所以解决的办法就是降低交换页面数量，加大内存容量，改变置换选择算法。但是降低交换页面数量和改变置换选择算法对于一个应用系统来讲是不可能的，只能增加内存容量。增加内存容量可以是直接添加物理内存（大型计算机都可以在不关机的情况下增加物理内存条），或者，降低进程数量，相对地增加内存。

I正确。撤销部分进程可以相对地增加内存。

II错误。增加交换区容量并不能解决内存不足的问题。

Ⅲ错误。提高用户进程的优先级并不能解决内存不足的问题。

综上，仅I正确。

答案：C

编译后的程序需要经过链接才能装载，而链接后形成的目标程序中的地址也就是逻辑地址。

A错误。编辑：在编辑阶段，程序员编写程序代码，并使用文本编辑器进行修改和保存。

B错误。编译：编译器将源代码转换为目标代码。

C正确。链接：在链接阶段，编译器将生成的目标代码与程序所需的库函数和其他目标文件进行链接，生成最终的可执行文件和该文件的逻辑地址（虚拟地址）。

D错误。装载：在装载阶段，操作系统将可执行文件从磁盘加载到物理内存中，并将程序的逻辑地址（虚拟地址）转换为物理地址。这个过程由地址变换机构（如页表或段表）完成。

设磁盘数据输入到缓冲区用时T，缓冲区传送数据到工作区用时M，CPU处理数据用时C。

连续输入情况下，单缓冲区处理每块数据用时 max{C,T}+M （C和T并行）

单缓冲区仅处理 n 块数据用时 (n−1)(max{C,T}+M)+T+M+C （中间n-1段包含C和T并行，第一个数据块的T和M以及最后一个数据块的C无法并行执行）。

连续输入情况下，双缓冲区处理每块数据用时 max{C+M,T} （C+M和T并行执行）

双缓冲区仅处理 n 块数据用时 (n−1)max{C+M,T}+T+M+C （中间n-1段包含C+M和T并行执行，第一个数据块的T和最后一个数据块的M和C无法并行执行）。

本题中，T=100μs，M=50μs，C=50μs，n=10，代入公式得

在单缓冲区读入并分析完该文件的时间是1550μs。

在双缓冲区读入并分析完该文件的时间是1100μs。

本题选B。

将P1中的3条语句依次编号为1，2，3，将P2中的3条语句依次编号为4，5，6，则依次执行1，2，3，4，5，6得结果1，依次执行1，2，4，5，6，3得结果2，依次执行4，5，1，2，3，6得结果0.结果-1不可能得出。

为了方便讨论，将每行代码进行编号

load R1, x ① // 取x到寄存器R1中
inc R1 ② // 将R1中的操作数加一
store x, R1 ③ // 将R1的内容存入x
load R2, x ④ // 取x到寄存器R2中
dec R2 ⑤ // 将R2中的操作数减一
store x, R2 ⑥ // 将R2的内容存入x

方法一：枚举所有情况

x为1：例如执行①, ②, ③, ④, ⑤, ⑥，或者执行④, ⑤, ⑥, ①, ②, ③。

x为2：例如执行①, ②, ④, ⑤, ⑥, ③。

x为0：例如执行 ④, ⑤, ①, ②, ③ ⑥。

本题选C。

方法二：排除法

由于P1为加1操作，P2为减1操作，各执行一次，结果在数轴上具有对称性，由共享初值为1的变量x，结果关于1对称，排除D。

由于P1和P2均只执行1次，要得到3需要执行两次P1，得到-1需要执行两次P2，排除A和D。

由于先执行P1后执行P2得到1，正确选项一定包含1，排除A。

由于P1和P2均不是原子操作，排除B。

本题选C。

虚电路服务是面向连接的可靠的服务。虚电路服务是为整个传输建立通路，包括线路建立，数据传输和线路拆除，并在建立虚电路时有延时，传输数据时延时较小。虚电路对网络的可靠性依赖较大，数据报较灵活；虚电路是可靠的传输，适合交互通信。

数据报服务是无连接，不可靠的服务。数据报服务是为每个分组寻找通路；数据报为每个分组寻找通路，没建立线路的过程，传输分组时延时较大。数据报是不可靠的传输，但可提高线路的利用率。

根据 TCP/IP 参考模型，网络层提供的是无连接不可靠的数据报服务。

本题选 A。

数据传输速率的单位是 bps，即比特/秒，波特率的单位是波特 (Baud)，即码元/秒。每个码元可携带比特数量为 log2⁡M ，其中 M 为调制技术中可利用的符号数量。

本题中，采用 4 相位调制，即 M=4,log₂⁡M=2 ，有 1 Baud = 2 bps，推出 2400 bps = 1200 Baud。

本题选 B。

在选择重传协议中，接收方会独立确认每一个帧。根据问题描述，1 号帧已经收到确认，而 0 和 2 号帧超时未收到确认。因此需要需要重传 0 和 2 号帧，需要重传的帧数为 2。

本题选 B。

A 错误。CSMA (Carrier Sense Multiple Access) 载波监听多点接入。

B 错误。CDMA (Code Division Multiple Access) 码分多址，一种无线通信技术，用于多用户同时在同一频率范围内进行通信。它采用编码和分配不同的码片给每个用户，从而实现信号的隔离和并行。CDMA被广泛应用于移动通信系统中。

C 错误。CSMA/CD (Carrier Sense Multiple Access/collision detection) 带有冲突检测的载波监听多点接入，在以太网中使用随机争用型的介质访问控制方法，CSMA/CD 的基本原理是：每个节点都共享网络传输信道，在每个站要发送数据之前，都会检测信道是否空闲，如果空闲则发送，否则就等待；在发送出信息后，则对冲突进行检测，当发现冲突时，则取消发送。CSMA/CD 是早期以太网使用的有线信道访问控制协议，并不采用确认机制。

D 正确。CSMA/CA（Carrier Sense Multiple Access with Collision Avoidance）带有冲突避免的载波侦听多路访问。是802.11局域网采用的无线信道访问控制协议。由于不可能避免所有的碰撞，并且无线信道误码率较高，CSMA/CA使用了数据链路层确认机制（停止-等待协议）来保证数据被正确接收。CSMA/CA 利用 ACK 帧来避免冲突的发生，也就是说，只有当客户端收到网络上返回的 ACK 帧后才确认送出的数据已经正确到达目的地址。

本题选 D。

若不考虑路由聚合，则 R1 的路由表如下：

由于路由器 R1 只有到达子网 192.168.1.0/24 的路由，且仅需要增加的一条路由，所以需要将后两条路由进行聚合，采用找最长公共前缀的方法，得到 192.168.2.0/25 和 192.168.2.128/25 聚合后的网络为 192.168.2.0/24，即需要增加的一条路由（目的网络，子网掩码，下一跳）是 192.168.2.0 255.255.255.0 192.168.1.2。

本题选 D。

首先需要判断 192.168.4.3 是地址空间 192.168.4.0/30 中的一个单播地址还是广播地址，或者不在该地址空间中。

若给定目的地址不在给定地址空间中，则接收给定目的地址即的 IP 分组的最大主机数是 0。

若给定目的地址是给定地址空间中的一个单播地址，则接收给定目的地址即的 IP 分组的最大主机数是 1。

若给定目的地址是给定地址空间中的一个广播地址，则接收给定目的地址即的 IP 分组的最大主机数是给定地址空间中可分配的最大主机数。

子网 192.168.4.0/30 前 30 位为网络前缀，将 192.168.4.0/30 低 8 位写成二进制形式，其中主机号部分用的位用 x 表示，每个 x 可以取 0 或 1。二进制位用红色表示。 192.168.4.000000xx 。

将主机号全取 0，得到该子网的网络地址， 192.168.4.00000000 ，即 192.168.4.0。

将主机号全取 1，得到该子网的广播地址， 192.168.4.00000011 ，即 192.168.4.3。

计算出子网中可以分配的主机数为 2^(32−30)−2=2^2−2=4−2=2 。

显然题目给定目的地址是给定地址空间中的一个广播地址，因此接收给定目的地址即的 IP 分组的最大主机数是给定地址空间中可分配的最大主机数 2。

本题选 C。

本题考察 TCP 协议的三次握手过程。该过程的示意图如下：

主机乙在接受连接请求后，会向主机甲发送确认连接的 TCP 段。在这个过程中，应该设定 SYN 标志位为 1 表示连接请求，ACK 标志位为 1 表示确认号字段包含有效的确认序号。主机甲向主机乙发送的报文 seq＝11220，主机乙向主机甲发送的确认号 ack = 11220 + 1 = 11221。

本题选 C。

TCP 使用累积确认，确认号字段对已接收且按序到达的最后一个报文段进行确认，指示的是期望接收的下一个字节的序号。当主机乙仅正确接收到第 1 和第 3 个段时，说明第 2 个段在网络传输中滞留或丢失，按序到达的最后一个报文段是第 1 个段。主机乙期望接收第 1 个段的最后一个字节号的下一个字节号，即第 2 个段的第一个字节号。

因为第 3 个段的序号为 900 且有 500 字节的有效载荷，所以第 3 个段的字节序号为 900~1399，

因为第 2 个段有 400 字节的有效载荷，所以第 2 个段的字节序号为 500~899。

第 2 个段的第一个字节号为 500，主机乙发送给主机甲的确认序号是 500。

本题选 B。

⑴ 将一维数组按行优先填入上三角矩阵即可，注意某顶点到自身的距离为 0 ，即 A[i][i]=0 。

画图可得矩阵 A ，如图(b)所示。

⑵ 如图(c)所示。

⑶ 方法一：求解关键路径

关键路径求解步骤如下：

1. 找出有向带权图 G=(V,E) 一个拓扑序列。
2. 按拓扑序列（从源点往汇点）推导事件（顶点） i 的最早发生时间 ve(i)=max{ve(j)+w(j,i):(j,i)∈E} 。
3. 按逆拓扑序列（从汇点往源点）推导事件（顶点） i 的最晚发生时间 vl(i)=min{vl(j)−w(i,j):(i,j)∈E} 。
4. 按拓扑序列（从源点往汇点）推导活动（有向边） (i,j) 的最早发生时间 e(i,j) ，即有向边 (i,j) 的起点 i 的最早发生时间 ve(i) 。
5. 按逆拓扑序列（从汇点往源点）推导活动（有向边） (i,j) 的最晚发生时间 l(i,j) ，即有向边 (i,j) 的终点最晚发生时间 vl(j) 减去弧长 w(i,j) 。
6. 计算活动时间余量 l(i,j)−e(i,j) ，时间余量为 0 的活动为关键活动。

选取拓扑序列为：0, 1, 2, 3, 4, 5，本题拓扑序列不唯一，也可以是0, 1, 2, 4, 3, 5。

很明显，关键路径为0→1→2→3→5，关键路径长度为 4+5+4+3=16 。

方法二：找出最长路径

从源点到汇点的关键路径也是从源点到汇点的最长路径，显然从源点0到汇点5一定经过结点2，即关键路径一定是 0⇝2⇝5 的形式，拆分成 0⇝2 和 2⇝5 。

对于 0⇝2 ，有  和  ，显然前者权值6小于后者4+5=9，所以关键路径包含  。

对于 2⇝5 ，有  和  ，显然前者权值4+3=7大于后者3+3=6，所以关键路径包含  。

综上，从源点到汇点的最长路径为为，即为关键路径，关键路径长度为 4+5+4+3=16 。

两个有序数组分别是 A[0:n−1] 和 B[0:n−1] 。要找到第 n 个元素，我们可以比较 A[⌈n/2⌉−1] 和 B[⌈n/2⌉−1] 。

由于 A[⌈n/2⌉−1] 和 B[⌈n/2⌉−1] 的前面分别有 A[0:⌈n/2⌉−2] 和 B[0:⌈n/2⌉−2] ，即各有 ⌈n/2⌉−1 个元素，对于 min{A[⌈n/2⌉−1],B[⌈n/2⌉−1]} ，

若 n 为奇数，则 2(⌈n/2⌉−1)<2(n/2+1−1)=n ，最多只会有 n−1 个元素比它小，也就是 min{A[⌈n/2⌉−1],B[⌈n/2⌉−1]} 最多恰为第 n 小的数，这里先假设 A[⌈n/2⌉−1]<B[⌈n/2⌉−1] ，则 A[0:⌈n/2⌉−2] （等价于 A[0:⌊n/2⌋−1] ）都小于或等于 A[⌈n/2⌉−1] ，可以直接排除。

若 n 为偶数，则 2(⌈n/2⌉−1)=2(n/2−1)=n−2 ，最多只会有 n−2 个元素比它小，也就是 min{A[⌈n/2⌉−1],B[⌈n/2⌉−1]} 最多恰为第 n−1 小的数，这里先假设 A[⌈n/2⌉−1]<B[⌈n/2⌉−1] ，则 A[0:⌈n/2⌉−1] （等价于 A[0:⌊n/2⌋−1] ）都小于或等于 A[⌈n/2⌉−1] ，可以直接排除。

由于 A[⌈n/2⌉−1] 和 B[⌈n/2⌉−1] 的后面分别有 A[⌈n/2⌉:n−1] 和 B[⌈n/2⌉:n−1] ，即各有 n−⌈n/2⌉ 个元素，对于 max{A[⌈n/2⌉−1],B[⌈n/2⌉−1]} ，因为 2(n−⌈n/2⌉)≤2(n−n/2)=n 最多只会有 n 个元素比它大，也就是 max{A[⌈n/2⌉−1],B[⌈n/2⌉−1]} 最少恰为第 n 小的数，这里先假设 A[⌈n/2⌉−1]<B[⌈n/2⌉−1] ，则 B[⌈n/2⌉:n−1] （等价于 B[n−⌊n/2⌋−1:n−1] ）都大于或等于 B[⌈n/2⌉−1] ，可以直接排除。

因此我们可以归纳出三种情况：

• 情况一： A[⌈n/2⌉−1]<B[⌈n/2⌉−1] ，排除 A[0:⌊n/2⌋−1] 和 B[n−⌊n/2⌋−1:n−1] ，同时缩小 n 为 ⌈n/2⌉ 。
• 情况二： A[⌈n/2⌉−1]>B[⌈n/2⌉−1] ，排除 A[n−⌊n/2⌋−1:n−1] 和 B[0:⌊n/2⌋−1] ，同时缩小 n 为 ⌈n/2⌉ 。
• 情况三： A[⌈n/2⌉−1]=B[⌈n/2⌉−1] ，归纳为情况一或者情况二。

其实我们可以对情况三进行进一步讨论，此时设 A[⌈n/2⌉−1]=B[⌈n/2⌉−1]=m 。

若 n 为奇数，此时恰有 n−1 个元素小于或等于 m ，且恰有 n−1 个元素大于或等于 m ，取 A[⌈n/2⌉−1] 或 B[⌈n/2⌉−1] 放入大于或等于 m 的集合，则恰有 n−1 个元素小于或等于 m ，且恰有 n 个元素大于或等于 m ，则 m 为中位数，可以直接返回。

若 n 为偶数，此时恰有 n−2 个元素小于或等于 m ，且恰有 n−1 个元素大于或等于 m ，取 A[⌈n/2⌉−1] 或 B[⌈n/2⌉−1] 放入小于或等于 m 的集合，则恰有 n−1 个元素小于或等于 m ，且恰有 n 个元素大于或等于 m ，则 m 为中位数，可以直接返回。

因此三种情况可以优化为：

• 情况一： A[⌈n/2⌉−1]<B[⌈n/2⌉−1] ，排除 A[0:⌊n/2⌋−1] 和 B[n−⌊n/2⌋−1:n−1] ，同时缩小 n 为 ⌈n/2⌉ 。
• 情况二： A[⌈n/2⌉−1]>B[⌈n/2⌉−1] ，排除 A[n−⌊n/2⌋−1:n−1] 和 B[0:⌊n/2⌋−1] ，同时缩小 n 为 ⌈n/2⌉ 。
• 情况三： A[⌈n/2⌉−1]=B[⌈n/2⌉−1] ，直接返回 A[⌈n/2⌉−1] 。

递归调用上述过程，终止情况：

• n=1 ，返回两个数组仅剩余两个元素中的最小值。

因为 0<⌈n/2⌉<n−1 ，所以不会越界。

画出有向图，→指向表示有向边，有向边起点元素小于或等于有向边终点元素。

如上图，灰色结点淘汰。

递归版本一，保存下标，为原地算法。这里总共有五个变量， 两个数组的首尾元素下标合计4个，数组长度一个，由于 p+n−1=r ，我们只记录 A 首个元素下标 pa ，B 首个元素下标 pb ，和数组长度 n 。

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

#include <stdio.h>

int min(int x, int y) {
    return x < y ? x : y;
}

int findMedian(int *a, int *b, int n, int pa, int pb) {
    if (n == 1) {
        return min(a[pa], b[pb]);
    }
    int ma = pa + (n + 1) / 2 - 1;
    int mb = pb + (n + 1) / 2 - 1;
    if (a[ma] < b[mb]) {
        return findMedian(a, b, (n + 1) / 2, pa + n / 2, pb);
    } else if (a[ma] > b[mb]) {
        return findMedian(a, b, (n + 1) / 2, pa, pb + n / 2);
    } else {
        return a[ma];
    }
}

int findMedianSortedArrays(int *A, int *B, int n) {
    return findMedian(A, B, n, 0, 0);
}

int main() {
    int s1[] = {11, 13, 15, 17, 19};
    int s2[] = {2, 4, 6, 8, 20};
    printf("%d", findMedianSortedArrays(s1, s2, 5));
    return 0;
}

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

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

int findMedian(vector<int>& A, vector<int>& B, int pa, int pb, int n) {
    if (n == 1) {
        return min(A[pa], B[pb]);
    }
    int ma = pa + (n + 1) / 2 - 1;
    int mb = pb + (n + 1) / 2 - 1;
    if (A[ma] < B[mb]) {
        return findMedian(A, B, pa + n / 2, pb, (n + 1) / 2);
    } else if (A[ma] > B[mb]) {
        return findMedian(A, B, pa, pb + n / 2, (n + 1) / 2);
    } else {
        return A[ma];
    }
}

int findMedianSortedArrays(vector<int>& A, vector<int>& B) {
    int n = (int)A.size();
    return findMedian(A, B, 0, 0, n);
}

int main() {
    vector<int>s1 = {11, 13, 15, 17, 19};
    vector<int>s2 = {2, 4, 6, 8, 20};
    cout << findMedianSortedArrays(s1, s2);
    return 0;
}

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

迭代版本一，保存下标，为原地算法。

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

#include <stdio.h>

int min(int x, int y) {
    return x < y ? x : y;
}

int findMedianSortedArrays(int *a, int *b, int n) {
    int pa = 0, pb = 0, ma, mb;
    while (n > 1) {
        ma = pa + (n + 1) / 2 - 1;
        mb = pb + (n + 1) / 2 - 1;
        if (a[ma] == b[mb]) return a[ma];
        if (a[ma] < b[mb]) {
            pa += n / 2;
        } else {
            pb += n / 2;
        }
        n = (n + 1) / 2;
    }
    return min(a[pa], b[pb]);
}

int main() {
    int s1[] = {11, 13, 15, 17, 19};
    int s2[] = {2, 4, 6, 8, 20};
    printf("%d", findMedianSortedArrays(s1, s2, 5));
    return 0;
}

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

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

int findMedianSortedArrays(vector<int>& A, vector<int>& B) {
    int n = (int)A.size();
    int pa = 0, pb = 0, ma, mb;
    while (n > 1) {
        ma = pa + (n + 1) / 2 - 1;
        mb = pb + (n + 1) / 2 - 1;
        if (A[ma] == B[mb]) return A[ma];
        if (A[ma] < B[mb]) {
            pa += n / 2;
        } else {
            pb += n / 2;
        }
        n = (n + 1) / 2;
    }
    return min(A[pa], B[pb]);
}

int main() {
    vector<int>s1 = {11, 13, 15, 17, 19};
    vector<int>s2 = {2, 4, 6, 8, 20};
    cout << findMedianSortedArrays(s1, s2);
    return 0;
}

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

迭代版本二，C代码如下（含测试用例）：

#include <stdio.h>

int min(int x, int y) {
    return x < y ? x : y;
}

int findMedianSortedArrays(int *A, int *B, int n) { // n即为序列长度L
    int s1 = 0, e1 = n - 1, mid1, s2 = 0, e2 = n - 1, mid2;
    while(s1 != e1 || s2 != e2) {
        mid1 = (s1 + e1) / 2;
        mid2 = (s2 + e2) / 2;
        if (A[mid1] == B[mid2]) {
             return A[mid1];
        } else if (A[mid1] < B[mid2]) {
            // 分别考虑奇数和偶数，保持两个子数组元素个数相等
            if ((s1 + e1) % 2 == 0) { // 若元素个数为奇数
                 s1 = mid1;  // 舍弃A中间点以前的部分
                 e2 = mid2;  // 舍弃B中间点以后的部分
            } else { // 若元素个数为偶数
                 s1 = mid1 + 1;  // 舍弃A中间点及中间点以前的部分
                 e2 = mid2;  // 舍弃B中间点以后的部分
            }
        } else {
            // 分别考虑奇数和偶数，保持两个子数组元素个数相等
            if ((s1 + e1) % 2 == 0) { // 若元素个数为奇数
                 e1 = mid1;  // 舍弃A中间点以后的部分
                 s2 = mid2;  // 舍弃B中间点以前的部分
            } else { // 若元素个数为偶数
                 e1 = mid1;  // 舍弃A中间点以后的部分
                 s2 = mid2 + 1;  // 舍弃B中间点及中间点以前的部分
            }
        }
    }
    return min(A[s1], B[s2]);
}

int main() {
    int s1[] = {11, 13, 15, 17, 19};
    int s2[] = {2, 4, 6, 8, 20};
    printf("%d", findMedianSortedArrays(s1, s2, 5));
    return 0;
}

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

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

int findMedianSortedArrays(vector<int>& A, vector<int>& B) {
    const int n = A.size();
    int s1 = 0, e1 = n - 1, mid1, s2 = 0, e2 = n - 1, mid2;
    while(s1 != e1 || s2 != e2) {
        mid1 = (s1 + e1) / 2;
        mid2 = (s2 + e2) / 2;
        if (A[mid1] == B[mid2]) {
             return A[mid1];
        } else if (A[mid1] < B[mid2]) {
            // 分别考虑奇数和偶数，保持两个子数组元素个数相等
            if ((s1 + e1) % 2 == 0) { // 若元素个数为奇数
                 s1 = mid1;  // 舍弃A中间点以前的部分
                 e2 = mid2;  // 舍弃B中间点以后的部分
            } else { // 若元素个数为偶数
                 s1 = mid1 + 1;  // 舍弃A中间点及中间点以前的部分
                 e2 = mid2;  // 舍弃B中间点以后的部分
            }
        } else {
            // 分别考虑奇数和偶数，保持两个子数组元素个数相等
            if ((s1 + e1) % 2 == 0) { // 若元素个数为奇数
                 e1 = mid1;  // 舍弃A中间点以后的部分
                 s2 = mid2;  // 舍弃B中间点以前的部分
            } else { // 若元素个数为偶数
                 e1 = mid1;  // 舍弃A中间点以后的部分
                 s2 = mid2 + 1;  // 舍弃B中间点及中间点以前的部分
            }
        }
    }
    return min(A[s1], B[s2]);
}

int main() {
    vector<int>s1 = {11, 13, 15, 17, 19};
    vector<int>s2 = {2, 4, 6, 8, 20};
    cout << findMedianSortedArrays(s1, s2);
    return 0;
}

时间复杂度： O(log⁡n) 。

空间复杂度： O(1) 。

（1）R1=134=86H, R5=90H, R6=7CH；
134=1000 0110B=86H；x - y=1000 0110B - 1111 0110B=1001 0000B=90H；x + y=1000 0110B + 1111 0110B=0111 1100B（溢出）
（2）m=-122,k1=-112
m=1000 0110B，做高位为符号位，则m的原码为1111 1010B=-122；n=1111 0110B
n的原码为1000 1001=-10；k1=m - n=-112。
（3）能。无符号数和有符号数都是以补码的形式存储，加减运算没有区别（不考虑溢出情况时），只是输出的时候若是有符号数的最高位是符号位。
减法运算求[-x]补的时候，是连同符号位一起按位取反末位加1，但是如果有溢出情况，这两者是有区别的，所以可以利用同一个加法器实现，但是溢出判断电路不同。
（4）判断方法是如果最高位进位和符号位的进位不同，则为溢出；“int k2=m + n;”会溢出；
三种方法可以判断溢出，双符号位、最高位进位、符号相同操作数的运算后与原操作数的符号不同则溢出 

（1）24位、前12位；20位、前8位。

16M=224故虚拟地址24位，4K=212，故页内地址12位，所以虚页号为前12位；

1M=220故物理地址20位，20-12=8，故前8位为页框号。

（2）主存字块标记（12bit）、cache字块标记（3bit）、字块内地址（5bit）物理地址20位，其中，块大小为32B=25B故块内地址5位；cache共8行，8=23，故字块标记为3位20-5-2=12，故主存字块标记为12位。

（3）在主存中，04C60H, 不命中，没有04C的标记字段001C60H中虚页号为001H=1，查页表知其有效位为1，在内存中；该物理地址对应的也表项中，页框号为04H故物理地址为04C60H；物理地址04C60H在直接映射方式下，对应的行号为3，有效位为1但是标记位为064H≠04CH故不命中。

（4）在，012的那个标记是对的。思路：标记11位组地址1位页内地址12位，前12位为0000 0010 0100，组地址位为0，第0组中存在标记为012的页，其页框号为1F，故024BACH所在的页面存在主存中。

本题为典型的生产者消费者问题，生产者为顾客，消费者为营业员，缓冲区为座位区。

取号机只有一个资源，需要互斥访问，增加一个取号机的信号量，初始值为1，服务员叫号然后顾客接受服务为同步关系，增加一个服务的信号量，初始值为0。

补充说明：顾客i只会进银行一次，不会反复进银行，所以process 顾客i不需要while (TRUE) 死循环。营业员上班期间要时刻处于工作状态，所以process 营业员需要while (TRUE) 死循环。

很容易写出如下代码：

semaphore mutex = 1;    // 座位区互斥信号量
semaphore empty = 10;    // 座位区空闲位置数量
semaphore full = 0;     // 座位区等待人的数量
semaphore service_i = 0;  // 顾客i等待叫号
semaphore machine = 1;  // 取号机

cobegin
process 顾客i {
    P(empty);
    P(machine);
    从取号机获得一个号码;
    V(machine);
    P(mutex);
    一位顾客进入座位区;
    V(mutex);
    V(full);
    P(service_i);    // 等待叫号
    获得服务;
}
process 营业员 {
    while (TRUE) {
        P(full);
        P(mutex);
        一位顾客离开座位区;
        V(mutex);
        V(empty);
        V(service_i);
        叫号;
        为顾客服务;
    }
}
coend

由于service_i是针对某个顾客i的，如果是针对所有顾客，可以用散列表存储<服务号, 服务信号量>键值对，可以写出如下伪代码，更加方便理解。

semaphore mutex = 1;    // 座位区互斥信号量
semaphore empty = 10;    // 座位区空闲位置数量
semaphore full = 0;     // 座位区等待人的数量
map<int, semaphore> service_map;  // <服务号, 服务信号量>键值对映射表，初始为空
semaphore machine = 1;  // 取号机

cobegin
process 顾客i {
    P(empty);
    P(machine);
    从取号机获得一个号码x;
    V(machine);
    semaphore service_i = 0;  // 生成顾客i的服务号对应的服务信号量
    service_map[x] = semaphore service_i;   // 将顾客i的<服务号, 服务信号量>存入<服务号, 服务信号量>键值对映射表
    P(mutex);
    一位顾客进入座位区;
    V(mutex);
    V(full);
    P(service_i);    // 等待叫号
    获得服务;
}
process 营业员 {
    while (TRUE) {
        P(full);
        P(mutex);
        一位顾客离开座位区;
        V(mutex);
        V(empty);
        叫号x;
        semaphore service_i = service_map[x];   // 根据顾客i的服务号从<服务号, 服务信号量>键值对映射表获取顾客i的服务信号量
        V(service_i);
        为顾客服务;
        service_map.erase(x);    // 服务完成，从<服务号, 服务信号量>键值对映射表中移除该服务
    }
}
coend

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

连续结构可以视为数组，因为数组适合随机访问但插入删除慢，所以连续结构适合随机访问但不于文件扩展。

链式结构可以视为链表，因为链表只能顺序访问但插入删除块，所以链式结构不适合随机访问但易于文件扩展。

索引结构可以视为索引树，因为索引树适合随机访问但插入删除较快，所以索引结构适合随机访问且易于文件扩展。

FCB 是 File Control Block 的缩写，即文件控制块，是计算机文件系统中的一个数据结构，用于管理文件的元数据和访问权限。FCB通常包含以下字段：

1. 文件名：指定文件的名称和扩展名。
2. 文件类型：指定文件的类型，如文本文件、图像文件、音频文件等。
3. 文件大小：指定文件的大小，以字节为单位。
4. 创建时间：记录文件的创建时间和日期。
5. 修改时间：记录文件的最后修改时间和日期。
6. 访问时间：记录文件的最后访问时间和日期。
7. 文件权限：指定文件的访问权限，包括所有者权限、组权限和其他用户权限。
8. 所有者：记录文件的所有者。
9. 文件扩展属性：包含文件的额外属性信息，如版本号、作者等。
10. 文件数据块：存储文件的实际数据内容的指针或索引。

第一问。连续更合适，因为一次写入不存在扩展问题，连续的数据块组织方式完全可以满足一次性写入磁盘。同时连续文件组织方式减少了其他不必要的空间开销，而连续的组织方式顺序查找时磁盘寻道时间最短，读取速度是最快的。

第二问。为定位文件数据块，需要在FCB中设计的相关描述字段为起始块号和块数，或者起始块号和结束块号。类比数组在内存中的分布，需要知道起始元素地址和元素个数，或者起始元素地址和结束元素地址。

(2) 第一问FCB集中存储好。

第二问。FCB是存在磁盘上的。所以检索FCB的时候需要访问磁盘。所以访问磁盘次数越少越好，将FCB集中存储，最大化减少了存储FCB需要的磁盘块数量，这样在随机查找文件时，只需要访问FCB对应的磁盘块，最大化减少了磁头移动和磁盘I/O次数。

根据以太网数据帧结构和 IP 分组头结构，将以太网数据帧中的各个字段标出。如下图所示。

完整分析所有 IP 字段如下：

版本：占 4 bit，因为是 IPv4，对应十六进制值为 4 H。本题中为 4 H。

头部长度：占 4 bit，表示 IP 数据报首部长度，取值以 4 B 为单位，最小长度 20 B，对应十六进制值为 5 H。本题中为 5 H。

服务类型：占 8 bit，用于表示数据包的优先级，不同数值可提供不同等级的服务质量，一般情况下不使用，默认值为 0，对应十六进制值为 00 H。本题中为 00 H。

总长度：占 16 bit，IP 数据报总长度 = 头部长度 + 数据载荷长度，取值以 1 B 为单位，最大传送单元 MTU = 1500 B，总长度不超过 MTU。本题中为 01ef H。即 IP 数据报总长度为 495 B。

标识：占 16 bit，用于唯一标识主机发送的每一个IP包，每发送一个包其值就会加1。当 IPv4 数据报长度超过 MTU 时，无法封装成帧，必须进行分片，属于同一个数据报的各分片有相同的标识。本题中为 113b H。

标志：占 3 bit，从左到右依次为

• 保留位：占 1 bit，为 0。
• DF (Don’t Fragment)：占 1 bit，1 表示不允许分片，0 表示允许分片。
• MF (More Fragment)：占 1 bit，1 表示后面还有分片，0 表示这是最后一个分片。

片偏移：占 13 bit，取值以 8 B 为单位，指出分片数据的数据载荷部分偏移其原数据报位置有多少个单位。

本题中，标志和片偏移拼接为 4000 H，二进制为 0100 0000 0000 0000 B，标志二进制为 010 B，其中保留位为 0，DF 为 1，表示不允许分片，MF 为 0，表示这是最后一个分片。片偏移二进制为 0 0000 0000 0000 B，即为 0。因为没有分片，所以不会产生片偏移。

生存时间 (TTL)：占 8 bit，设置数据包可以经过的路由器数目。每经过一个路由器，TTL 值就会减1，当该字段值为 0 时，数据包将被丢弃。本题中为 80 H。

协议：占 8 bit，此分组数据提供给哪个传输层协议。常用 IP 协议号对应的上层协议如下：

本题中为 06 H。上层协议为 TCP 协议，HTTP 协议是基于 TCP 协议的。

头部校验和：占 16 bit，用于检验 IP 头部是否损坏，数据的可靠性是由 TCP 保证的。本题中为 ba9d H。

源 IP 地址：占 32 bit，数据包的源节点的 IP 地址。本题中为 0a028064 H。点分十进制格式为 10.2.128.100。

目的 IP 地址：占 32 bit，数据包的目的点的 IP 地址。本题中为 40aa6220 H。点分十进制格式为 64.170.98.32。

(1) 第一问。因为题 47-b 图是该主机进行 Web 请求的以太网数据帧内容，所以 Web 服务器的 IP 地址位于 IP 头部的目的 IP 地址字段，16进制格式为 40 aa 62 20，转化为点分十进制格式为 64.170.98.32。

第二问。根据网络拓扑图可知，该主机的默认网关是路由器 R，分析数据链路，主机会将 Web 请求发送给默认网关，再由默认网关将 Web 请求转发给 Web 服务器。所以以太网帧的目的 MAC 地址 00-21-27-21-51-ee 即为该主机的默认网关的 MAC 地址。

(2) 已知目的 IP 地址，但不知道目的 MAC 地址，需要使用 ARP 协议确定目的 MAC 地址。因为 ARP 协议请求报文需要进行广播，最后路由器返回 ARP 单播响应得到目的 MAC 地址。所以封装 ARP 协议请求报文的以太网数据帧的目的 MAC 地址是 ff-ff-ff-ff-ff-ff。

(3) HTTP/1.1 协议与 HTTP/1.0 相比有了一些重要的改进，其中包括持续连接的引入。持续连接允许客户端和服务器之间的单个TCP连接传输多个 HTTP 请求和响应，而无需为每个请求/响应对创建新的连接。这样可以减少连接的建立和关闭所带来的开销，并且可以更有效地利用网络资源。在 HTTP/1.1 中，默认情况下使用持续连接，除非在请求头中显式指定 Connection: close 来关闭连接。这与 HTTP/1.0 不同，后者在每个请求/响应后都会关闭连接。

非流水线方式指每一个请求需要等待其对应的响应返回之后，才能发送下一个请求。换句话说，当使用非流水线方式时，客户端发送一个请求后需要等待服务器返回相应的响应后才能发送下一个请求，而不会同时发送多个请求。

HTTP 是基于 TCP 的应用层协议。

TCP 头结构如下图所示：

根据以太网数据帧结构、IP 分组头和 TCP 头的结构，将以太网数据帧中的各个字段标出。如下图所示。

完整分析 TCP 段头字段如下：

源端口：占 16 bit，发送端的应用程序端口号。

目标端口：占 16 bit，接收端的应用程序端口号。

序号 (seq)：占 32 bit，TCP 报文段数据载荷第一个字节的序号，以确保接收方能够按正确的顺序重新组装。

确认号 (ack)：占 32 bit，只有在 ACK 标志位被设置为 1 时才有效，表示接收端期望收到的下一个字节的序号。

数据偏移：占 4 bit，以 4 B 为单位，表示 TCP 报文段数据载荷的起始处与 TCP 报文段的起始处的距离。实际上指出了 TCP 报文段头的长度。

保留：占 6 bit，保留供将来使用，目前应设置为 0。

控制位：占 6 bit，总共 6 个标志位，每个各占 1 bit，用于指示TCP报文段的各种控制信息。从左到右依次为

• URG：表示紧急指针字段是否有效。
• ACK：表示确认号字段是否有效。
• PSH：表示接收端是否应该尽快将数据交给应用程序。
• PST：表示是否需要重置连接。
• SYN：在建立 TCP 连接时用来同步请求。
• FIN：在释放 TCP 连接时用于关闭连接。

窗口：占 16 bit，指定发送端希望接收端为此连接分配的接收窗口大小。

校验和：占 16 bit，用于检测 TCP 报文段是否在传输过程中发生错误。

紧急指针：占 16 bit，只有在 URG 标志位被设置为1时才有效。指示紧急数据的边界。

TCP 建立三次握手的示意图如下：

本题中，保留和控制位内容为 018 H = ，其中 ACK = 1，SYN = 0。

若该报文是 TCP 的第一次握手，则其中 ACK = 0，SYN = 1，所以该报文不是 TCP 的第一次握手。

若该报文是 TCP 的第二次握手，则其中 ACK = 1，SYN = 1，所以该报文不是 TCP 的第二次握手。

所以该报文是 TCP 的第三次握手或者 TCP 已经建立完成后发送的，因此无需考虑建立 TCP 的一个 RTT 的开销。

HTTP/1.1 协议以持续的非流水线方式工作，每个 RTT 传输一个对象，共需传输 6 个对象（1 个 html 页面引用了 5 个 JPEG 小图像），所以共需要 6 个 RTT。

(4)

方法一：读取 IP 头总长度字段

因为该帧中 IP 头总长度字段为 01ef H，单位字节，即 495 B，说明 IP 数据报总长度为 495 B，即以太网帧的数据载荷为 495 B，小于 MTU=1500 B，所以该帧所封装的 IP 分组经过路由器 R 转发时，不需要进行分片。

方法二：读取 IP 头标志字段

标志和片偏移拼接为 4000 H，即 0100 0000 0000 0000 B，标志为 010 B，其中保留位为 0，DF 为 1，表示不允许分片，MF 为 0，表示这是最后一个分片。不允许分片蕴含 IP 数据报总长度不超过 MTU，所以该帧所封装的 IP 分组经过路由器 R 转发时，不需要进行分片。

修改 IP 分组头中的字段如下：

源 IP 地址：由主机的 IP 地址 10.2.128.100 修改为路由器 R 连接 Internet 的接口的 IP 地址 101.12.123.15。

生存时间 (TTL)：IP 分组每经过一个路由器，生存时间 TTL 字段的值就减 1，由 80 H 修改为 7F H。

首部校验和：由于上述字段发生改变，因此需要重新计算首部校验和。