函数的主体为while循环，sum +=++i 的时间复杂度为 O(1) ，所以函数运行时间与while循环迭代次数有关。

方法一：精确计算

本题选B。

方法二：渐近计算

本题选B。

C 
（1）错误。阶乘，尾递归都能很好的转换为普通循环
（3）错误。出现顺序不能确定
（4）错误。只允许在一端进行操作

I. 将递归改写成非递归有很多种方式，可以用数组，栈，散列表等等，并非必须使用栈，比如经典的斐波那契数列问题，可以用借助数组用动态规划实现，进一步可以用滚动数组优化，最后只需要3个变量即可实现。I错误。

II. 这里利用了栈先进后出的特性，例如函数A中执行过程中嵌套了函数B（也可以是自身），那么这个时候先要把函数A中的一些变量记录下来，就是压入栈中，然后再调用函数B，等函数B执行完毕返回后，回到函数A继续执行，此时将栈中保存的函数A的变量弹出。II正确。

Ⅲ．入栈次序，出栈序列有卡特兰数种，并不唯一，所以无法确定。Ⅲ错误。

Ⅳ．栈是一种受限的线性表，只允许在其一端进行操作。Ⅳ错误。

综上，Ⅰ、Ⅲ、Ⅳ错误。

本题选C。

解答：

关于图的存储结构，我们学过邻接矩阵、邻接表、十字链表和邻接多重表。

这边要求压缩稀疏矩阵，所以建议使用 O(|V|+|E|) 的存储结构存储， O(|V|^2) 空间复杂度的邻接矩阵排除，剩选项A和C，十字链表空间复杂度为 O(|V|+|E|) ，正确。剩下的两个概念三元组表和二叉链表在图的存储结构中我们并没有接触过，但是我们可以排除二叉链表，二叉链表就是有两个指针的链表啊，不就是二叉树吗？树是图的一种特例，图的存储结构能存储树，但树的存储结构不能存储图，排除选项C，只剩选项A了。

三元组表的结点存储了行row、列col、值value三种信息，即两个顶点和边权，是主要用来存储稀疏矩阵的一种数据结构。也就是三元组表存储系数矩阵的空间复杂度为 O(|V|+|E|) ，正确。

二叉链表又名左孩子右兄弟表示法，可用于表示树或森林。

本题选A。

方法一：取交集

前序遍历为“根左右”，中序遍历为“左根右”，非空二叉树的先序序列与中序序列相同，取交集，都为“根右”，所以只有右子树。B正确。非叶结点只有右子树是一棵非空二叉树的先序序列与中序序列相同的充分必要条件。但非叶结点的度均为1是一棵非空二叉树的先序序列与中序序列相同的必要不充分条件。

本题选B。

方法二：构造二叉树

这里第一步先构造二叉树，本人拓展一下给出以下结论：

• 已知某二叉树的前序遍历序列和中序遍历序列，能确定唯一的二叉树。
• 已知某二叉树的后序遍历序列和中序遍历序列，能确定唯一的二叉树。
• 已知某二叉树的层序遍历序列和中序遍历序列，能确定唯一的二叉树。

已知二叉树的前序遍历序列与中序遍历序列相同。我们可以构造出二叉树。

前序遍历序列和中序遍历序列均为a, b, c。

所有非叶结点只有右子树。B正确。非叶结点只有右子树是一棵非空二叉树的先序序列与中序序列相同的充分必要条件。但非叶结点的度均为1是一棵非空二叉树的先序序列与中序序列相同的必要不充分条件。

本题选B。

B

方法一：模拟

后序序列是先左子树，接着右子树，最后父结点，递归进行。根结点左子树的叶结点首先被访问，它是e。接下来是它的父结点a，然后是a的父结点c。接着访问根结点的右子树。它的叶结点b首先被访问，然后是b的父结点d，再者是d的父结点g。最后是根结点f。因此d与a同层，B正确。

本题选B。

方法二：环线法

按照箭头标记填入序列。

本题选B。

解答：

方法一：直接分割序列

哈夫曼编码是前缀编码，各个编码的前缀各不相同，因此直接拿编码序列与哈夫曼编码一一比对即可。序列可分割为0100 011 001 001 011 11 0101，译码结果是 a f e e f g d，D正确。

本题选D。

方法二：构造出哈夫曼树分割序列

当然，也可以构造出哈夫曼树，每次从根结点走到叶结点，输出对应字符。

序列可分割为0100 011 001 001 011 11 0101，译码结果是 a f e e f g d，D正确。

本题选D。

无向图边数的两倍等于各顶点度数的总和。由于其他顶点的度均小于3，所以它们的度至多为2，可列出方程：

解得：

本题选B。

折半查找判定树实际上是一棵二叉搜索树，它的中序遍历序列是一个单调序列。

折半查找即二分查找，假设搜索的有序数组为 A[1:n] ，目标元素为 target，二分查找伪代码如下：

向下取整：

BINARY-SERACH(A, n, target){
    left = 1
    right = n;
    while(left <= right) {
        mid = ⌊(left + right) / 2⌋
        if (A[mid] == target) { 
            return mid; 
        } else if(nums[mid] < target) { 
            left = mid + 1; 
        } else { 
            right = mid - 1; 
        }
    }
    error "not found"
}

向上取整：

BINARY-SERACH(A, n, target){
    left = 1
    right = n;
    while(left <= right) {
        mid = ⌈(left + right) / 2⌉
        if (A[mid] == target) { 
            return mid; 
        } else if(nums[mid] < target) { 
            left = mid + 1; 
        } else { 
            right = mid - 1; 
        }
    }
    error "not found"
}

方法一：构造

A选项二叉树10个结点。

B选项二叉树11个结点。

C选项二叉树9个结点。

D选项二叉树10个结点。

我们尝试构造一棵含10个元素的折半查找判定树，每个结点存储数组元素下标。

设有长度为10的升序序列 A[1:10] ，即满足 a1<a2<a3<a4<a5<a6<a7<a8<a9<a10 。为了方便讨论，考虑下标序列 {1,2,3,4,5,6,7,8,9,10} 。

折半查找规则要统一，要不全部折半向下取整，要不全部折半向上取整。下面分情况讨论。

折半向下取整：

根结点元素下标为⌊(1 + 10) / 2⌋ = 5，下标序列 {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}分为{1, 2, 3, 4}, {5}, {6, 7, 8, 9, 10}。对于左子树，根结点元素下标为⌊(1 + 4) / 2⌋ = 2。{1, 2, 3, 4}可以分为{1}, {2}, {3, 4}。对于右子树，根结点元素下标为⌊(6 + 10) / 2⌋ = 8。{6, 7, 8, 9, 10}可以分为{6, 7}, {8}, {9, 10}。递归执行上述过程直到折半查找判定树构造完成。

折半向上取整：

根结点元素下标为⌈(1 + 10) / 2⌉ = 6，下标序列{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}分为{1, 2, 3, 4, 5}, {6}, {7, 8, 9, 10}。对于左子树，根结点元素下标为⌈(1 + 5) / 2⌉ = 3。{1, 2, 3, 4, 5}可以分为{1, 2}, {3}, {4, 5}。对于右子树，根结点元素下标为⌈(7 + 10) / 2⌉ = 9。{7, 8, 9, 10}可以分为{7, 8}, {9}, {10}。递归执行上述过程直到折半查找判定树构造完成。

此折半查找判定树与选项A中的二叉树一致。

本题选A。

方法二：代入选项

考虑升序序列 A[1:n] ，其中 n 为对应二叉搜索树的结点个数，可以在树结点上依次填上相应的元素下标，符合折半查找规则的二叉树树即为所求。

折半查找规则要统一，要不全部折半向下取整，要不全部折半向上取整。

B选项中，观察以元素下标 2 为根结点的子树，二分查找区间为 [1, 2]，⌈(1 + 2) / 2⌉ = 2；观察以元素下标 7 为根结点的子树，二分查找区间为 [7, 8]，⌊(7 + 8) / 2⌋ = 7，错误。

C选项，观察以元素下标 2 为根结点的子树，二分查找区间为 [1, 4]，⌊(1 + 4) / 2⌋ = 2；观察以元素下标 8 为根结点的子树，二分查找区间为 [6, 9]，⌈(6 + 9) / 2⌉ = 8，错误。

D选项，观察以元素下标 7 为根结点的子树，二分查找区间为 [6, 7]，⌈(6 + 7) / 2⌉ = 7；观察以元素下标 5 为根结点的子树，二分查找区间为 [1, 10]，⌊(1 + 10) / 2⌋ = 5，错误。

只有A选项符合折半查找规则，正确。

本题选A。

方法三：确定性

本题考察算法的确定性。

折半查找规则要统一，要不全部折半向下取整，要不全部折半向上取整。也就是只有一个孩子结点的子树孩子结点固定在一侧，可以断言：下面两个命题必然有一个为真。

1. 对于任意一个结点，其左子树结点个数大于或等于其右子树结点个数。
2. 对于任意一个结点，其左子树结点个数小于或等于其右子树结点个数。

命题1对应折半向上取整的情况，命题2对应折半向下取整的情况。

观察最下面一层子树，只有选项A和D符合要求，均满足命题1，继续扩大范围观察，观察根结点所在子树，即整棵树，发现D中出现了右子树结点比左子树结点多的情况，违反命题1，排除。只有A符合要求。

本题选A。

B

 树是B树的一种变形形式。 B+ 树上的叶结点存储关键字以及相应记录的指针，叶结点中将关键字按大小顺序排列，并且相邻叶结点按大小顺序相互链接起来。所有分支结点（可视为索引的索引）中仅包含它的各个子结点（即下一级索引块）中关键字的最大值及指向其子结点的指针。

B+ 树支持两种查找运算：一种是从最小关键字开始的顺序查找，另一种是从根结点开始的多路查找。

在搜索树中查找关键字的时间复杂度与树高 ℎ 有关为 O(ℎ)=O(log⁡n) ，结点越茂盛，树高越低，搜索越快。所以 B+ 树和B树比二叉搜索树更适合运用于数据量很大的系统。对于文件系统， B+ 树相比B树结构更加合理，功能更加强大，适合用于数据库系统。

本题选B。

本题将归并排序和插入排序进行了对比。

归并排序的程序代码比插入排序的程序代码更长。1错误。

归并排序的平均时间复杂度为 O(nlog⁡n) ，插入排序的平均时间复杂度为 O(n^2) 。3正确。

归并排序的空间复杂度为 O(n) ，插入排序的空间复杂度为 O(1) 。2错误。

本题选B。

能够将顺序存储的顺序表修改为链式存储的顺序表进行同样排序的算法有插入排序、选择排序、冒泡排序、归并排序，时间复杂度没有变化。所以1、2、3正确。

希尔排序和堆排序都利用了顺序存储的随机访问特性，而链式存储不支持这种性质，所以时间复杂度会增加，4、5错误。

本题选D。

本题为小学应用题，执行时间 = 指令条数 × CPI × 时钟周期。

由题意，计算机M1主频 f1=1.5GHz ，时钟周期 T1=1/f1 ，平均CPI CPI1=2 。计算机M2主频 f2=1.2GHz ，时钟周期 T2=1/f2 ，平均CPI CPI2=1 。

设程序P的指令数为 n ，则程序P在M1和M2上运行时间的比值是  。

本题选C。

该计算机主存由4个64M×8位的DRAM芯片采用交叉编址方式构成，即4体低位交叉编址，低log 4 = 2位为模块编号，即4个模块编号为0, 1, 2, 3，二进制编号为00B, 01B, 10B, 11B。x的数据类型为double，占64位，8个字节，主存按字节编址，所以x占8个地址单元。x的主存地址为804 001AH=1000 0000 0100 0000 0000 0001 1010B，低2位为10B，也就是x从编号为2的模块开始存储。可以画出x的存储布局如下。

存储器总线为32位，每个模块占8位，4个模块正好占32位，每次可以按行存取，并行启动4个模块，主存每次最多读写32位数据，满足要求。x的内容存储在3行中，所以需要执行3次主存读写数据，每次需要一个存储周期，总共需要3个存储周期。

本题选C。

时间局部性指的是程序在某个时间点访问的数据或指令很可能在未来的某个时间点再次被访问。换句话说，如果程序在某个时刻访问了一条指令或数据，那么在接下来的一段时间内，程序可能会再次访问相同的指令或数据。这种局部性特性可以通过缓存来提高程序的执行效率。缓存将最近被访问过的数据或指令保存在高速存储器中，以便更快地满足程序的访问需求。

空间局部性指的是程序在某个时间点访问的数据或指令的附近地址上的数据或指令也很可能在接下来的一段时间内被访问。换句话说，如果程序在某个时刻访问了特定的数据或指令，那么在其附近的地址上的数据或指令也很可能在接下来的访问中被访问到。这种局部性特性可以通过预取和数据块传输来提高程序的访问效率。预取将紧邻的数据或指令提前加载到高速缓存中，而数据块传输则是将一块数据同时传输到高速缓存以满足未来的访问。

for循环具有时间局部性，每次迭代调用的指令序列相同，所以第一次迭代的指令在第二次迭代中将再次被访问。每次迭代调用的部分数据相同，分析代码可知，外层for循环每次迭代都会访问a[0]且会访问上一次迭代访问过的元素。

数组占用一段连续的内存区域，所以相邻的数组元素大概率在一个块中，根据内层for循环的代码，可知程序依次访问a[0], a[1], …, a[i]，符合空间局部性的性质。

综上，该C语言程序段时间局部性和空间局部性皆有。

本题选A。

相对寻址以PC为基地址，以指令中的地址为偏移量确定有效地址。A错误。

寄存器寻址则是在指令中指出需要使用的寄存器。B错误。

直接寻址是在指令的地址字段直接指出操作数的有效地址。C错误。

在变址操作时，将计算机指令中的地址与变址寄存器中的地址相加，得到有效地址。在访问数组元素时，指令提供数组首地址，由变址寄存器来定位数据中的各元素。所以它最适合按下标顺序访问一维数组元素。D正确。

本题选D。

答案解析：A，三地址指令有29条，所以需要操作码5位，剩余32-29=3条，提供给二地址指令使用，而二地址比三地址指令多出6位，则可以表示3× 2 6 \times 2^6×2 
6
 =192条>107条，所以至少需要3 × 6 + 5 = 23 3\times 6+5=233×6+5=23条，而指令字长应为8的倍数，所以指令字长至少应该是24条。
 

超标量流水线是指在CUP中有一条以上的流水线，并且每个时钟周期内可以完成一条以上的指令，其实质是以空间换时间。

超标量流水线不影响流水线功能段的处理时间。I错误。

超标量流水线可以将多条可并行执行的指令并行执行。II正确。

超标量流水线不能调整指令的执行顺序，因此通过编译优化技术，把可并行执行的指令搭配起来，提高并行性。III正确。

本题选C。

主存储器就是我们通常说的主存，在CPU外，存储指令和数据，由RAM和ROM实现。控制存储器用来存放实现指令系统的所有微指令，是一种只读型存储器，机器运行时只读不写，在CPU的控制器内。CS按照微指令的地址访问。B错误。

本题选B。

生成控制信号的控制部件负责根据当前指令的操作码生成相应的控制信号，用于指导数据通路的操作。

算术逻辑运算部件（ALU）用于执行指令中的算术和逻辑运算。

通用寄存器组用于存储程序执行过程中的数据，供指令使用和保存中间结果。指令寄存器（IR）存储当前正在执行的指令，供指令解码和执行。

组合逻辑电路用于执行组合逻辑功能，它根据输入的信号立即给出相应的输出。在指令流水线中，组合逻辑电路通常用于执行指令解码、操作控制和数据选择等功能。时序逻辑电路则与时间相关，根据时钟信号和状态信息来确定输出。它用于处理与时序相关的操作和状态转换，如时钟同步、状态存储和时序控制等。在指令流水线中，时序逻辑电路用于实现指令流水线各个阶段的时序控制和状态转换。通过组合逻辑电路和时序逻辑电路的组合，指令流水线数据通路能够实现指令的流水线化执行，提高计算机的指令执行效率。

五阶段流水线可分为取指(IF)、译码/取数(ID)、执行(EXE)、存储器读(MEM)、写回(WriteBack)。数字系统中，各个子系统通过数据总线连接形成的数据传送路径称为数据通路，包括程序计数器、算术逻辑运算部件、通用寄存器组、取指部件等，不包括控制部件。B、C、D正确，A错误。

本题选A。

多总线结构用速率高的总线连接高速设备用速率低的总线连接低速设备。一般来说，CPU 是计算机的核心，是计算机中速度最快的设备之一。A正确。

突发传送方式把多个数据单元作为一个独立传输处理，从而最大化设备的吞吐量。现实中一般用支待突发传送方式的总线提高存储器的读写效率。B正确。

各总线通过桥接器相连，后者起流量交换作用。C正确。

PCI-Express (Peripheral Component Interconnect Express) 是一种高速串行总线标准，广泛用于计算机系统中连接各种外部设备和扩展卡。PCI-Express总线的设计旨在提供高带宽和低延迟的数据传输，适用于多种应用领域，包括图形显示卡、网络适配器、存储控制器、声卡和其他I/O设备。D错误。

PCI-Express×16 (PCIe×16) 是PCI-Express总线规范中的一个插槽类型，用于连接高性能显卡、图形加速器和其他需要更大带宽的扩展卡。PCIe×16插槽提供了16个差分信号对，用于数据传输，每个差分信号对包括一个发送和一个接收信号。这种插槽设计可以支持更高的数据传输速率和带宽需求，以满足现代图形处理等高性能计算需求。

本题选D。

I/O接口的基本组成如下图所示。

I/O接口是CPU与设备之间的交接面，I/O端口是I/O接口电路中可以被CPU直接访问的寄存器。由于主机和I/O设备的工作方式和工作速度有很大差异，I/O端口就应运而生。在执行一条指令时，CPU使用地址总线选择所请求的I/O端口，使用数据总线在CPU寄存器和端口之间传输数据。D正确。

本题选D。

多重中断系统在保护被中断进程现场时关中断，执行中断处理程序时开中断，B错误。

CPU一般在一条指令执行结束的阶段采样中断请求信号，查看是否存在中断请求，然后决定是否响应中断，A、D正确。

中断请求一般来自CPU以外的事件，异常一般发生在CPU内部，C正确。

本题选B。

系统在t=2时开始作业调度，此时已经到达的作业有J1、J2和J3。

先来先服务调度算法优先选择到达时刻早的作业，J1、J2和J3中J1到达时刻最早。若采用先来先服务调度算法，则选中J1。

短作业优先调度算法优先选择运行时间短的作业，J1、J2和J3中J3的运行时间最短。若采用短作业优先调度算法，则选中J3。

本题选D。

【答案】C

【解析】执行系统调用的过程如下：正在运行的进程先传递系统调用参数，然后由陷入（trap）指令负责将用户态转换为内核态，并将返回地址压入堆栈以备后用，接下来CPU执行相应的内核态服务程序，最后返回用户态。所以选项C 正确。

回收起始地址为60K、大小为140KB的分区后，起始地址为20K、和起始地址为200K的空闲分区合并为一个40KB+140KB+200KB=380KB的新空闲分区，如下图所示：

此时系统中还剩3个空闲分区，空闲分区信息如下表所示。

空闲分区链第一个分区的起始地址和大小分别是500K、80KB。

本题选B。

对于一个文件系统，文件的磁盘空间是以簇 (cluster) 为单位进行分配的。若一个文件的大小为1026B，系统的簇大小为1KB，则系统分配给该文件的簇的数量是 ⌈1026B/1KB⌉=2，磁盘空间大小是1KB×2=2KB=2048B。

本题选D。

A正确。因为每个进程只能在一个时间片内执行一段时间，然后切换到下一个进程。这会增加系统开销，因为每次进程切换都需要一定的处理时间。因此，时间片越短，进程切换的次数越多，系统开销也越大。

B错误。当前进程的时间片用完后，并不一定会导致该进程状态由执行态变为阻塞态。在基于时间片的进程调度中，当一个进程的时间片用完后，它的状态会变为就绪态，然后调度程序会选择另一个就绪态的进程来执行。进程的状态从执行态变为阻塞态通常是由于等待某些资源（如 I/O 操作）而无法继续执行。

C正确。进程的时间片不会自己减少，是由时钟中断程序来控制进程的时间片的减少。时钟中断是指每隔一段相同的时间，都会发出一个中断信号， CPU接受到中断信号后触发内核中相应的中断处理程序。时钟中断通常由计算机内部的硬件计时器生成。计时器以固定的时间间隔发送一个中断请求给处理器。这个时间间隔通常是几毫秒，根据操作系统和硬件的不同而有所不同。例如，在Windows系统中，时钟中断的频率为每秒1000次，而在Linux系统中，它通常为每秒100或1000次。

D正确。时间片的大小会影响系统的响应速度和吞吐量。更短的时间片可以更频繁地切换进程，提高对交互性任务的响应时间，但也会增加系统开销。同时，进程数量的增加也会影响时间片的分配情况。因此，影响时间片大小的主要因素包括响应时间、系统开销和进程数量等。

本题选B。

【答案】D

【解析】多道程序系统通过组织作业（编码或数据）使 CPU总有一个作业可执行，从而提高了 CPU的利用率、系统吞吐量和I/O设备利用率，I、III、IV 是优点。但系统要付出额外的开销来组织作业和切换作业，11错误。所以选D。

磁盘的格式化分为物理格式化和逻辑格式化。

物理格式化又称低级格式化，是对磁盘的物理表面进行处理，在磁盘上建立标准的磁盘记录格式，划分磁道和扇区，记录专用信息，如磁道标志(每个磁道一个)、扇区标志（每个扇区一个）和保证所记录的信息是准确的循环冗余校验 (CRC) 位。

逻辑格式化又称高级格式化，是在磁盘上建立一个系统存储区域，包括引导记录区、文件目录区FCT、文件分配表FAT。磁盘文件的存贮是以簇为单位，簇在磁盘上文件并不是连续存储的，而是由FAT表来保存文件存放簇号顺序。由目录项的起始簇号指出该文件在FAT中的第1个簇号，在这个簇号单元里，记载的是该文件下一簇的簇号，依次类推直至该文件的最后一个簇号。这样通过“簇号链”将文件的存储空间链接在一起。

I错误。对磁盘进行分区即将磁盘划分为一个或多个柱面组成的分区，如C盘、D盘等。分区完成后才能进行逻辑格式化。

II正确。建立文件系统的根目录是逻辑格式化的工作。

III错误。确定磁盘扇区校验码所占位数是物理格式化的工作。

IV正确。对保存空闲磁盘块信息的数据结构进行初始化是逻辑格式化的工作。

综上，仅Ⅱ、Ⅳ正确。

本题选B。

答案：D
可以把用户访问权限抽象为一个矩阵，行代表用户，列代表访问权限。这个矩阵有4行5列，1代表true，0代表false，所以需要20位，选D。

I错误。f1和f2的具有各自的读写指针，位置不一定相同。

II和III正确。当文件f1和f2是硬链接关系时，它们共享同一个索引节点，但是拥有各自独立的文件描述符。

综上，仅Ⅱ、Ⅲ正确。

本题选B。

正确的执行顺序是：

第一步：初始化DMA控制器并启动磁盘，这些操作通常由设备驱动程序完成。

第二步：DMA控制器从磁盘传输一块数据到内存缓冲区。

第三步：在数据传输完成之后，DMA控制器发出中断请求，通知CPU数据已经准备好了。

第四步：执行“DMA结束”中断服务程序

综上，正确的执行顺序是②→③→①→④。

本题选B。

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

根据题目条件，应用层要发送 400B 的数据，每层在封装PDU时会引入 20B 的额外开销（除物理层和应用层）。

除了应用层和物理层外，共有 5 个中间层，每个中间层的封装额外开销为 20B。所以，总的封装额外开销为 20 B × 5 = 100 B，总共需要发送的数据量为 400 B + 100 B = 500B。

本题选 A。

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

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

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

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

有  ，即 ，将 SNR = 30 dB 代入，得，再将 代入香农公式，解得  。

根据奈式准则，无噪声情况下可获得的最大数据传输速率为

C=2W （单位：波特 (Baud)，即码元/秒）

其中W 为带宽，单位 Hz。每个码元可携带比特数量为，其中 M 为调制技术中可利用的符号数量。即

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

若信道在无噪声情况下的极限数据传输速率不小于信噪比为30dB条件下的极限数据传输速率，则 ，化简得  ， 取。

本题选 D。

本题考察IEEE 802.11数据帧的格式。

IEEE 802.11数据帧的格式如下：

802.11数据帧最特殊的地方就是有四个地址字段。地址4用于自组网络。本题考察前三个地址。这三个地址的内容取决于帧控制字段中的“去往 AP”（发送到接入点）和“来自 AP”（从接入点发出）这两个字段的数值。这两个子字段各占1为，合起来有4种组合，用于定义802.11帧中的几个地址字段的含义。

下表给出了802.11帧的地址字段最常用的两种情况（在右基础设施的网络中只使用前三种地址，而不使用仅在自组移动网络最后使用的地址4）。

根据题意，数据帧F是去往AP的，因此，F中去往AP控制位的值为1，来自AP控制位的值为0，地址1为AP地址00-12-34-56-78-9b，地址2为源MAC地址即主机H的MAC地址00-12-34-56-78-9a，由于802.11数据帧在数据链路层进行传输，源MAC地址和目的MAC地址逐段链路发生改变，要访问Internet，需要经过路由器R进行转发，因此地址3为目的MAC地址即路由器R的MAC地址00-12-34-56-78-9c。

本题选 B。

在IPv4的地址规划中，有一些特殊的IP地址分配。

下表给出了一般不使用的特殊IP地址

A 正确。0.0.0.0 是一种保留地址，表示在本网络上的本主机。只能作为源地址，不能作为目的地址。

B 错误。127.0.0.1 用作本地软件的环回测试地址，用于主机本身的测试和通信。既能作为源地址，也能作为目的地址。

C 错误。20.10.10.3 是一个普通地址，既能作为源地址，也能作为目的地址。

D 错误。255.255.255.255 是本网络上的广播地址，只在本网络上进行广播（各路由器均不转发）。只能作为目的地址，不能作为源地址。

本题选 A。

RIP (Routing Information Protocol) 使用UDP进行直接封装，使用的端口号为520。

OSPF (Open Shortest Path First) 使用IP进行直接封装，使用的协议号为89。

BGP 使用 TCP 进行直接封装，使用的协议号为179。

本题选 D。

网络21.3.0.0/16的网络号占16位，主机号占32-16=16位，要将该网络划分为128个规模相同的子网，子网号占 log2⁡128=7 位，从主机号中划分前 7 位为子网号，剩余16-7=9位为子网的主机号。每个子网地址空间包含的地址数为 29=512 ，从中排除一个主机号位全0的网络地址和一个主机号位全1的广播地址，剩余512-1-1=510就是每个子网可分配的最大IP地址个数。

本题选 C。

本题没有给出慢开始门限 ssthresh，默认一直使用慢开始算法。

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

慢开始算法

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

采用慢开始算法。

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

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

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

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

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

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

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

所以甲从连接建立成功至发送窗口达到32KB，需要经过5个RTT。RTT=5ms，5RTT=5×5ms=25ms。

本题选 A。

FTP (File Transfer Protocol) 是用于在网络上传输文件的标准网络协议。

FTP 连接分为主动模式和被动模式。

主动模式（由客户端发起）下，客户端的TCP临时端口与服务器的TCP 21端口建立控制连接。客户端的另一个TCP临时端口与服务器的TCP 20端口建立数据连接。

被动模式（由服务器发起）下，客户端的TCP临时端口与服务器的TCP 21端口建立控制连接。客户端的另一个TCP临时端口与服务器随机选择的TCP临时端口建立数据连接。

A 正确。FTP使用两个连接：一个用于控制（命令和响应），另一个用于数据传输。数据连接在每次数据传输完毕后会关闭。

B 正确。FTP中的控制连接在整个会话期间保持打开状态，直到用户结束会话。

C 错误。数据连接根据不同情况可以使用不同的端口。主动模式下，客户端的一个TCP临时端口与服务器的TCP 20端口建立数据连接。被动模式下，客户端的一个TCP临时端口与服务器随机选择的TCP临时端口建立数据连接。即便仅考虑主动模式，该选项中服务器和客户端的位置正好颠倒了。

D 正确。客户端的TCP临时端口与服务器的TCP 21端口建立控制连接。

本题选 C。

题目要求输出中缀表达式，对应表达式树（二叉树）的中序遍历序列。但本题难点在于要输出左右括号，所以也融合了二叉树的前序遍历和后序遍历，二叉树的前序遍历、中序遍历、后序遍历本质都是深度优先搜索。

深度优先搜索

递归遍历

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

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

typedef struct node{
    char data[10];   // 存储操作数或操作符
    struct node *left, *right;
}BTree;

void dfs(BTree* root) {
    if (root == NULL) return;
    if (root->left == NULL && root->right == NULL) {  // 如果只有一个数那么不需要加括号
        printf("%s", root->data);
    } else {
        printf("(");
        dfs(root->left);
        printf("%s", root->data);
        dfs(root->right);
        printf(")");
    }
}

void expressionTree(BTree* root) {
    if(root == NULL) return;
    dfs(root->left);
    printf("%s", root->data);
    dfs(root->right);
    return;
}

BTree *createBinaryTree(char a[][10], int n) {
    if (strcmp(a[0], "null") == 0) {
        return NULL;
    }
    int i = 0;
    BTree *root = (struct node*)malloc(sizeof(struct node));
    strcpy(root->data, a[i++]);
    root->left = NULL;
    root->right = NULL;
    struct node** que = (struct node**)malloc(sizeof(struct node*));
    int front = 0, rear = 0;
    BTree *curr = root;
    que[rear++] = curr;
    while (front < rear && i < n) {
        curr = que[front++];
        for (int j = 0; j < 2 && i < n; j++, i++) {
            if (strcmp(a[i], "null") != 0) {
                if (j == 0) {
                    curr->left = (struct node*)malloc(sizeof(struct node));
                    strcpy(curr->left->data, a[i]);
                    curr->left->left = NULL;
                    curr->left->right = NULL;
                    que[rear++] = curr->left;
                } else {
                    curr->right = (struct node*)malloc(sizeof(struct node));
                    strcpy(curr->right->data, a[i]);
                    curr->right->left = NULL;
                    curr->right->right = NULL;
                    que[rear++] = curr->right;
                }
            }
        }
    }
    return root;
}

int main() {
    char a[][10] = {"*", "+", "*", "a", "b", "c", "-", "null", "null", "null", "null", "null", "null", "null", "d"};
    expressionTree(createBinaryTree(a, 15));
    return 0;
}

复杂度分析

• 时间复杂度： O(n) ，其中 n 为二叉树的结点个数。二叉树的每个结点最多被访问三次，因此时间复杂度为 O(n) 。
• 空间复杂度： O(n) ，其中 n 为二叉树的结点个数。递归栈最深为 n ，因此需要额外的 O(n) 的空间。

⑴ Prim算法运用了贪心策略。

开始点集 S 和边集 A 为空，从一个任意的顶点开始，并将该顶点加入 S ，然后将距离点集 A 距离（代价）最小的顶点加入到点集 S 中，该带权边加入边集 A 中，直到点集 S 包含图中所有顶点为止。当算法终止时，由点集 S 和边集 A 构成的树就是最小生成树。

题目中给定从A开始， S 可以初始化为{A}。模拟步骤如下：

• S 中顶点为A，候选边为(A, B), (A, D), (A, E)，其中|(A, B)| = 6, |(A, D)| = 4, |(A, E)| = 5，选择(A, D)，D加入 S ，(A, D)加入 A 。
• S 中顶点为A, D，候选边为(A, B), (A, E), (D, E), (C, D)，其中|(A, B)| = 6, |(A, E)| = 5, |(D, E)| = 4, |(C, D)| = 6，选择(D, E)， E加入 S ，(D, E)加入 A 。
• S 中顶点为A, D, E，候选边为(A, B), (C, D), (C, E)，其中|(A, B)| = 6, |(C, D)| = 6, |(C, E)| = 5，选择(C, E)，C加入 S ，(C, E)加入 A 。
• S 中顶点为A, D, E, C，候选边为(A, B), (B, C)，其中|(A, B)| = 6, |(B, C)| = 4，选择(B, C)，B加入 S ，(B, C)加入 A 。

点集 S 包含图中所有顶点，此时由点集 S 和边集 A 构成的树就是最小生成树。

依次选出的边为：(A,D), (D,E), (C, E), (B, C)。

⑵ 图G的MST是唯一的，该MST包含了图中权值最小的4条边。

⑶ 如果任意的带权连通图的所有边的权值互不相同时，其MST是唯一的。该条件为MST是唯一的的充分不必要条件。

虽然f1和f2都是计算的是 f(n)=2^(n+1)−1 ，但是由于输入和输出数据类型的限制，实际输出结果可能有出入。

(1) 由于i和n是unsigned型，因此“i <= n-1”是无符号数比较。n=0时，n-1的机器数为全1，值是 2^32−1 ，为unisgned型可表示的最大数，条件“i <= n-1”恒为真，因此出现死循环。

若将i和n改为int类型，则不会出现死循环。因为“i <= n-1”是有符号数比较。n=0时，n-1的值是-1，当i = 0时条件“i <= n-1”为假，此时退出for循环。

(2) f1(23)与f2(23)的返回值相等。 。f1(23)为int类型，int占32位，没有溢出。f2(23)为float类型，float采用IEEE754单精度标准，float有1个符号位，8个指数位，23个尾数位，考虑小数点前面省略的1，float有24个有效数值位。阶码为 23+127=150=10010110B。所以两者返回值相等。

f1(23)为int类型，机器数是0000 0000 1111 1111 1111 1111 1111 1111B = 00FFFFFFH。

f2(23)为float类型，float采用IEEE754单精度标准，机器数是  =4B7FFFFFH。

(3) 当n=24时，  。f1(23)为int类型，int占32位，没有溢出。f2(23)为float类型，float采用IEEE754单精度标准，float有1个符号位，8个指数位，23个尾数位，考虑小数点前面省略的1，float有24个有效数值位。不满足25个有效数值位的要求，这里需要进行舍入，按0舍1入，f2(24)= 2^25 =33554432.0，比f1(24)= 2^25−1 =33554431大，即f1(24)和f2(24)返回值不相等。

(4) f(31)= 2^32−1 ，int表示范围为 −2^31∼2^31−1 ，溢出，f1(31)的二进制形式是32个1，C语言整型用补码表示，得到f1(31)的返回值为-1。因为 位f(n)= 且int型最大可表示数是符号位为0后面31个数值位全为1，即n+1=31，解得n=30，所以使f1(n)的返回值与f(n)相等的最大n值是30。

(5) 7F80 0000H=  ，阶码位全1，尾数位全0，表示无穷大，符号位为0，表示正无穷大，即 +∞ 。

当n=127时，  。表示为浮点数 ，括号内为需要舍入的部分，按0舍1入进行舍入后需要右规，阶码加1，得到 ，该浮点数表示 +∞ ，溢出。

当n=126时，  。表示为浮点数 ，括号内为需要舍入的部分，按0舍1入进行舍入后需要右规，阶码加1，得到  ，阶码11111110B达到IEEE754单精度格式表示的最大阶码。

综上，若使f2(n)的结果不溢出，则最大的n是126。

当 n = 24 时根据(1)的结果，f2(24)需要舍入。

当 n = 23 时， 。f2(23)为float类型，float采用IEEE754单精度标准，float有1个符号位，8个指数位，23个尾数位，考虑小数点前面省略的1，float有24个有效数值位。所以不需舍入，结果精确。

综上，若使f2(n)的结果精确（无舍入），则最大的n是23。

(1) M为CISC。观察题44图，指令1的内容为55H，指令长8位，指令20的内容为394DF4H，指令长24位，显然M的指令长短不一，不符合RISC指令系统特点。

(2) f1的机器代码占96B。因为f1的指令1所在的虚拟地址为00401020H，最后一条指令即指令35所在的虚拟地址为0040107FH，指令35的内容为C3H，指令长8位，计算机M按字节编址，指令35占一个地址单元。f1的机器指令代码占0040107FH+1H-00401020H=60H=96个地址单元，又因为计算机M按字节编址，所以f1的机器指令代码共占96字节。

(3) CF=1。cmp指令实现i与n-1的比较功能，i<=n-1，即i-(n-1)<0或i==(n-1)，i-(n-1)进行的是减法运算。在执行f1(0)过程中，n=0，当i=0时，i=00000000H，n-1=FFFFFFFFH。因此，当执行指令20时，在补码加/减运算器中执行00000000H-FFFFFFFFH，被减数和减数都视为无符号数，显然00000000H不够减FFFFFFFFH，要向最高位的更高一位借1，出现借位，所以CF=1。

(4) f2中不能用shl指令实现power*2。因为shl指令用来将一个整数的所有有效数位作为一个整体左移，但f2中的变量power是float型，按照IEEE754标准，其机器数中不包含最高有效数位，但包含了阶码部分，将其作为一个整体左移时并不能实现乘以2的功能，所以f2中不能用shl指令实现 power*2。

浮点数运算比整型运算要复杂，耗时也较长。

(1) 页目录号用干寻找页目录的表项，该表项包含页表的位置。页表索引用于寻找页表的表项，该表项包含页的位置。根据虚拟地址格式，页目录号占10位，页表索引占10位，共占10+10=20位。函数f1的代码段中所有指令的虚拟地址的高20位相同，均为00401H，因此f1的机器指令代码在同一页中，仅占用1页。

(2) push ebp指令的虚拟地址是00401020H= ，页目录号是00 0000 0001B=1，页表索引是000000 0001B=1，所以，取该指令时访问了页目录的第1（编号从0开始）个表项，在对应的页表中访问了第1（编号从0开始）个表项。

(3) 第一问。在执行 scanf() 的过程中，进程P因等待输入而从执行态变为阻塞态。输入结束时，P被中断处理程序唤醒，变为就绪态。P被调度程序调度，变为运行态。

第二问。中断控制方式是指在计算机系统中，通过中断机制来处理硬件设备或其他外部事件引起的中断请求。在中断控制方式下，计算机系统正常执行的程序可以被中断请求打断，转而执行中断服务程序来处理中断事件。在中断控制方式下，中断事件必须在内核态被处理，以保证对系统资源的管理和保护。所以CPU会进入内核态。

全局变量需要互斥访问。

thread1会访问全局变量x和y。

thread2会访问全局变量y和z。

thread3会访问全局变量y和z。

thread1和thread2对y的访问均为读操作，不会改变y的值，两者可以并行执行，因此

thread1和thread3需要互斥访问y，构造信号量semaphore mutex_y1＝1。

thread2和thread3需要互斥访问y，构造信号量semaphore mutex_y2＝1。

thread2和thread3需要互斥访问z，构造信号量semaphore mutex_z＝1。

综上，添加这些信号量后伪代码如下：

semaphore mutex_y1; // mutex_y1用于thread1和thread3对变量y的互斥访问
semaphore mutex_y2; // mutex-y2用于thread2和thread3对变量y的互斥访问
smeaphore mutex_z;  // mutex_z用于变量z的互斥访问

//复数的结构类型定义
typedef struct
{
    float a;
    float b;
}cnum;
cnum x,y,z; //全局变量

//计算两个复数之和
cnum add(cnum p, cnum q)
{
    cnum s;
    s.a=p.a+q.a;
    s.b=p.b+q.b;
    return s;
}

thread1
{
    cnum w;
    wait(mutex_y1);
    w=add(x, y);
    signal(mutex_y1);
    ...
}

thread2
{
    cnum w;
    wait(mutex_y2);
    wait(mutex_z);
    w=add(y, z);
    signal(mutex_z);
    signal(mutex_y2);
    ...
}

thread3
{
    cnum w;
    w.a=1;
    w.b=2;
    wait(mutex_z);
    z=add(z, w);
    signal(mutex_z);
    wait(mutex_y1);
    wait(mutex_y2);
    y=add(y, w);
    signal(mutex_y1);
    signal(mutex_y2);
    ...
}

采用后退 N 帧协议 (GBN)，发送窗口大小 WT 满足 1<WT≤2^n−1 ，接受窗口大小 WR 满足 WR=1 。其中 n 是帧序号的比特数。将 n=3 代入， 1<WT≤7 。发送窗口最大为7。可以有 2^3=8 个帧序号，即帧编号 0 ~ 7。

(1) 对于图(a)。

第一问。t0 时刻到 t1 时刻期间，根据乙发送最后一个帧 R3,3 ，表示乙希望甲发送3号帧，后退 N 帧协议 (GBN) 为累积确认，表明乙已经正确接收甲发送的0~2号帧，t0时刻到t时刻期间，甲方可以断定乙方已正确接收了3个数据帧。

第二问。此时甲已经发送 S0,0,S1,0,S2,0,S3,0 和 S4,1 ，甲发送的0~2号帧对应 S0,0,S1,0,S2,0 ，即正确接收的是 S0,0,S1,0,S2,0 。

(2) 对于图(a)。

第一问。甲的发送窗口最大为7，在 t1 时刻前，甲已经发送 S0,0,S1,0,S2,0,S3,0 和 S4,1共计5个数据帧，其中乙方已正确接收了3个数据帧，还剩2个数据帧情况未知，这2个帧序号依次是3、4，甲可以将发送窗口中的剩余7-2=5个帧全部发送出去，即从 t1 时刻起，甲方最多还可以发送5个数据帧，这5个帧序号依次是5、6、7、0、1。

如下图所示：

第二问。甲收到乙发来的 R0,1,R1,3,R3,3 ，即乙发来的0、1、3号帧，其中 S4,1 对 R0,1 进行了确认，即乙发来的0号帧已经被确认，剩余1、3号帧需要确认，因为后退 N 帧协议 (GBN) 为累积确认，3号帧没有按序发送，所以甲正确接收乙发来的1号帧，希望接收乙发来的2号帧，所以甲方在不出现超时且未收到乙方新的数据帧之前，可以发送的数据帧为 S5,2,S6,2,S7,2,S0,2,S1,2 。其中第一个帧是 S5,2 ，最后一个帧是 S1,2 。

(3) 对于图(b)。

第一问。在 t1 时刻前，甲已经发送 S0,0,S1,0,S2,0,S3,2 和 S4,2 共计5个数据帧，表明甲发送了0~5号数据帧，最后收到乙发送的 R2,2 数据帧，表明乙已经正确接收甲发送的0~1号数据帧，希望接收甲发送的2号数据帧，因为 S2,0 超时，需要发送出错帧及其之后的帧，即甲需要重传2~4号数据帧，即从 t1 时刻起，甲方在不出现新的超时且未收到乙方新的数据帧之前，需要重发3个数据帧。

第二问。 t1 时刻前，甲已经正确接收 R2,2 ，即乙发来的2号数据帧，希望接收乙发来的3号数据帧，甲需要重传2~4号数据帧，第一个需要重传的是2号数据帧，因此，甲重发的第一个帧是 S2,3 。

(4) 本题支持持续的双向数据传输。

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

甲发送一个数据帧的时延为 ，经过一个RTT = 0.96 ms，乙采用等长的数据帧进行捎带确认，接收乙发送一个数据帧的时延为 t2=t1=0.08 ms 。一个周期 T=t1+RTT+t2=1.12 ms 。

在一个周期内，甲可以将发送窗口中的7个数据帧全部发送出去，因此甲的最大信道利用率 。