本题考察栈先进后出的性质，调用函数入口为main()，main()入栈，接着调用S(1)，S(1)入栈，S(1)需要递归调用S(0)，S(0)入栈，题目要求“自栈底到栈顶保存的信息”，即main()→S(1)→S(0)，如果是“自栈顶到栈底保存的信息”就要反过来。

本题选A。

评：这道题的代码含义不理解，递归计算  。

方法一：枚举

先序序列为满足二叉树递归遍历顺序为“根左右”的输出序列。

其实只要枚举一半就行，本人枚举了左子树结点数大于右子树结点数的所有情况，另一半对称，总计 7×2=14 。

但注意，如果结点个数为奇数个，需要考虑左子树结点数等于右子树结点数的情况。

本题选B。

方法二：计算

可以发现，暴力枚举需要非常小心，稍有不慎就会遗漏。如果先序序列为入栈顺序，中序序列为出栈顺序，由先序序列和中序序列可以唯一的确定一棵二叉树，出栈序列为 �=4 的卡特兰数：  。

本题选B。

哈夫曼树是构造哈夫曼编码过程的图形化展示，哈夫曼树有许多重要的性质，哈夫曼树是一棵完满二叉树，每个结点的度只能为 0 或 2。

我们先根据选项构造出对应的完满二叉树，再检查该完满二叉树是否为哈夫曼树。

为了更加贴近哈夫曼树：

• 任意一个结点的左孩子权值小于或等于右孩子权值。
• 一个非叶结点的权值等于其左孩子权值和右孩子权值之和。

选项A的根结点的左孩子10的左右孩子权值出现了两种情况，意味着这两条路径一定不会出现在同一棵哈夫曼树中。错误。

选项B的根结点24的左右孩子权值出现了两种情况，意味着这两条路径一定不会出现在同一棵哈夫曼树中。错误。

选项C虽然成功构造出了一棵完满二叉树，但这棵完满二叉树不是一棵哈夫曼树，错误原因有两点：

• 第一点：哈夫曼树中不会出现权值为 0 的结点，因为哈夫曼树对应哈夫曼编码，每个叶结点的权值表示词频或出现几率，权只为 0 表示该单词不存在，显然哈夫曼编码不可能对不存在的单词进行统计。也就是哈夫曼树中每个结点的权值为正数。
• 第二点：哈夫曼编码是一种贪心编码，每次选择词频最小的两个字符，我们假设 0 合法，我们用 0、 10、3 和 11 这四个关键字尝试还原这棵哈夫曼树，我们发现还原失败。其实也可直接观察，第一次选中 0 和 10，第二次选中 3 和 11，明显有第一次选中的 10 大于第二次选中的 3，不符合哈夫曼编码。也就是说，如果命题组加大难度，将选项C修改为 24, 10, 9 和 24, 14, 11，虽然没有违反第一点，但违反第二点，仍然错误。

选项D的这棵完满二叉树是一棵哈夫曼树，可以进行如下验证。

本题选D。

这道题只能逐个分析选项。

A选项中，根结点的度不一定为2，A错误。

B选项中，一棵平衡二叉树是一棵二叉搜索树，由于中序遍历可得到一个降序序列，树中最小元素一定是最右结点，即无右子树，但可能有左子树，所以不一定是叶结点，B错误。

C选项中，AVL树的插入分两步，第一步是按照二叉搜索树的规则插入元素，该元素此时是叶结点，第二步是调整二叉搜索树为AVL树，如果此时二叉搜索树不平衡，需要进行旋转，旋转后该元素所在结点不一定是叶结点，C错误。

D正确。

本题选D。

D

方法：枚举

根据顶点集和边集画出有向图：

由于图比较简单，很容易枚举出所有深度优先遍历序列，为了不要混乱，按照顶点下标从小到大的顺序枚举：

本题选D。

方法一：模拟 + 枚举 + 取差集

Kruskal算法：首先将边从图中剥离然后按照边权值从小到大排序。然后从小到大依次将边复原到图中，插入后检查是否成环，如果成环，丢弃插入的边，重复上述过程直到有顶点都连通。

Kruskal过程模拟如下图所示：

解答：

第一次出现“失配”（s[i] ≠ t[j]）时，i = j = 5，隐藏含义是主串和模式串下标都从0开始，这个条件非常重要。

方法一：计算 next 数组后模拟

第一步：计算出模式串的next数组。

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

这里由于主串和模式串下标都从0开始，没必要用优化后的next数组求解。优化后的next数组增加的1和下标都从0开始相比下标都从1开始减少的1正好相抵。

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

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

或者查表next数组失配字符c，其下标为5，其next值为next[5] = 2，已匹配字符数为5，移动位数 = 已匹配字符数 - 失配位置对应的匹配值 = 5 - 2 = 3。模式串向后移动3格，从失配位置开始重新进行匹配，此时 i = 5, j = 2。

或者查表next数组失配字符c，其下标为5，其next值为next[5] = 2，j指针直接跳转到模式串下标为2的位置，从失配位置开始重新进行匹配，此时 i = 5, j = 2。

本题选C。

方法三：贪心

贪心找到最多匹配的情况，同样画出上图。虽然这个方法不严谨，好在本题足够简单，从失配位置开始重新进行匹配，很容易看到i = 5, j = 2。

本题选C。

补充本人对本题完整KMP匹配过程的模拟。

C

除了基数排序外，其它三种排序都是基于比较的排序算法，元素的移动次数与关键字的初始排列次序有关。

解答：

删除8后，用小根堆最后一个元素占位，然后需要维护堆的性质，设根结点下标为1，调用MIN-HEAPIFY(A, 1)，MIN-HEAPIFY伪代码如下：

MIN-HEAPIFY(A, i)
    l = LEFT(i)
    r = RIGHT(i)
    if l ≤ A.heap-size and A[l] < A[i]
        smallest = l
    else smallest = i
    if r ≤ A.heap-size and A[r] < A[smallest]
        smallest = r
    if smallest ≠ i
        exchange A[i] with A[smallest]
        MIN-HEAPIFY(A, smallest)

总共发生3次比较。

本题选C。

A

希尔排序是插入排序的一种，又称“缩小增量排序”，是直接插入排序算法的一种更高效的改进版本。

I正确。计算机硬件的本质是执行机器语言程序，它是由二进制指令组成的、直接被硬件执行的程序。机器语言是针对特定的计算机体系结构和硬件设计的低级语言。

II错误。汇编语言程序是与机器语言一一对应的助记符形式的指令，需要通过汇编器将其转换为对应的机器语言指令，然后才能被计算机硬件执行。

III错误。硬件描述语言(Hardware Description Language， HDL)，例如Verilog和VHDL，是一种用于描述和设计数字电路的高级语言，但它本身并不能直接被计算机硬件执行。HDL需要先进行综合和布局布线，最终生成对应的电路结构，然后该电路结构才能被硬件执行。

本题选A。

最小的整数显然为负数，最高符号位为1，剩余2个“1”和5个“0”，对于二进制补码，在符号位相同的情况下，若二进制补码对应的无符号数越小，则该二进制补码表示的数越小。

设该数为x，显然有[x]补 = 10000011B，[x]原 = 11111101B = -125。

本题选B。

本题选D。

直接映射方式的格式为  。

因为主存块大小为4个字，每字32位，所以块大小为4×32bit=16B= B。计算机字节编址，所以块内地址占4位。

因为Cache能存放4K字数据，块大小为4个字，所以Cache行数为4K/4=1K= ，行号占10位。

因为主存地址位数为32位，块内地址占4位，行号占10位，所以主存字块标记占32-4-10=18位。

写操作时采用回写 (Write Back) 方式，标记位包含1位脏位，还有18位主存字块标记位和1位有效位。每行标记占18+1+1=20位，每行数据占4个字，每字32位，即4×32=128位。

Cache的总容量=(每行标记位数+每行数据位数)×行数=(20+128)×1K=148K。

本题选C。

上述指令的执行过程可划分为取数、运算和写回过程，取数时读取xaddr可能不需要访问主存而直接访问Cache，而直写方式需要把数据同时写入Cache和主存，因此至少访问1次。

本题选B。

SRAM (Static Random Access Memory) 是一种静态随机存取存储器，不需要进行刷新操作，因为它是通过触发器来存储数据，不会出现电容泄漏的问题。A错误。

SDRAM (Synchronous Dynamic Random Access Memory) 是一种动态随机存取存储器，它在工作期间需要进行周期性的刷新操作。这是因为DRAM存储单元使用电容来存储数据，电容会逐渐泄漏导致数据的丢失。为了保持存储的数据有效，SDRAM需要以固定的时间间隔对存储单元进行刷新。B正确。

ROM (Read-Only Memory) 是只读存储器，无需刷新操作。C错误。

FLASH存储器属于非易失性存储器，也不需要刷新操作。D错误。

本题选B。

4体交叉编址默认为4体低位交叉编址，采用流水线方式可以进行四体并行。

模块序号 = 访存地址 mod 存储器交叉模块数。

8005 mod 4 = 1， 8006 mod 4 = 2，以此类推。

同一个模块下每次最多从1个地址传输数据，所以同一个模块下的地址访存是互斥的，即同时访问同一个模块下的地址会发生访存冲突。即

• 8000、8004、8008互斥。
• 8001、8005互斥。
• 8002、8006互斥。
• 8003、8007互斥。

4体低位交叉编址，采用流水线方式，假设每次访存需要4个总线传输周期，每隔1个总线传输周期启动一个模块，按照8005，8006，8007，8008，8001，8002，8003，8004，8000的访存序列，可以画出如下示意图。很明显，在第9个总线传输周期启动访问8000会出现访存冲突。但如果存储周期小于或等于总线传输周期，那么不会发生访存冲突。所以可能发生访存冲突的地址对是8000和8004。

本题选D。

在异步定时方式中，没有统一的时钟，也没有固定的时间间隔，完全依靠传送双方相互制约的“握手”信号来实现定时控制。主模块提出交换信息的“请求”信号，经接口传送到从模块。从模块接到主模块的请求后，通过接口向主模块发出“回答”信号。

优点：总线周期长度可变，能保证两个工作速度相差很大的部件或设备之间可靠地进行信息交换，自动适应时间的配合。

缺点：比同步控制方式稍复杂一些，速度比同步定时方式慢。

根据“请求”和“回答”信号的撤销是否互锁，分为以下3种类型。不互锁方式速度最快，可靠性最差，全互锁方式最可靠，速度最慢。

不互锁方式：主模块发出“请求”信号后，不必等到接到从模块的“回答”信号，而是经过一段时间，便撤销“请求”信号。而从模块在接到“请求”信号后，发出“回答”信号，并经过一段时间，自动撤销“回答”信号。双方不存在互锁关系。

半互锁方式：主模块发出“请求”信号后，必须等接到从模块的“回答”信号后，才撤销“请求”信号，有互锁的关系。而从模块在接到“请求”信号后，发出“回答”信号，但不必等待获知主模块的“请求”信号已经撤销，而是隔一段时间后自动撤销“回答”信号，不存在互锁关系。

全互锁方式：主模块发出“请求”信号后，必须等从模块“回答”后，才撤销“请求”信号。从模块发出“回答”信号，必须待获知主模块“请求”信号已撤销后，再撤销其“回答”信号。双方存在互锁关系。

A表述正确，B表述正确，

在同步通信方式中，系统采用一个统一的时钟信号来协调发送和接收双方的传送定时关系。时钟产生相等的时间间隔，每个间隔构成一个总线周期。在一个总线周期中，发送方和接收方可以进行一次数据传送。

C表述错误。

半同步通信是一种介于异步和同步通信之间的通信方式。它在数据的传输过程中使用同步时钟信号，但在握手信号的采样上仍然依赖于同步时钟。在半同步通信中，数据和同步时钟信号是同时传输的，而握手信号则根据同步时钟的边沿来采样。具体来说，握手信号的状态通常在同步时钟信号的上升沿或下降沿采样，以确保正确的信号同步和数据传输。

D表述正确。

本题选C。

访问一个扇区的平均存取时间 = 平均寻道时间 + 平均延迟时间 + 传输时间。

平均寻道时间 = 8ms。

平均延迟时间 =  。

传输时间 = 。

访问一个扇区的平均存取时间 = 8ms + 4.167ms + 0.008ms = 12.175ms。

本题选B。

I/O接口的功能包括：1.选址功能；2.传送命令功能；3.传送数据功能；4.反映I/O设备工作状态功能。

打印字符为数据，对应功能3。A可能。

主存地址在中断方式控制下是不需要的，因此，它不可能是CPU和打印控制接口中的I/O端口之间交换的信息。B不可能。

设备状态对应功能4。C可能。

控制命令对应功能2。D可能。

本题选B。

内中断是指来自CPU和内存内部产生的中断，包括程序运算引起的各种错误，如地址非法、校验错、页面失效、非法指令、用户程序执行特权指令自行中断 (INT) 和除数为零等，以上都在指令的执行过程中产生的。A正确。

这种检测异常的工作肯定是由CPU（包括控制器和运算器）实现的。B正确。

内中断不能被屏蔽，一旦出现应立即处理。C正确。

陷阱（trap）一般用于进行系统调用，完成后返回到下一条指令继续执行，不会返回到发生异常的指令继续执行。D错误。

中断的可分类如下：

本题选D。

A错误。程序计数器 (PC) 的内容由中断隐指令保存。中断隐指令并不是指令系统中的一条真正的指令，它没有操作码，所以中断隐指令是一种不允许、也不可能为用户使用的特殊指令。

B正确。通用寄存器的内容由中断服务程序保存，中断服务程序属于操作系统。

C错误。快表 (TLB) 中的内容在处理外部中断时不需要保存。

D错误。Cache中的内容在处理外部中断时不需要保存。

本题选B。

【答案】C

【解析】A 选项中若R 1中的内容为0 , 则会出现内中断，从用户态变为内核态；B 选项软中断在内核态执行；C 选项寄存器取非不会产生中断，且不属于其他操作系统内核，故不会变为内核态；D 选项addr是主存地址，访存需要进入内核态。

【答案】D

【解析】P（wait）操作表示进程请求某一资源，A、B 和 C 都因为请求某一资源会进入阻塞态，而 D 只是被剥夺了处理机资源，进入就绪态，一旦得到处理机即可运行。

答案：B
死锁的处理采用三种策略：死锁预防、死锁避免、死锁检测和解除。

死锁预防采用破坏产生死锁的4个必要条件中的一个或几个来防止发生死锁。其中之一的“破坏循环等待条件”，一般采用顺序资源分配法，首先给系统的资源编号，规定每个进程必须按编号递增的顺序请求资源，即限制了用户申请资源的顺序，因此Ⅰ的前半句属于死锁预防的范畴。

银行家算法是著名的死锁避免算法，其中的最大需求矩阵Max定义了每个进程对m类资源的最大需求量，系统在执行安全性算法中都会检查次资源试分配后，系统是否处于安全状态，若不安全则将本次的试探分配作废。在死锁的检测和解除中，系统为进程分配资源时不采取任何措施，但提供死锁的检测和解除手段，因此Ⅱ、Ⅲ正确。

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

根据题意，模拟过程如下（红色标记未命中，绿色标记命中）：

本题选A。

磁盘缓冲区是一块内存区域，用于临时存储从磁盘读取的数据或待写入磁盘的数据。它的存在可以带来许多性能和效率上的好处，其中最重要的目标之一是减少磁盘I/O次数。当系统需要读取或写入磁盘上的数据时，它可以首先将这些数据加载到磁盘缓冲区中进行处理。这样，如果需要再次访问同样的数据，可以直接从缓冲区中获取，而无需再次进行磁盘I/O操作。缓冲区允许系统更有效地利用内存中的数据，从而减少了与较慢的磁盘操作相关的延迟。

本题选A。

磁盘块大小为1KB，每个索引指针占4B，一个磁盘块可以装载1KB/4B=256个索引指针。

直接索引视为0级索引。

ni 个 i 级索引指向数据块大小为  。

访问 i 级索引指向数据块需要读 i 次索引，1次数据块，总计 i+1 次磁盘。

10个直接索引指向数据块大小为10×1KB=10240B。首地址偏移量为0，按字节编址，直接索引指向数据块偏移量范围为[0, 10239]。

1个一级索引指向数据块大小为1×256×1KB=262144B。首地址偏移量为0，按字节编址，前面有直接索引指向数据块，一级索引指向数据块偏移量范围为[10240, 10240+262143]，即[10240, 272383]。

1个二级索引指向数据块大小为1× 256^2 ×1KB=67108864B。首地址偏移量为0，按字节编址，前面有直接索引和一级索引指向数据块，二级索引指向数据块偏移量范围为[10240+262144, 10240+262144+67108863]，即[272384, 67381247]。

因为偏移量为1234∈[0, 10239]，所以该偏移量位于直接索引指向数据块范围内，访问该数据块需要读1次磁盘。

因为偏移量为307400∈[272384, 67381247]，所以该偏移量位于二级索引指向数据块范围内，访问该数据块需要读3次磁盘。

本题选B。

在请求分页系统中，可采取两种内存分配策略，即固定和可变分配策略；在进行置换时，也可采取两种策略，即全局置换和局部置换。

固定分配：指为每个进程分配一组固定数目的物理块，在进程运行期间不再改变。

可变分配：指先为每个进程分配一定数目的物理块，在进程运行期间，可根据情况做适当的增加或减少。

局部置换：指如果进程在运行中发现缺页，则只能从分配给该进程的n个页面中选出一页换出，然后再调入一页，以保证分配给该进程的内存空间不变。

全局置换：指如果进程在运行中发现缺页，则将操作系统保留的空闲物理块（一般组织为一个空闲无论块队列）取出一块分配给该进程，或者以所有进程的全部物理块为标的，选择一块换出，然后将所缺页调入。

A. 可变分配，全局置换：因为可变分配允许页面在不同的进程之间转移，全局置换允许在不同的进程之间置换页面。所以这两种策略可以组合使用。

B. 可变分配，局部置换：因为可变分配允许在不同的进程之间转移页面，局部置换允许在一个进程的地址空间内置换页面。所以这两种策略可以组合使用。

C. 固定分配，全局置换：因为固定分配限制了页面的分配，不允许页面在进程之间转移，而全局置换需要在不同的进程之间置换页面。所以这两种策略不能组合使用。

D. 固定分配，局部置换：固定分配将每个页面固定地分配给某个进程地址空间，局部置换允许在一个进程的地址空间内置换页面。所以这两种策略可以组合使用。

本题选C。

位图存于磁盘的32～127号块中，所以位图的起始盘块号为32，每个盘块占1024B，一个盘块的位图可表示的盘块号数量为1024×8。

目标盘块号位于位图中的盘块号 = 位图的起始盘块号 + ⌊ 目标盘块号 / 一个盘块的位图可表示的盘块号数量 ⌋ 。

目标盘块号位于位图中的块内位号 = 目标盘块号 mod 一个盘块的位图可表示的盘块号数量。

将位图的起始盘块号 = 32，一个盘块的位图可表示的盘块号数量 = 1024×8，目标盘块号 = 409612代入上式。

解得目标盘块号位于位图中的盘块号 = 82，目标盘块号位于位图中的块内位号 = 12。

目标盘块号位于位图中的块内字节号 = ⌊ 目标盘块号位于位图中的块内位号 / 8 ⌋ ，所以目标盘块号位于位图中的块内字节号 = 1。

本题选C。

对于SCAN调度（电梯调度）算法，磁臂从磁盘的一端开始，向另一端移动；在移过每个柱面时，处理请求。当到达磁盘的另一端时，磁头移动方向反转，并继续处理。磁头连续来回扫描磁盘。磁头的行为就像大楼里面的电梯，先处理所有正在移动的方向的请求，然后再处理相反方向的请求。

该硬盘有200个磁道，最外侧磁道号为0，最内侧磁道号为0+200-1=199。磁道访问请求序列为：130，42，180，15，199，当前磁头位于第58号磁道并从外侧向内侧移动。模拟过程如下：

访问序列为130, 180, 199, 42, 15。分为两段，第一段从第58号磁道从外侧向内侧移动到第199号磁道，磁头移过的磁道数是199-58=141，第二段从第199号磁道从内侧向外侧移动到第15号磁道，磁头移过的磁道数是199-15=184。综上，磁头移过的磁道数是141+184=325。

本题选C。

POP3 (Post Office Protocol version 3) 邮局协议第3版，它是用于接收电子邮件的标准协议。当你用邮件客户端以从邮件服务器上下载邮件时，它通常会使用 POP3 协议。在接收邮件时使用的传输层服务类型通常是有连接可靠的数据传输服务，因为接收邮件需要确保数据的完整性和可靠性，而且采用了建立连接的方式进行通信。

正因为通过POP3协议接收邮件要求使用有连接可靠的数据传输服务，所以POP3协议是基于TCP的。TCP提供有连接可靠的数据传输服务。而UDP提供无连接不可靠的数据传输服务。

本题选 D。

本题考察数字信号调制中常见的编码方式：

1. RZ (Return to Zero) 归零编码：正电平代表比特 1，负电平代表比特 0，并且每传输完一位数据，信号返回到零电平。
2. NRZ (Not Return to Zero) 不归零编码：正电平代表比特 1，负电平代表比特 0，在整个位期间保持相同的电平。需要额外的传输线来传输时钟信号。
3. NRZI (Non Return Zero Inverted) 反向不归零编码：一次电平翻转来表示比特 0，与前一个电平相同的电平表示比特 1。需要额外的传输线来传输时钟信号。
4. 曼彻斯特编码：每个时钟周期的中间有一跳变，该跳变既作时钟信号，又作数据信号。正跳变表示比特 1，负跳变表示比特 0，或者正跳变表示比特 0，负跳变表示比特 1。
5. 差分曼彻斯特编码：每个时钟周期的中间有一跳变，这个跳变用于同步时钟信号。另在每个数据位的开始处加入一个电平转变来表示数据。在时钟周期的起始处会出现跳变表示比特 0，没有跳变表示比特 1。

方法一：观察电平变化

编码1每个时钟周期中间无跳变，正电平代表比特 1，负电平代表比特 0，是NRZ。

编码2每个时钟周期中间有跳变，正跳变表示比特 1，负跳变表示比特 0，是曼彻斯特编码。

方法二：绘制所有可能情况后进行比对

比特流01100111，则对应的编码如下：

对比本题图片得出结果：编码1是NRZ，编码2是曼彻斯特编码。

本题选 A。

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

卫星系统一般采用全双工通信，会话双方可以同时接收和发送数据。在408真题中，一般情况下，采用滑动窗口协议默认支持全双工通信。

主机甲发送一个数据帧的时延为 数据帧长信道带宽 ，传播时延为 τ=250 ms ，主机乙发送一个确认帧的时延为 t2 ，因为乙每收到一个数据帧立即利用一个短帧（忽略其传输延迟）进行确认，所以 t2=0 ，传播时延为 τ=250 ms 。一个周期 T=t1+τ+t2+τ=562.5 ms 。因为数据链路层采用滑动窗口协议传输数据，为使信道利用率达到最高，在一个周期内，发送方可以连续发送多个数据帧，将位于发送窗口中的帧全部发送出去。

设发送窗口大小为 WT ，链路利用率  ，解得 WT≥7.2 。取 WT=8 。

由于题目没有明确表示具体采用哪一种滑动窗口协议，所以这里需要分情况讨论：

情况一：采用后退 N 帧协议 (GBN)，发送窗口大小满足 1<WT≤2^n−1 ，其中 n 是帧序号的比特数，解得 n≥4 。

情况二：采用选择重传协议，发送窗口大小满足 1<WT≤2^(n−1) ，其中 n 是帧序号的比特数，解得 n≥4 。

综上所述，帧序号的比特数至少是 4。

本题选 B。

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

A 正确。边发送数据帧，边检测是否发生冲突，简记“边听边说”。

B 错误。CSMA/CD 是早期以太网使用的有线信道访问控制协议。CSMA/CA 适用于无线网络，以实现无线链路共享。

C 正确。最小帧长 = 争用期（端到端往返时延 ）× 数据传输速率。

D 正确。信号传播延迟趋近 0 时，即端到端最大单程时延 τ 趋近 0，争用期 2τ 趋近 0，因此忽略争用期，设数据发送时延为 t1 ，现在考虑一种理想化的情况。假定以太网上的各站发送数据都不会产生碰撞，并且能够非常有效地利用网络的传输资源，即总线一旦空闲就有某一个站立即发送数据。

因为CSMA/CD 并不采用确认机制，因此每个周期只需要考虑发送时延和单程传播延迟，最大周期 T=t1+τ 。可计算出极限信道利用率  。

本题选 B。

网桥：是工作在数据链路层上的连接设备，网桥的两个端口分别有一条独立的交换信道，不是共享一条背板总线。网桥只能分割冲突域不能分割广播域。

以太网交换机：是一种多端口网桥。交换机通常是由多个端口构成，每个端口都能够提供独立的通信通路。

冲突域：连接在同一导线上的所有工作站的集合，或者说是同一物理网段上所有节点的集合或以太网上竞争同一带宽的节点集合。这个域代表了冲突在其中发生并传播的区域。在 OSI 模型中，冲突域被看作是物理层的概念。

广播域：接收同样广播消息的节点的集合。如：在该集合中的任何一个节点传输一个广播帧，则所有其他能收到这个帧的节点都被认为是该广播帧的一部分。在 OSI 模型中，广播域被看作是数据链路层的概念。

A 正确。

B 错误。以太网交换机能够隔离冲突域。

C 错误。以太网交换机不能够隔离广播域。

D 错误。以太网交换机工作在数据链路层，不能实现采用不同网络层协议的网络互联。路由器是工作在网络层的连接设备，路由器能够连接不同类型网络并能够选择数据传送路径的网络设备。

本题选 A。

查路由表，目的 IP 地址为 169.96.40.5 的 IP 分组和目的网络 169.96.40.0/23、169.96.40.0/25 和 169.96.40.0/27 的前3个十进制数相同，即前 24 个比特位均相同，将 169.96.40.5 后 8 位写成二进制形式为 169.96.40.00000101 ，观察可得其有效位为 101 ，最多支持网络号为 169.96.40.0 中 32-3 = 29 位为网络号，根据最长前缀匹配原则，169.96.40.0/23、169.96.40.0/25 和 169.96.40.0/27 中 169.96.40.0/27 能够匹配的前缀最长，则转发该IP分组的接口是 S3。

本题中，0.0.0.0/0为默认路由，只有找不到其他匹配的路由时，才按照默认路由进行转发。

本题选 C。

发送方发送窗口 swnd = min {拥塞窗口 cwnd, 接收方接收窗口 rwnd}。

乙的TCP接收缓存仅有数据存入而无数据取出。根据题意，初始时，rwnd =16 KB。

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

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

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

慢开始算法

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

拥塞避免算法

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

接下来对本题进行分析。

拥塞窗口初始阈值为32 KB，乙的接受缓存为 16 KB，16 KB < 32 KB，即便在一个RTT中发送 16 KB数据都不会触发拥塞避免算法。可以断言从主机甲发送第1个TCP段到主机甲收到的第 16 个确认段所通告时慢开始算法都适用，不会触发拥塞避免算法。

采用慢开始算法。

初始时，拥塞窗口cwnd = 1KB，乙的接收窗口rwnd = 16 KB。

甲的发送窗口 swnd = min{cwnd, rwnd} = min {1 KB, 16 KB} = 1KB。

第1个RTT开始时，可以将第1个TCP段连续发送出去，第1个RTT结束后，上述TCP段进入乙的缓存，乙的接收窗口rwnd = 16 KB -1 KB = 15 KB，调整当前拥塞窗口大小为上一轮次拥塞窗口大小的两倍，拥塞窗口cwnd = 2 KB。甲的发送窗口 swnd = min{cwnd, rwnd} = min {2 KB, 15 KB} = 2 KB。

第2个RTT开始时，可以将第2、3个TCP段连续发送出去。第2个RTT结束后，上述TCP段进入乙的缓存，乙的接收窗口rwnd = 15 KB -2 KB = 13 KB，调整当前拥塞窗口大小为上一轮次拥塞窗口大小的两倍，拥塞窗口cwnd = 4 KB。甲的发送窗口 swnd = min{cwnd, rwnd} = min {4 KB, 13 KB} = 4 KB。

第3个RTT开始时，可以将第4、5、6、7个TCP段连续发送出去。第3个RTT结束后，上述TCP段进入乙的缓存，乙的接收窗口rwnd = 13 KB -4 KB = 9 KB，调整当前拥塞窗口大小为上一轮次拥塞窗口大小的两倍，拥塞窗口cwnd = 8 KB。甲的发送窗口 swnd = min{cwnd, rwnd} = min {8 KB, 9 KB} = 8 KB。

第4个RTT开始时，可以将第8、9、10、11、12、13、14、15个TCP段连续发送出去。第4个RTT结束后，上述TCP段进入乙的缓存，乙的接收窗口rwnd = 9 KB - 8 KB = 1 KB，调整当前拥塞窗口大小为上一轮次拥塞窗口大小的两倍，拥塞窗口cwnd = 16 KB。甲的发送窗口 swnd = min{cwnd, rwnd} = min {16 KB, 1 KB} = 1 KB。

为了简化模型，假设同一个TCP段的发送和确认在同一个RTT内完成，可画出如下示意图。

本题选 A。

本题考察 HTTP 请求报文的解读。

HTTP 报文格式如下：

A 正确，根据HTTP请求报文第一行，可知请求 url 为 /index.html。

B 正确，host字段指明了请求的主机，因此页面存放在该主机上。

C 错误，报文中指定了 connection: close ，表示请求使用短连接，而非持续连接。持续连接在HTTP/1.1中是默认的行为，因此即使在请求报文中没有明确指定使用持续连接，但在HTTP/1.1中，连接会被默认地保持开放，除非在请求或响应头中显式指定关闭连接。因此，即使报文中没有提到使用持续连接，但在HTTP/1.1中，连接也会被默认地保持开放。也就是如果使用持续连接，该字段应该是 Connection: keep-alive 或者缺省。

D. 正确，根据报文中的 cookie 字段，可以推断出该浏览器曾经浏览过 www.test.edu.cn 并且存储了一个名为 123456 的cookie。

方法一：散列表

题目要求“时间复杂度尽可能高效”，所以可以考虑用散列表进行辅助。

算法基本思想如下：

从链表第一个元素开始遍历链表：

如果散列表中没有绝对值为当前元素绝对值的记录，保留该结点，并在散列表中记录当前元素绝对值，继续检查下一个结点。

如果散列表中已经有绝对值为当前元素绝对值的记录，删除该结点，继续检查下一个结点。

直到链表遍历结束。

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

C语言没有散列表这种数据结构，可以考虑用数组代替，由题目条件 |data|≤n ，只需要开辟一个大小为 n+1 的辅助数组。

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

struct ListNode {
    int data;
    struct ListNode* link;
};

struct ListNode* deleteDuplicates(struct ListNode* head, int n) {
    int st[n + 1];
    memset(st, 0, sizeof(st));
    struct ListNode *prev = head;
    struct ListNode *curr = head->link;
    while (curr != NULL) {
        if (st[abs(curr->data)] == 1) {
            prev->link = curr->link;
            struct ListNode *temp = curr;
            curr = curr->link;
            free(temp);
        } else {
            st[abs(curr->data)] = 1;
            prev = prev->link;
            curr = curr->link;
        }
    }
    return head;
}

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

int main(int argc, const char * argv[]) {
    int a[] = {21, -15, -15, -7, 15};
    struct ListNode* head = createLinkedList(a, 5);
    struct ListNode* newhead = deleteDuplicates(head, 32);
    struct ListNode* curr = head->link;
    printf("head");
    while (curr != NULL) {
        printf("->%d", curr->data);
        curr = curr->link;
    }
    return 0;
}

复杂度分析

• 时间复杂度： O(m+n) ，初始化辅助数组时间为 O(n) ，只需要遍历一次链表，时间为 O(m) 。
• 空间复杂度： O(n) ，辅助数组空间为 O(n) 。

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

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

struct ListNode {
    int data;
    ListNode *link;
};

ListNode* deleteDuplicates(ListNode* head, int n) {
    vector<int>st(n + 1);
    ListNode *prev = head;
    ListNode *curr = head->link;
    while (curr) {
        if (st[abs(curr->data)]) {
            prev->link = curr->link;
            ListNode *temp = curr;
            curr = curr->link;
            delete temp;
        } else {
            st[abs(curr->data)] = 1;
            prev = prev->link;
            curr = curr->link;
        }
    }
    return head;
}

ListNode* createLinkedList(vector<int> nums) {
    ListNode* head = new ListNode();
    ListNode* tail = head;
    for (int i = 0; i < nums.size(); i++) {
       ListNode* node = new ListNode();
        node->data = nums[i];
        node->link = nullptr;
        tail->link = node;
        tail = tail->link;
    }
    return head;
}

int main(int argc, const char * argv[]) {
    vector<int>nums{21, -15, -15, -15, -7, 15, 15};
    ListNode* head = createLinkedList(nums);
    ListNode* newhead = deleteDuplicates(head, 32);
    ListNode* curr = newhead->link;
    cout << "head";
    while (curr) {
        cout << "->" << curr->data;
        curr = curr->link;
    }
    return 0;
}

复杂度分析

• 时间复杂度： O(m+n) ，初始化辅助数组时间为 O(n) ，只需要遍历一次链表，时间为 O(m) 。
• 空间复杂度： O(n) ，辅助数组空间为 O(n) 。

虽然C++的标准函数库提供了具有散列表功能的数据结构如unordered_set和unordered_map，但首选仍然是用数组代替散列表，unordered_set和unordered_map不到迫不得已的情况不考虑使用，散列表适用于元素稀疏离散或元素范围未知的情况。C语言没有提过散列表，可以采用三方开源uthash。

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

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

struct ListNode {
    char data;
    struct ListNode* link;
};

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;
    }
}

struct ListNode *deleteDuplicates(struct ListNode* head) {
    hashtable = NULL;
    struct ListNode *prev = head;
    struct ListNode *curr = head->link;
    while (curr) {
        struct hashTable *it = find(abs(curr->data));
        if (it != NULL) {
            prev->link = curr->link;
            struct ListNode *temp = curr;
            curr = curr->link;
            free(temp);
        } else {
            insert(abs(curr->data), 1);
            prev = prev->link;
            curr = curr->link;
        }
    }
    return head;
}

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

int main(int argc, const char * argv[]) {
    int a[] = {21, -15, -15, -7, 15};
    struct ListNode* head = createLinkedList(a, 5);
    struct ListNode* newhead = deleteDuplicates(head);
    struct ListNode* curr = head->link;
    printf("head");
    while (curr != NULL) {
        printf("->%d", curr->data);
        curr = curr->link;
    }
    return 0;
}

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

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

struct ListNode {
    int data;
    ListNode *link;
};

ListNode* deleteDuplicates(ListNode* head) {
    unordered_set<int>st;
    ListNode *prev = head;
    ListNode *curr = head->link;
    while (curr) {
        if (st.count(abs(curr->data))) {
            prev->link = curr->link;
            ListNode *temp = curr;
            curr = curr->link;
            delete temp;
        } else {
            st.insert(abs(curr->data));
            prev = prev->link;
            curr = curr->link;
        }
    }
    return head;
}

ListNode* createLinkedList(vector<int> nums) {
    ListNode* head = new ListNode();
    ListNode* tail = head;
    for (int i = 0; i < nums.size(); i++) {
       ListNode* node = new ListNode();
        node->data = nums[i];
        node->link = nullptr;
        tail->link = node;
        tail = tail->link;
    }
    return head;
}

int main(int argc, const char * argv[]) {
    vector<int>nums{21, -15, -15, -15, -7, 15, 15};
    ListNode* head = createLinkedList(nums);
    ListNode* newhead = deleteDuplicates(head);
    ListNode* curr = newhead->link;
    cout << "head";
    while (curr) {
        cout << "->" << curr->data;
        curr = curr->link;
    }
    return 0;
}

复杂度分析

• 时间复杂度： O(m) ，只需要遍历一次链表。
• 空间复杂度： O(m) ，辅助散列表空间为 O(m) 。

1）图 G 的邻接矩阵 A 如下：
\[
A=\begin{bmatrix}
0 & 1 & 1 & 0 & 1 \\
1 & 0 & 0 & 1 & 1 \\
1 & 0 & 0 & 1 & 0 \\
0 & 1 & 1 & 0 & 1 \\
1 & 1 & 0 & 1 & 0
\end{bmatrix}
\]
2）$A^{2}$如下：
\[
A^{2}=\begin{bmatrix}
3 & 1 & 0 & 3 & 1 \\
1 & 3 & 2 & 1 & 2 \\
0 & 2 & 2 & 0 & 2 \\
3 & 1 & 0 & 3 & 1 \\
1 & 2 & 2 & 1 & 3
\end{bmatrix}
\]
0 行 3 列的元素值 3 表示从顶点 0 到顶点 3 之间长度为 2 的路径共有 3 条。
3）$B^{m}$（$2\leq m\leq n$）中位于 i 行 j 列（$0\leq i$，$j\leq n - 1$）的非零元素的含义是：图中从顶点 i 到顶点 j 长度为 m 的路径条数。 

(1) 第一问。程序员可见寄存器为通用寄存器R0～R3和PC。

第二问。因为CPU采用单总线结构同一时间内，只能有一个操作数在单总线上，为了把两个操作数输入到ALU，需要分两次来做，而只有两个操作数同时出现在ALU的两个输入端，ALU才能执行运算。因此若无暂存器T，则ALU的A、B端口会同时获得两个相同的数据，使数据通路不能正常工作。

(2) ALU共有7种操作，故其操作控制信号ALUop至少需要 ⌈log⁡7⌉=3 位；移位寄存器有3种操作，其操作控制信号SRop至少需要 ⌈log⁡3⌉=2 位。

(3) 因为CPU采用单总线结构，为了防止总线冲突，挂载在总线上的部件需要用三态门进行控制，所以信号Sout所控制的部件是一个三态门，用于控制移位器与总线之间数据通路的连接与断开。三态门第一次出现在2009年题44中，三态门的定义和作用详见该题题解。

(4) 端口①、②、③、⑤、⑧须连接到控制部件输出端。

(5) 加法操作需要两个操作数作为输入，一个输入经暂存器T进入ALU的A端，另一个输入经过MUX进入ALU的B端。很容易得到连线。

连线1，⑥→⑨；连线2，⑦→④。

注：MUX是multiplexers的缩写，称为数据选择器，也称多路选择器或多路开关。在多路数据传送过程中，能够根据需要将其中任意一路选出来的电路。

(6) 因为每条指令的长度为16位，按字节编址，所以每条指令占用16bit/1B=2个内存单元，顺序执行时，下条指令地址为(PC)+2。MUX的一个输入端为2，便于执行(PC)+2操作。

根据题43的结果，重绘题43图如下：

(1) 根据题44图b的指令格式。

方法一：有寄存器直接和寄存器间接两种寻址方式，寻址方式位分别为0和1，表示寻址方式需要1位，Md、Ms1、Ms2均为1位，通用寄存器R0～R3总共4个寄存器，编号分别为0、1、2和3，二进制编号分别为00、01、10和11，表示一个寄存器需要2位，Rd、Rs1、Rs2均为2位，指令字长16位，OP占16-(1+2)×3=7位，即指令操作码占7位，因此最多可定义 2^7=128 条指令。

方法二：二地址指令末三位均为0，即源操作数2地址占3位，单地址指令末6位均为0，即源操作数1地址和源操作数2地址占6位，一个地址占3位，指令最多有3个地址，OP占16-3×3=7位，即指令操作码占7位，因此最多可定义 2^7=128 条指令。

(2) 因为inc、shl和sub指令的操作码分别为01H、02H和03H，且操作码占7位，所以inc、shl和sub指令的操作码分别为0000001B、0000010B和0000011H。

“inc R1”为单地址指令，末6位均为0，inc指令的操作码分别为0000001B，(R1)+1→R1，目的操作数R1采用直接寻址，Md为0，因为R1的寄存器编号为1=01B，所以Rd为01，所以“inc R1”的机器码为  。

“shl R2, R1”为二地址指令，末3位均为0，shl指令的操作码分别为0000010B，(R1)<<1→R2，目的操作数R2采用直接寻址，Md为0，因为R2的寄存器编号为2=10B，所以Rd为10，源操作数R1采用直接寻址，Ms1为0，因为R1的寄存器编号为1=01B，所以Rs1为01，所以“shl R2，R1”的机器码为  。

“sub R3, (R1), R2”为三地址指令，sub指令的操作码为0000011H。((R1))–(R2)→R3，目的操作数R3采用直接寻址，Md为0，因为R3的寄存器编号为3=11B，所以Rd为11，源操作数1的R1采用间接寻址，Ms1为1，因为R1的寄存器编号为1=01B，所以Rs1为01，源操作数2的R2采用直接接寻址，Ms2为0，为R2的寄存器编号为2=10B，所以Rs2为10，所以“sub R3，(R1)，R2”的机器码为  。

(3) 根据题44图a的部分指令控制信号。

方法一：完整推理

I. 取指周期：

• T1: PCout=1, MARin=1, Tin =1, MEMop = read
  • 执行功能 (PC)→MAR, (PC)→T, 1→R。
• T2: MUXop = ①, ALUop = add, SRop = ②
  • 执行功能 (T)→ALU的A端, (ALU的A端)+2→SR。(PC)+2→PC 不需额外的MUXop输入，所以①为0，SR进行直送(mov)，所以②为mov。以及 M(MAR)→MDR。
• T3: SRout=1, PCin = 1
  • 执行功能(SR)→PC。
• T4: MDRout = 1, IRin = 1
  • 执行功能 (MDR)→IR。

II. 执行“shl R2, R1”周期：

• T1: R1out = 1, Tin = 1, ALUop = ③
  • 执行功能(R1)→T，(T)→ALU的A端，该指令不需要进行加减法，ALU直送A(mova)端内容到SR，(ALU的A端)→SR，所以③为mova。
• T2: SRop = ④
  • 指令需要实现shl，执行功能(SR)<<1→SR，SR可以实现左移一位(left)，所以④为left。
• T3: SRout = 1, R2in = 1
  • 执行功能(SR)→R2。

III. 执行“sub R0, R2, (R1)”周期：

• T1: R1out = 1, MARin = 1, MEMop = ⑤
  • 执行功能(R1)→MAR，需要读存储器，存储器控制信号为MEMop，用于控制存储器的读(read)和写(write)操作，所以⑤为read。
• T2: R2out = 1, Tin = 1
  • 执行功能(R2)→T，(T)→ALU的A端。以及 M(MAR)→MDR。
• T3: MDRout = 1, MUXop = 1, ALUop = ⑥, SRop = ⑦
  • 执行功能(MDR)→MUX，(MUX)→ALU的B端，指令需要实现sub，ALU可以实现A减B(sub)，即(ALU的A端)-(ALU的B端)→SR，所以⑥为sub，减法完成后没有额外计算操作，SR为进行直送(mov)，所以⑦为mov。
• T4: ⑧ = 1, R0in = 1
  • 执行功能(SR)→R0，SRout需要打开，所以⑧为SRout。

综上，各标号处的控制信号或控制信号取值如下：

①0；②mov；③mova；④left；⑤read；⑥sub；⑦mov；⑧SRout。

方法二：关键信息推理

I. 取指周期的一般过程如下

• T1: (PC)→MAR, 1→R,
• T2: M(MAR)→MDR, (PC)+1→PC
• T3: (MDR)→IR

只有一步执行加法，没有额外计算操作，所以①为0，SRop是SR的操作，SR为移位寄存器，可实现直送(mov)、左移一位(left)和右移一位(right)3种操作，因为没有额外计算操作，所以②为mov。

II. 执行“shl R2, R1”周期执行左移运算，没有额外计算操作，执行过程可划分为取数、运算和写回过程。

ALUop是ALU的操作，ALU可实现直送A(mova)、A加B(add)、A减B(sub)、A与B(and)、A或B(or)、非A(not)、A加1(inc)这7种操作，因为没有额外计算操作，所以③为mova。

SRop是SR的操作，SR为移位寄存器，可实现直送(mov)、左移一位(left)和右移一位(right)3种操作，因为要实现左移，所以④为left。

III. 执行“sub R0, R2, (R1)”周期执行减法操作，没有额外计算操作，执行过程可划分为取数、运算和写回过程。

MEMop是MEM的操作，存储器控制信号为MEMop，用于控制存储器的读(read)和写(write)操作，第一步是取数，所以⑤为read。

ALUop是ALU的操作，ALU可实现直送A(mova)、A加B(add)、A减B(sub)、A与B(and)、A或B(or)、非A(not)、A加1(inc)这7种操作，因为需要进行减法操作，所以⑥为sub。

SRop是SR的操作，SR为移位寄存器，可实现直送(mov)、左移一位(left)和右移一位(right)3种操作，因为没有额外计算操作，所以⑦为mov。

运算结束后需要写回，SRout需要打开，所以⑧为SRout。

综上，各标号处的控制信号或控制信号取值如下：

①0；②mov；③mova；④left；⑤read；⑥sub；⑦mov；⑧SRout。

(4) 类比“sub R0, R2, (R1)”，得到指令“sub R1，R3，(R2)”的执行周期如下：

• T1: R2out = 1, MARin = 1, MEMop = 0
• T2: R3out = 1, Tin = 1
• T3: MDRout = 1, MUXop = 1, ALUop = sub, SRop = mov
• T4: SRout = 1, R1in = 1

所以指令“sub R1，R3，(R2)”的执行阶段执行阶段至少包含4个时钟周期。

类比“shl R2, R1”，得到指令“inc R1”的执行周期如下：

• T1: R1out = 1, Tin = 1, ALUop = inc, SRop = mov
  • 执行功能(R1)→T，(T)→ALU的A端，(ALU的A端)+1→SR。
• T2: SRout = 1, R1in = 1。
  • 执行功能(SR)→R1。

所以指令“inc R1”的执行阶段至少包含2个时钟周期。

本题为多生产者多消费者多缓冲区模型，有两个单生产者单消费者单缓冲区模型组成：

B向A写邮件，A收邮件：B为生产者，A为消费者，A的信箱为缓冲区。伪代码如下：

semaphore box_A_mutex = 1;    // A的信箱互斥信号量
semaphore box_A_empty = M-x;  // A的信箱空闲位置数量
semaphore box_A_full = x;     // A的信箱邮件数量

CoBegin
Sender_B {
    while (true) {
        提出一个新问题;
        P(box_A_empty);    // 请求A的信箱一个空位
        P(box_A_mutex);
        将新邮件放入A的信箱;
        V(box_A_mutex);
        V(box_A_full);    // A的信箱邮件数量加一
    }
}
Receiver_A {
    while (true) {
        P(box_A_full);    // 请求A的信箱一个邮件
        P(box_A_mutex);
        从A的信箱中取出一个邮件;
        V(box_A_mutex);
        V(box_A_empty);    // A的信箱空位数量加一
        回答问题;
    }
}
CoEnd

A向B写邮件，B收邮件：A为生产者，B为消费者，B的信箱为缓冲区。伪代码如下：

semaphore box_B_mutex = 1;    // B的信箱互斥信号量
semaphore box_B_empty = N-y;  // B的信箱空闲位置数量
semaphore box_B_full = y;     // B的信箱邮件数量

CoBegin
Sender_A {
    while (true) {
        提出一个新问题;
        P(box_B_empty);    // 请求B的信箱一个空位
        P(box_B_mutex);
        将新邮件放入B的信箱;
        V(box_B_mutex);
        V(box_B_full);    // B的信箱邮件数量加一
    }
}
Receiver_B {
    while (true) {
        P(box_B_full);    // 请求B的信箱一个邮件
        P(box_B_mutex);
        从B的信箱中取出一个邮件;
        V(box_B_mutex);
        V(box_B_empty);    // B的信箱空位数量加一
        回答问题;
    }
}
CoEnd

进程 Receiver_A 和进程 Sender_A 合成进程 A，进程 Receiver_B 和进程 Sender_B 合成进程 B，得到最终伪代码：

semaphore box_A_mutex = 1;    // A的信箱互斥信号量
semaphore box_A_empty = M-x;  // A的信箱空闲位置数量
semaphore box_A_full = x;     // A的信箱邮件数量
semaphore box_B_mutex = 1;    // B的信箱互斥信号量
semaphore box_B_empty = N-y;  // B的信箱空闲位置数量
semaphore box_B_full = y;     // B的信箱邮件数量

CoBegin
A {
    while (true) {
        P(box_A_full);    // 请求A的信箱一个邮件
        P(box_A_mutex);
        从A的信箱中取出一个邮件;
        V(box_A_mutex);
        V(box_A_empty);    // A的信箱空位数量加一
        回答问题并提出一个新问题;
        P(box_B_empty);    // 请求B的信箱一个空位
        P(box_B_mutex);
        将新邮件放入B的信箱;
        V(box_B_mutex);
        V(box_B_full);    // B的信箱邮件数量加一
    }
}
B {
    while (true) {
        P(box_B_full);    // 请求B的信箱一个邮件
        P(box_B_mutex);
        从B的信箱中取出一个邮件;
        V(box_B_mutex);
        V(box_B_empty);    // B的信箱空位数量加一
        回答问题并提出一个新问题;
        P(box_A_empty);    // 请求A的信箱一个空位
        P(box_A_mutex);
        将新邮件放入A的信箱;
        V(box_A_mutex);
        V(box_A_full);    // A的信箱邮件数量加一
    }
}
CoEnd

(1) 第一问。根据虚拟地址格式，页内偏移量占12位，计算机系统按字节编址，页大小为 2^12 ×1B=4KB，页框大小与页大小相同，为4KB。

第二问。根据虚拟地址格式，虚拟地址占10+10+12=32位，计算机系统按字节编址，进程的虚拟地址空间大小为 2^32 ×1B= 2^32 B，页大小为 2^12 B，虚拟地址空间大小为 2^32B/2^12B=2^20 页。或者页目录号占10位，有 2^10 个页目录项，又页表索引占10位，每个页目录号下有 2^10 个页表索引，总共有 2^10×2^10=2^20 个页表索引，所以进程的虚拟地址空间大小为 2^20 页。

(2) 根据虚拟地址格式，页目录号占10位，有 2^10 个页目录项，页目录项占4B，页大小为4KB，进程的页目录占 2^10 ×4B/4KB=1页。又页表索引占10位，每个页目录号下有 2^10 个页表索引，总共有 2^10×2^10=2^20 个页表索引，页表项占4B，页大小为4KB，进程的页表占 2^20 ×4B/4KB=1024页。综上，进程的页目录和页表共占1+1024=1025页。

(3)  等价于  。根据虚拟地址格式，因为虚拟地址 0100 0000H = B 和 0111 2048H = B 的页目录号都是0000 0001 00B=4，所以进行地址转换时需访问一级页表的同一个页表项，对应同一个二级页表，即 4 号二级页表，两个虚拟地址在二级页表中的页表项不同。如下图所示：

综上，访问的虚拟地址为0100 0000H和0111 2048H共访问1个二级页表。

(1) 在网络拓扑图中，网关接口的IP地址111.123.15.1/24、DHCP服务器的IP地址111.123.15.2/24、WWW服务器的IP地址111.123.15.3/24 和主机 1 的 IP地址111.123.15.4/24 都属于 CIDR 地址块 111.123.15.0/24，该地址块主机号占 8 位。

第一问。除去1个主机号全0的网络地址111.123.15.0/24、一个主机号全1的广播地址111.123.15.255/24以及前面已分配的4个IP地址，剩余 DHCP 服务器可为主机 2~主机 N 动态分配 IP 地址的最大范围是 111.123.15.5~111.123.15.254。

第二问。DHCP Discover报文用于在局域网中寻找可用的DHCP 服务器。这个报文是在设备启动连接网络时发送的，用来请求IP地址分配。DHCP Discover报文中的源IP地址通常被设置为0.0.0.0，因为在发送Discover消息时，设备还没有被分配IP地址。这个地址表示未知或无效。目的IP地址通常是广播地址，即255.255.255.255。这是因为DHCP Discover需要被局域网中的所有DHCP服务器接收，以便它们可以回复设备的请求，并提供IP地址与其他网络配置信息。广播地址确保了所有网络中的DHCP服务器都可以收到这个消息。因此，主机2发送的封装 DHCP Discover 报文的IP分组的源IP地址和目的IP地址分别是0.0.0.0和 255.255.255.255。

(2) 因为主机2的ARP表为空，它将会发送一个ARP请求来解析互联网上的目标IP地址。在发送这个ARP请求之前，主机2会尝试查找默认网关的IP地址（通常是连接到互联网的路由器），然后构建一个ARP请求，其中包含该默认网关的IP地址。当这个ARP请求被发送时，目的MAC地址会被设置为广播地址（即所有位全为1的MAC地址 ff:ff:ff:ff:ff:ff），以确保所有网络中的设备都能收到这个请求。

一旦主机2收到了默认网关的MAC地址00-al-al-al-al-al，它就可以构建IP数据包并封装成以太网帧。这时，封装主机2发往互联网的IP数据包的以太网帧的目的MAC地址将会被设置为默认网关的MAC地址00-al-al-al-al-al，这样数据包就可以被正确地路由到互联网上的目标地址。

综上所述，主机 2发出的第一个以太网帧的目的 MAC地址是 ff-ff-ff-ff-ff-ff，封装主机2发往Internet 的 IP分组的以太网帧的目的 MAC地址是00-al-al-al-al-al。

(3) 第一问。主机1的IP地址为111.123.15.4，子网掩码为255.255.255.0，子网掩码前24位全1，表示网络号占24位，因此主机1的IP地址为111.123.15.4/24，因为WWW服务器的IP地址111.123.15.3/24 和主机 1 的 IP地址111.123.15.4/24 都属于 CIDR 地址块 111.123.15.0/24，两者处于一个局域网中，因此主机 1 能访问WWW服务器。

第二问。主机1要访问Internet，默认网关应该是111.123.15.1，但被错误配置成111.123.15.2，因此当主机1访问 Internet时，主机 1发出的IP分组会被路由到错误的默认网关（111.123.15.2），因此主机 1 不能访问Internet。

综上所述，主机 1 能访问WWW服务器，但不能访问Internet。