D
链接地址相当于->next指针，a->f->e

首先要构造出这条链表，题目已经降低难度告诉你表头元素为c，正向构造单链表为：

c(1008H)→a(1000H)→e(1010H)→b(1004H)→d(100CH)→NULL

当然命题组可以加大难度，不告诉你表头元素为c这个条件，那么就需要从d的链接地址为NULL从表尾到表头逆向构造链表。如果进一步加大难度，可以添加一些不在链表中的干扰元素。

按照题意，插入f(1014H)到a和e之间，单链表变为：

c(1008H)→a(1000H)→f(1014H)→e(1010H)→b(1004H)→d(100CH)→NULL

a指向f，链接地址为1014H；e指向b，链接地址为1004H；f指向e，链接地址为1010H。

本题选D。

注意：如果没有按照题目要求a, e, f的顺序输出链接顺序，而是按照链表a, f, e的顺序输出链接顺序，会误选C，所以审题一定要仔细。

本题为送分题，修改p的前驱结点的next指针指向p的后继结点，修改p的后继结点的prev指针指向p的前驱结点，最后释放p占用的内存。

本题选D。

队列为先进先出，这里要求出队顺序为1~9，相当于利用多个队列作为归并段，然后多路归并成一个有序数组，每个归并段单调递增。题目要求 n 最少，所以采用贪心策略，尽量少创建队列，我们很容易模拟出这个过程：

很明显，最后有4个队列（归并段）。

当然，这个答案不唯一，我是按照从上到下的方式选择入队队列，也可以按照别的顺序选择，但是必须要求每个队列队头到队尾升序排序。

最后一步归并排序也很简单，每次选择所有队列中最小的队头元素出队。

本题选C。

B

方法一：计算

每棵树的结点数比边数多一，设有 x 棵树，每棵树有 ni(1≤i≤x) 个结点，则有：

两式相减得： x=10 。

本题选C。

方法二：归纳法

下面提供秒题解法。

每棵树的结点数比边数多一，一棵树就相差1，两棵树就相差2， k 棵树就相差 k 。

25−15=10 。

本题选C。

方法一：代入选项

深度优先搜索就是一个“一条路走到黑”的搜索策略，直到无路可走才开始回溯，找到前一个能够继续搜索的结点重复上述步骤。

注意本图为有向图，只能按照箭头的方向走。

由于本题图中分支很多，如果正向枚举所有深度优先搜索序列会非常复杂，所以这里采用带入选项检查策略。

很明显，D选项走到 V2 后无法走到 V3 ，错误。

本题选D。

方法二：观察选项

如果你连深度优先搜索是什么都不知道，那只能猜了，观察选项，只有D选项序列有序，其它为乱序。

这种猜法就是赌命题组设置错误选项很无脑，就和很多人喜欢用123456作为密码一样。别笑，我还真用123456当密码过，而且不止一次。

本题选D。

方法一：深度优先搜索

如果在拓扑序列中顶点u在顶点v前面，则在深度优先搜索中顶点v先访问完成。按照访问顶点的结束时间从大到小输出即为拓扑序列。

所以每个顶点在搜索过程中需要记录一个状态，用color表示，该状态有3种情况：

• 未访问：还没有搜索到这个顶点，记为WHITE；
• 访问中：搜索过这个顶点，但还没有回溯到该顶点，该顶点还有相邻顶点没有访问完成，记为GRAY；
• 访问完成：搜索过并且回溯到这个顶点，且该顶点的所有相邻顶点均已访问完成，记为BLACK。

拓扑排序过程 TOPOLOGICAL-SORT 的伪代码如下：

DFS(u, L)
    u.color = GRAY
    for each vertex v ∈ G.Adj[u]
        if v.color == WHITE
            DFS(v, L)
            if valid == FALSE
                return
            else if v.color == GRAY
                valid = FALSE
                return
    u.color = BLACK
    insert u onto the front of L

TOPOLOGICAL-SORT(G)
    let L be a new linked-list
    valid = TRUE
    for each vertex u ∈ G.V
        u.color = WHITE
    for each vertex u ∈ G.V
        if valid == TRUE
            if u.color == WHITE
                DFS(u, L)
        else break
    if valid == FALSE
        error "G has cycles"
        return
    else return L

由于深度优先搜索运行时间为O(n+e)，其它开销为常数，因此过程 TOPOLOGICAL-SORT 的运行时间为 O(n+e) 。

本题选B。

方法二：广度优先搜索

若一个顶点的所有前驱顶点均已输出到拓扑序列中，则该顶点的入度为0。重复寻找入度为0的顶点，输出该顶点并将该顶点及从该顶点发出的边从图中删除。

拓扑排序过程 TOPOLOGICAL-SORT 的伪代码如下：

TOPOLOGICAL-SORT(G)
    let L be a new linked-list
    for each vertex u ∈ G.V
        u.in-degree = 0
    for each vertex u ∈ G.V
        for each v ∈ G.Adj[u]
            v.in-degree = v.in-degree + 1
    Q = ∅
    for each vertex u ∈ G.V
        if u.in-degree == 0
            ENQUEUE(Q, u)
            insert u onto the rear of L
    while Q ≠ ∅
        u = DEQUEUE(Q)
        for each vertex v ∈ G.Adj[u]
            v.in-degree = v.in-degree - 1
            if v.in-degree == 0
                ENQUEUE(Q, v)
                insert v onto the rear of L
    for each vertex u ∈ G.V
        if u.in-degree ≠ 0
            error "G has cycles"
            return
    return L

由于广度优先搜索运行时间为O(n+e)，其它开销为常数，因此过程 TOPOLOGICAL-SORT 的运行时间为 O(n+e) 。

本题选B。

Dijkstra算法使用贪心策略，每次选择距离起点最近的顶点进行继续搜索，并更新起点到各个顶点的距离。

根据Dijkstra算法，点集 S 初始为空，从顶点 1 到其余各顶点的最短路径如下表所示：

本题选B。

本题代码为一步一跳的线性查找代码的优化，三步一跳找到目标元素或者目标元素附近再进行进一步检查。

但本质上仍然是从前往后的线性遍历，时间复杂度仍为 O(n) 。

既然是从前往后的线性遍历，当然是当 x 接近数组开头处时，比较次数更少。

本题选B。

B+树和B树的区别主要有两点：

• B+树的非叶结点不存储关键字，只作索引使用，而B树的非叶结点存储关键字。所以B+树的所有叶结点中包含了全部的关键字信息，但B树不一定。
• B+树上的叶结点存储关键字以及相应记录的指针，叶结点中将关键字按大小顺序排列，并且相邻叶结点按大小顺序相互链接起来。所以B+树支持两种查找运算：一种是从最小关键字开始的顺序查找，另一种是从根结点开始的多路查找。但B树只支持从根结点开始的多路查找。

本题选A。

10TB意思是数据量非常大，不适合用内部排序，只能用外部排序，外部排序通常采用归并排序的方法。

本题选D。

汇编程序 (Assembler)：用于将汇编语言程序翻译为机器目标代码。

链接程序 (Linker)：用于将多个目标代码文件和库文件组合成一个可执行文件。

编译程序 (Compiler) ：将高级语言源程序翻译为机器目标代码的程序。编译程序将高级语言中的源代码作为输入，经过词法分析、语法分析、语义分析、优化和代码生成等阶段的处理，最终生成相应的机器目标代码文件。

解释程序 (Interpreter)：是逐行解释执行高级语言源程序，而不是生成独立的目标代码文件。

本题选C。

方法一：二进制计算

C语言中的数据在内存中为补码表示形式，short为有符号短整型，占16位，si = -32767 = -(32768-1)，[si]原 = 1111 1111 1111 1111B，[si]补 = 1000 0000 0000 0001B。

第2行代码进行了强制类型转换，由signed型转化为等长unsigned型数据时，符号位成为数据的一部分，usi = [si]补 = 1000 0000 0000 0001B = 2^15+1 = 32768 + 1 = 32769。

本题选D。

方法二：十进制计算

short为有符号短整型，占16位，表示范围为 −2^15∼2^15−1 ，即-32768~32767。

unsigned short为无符号短整型，占16位，表示范围为 0∼2^16−1 ，即0~65535。

short和unsigned short均占16位，表示范围大小均为 2^16=65536 。

-32767对于unsigned short负越界，正向偏移一个表示范围大小，即偏移 2^16=65536 ，得到-32767+65536=32769。

本题选D。

本题中按字节编址，一个double型变量占64位，即8字节，占用8个连续存储单元。

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

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

机器数1122 3344 5566 7788H存放在0000 8040H开始的连续存储单元中，可以画出如下内存分配。

因此存储单元0000 8046H中存放的是22H。

本题选A。

a[k]的访问步骤是：先访问cache，cache缺失，之后从主存中取出一个块调入cache，这个块中的后几个数据都是命中的，本题中一个数据占4B，一个块大小是16B，这说明一个块中有4个数据，关键是后面还有一次写，这说明一次循环要八次访问cache，其中只有第一次是缺失的，后面七次都是命中的，所以缺失率是12.5%。

数据区大小是 1KB，块大小是 16B，Cache 有 1KB/16B = 64 行，每个块可以装 16B/4B = 4 个数组元素。

对于数组中任意一个元素 a[k]，只有在 a[k] = a[k] + 32 这行代码中会对 a[k] 进行访问。其中包含读 a[k] 一次，做完加法后写 a[k] 一次。

每次调入块后加载连续的四个数组元素，a[4i]、a[4i + 1]、a[4i + 2]、a[4i + 3]，其中 i 为整数，i = 0, 1, …, 249。

缺失率为 1/8 = 12.5%。

本题选C。

因为ROM区地址为4000H～5FFFH，按字节编址，所以ROM区容量为(5FFFH+1H-4000H)B=(2000H)B= 2×16^3B=8KB。该存储器容量为64KB，除ROM区外为RAM区，RAM区容量为64KB-8KB=56KB，需要8K×4位的SRAM芯片的数量为56KB/(8K×4bit)=14。

本题选C。

变址寻址中，有效地址EA等于指令字中的形式地址D与变址寄存器I的内容相加之和，即EA=(I)+D。间接寻址是相对于直接寻址而言的，指令的地址字段给出的形式地址不是操作数的真正地址，而是操作数地址的地址，所以需要再直接寻址的基础上再寻址一次，即EA=(A)。

该指令采用先变址后间址的寻址方式，复合可得该操作数的有效地址是((I)+D)。

本题选C。

计算机主存空间为4GB，字长为32位，指令按字边界对齐存放，计算机能存放的指令数量最多为4GB/32bit= 2^30 ，即一条指令地址位数最多为30，程序计数器 (PC) 用于存放指令地址，所以程序计数器 (PC) 的位数至少（需要满足指令地址位数最多的情况）是30位，指令寄存器 (IR) 用于接收取得的指令，指令字长为32位，所以指令寄存器 (IR) 的位数至少为32位。

本题选B。

数据冒险，即数据相关，若一个程序中存在必须等前一条指令执行完才能执行后一条指令的情况，则这两条指令即为数据相关。当多条指令重叠处理时就会发生冲突。

观察指令序列，考虑五段流水线①IF取值②ID译码和取数③EX执行④M访存⑤WB写回，I2在WB阶段写入R5，R3在ID阶段读取R5，发生写后读数据冒险。可以采用数据旁路技术解决该数据冲突。

本题选B。

本题考察对CPU时钟周期的理解。

时钟周期：又称节拍周期，是处理操作的最基本单位。时钟周期是计算机中最基本的、最小的时间单位。在一个时钟周期内，CPU仅完成一个最基本的动作。时钟周期是一个时间的量。

单总线结构将CPU、主存、I/O设备都挂在一组总线上，允许I/O设备之间、I/O设备与主存之间直接交换信息，但多个部件只能争用唯一的总线，且不支持并发传送操作，会造成总线冲突。单周期处理器不可以采用单总线结构数据通路。A错误。假设一条指令分为五段①IF取值②ID译码和取数③EX执行④M访存⑤WB，每段执行需要一个时钟周期，若要在一个时钟周期内完成该指令，则需要5条总线并行，单总线显然无法满足要求，若要在单总线上完成，则需要串行执行5个时钟周期。单周期处理器采用单总线结构数据通路，好比上班高峰交通要道限速又限流，直接造成交通堵塞。

因为要考虑比较慢的指令，所以处理器的时钟频率较低，B正确。

因为在一个时钟周通常为一个节拍脉冲，控制信号时控制单元 (CU) 根据指令操作码发出的信号，一个时钟周期内的控制信号不变，单周期处理器中所有指令的指令周期为一个时钟周期，在指令执行过程中控制信号不变。C正确。

因为单周期处理器即指所有指令的指令周期为一个时钟周期，所以每条指令的CPI为1。D正确。

本题选A。

并行总线传输通常比串行总线传输速度快，但这不是绝对的。在实际时钟频率比较低的情况下，并行总线因为可以同时传输若干比特，速率确实比串行总线快。但是，随着技术的发展，时钟频率越来越高，并行导线之间的相互干扰越来越严重，当时钟频率提高到一定程度时，传输的数据已经无法恢复。而串行总线因为导线少，线间干扰容易控制，反而可以通过不断提高时钟频率来提高传输速率。A错误。

总线复用是指一种信号线在不同的时间传输不同的信息。可以使用较少的线路传输更多的信息，从而节省了空间和成本。B正确。

突发（猝发）传输是在一个总线周期中，可以传输多个存储地址连续的数据，即一次传输一个地址和一批地址连续的数据。C正确。

分离事务通信即总线复用的一种，相比单一的传输线路可以提高总线的利用率。D正确。

本题选A。

本题中，中断指外中断，指来自CPU执行指令以外事件的发生，如设备发出的I/O结束中断，表示设备I/O处理已经完成，希望处理机能够向设备发出下一个I/O请求，同时让完成I/O后的程序继续运行。A错误，C正确。

异常指内中断，也称例外或陷入 (Trap)，指源自CPU执行指令内部的事件的发生，如程序的非法操作码、地址越界、算术溢出、虚存系统的缺页以及专门的陷入指令等引起的事件。B正确，D正确。选项A“访存时缺页”属于异常。

本题选A。

【答案】A

【解析】批处理系统中，作业执行时用户无法干预其运行，只能通过事先编制作业控制说明书来间接干预，缺少交互能力，也因此才发展出分时系统，I 错误。批处理系统按发展历程又分为单道批处理系统、多道批处理系统，II正确。多道程序设计技术允许同时把多个程序放入内存，并允许它们交替在CPU中运行，它们共享系统中的各种硬/软件资源，当一道程序因I/O请求而暂停运行时，CPU便立即转去运行另一道程序，即多道批处理系统的I/O设备可与CPU并行工作，这都是借助于中断技术实现的，III正确。

答案：B

这类调度题目最好画图。

因CPU、输入设备、输出设备都只有一个，因此各操作步骤不能重叠，画出运行时的甘特图后，就能清楚地看到不同作业间的时序关系，如下图所示

根据题意，画出资源分配图，一个方框表示一类资源，里面的圆表示资源数量。由进程指向资源叫请求边，由资源指向进程叫分配边。由于题目中只给出了资源请求情况，没有明确给出资源分配情况，所以只可以画出请求边，如图(a)所示。

若系统出现死锁，则系统中出现了一条进程资源的循环等待链，链中每个进程已获得的资源同时被链中下一个进程所请求。很明显，系统中只有一个环，环上的三个进程处于死锁状态。此时可能的资源分配图如图(b)和(c)所示。

本题选C。

改进型CLOCK置换算法会优先尝试淘汰不会影响数据一致性的页，然后淘汰可能会导致数据一致性问题的页。其算法规则为将所有可能被置换的页面排成一个循环队列，然后进行至多四轮扫描：

第一轮：从当前位置开始扫描到第一个 (0, 0) 的帧用于替换。本轮扫描不修改任何标志位；

第二轮：若第一轮扫描失败，则重新扫描，查找第一个 (0, 1) 的帧用于替换。本轮将所有扫描过的帧访问位设为0；

第三轮：若第二轮扫描失败，则重新扫描，查找第一个 (0, 0) 的帧用于替换。本轮扫描不修改任何标志位；

第四轮：若第三轮扫描失败，则重新扫描，查找第一个 (0, 1) 的帧用于替换。

所以该算法淘汰页的次序为：

1. (0, 0)：选择(A, M)为(0, 0)的页进行淘汰。这表示页最近没有被访问过且没有被修改过。
2. (0, 1)：选择(A, M)为(0, 1)的页进行淘汰。这表示页最近没有被访问过，但已经被修改过。
3. (1, 0)：选择(A, M)为(1, 0)的页进行淘汰。这表示页最近被访问过，但没有被修改过。
4. (1, 1)：选择(A, M)为(1, 1)的页进行淘汰。这表示页最近被访问过且已经被修改过。

本题选A。

答案：B
当进程退出临界区时置lock为FALSE，会负责唤醒处于就绪态得进程，A错误。

等待进入临界区得进程会一直停留在执行while(TSL(&lock))的循环中，不会主动放弃CPU，B正确。

让权等待，即进程不能进入临界区时，应立即释放处理器，防止进程忙等待。通过B的分析发现，上述伪代码并不满足“让权等待”的同步准则，C错误。

while(TSL(&lock))在关中断状态下执行时，若TSL(&lock)一直为true，不再开中断，则系统可能会因此终止，D错误。

查表访问段号2，先查该段状态，该段在内存中，再查该段段长，该段长300，段内地址范围为[0, 299]，段内地址400>299，越界。

本题选D。

工作集是指在某段时间间隔内，进程要访问的页面的集合。工作集W可由时刻t和工作集窗口大小 Δ 确定。根据题意，工作集的窗口大小为6，t时刻前访问的6个页面为6,0,3,2,3,2，去重得到工作集W={6, 0, 3, 2}。

本题选A。

首先需要明确的是，进程（或线程）外的为全局变量，进程（或线程）内的为局部变量，多进程（或线程）并发执行时，全局变量为临界资源，需要互斥访问。

A错误。a=1中的a为Thread1中的局部变量，a=2中的a为Thread2中的局部变量，两者相互独立。

B错误。a=x中的a为Thread3中的局部变量，b=x中的b为Thread4中的局部变量，两者相互独立。

C正确。x+=1在Thread1中执行，x+=2在Thread2中执行，Thread1和Thread2都属于进程P1，Thread1和Thread2并行修改进程P1的全局变量x，需要互斥执行。

D错误。x+=1在Thread1中执行，x+=3在Thread3中执行，Thread1属于进程P1，而Thread3属于进程P2，这两个x分属于不同进程，两者相互独立。

本题选C。

SPOOLing（Simultaneous Peripheral Operation On-Line）技术是一种用于提高计算机系统输入/输出效率的技术。具体地说，SPOOLing技术是低速输入输出设备与主机交换的一种技术，通常也称为“假脱机真联机”，他的核心思想是以联机的方式得到脱机的效果。低速设备经通道和外设在主机内存的缓冲存储器与高速设备相联，该高速设备通常是辅存。为了存放从低速设备上输入的信息，或者存放将要输出到低速设备上的信息（来自内存），在辅存分别开辟一固定区域，叫“输出井”（对输出），或者“输入井”（对输入）。简单来说就是在内存中形成缓冲区，在高级设备形成输出井和输入井，传递的时候，从低速设备传入缓冲区，再传到高速设备的输入井，再从高速设备的输出井，传到缓冲区，再传到低速设备。通过SPOOling技术便可将一台物理I/O设备虚拟为多台逻辑I/O设备，同样允许多个用户共享一台物理I/O设备。

A正确。SPOOLing 技术需要外存（磁盘或磁带等）的支持。它通过将I/O数据暂时存储在外存中，以实现系统与独占设备的并行操作，提高了系统的效率。

B正确。SPOOLing 技术必须建立在具有多道程序功能的操作系统上。

C正确。SPOOLing 技术的一个主要特点是可以让多个作业共享一台独占设备。通过将作业的输入/输出数据暂存到外存中，其他作业可以同时使用设备进行输入/输出操作，而不需要等待前一个作业完成。

D错误。SPOOLing 技术不是由用户作业直接控制设备与输入/输出井之间的数据传送，而是由操作系统操作系统负责将作业的输入/输出数据从外存传送到设备或从设备传送到外存。

本题选D。

管程 (Monitor) 是一种并发编程中的概念，用于实现进程之间的协作和同步。管程是由局部于自己的若干公共变量及其说明和所有访问这些公共变量的过程所组成的软件模块，由编程语言提供的语法和语义支持。

A错误。管程不仅可以用于实现进程的互斥，即保证在同一时间只有一个进程能够在管程内执行，还可以用于实现其他进程间的同步操作，例如条件变量的等待与唤醒。

B正确。管程是由编程语言支持的进程同步机制。它提供了一套语法和语义，使得程序员可以方便地使用管程来实现进程之间的同步和协作。

C正确。在管程中，可以允许多个进程请求，但是同一时间只能有一个进程在管程内执行。当一个进程试图进入一个已被占用的管程时它应当在管程的入口处等待，因而在管程的入口处有一个进程等待队列。其他进程需要等待当前进程执行完毕并退出管程后，才能进入管程执行。

D正确。管程中定义的变量通常只能被管程内的过程访问。 管程是一种并发编程模型，用于管理共享资源和并发访问的同步。在管程内部，可以定义共享资源和操作这些资源的过程。这些资源通常定义为私有变量，只能在管程内部访问。这种访问限制的设计是为了保持管程内部的数据的封装性和一致性，防止外部进程对共享资源的直接访问，从而减少了竞态条件和数据冲突的可能性，提供了更高的并发安全性。

本题选A。

OSI 参考模型 (Open System Interconnection Reference Model) 是一个由国际标准化组织提出的概念模型，旨在为各种计算机互连构成网络提供标准框架。该模型将通信系统划分为七层，从下到上依次为物理层、数据链路层、网络层、传输层、会话层、表示层和应用层。

R1 是路由器，路由器是工作在网络层（OSI 参考模型第三层）的连接设备。

Switch 是交换机，交换机是工作在数据链路层（OSI 参考模型第二层）的连接设备。

Hub 是集线器，集线器是工作在物理层（OSI 参考模型第一层）的连接设备。

本题选 C。

根据香农公式，在被高斯白噪声干扰的信道中，信道的最大数据传输速率为

 （单位：比特每秒 (bits per second, bps)）

其中 W 是信道带宽，单位 Hz，S 是信号功率，单位瓦，N 是噪声功率，单位瓦。

S/N 为信号与噪声的功率之比，简称信噪比。信噪比 SNR 通常以分贝 (dB) 为单位。

有  ，即  ，将 SNR = 30 dB 代入，得 S/N=1000 ，再将 S/N=1000 和 W=8 kHz 代入香农公式，解得  。

又因为该链路实际数据传输速率约为理论最大数据传输速率的 50％，所以则该链路的实际数据传输速率约是 C×50%≈40 kbps 。

本题选 C。

本题考察交换机自学习和转发帧的相关知识，其一般步骤如下：

自学习：以太网收到一帧后先进行自学习。查找转发表最后与收到帧的源地址有无匹配的项。如果没有，就在转发表中增加一个项（包括源地址，进入端口的口和时间）；如果有，就把原来的项进行更新。

转发帧：查找转发表中与收到帧的目的地址有无想匹配的项。如果没有，则通过除进入交换机的端口外的所有其他端口进行转发；如果有，则按照转发表中给出的端口进行转发，但要注意，如果转发表在给出的端口就是该帧进入交换机的端口，则应该丢弃该帧（因为此时无需经过交换机进行转发）。

下面对本题进行分析。

若主机H2向主机H4发送1个数据帧，首先经过Switch，此时Switch进行自学习，记录源地址为主机H2的地址，以H2和Switch连接的端口。

主机H4向主机H2立即发送一个确认帧，该确认帧首先经过Hub，Hub从所有端口广播出去，即转发给H4、H3和Switch，Switch收到该确认帧后，会先进行自学习，记录源地址为主机H4的地址，以Hub和Switch连接的端口，然后查询转发表，转发表中已经包含目的地址为H2地址的项，所以会转发给H2。

综上所述，除H4外，从物理层上能够收到该确认帧的主机还有H2、H3。

本题选 D。

本题采用100Base-T的Hub，其传输速率为100 Mbps。

以太网帧的格式如下：

不考虑以太网帧的前导码，以太网帧的最短帧长为 6 B + 6 B + 2B + 46 B + 4 B = 64B = 512 bit。 ，单程时延 τ=2τ/2=2.56 μs ，因为单程传播中会经过一次 Hub，所以单程时延 = Hub再生比特流时延 + 无 Hub 单程传播时延，已知 Hub 再生比特流时延为 1.535μs，计算出无 Hub 单程传播时延 = 2.56 μs - 1.535μs = 1.025 μs，H3与H4之间理论上可以相距的最远距离 = 信号传播速度 × 无 Hub 单程传播时延 = 200 m/μs × 1.025 μs = 205 m。

本题选 B。

本题考察对 RIP 协议的理解。

RIP 存在的一个问题是当网络出现故障时，要经过比较长的时间才能将此信息传送到所有路由器，即收敛速度较慢。

R1、R2、R3和网络201.1.2.0/25的在连通情况下的拓扑图如下：

在本题中，已知路由器R3到网络201.1.2.0/25的链路出现故障。于是路由器R3把到网络201.1.2.0/25的距离改为16（表示不可达）。

RIP协议要求仅和相邻的路由器交换信息，因此R2会接收R3和R1的更新通告。

R2接受R3的通告更新一次路由向量。如果收到R2收到R3的通告后，得知通过R3网络201.1.2.0/25不可达，它会更新到201.1.2.0/25距离为16。更新后路由表如下：

由于此时网络尚未收敛，且RIP具有“好消息传的快，坏消息传的慢”的特点，即如果一个路由器发现了更短的路由，那么这种更新消息就传播的块。

R2还会接受R1的通告更新一次路由向量。R1先前对于网络201.1.2.0/25的距离为2，那么R2收到R1的通告后，到201.1.2.0/25距离为 2 + 1 =3。相比R3的通告，3 < 16，R2会选择更短的路由进行更新。R2误以为自己到网络201.1.2.0/25的距离是3，下一跳经过R1。更新后路由表如下：

本题选 B。

本题考察网络地址转换 NAT 和无分类编址 CIDR 的相关知识。

使用私有地址192.168.3.251的主机H3，要访问Internet中使用共有地址130.18.10.1的Web服务器S，H3需要使用NAT路由器R2转发去往S的IP分组。总共有两条路径H3→R2→R1→S和H3→R2→R3→R1→S，由于题目没有明确给出路由器之间的距离，所以选择跳数更少的路径进行转发，即H3→R2→R1→S，本题简化后的网络拓扑图如下：

从H3发出的IP分组，即H3到R2链路上的IP分组，其源IP地址是H3的IP地址192.168.3.251，目的地址是S的IP地址130.18.10.1。

当该IP分组到达R2后，R2具有NAT功能，会将IP分组中源IP地址中的私有IP地址，修改为自己连接外网的接口L0的公有IP地址，题目没有直接给出L0的IP地址，需要进行计算。已知连接R1、R2和R3之间的点对点链路使用201.1.3.x/30地址，由于地址块201.1.3.x/30中包含R1和R2直连的R1的接口IP地址201.1.3.9，将其后 8 位写成二进制形式，二进制位用红色表示。得 201.1.3.00001001 ，后两位为主机号，主机号部分用的位用 x 表示，得到R1和R2所在地址块为 201.1.3.000010xx 。

将主机号位全取0，得到该子网的网络地址 201.1.3.00001000 即201.1.3.8。

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

剩余IP为该子网可分配的主机号201.1.3.9~201.1.3.10，由于201.1.3.9已被分配给R1的接口，所以只能将201.1.3.10分配给R2的接口L0。

此时，R2转发出去的IP分组的源IP地址为201.1.3.10，目的地址为130.18.10.1。

本题选D。

H1的IP地址为192.168.3.2。子网掩码为255.255.255.128。进行按位与运算，

  11000000.10101000.00000011.00000010 (192.168.3.2)  
& 11111111.11111111.11111111.10000000 (255.255.255.128)  
---------------------------------------  
  11000000.10101000.00000011.00000000 (192.168.3.0)  

得到H1所在子网的网络地址为192.168.3.0，CIDR地址块为192.168.3.0/25。

H2的IP地址为192.168.3.3，子网掩码为255.255.255.128，进行按位与运算，

  11000000.10101000.00000011.00000011 (192.168.3.3)  
& 11111111.11111111.11111111.10000000 (255.255.255.128)  
---------------------------------------  
  11000000.10101000.00000011.00000000 (192.168.3.0)  

得到H2所在子网的网络地址为192.168.3.0，CIDR地址块为192.168.3.0/25。

H3的IP地址为192.168.3.251，子网掩码为255.255.255.128，进行按位与运算，

  11000000.10101000.00000011.11111011 (192.168.3.251)  
& 11111111.11111111.11111111.10000000 (255.255.255.128)  
---------------------------------------  
  11000000.10101000.00000011.10000000 (192.168.3.128)  

得到H3所在子网的网络地址为192.168.3.128，CIDR地址块为192.168.3.128/25。

H4的网络地址为192.168.3.252，子网掩码为255.255.255.128，进行按位与运算，

  11000000.10101000.00000011.11111100 (192.168.3.252)  
& 11111111.11111111.11111111.10000000 (255.255.255.128)  
---------------------------------------  
  11000000.10101000.00000011.10000000 (192.168.3.128)  

得到H4所在子网的网络地址为192.168.3.128，CIDR地址块为192.168.3.128/25。

因此，H1和H2在同一子网192.168.3.0/25中。H3和H4在同一子网192.168.3.128/25中。

下面依次分析四个选项。

A 错误。H1和H2在同一子网192.168.3.0/25中。H1能与H2进行正常IP通信。

B 错误。H3与H4的默认网关为192.168.3.254，即R2，R2有到达Internet的路由，因此H4能够访问Internet。H1和H2的默认网关为192.168.3.1未在网络拓扑图中出现，无法判断H2能否访问Internet。

C 正确。H1和H3不在同一子网中，若H1和H3传送IP分组，需要通过其默认网关进行转发，H1的默认网关为192.168.3.1，H3的默认网关为192.168.3.254，192.168.3.1未在网络拓扑图中出现，无法判断192.168.3.1和192.168.3.254是否连通，因此可能H1不能与H3进行正常IP通信。

D 错误。H3和H4在同一子网192.168.3.128/25中。H3能与H4进行正常IP通信。

本题选 C。

在迭代查询中，域名服务器向根域名服务器、顶级域名服务器和权威域名服务器发出查询。

最好情况下，如果主机的缓存中有 www.abc.xyz.com 的IP地址记录，则无需发出DNS查询。即发出DNS查询的最少为 0。

最坏情况下，如果所有与 www.abc.xyz.com 相关记录都不在各个服务器的缓存中，则域名服务器201.1.1.1需要向根域名服务器、顶级域名服务器 com、权限域名服务器 xyz.com 、权限域名服务器 abc.xyz.com 各发出一次查询，最终得到 www.abc.xyz.com 的IP地址，域名服务器201.1.1.1最后把结果传送给H4。域名服务器201.1.1.1总共需要发出 4 次迭代查询。即发出DNS查询的最多为 4。

本题选 C。

建立 TCP 连接三次握手的过程如下：

(1) 第一问。第二次握手的TCP段中，SYN=1 且 ACK=1。

第二问。H3建立连接时的初始序号为100，即第一次握手序号 seq = x = 100。第二次握手的确认序号 ack=x+1=100+1=101。

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

S端的TCP接收缓存仅有数据存入而无数据取出。初始时，rwnd = 20 MSS

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

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

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

慢开始算法

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

拥塞避免算法

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

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

接下来对本题进行分析。

拥塞窗口初始阈值为32 KB，20 KB < 32 KB，即便在一个RTT中发送20KB数据都不会触发拥塞避免算法。可以断言从 H3 发送第1个TCP段到 H3 收到的第 20 个确认段所通告时慢开始算法都适用，不会触发拥塞避免算法。也就意味着从 H3 发送第1个TCP段到 H3 收到的第 8 个确认段所通告时慢开始算法都适用，不会触发拥塞避免算法。因此，慢开始算法每收到一个对新的报文段的确认后，把拥塞窗口增加一个 MSS 的数值。本题中最大段长MSS=1 KB。

第一问。初始时S端的TCP接收缓存为 20 KB，且该接收缓存仅有数据存入而无数据取出。H3 收到的第 8 个确认段所通告时，已经传输了 8 KB 的数据，剩余接收窗口是 rwnd = 20 KB - 8 KB = 12 KB。

第二问。H3 的拥塞窗口为此前加一，cwnd = 8 KB + 1 KB = 9 KB，即cwnd = 9 KB。

第三问。H3的发送窗口 swnd = min{cwnd, rwnd} = min {9 KB, 12 MSS} = 9 KB，即swnd = 9 KB。

(3) 第一问。当H3的发送窗口等于0时，说明已经发送了20个TCP段，接下来准备发送第21个TCP段，已经发送的字节数为 20 KB / B= 20 × 1024 = 20480，H3建立连接时的初始序号seq=x=100，第三次握手时初始序号seq=x+1=101，即从序号101字节开始传输，第21个TCP段从序号101+20480 = 20581 字节开始传输，即下一个待发送数据段序号是20581。

第二问。根据 (2) 的分析，从 H3 发送第1个TCP段到 H3 收到的第 20 个确认段所通告时慢开始算法都适用，不会触发拥塞避免算法。

第1个RTT开始时，采用慢开始算法，拥塞窗口cwnd = 1MSS，S的接收窗口rwnd = 20 MSS。

H3的发送窗口 swnd = min{cwnd, rwnd} = min {1 MSS, 20 MSS} = 1MSS，此时可以将第1个TCP段连续发送出去。

第2个RTT开始时，调整当前拥塞窗口大小为上一轮次拥塞窗口大小的两倍，拥塞窗口cwnd = 2 MSS，S的接收窗口rwnd = 20 MSS -1 MSS = 19 MSS。H3的发送窗口 swnd = min{cwnd, rwnd} = min {2 MSS, 19 MSS} = 2 MSS，此时可以将第2、3个TCP段连续发送出去。

第3个RTT开始时，调整当前拥塞窗口大小为上一轮次拥塞窗口大小的两倍，拥塞窗口cwnd = 4 MSS，S的接收窗口rwnd = 19 MSS - 2MSS =17 MSS。H3的发送窗口 swnd = min{cwnd, rwnd} = min {4 MSS, 17 MSS} = 4 MSS，此时可以将第4、5、6、7个TCP段连续发送出去。

第4个RTT开始时，调整当前拥塞窗口大小为上一轮次拥塞窗口大小的两倍，拥塞窗口cwnd = 8 MSS，S的接收窗口rwnd = 17 MSS - 4 MSS = 13 MSS。H3的发送窗口 swnd = min{cwnd, rwnd} = min {8 MSS, 13 MSS} = 8 MSS，此时可以将第8、9、10、11、12、13、14、15个TCP段连续发送出去。

第5个RTT开始时，调整当前拥塞窗口大小为上一轮次拥塞窗口大小的两倍，拥塞窗口cwnd = 16 MSS，S的接收窗口rwnd = 13 MSS - 8 MSS = 5 MSS。H3的发送窗口 swnd = min{cwnd, rwnd} = min {16 MSS, 5 MSS} = 5 MSS，此时可以将第16、17、18、19、20个TCP段连续发送出去。

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

到此为止，发送这20个TCP段需要5个RTT，RTT = 200ms，5RTT = 1s，忽略段的传输延时，总时间为 1s。发送数据量为 20 KB。

平均数据传输率为  。

(4) 释放 TCP 连接四次挥手的过程如下：

为了使释放 TCP 连接的时间最短，CLOSE-WAIT 期间不再进行数据传输，CLOSE-WAIT 和 FIN-WAIT-2 的时间为 0，释放 TCP 连接四次挥手的过程就变成了三次挥手，过程如下：

忽略段的传输延时，每次挥手的传播时延为 0.5 RTT，如下图所示。

整个过程需要 3×0.5 RTT = 1.5 RTT，RTT = 200ms，1.5 RTT = 1.5×200ms=300ms。即从t时刻起，S释放该连接的最短时间是 300ms。

一棵树中，点数 = 边数 + 1。设度为 i 的结点数量为 ni ，则：

解得：

则 T 中的叶结点有 (k−1)m+1 个。

采用贪心策略。

T 的高度为 h 结点数最多时 T 为一棵满 k 叉树，结点数总计：

T 的高度为 h 结点数最少时，每层（除最下面一层）都只有一个结点有子树。

(1)算法的基本设计思想(4分)
由题意知，将最小的 $\lfloor n/2 \rfloor$ 个元素放在 $A_1$ 中，其余的元素放在 $A_2$ 中，分组结果即可满足题目要求。仿照快速排序的思想，基于枢轴将 $n$ 个整数划分为两个子集。根据划分后枢轴所处的位置 $i$ 分别处理：
①若 $i = \lfloor n/2 \rfloor$，则分组完成，算法结束；
②若 $i < \lfloor n/2 \rfloor$，则枢轴及之前的所有元素均属于 $A_1$，继续对 $i$ 之后的元素进行划分； 
③若 $i > \lfloor n/2 \rfloor$，则枢轴及之后的所有元素均属于 $A_2$，继续对 $i$ 之前的元素进行划分； 
基于该设计思想实现的算法，毋须对全部元素进行全排序，其平均时间复杂度是 $O(n)$，空间复杂度是 $O(1)$。 

(2) 算法实现 (9 分)

int setPartition(int a[ ], int n)
{
    int pivotkey, low = 0, low0 = 0, high = n - 1, high0 = n - 1, flag = 1, k = n / 2, i;
    int s1 = 0, s2 = 0;
    
    while(flag)
    {
        pivotkey = a[low];    // 选择枢轴
        
        // 基于枢轴对数据进行划分
        while(low < high)    
        {
            while(low < high && a[high] >= pivotkey)
                --high;
            if(low != high)
                a[low] = a[high];
                
            while(low < high && a[low] <= pivotkey)
                ++low;
            if(low != high)
                a[high] = a[low];
        }  // end of while(low < high)
        
        a[low] = pivotkey;
        
        // 如果枢轴是第n/2小元素，划分成功
        if(low == k - 1)    
            flag = 0;
        else    // 否则继续划分
        {
            if(low < k - 1)
            {
                low0 = ++low;
                high = high0;
            }
            else
            {
                high0 = --high;
                low = low0;
            }
        }
    }
    
    // 计算前半部分和后半部分的和
    for(i = 0; i < k; i++)
        s1 += a[i];
    for(i = k; i < n; i++)
        s2 += a[i];
        
    return s2 - s1;
}

(3) 算法的平均时间复杂度和空间复杂度 (2 分)
本参考答案给出的算法平均时间复杂度是 O (n)，空间复杂度是 O (1)。

(1) 第一问。每传送一个 ASCII字符，需要传输的位数有1位起始位、7位数据位（ASCII 字符占7 位）、1位奇校验位和1位停止位，故总位数为1+7+1+1=10。

第二问。从D接收启动命令到字符送入I/O端口需要0.5ms，I/O端口每秒钟最多可接收1×1s/0.5ms=2000个字符。

(2) 第一问。一个字符传送时间包括：设备D将字符送I/O端口的时间、中断响应时间和中断服务程序前15条指令的执行时间。CPU主频为50MHz，CPU时钟周期为 1/(50MHz)=20ns，设备D将字符送I/O端口的时间为0.5ms/20ns=25000个时钟周期，中断响应需10个时钟周期，CPI为4，中断服务程序前15条指令的执行时间为15×4=60个时钟周期，综上，一个字符的传送时间大约为25000+10+60=25070个时钟周期。完成1000个字符传送所需时间大约为1000×25070=25070000个时钟周期。

第二问。CPU用于一次中断的时间包括：中断响应时间和中断服务程序的执行时间。中断响应需10个时钟周期，中断服务程序共有20条指令，CPI为4，中断服务程序的执行时间为20×4=80个时钟周期，I/O端口每收到一个字符申请一次中断，CPU用于从D读取1000个字符的时间大约为1000×(10+80)=90000= 9×10^4 个时钟周期。

第三问。

参考答案一：

在中断响应阶段中，CPU主要完成以下操作：

①确定中断源：向中断源查询电路发出中断响应信号INTA，去读取当前最高优先权的中断源编码。

②关中断：将中断允许触发器IE清0，暂时不再响应任何中断请求。

③保护程序断点：将中断执行的指令地址，即程序计数器PC的内容，推入堆栈保护起来，以便在中断服务完毕，返回到中断点，继续执行被中断的程序。

④转至相应的中断服务程序入口：根据从中断查询电路获取的中断源编码，转至相应的中断服务程序入口。

参考答案二：

在中断响应阶段中，CPU主要完成以下操作：

①关中断。CPU进入中断周期，意味着CPU响应了某个中断源的请求，为了确保CPU响应后所需做的一系列操作不至于又受到新的中断请求的干扰，在中断周期内必须自动关中断，以禁止CPU再次响应新的中断请求。

②保护程序断点：将当前程序计数器 (PC) 的内容（程序断点）保存到存储器中，以便在中断服务完毕，返回到中断点，继续执行被中断的程序。

③引出中断服务程序。取出中断服务程序的入口地址（中断向量）并传送给程序计数器 (PC)。

(1) 虚拟地址格式为 ，计算机按字节编址，页大小为8KB= 2^13B，页内地址占13位，虚拟地址为32位，虚页号A占32-13=19位。

TLB将虚页号映射到页框号，标记B位数等于虚页号A位数，即19位。

物理地址格式为 ，计算机按字节编址，页大小为8KB= 2^13B，页内地址D占13位，物理地址为24位，页框号C占24-13=11位。

Cache组相联格式为 ，计算机按字节编址，主存块大小为64B= 2^6B，块内地址G占6位。数据区大小为64KB，Cache有64KB/64B= 2^10行，Cache按2路组相联方式组织，有 2^10/2=2^9 组，组号F占9位，物理地址为24位，主存字块标记E占24-6-9=9位。

综上，A占19位，B占19位，C占11位，D占13位，E占9位，F占9位，G占6位。

TLB中标记字段B的内容是虚页号，表示该TLB项对应哪个虚页的页表项。

(2) 物理地址载入Cache后，对于任意Cache格式，地址均可划分为 ，本题Cache采用组相联格式，  ，所以  。块号4099=4096+3= ，因此，所映射的Cache组号为0 0000 0011B=3。标记H为主存字块标记，块号4099对应的H字段内容为0 0000 1000B。

(3) Cache缺失处理的时间开销相对缺页处理的时间开销要小很多。因为Cache缺失只要访问主存，缺页处理需要访问磁盘，计算机访问主存的速度要比访问磁盘的速度快很多。

(4) 因为采用直写策略时需要同时写快速存储器和慢速存储器，而写磁盘比写主存慢得多，所以应该使写磁盘的次数尽量少。在Cache-主存层次，Cache可以采用直写策略，而在主存-外存（磁盘）层次，修改页面内容时总是采用回写策略。

(1) nice为静态优先数，若采用nice作为进程优先数，对于就绪队列中某一个尚未运行的nice值较大的进程，若有比该进程nice值小的进程源源不断进入就绪队列，则该进程将一直无法运行，从而导致饥饿现象。

注：在操作系统中，nice 值并不是表示优先级，而是表示优先级的修正数值，它与优先级 (priority) 的关系是这样的：priority(new) = priority(old) + nice。内核中，priority 的范围是 0~139，值越低，优先级越高，其中前面的 0~99 范围是提供给实时任务使用的，而 nice 值是映射到 100~139，这个范围是提供给普通任务用的，因此 nice 值调整的是普通任务的优先级。

nice 值越小，优先数就越小，任务的优先级就越高。

(2) 为了避免产生饥饿现象，需要将静态优先数调整为动态优先数，引入运行时间cpuTime和等待时间waitTime，根据高响应比优先调度算法，响应比=(等待时间＋要求服务时间)/要求服务时间，waitTime视为等待时间，cpuTime视为要求服务时间。

• cpuTime越大，响应比越小，优先级越低，优先数越大，采用乘法权重，设权值为k1 > 0，可以增加k1 · cpuTime。
• waitTime越大，响应比越大，优先级越高，优先数越小，采用乘法权重，设权值为k2 > 0，可以减少k2 · waitTime。

综上所述，优先数 = nice + k1 · cpuTime - k2 · waitTime，其中k1表示cpuTime的权重，k2表示waitTime的权重，k1、k2均为大于0的常数。

waitTime的使用保证若waitTime越大，则优先数越小，从而避免出现饥饿现象。

(1) dir文件夹中有dir1，dir1的第一个簇号为48，所以dir目录文件中有目录项<dir1, 48>。dir1文件夹中有file1和file2，file1的第一个簇号为100，file2的第一个簇号为200，所以dir1目录文件中有目录项<file1, 100>和<file2, 200>。dir和dir1中的内容分别如下表所示。

(2) 第一问。每个簇号占2B=16bit，最多表示 2^16 个簇号，若FAT的每个表项仅存放簇号，则FAT的最大长度为 2^16 ×2B=128KB。

第二问。最多有 2^16 个簇，簇大小为4KB，该文件系统支持的文件长度最大是 2^16 ×4KB=256MB。

(3) 由于磁盘文件系统使用链接分配方式组织文件，所以FAT的每个表项中会存放下一个簇号，file1的簇号106存放在FAT的100号表项中，簇号108存放在FAT的106号表项中。

(4) 仅FAT和dir目录文件已读入内存，需要将文件dir/dir1/file1的第5000个字节读入内存。

第一步：根据dir目录文件，访问目录文件dir1所在的48号簇。

第二步：簇大小为4KB，file1的第5000个字节位于第 ⌈5000B/4KB⌉=2 个簇中，file1第2个簇的簇号为106。首先根据dir1目录文件找到file1第一个簇的簇号100，然后根据FAT，100号表项存放簇号106，所以这一步仅需要访问文件file1的106号簇。

注：偏移量、下标、索引、页号、页框号、行号、组号、位号、簇号、磁盘块号、主存块号等一般从0开始计数。特别地，在没有计数范围说明的情况下，第几个一般从1开始计数，即第一个、第二个、第三个……