计算机： 数据结构 、计算机组成原理 、操作系统 、计算机网络
$\text{A. } O(\log n)$ $\text{B. } O(n^{1/2})$ $\text{C. } O(n)$ $\text{D. } O(n\log n)$
函数的主体为while循环，sum +=++i 的时间复杂度为 O(1) ，所以函数运行时间与while循环迭代次数有关。
Ⅰ．采用非递归方式重写递归程序时必须使用栈
Ⅱ．函数调用时，系统要用栈保存必要的信息
Ⅲ．只要确定了入栈次序，即可确定出栈次序
Ⅳ．栈是一种受限的线性表，允许在其两端进行操作
C （1）错误。阶乘，尾递归都能很好的转换为普通循环 （3）错误。出现顺序不能确定 （4）错误。只允许在一端进行操作
I. 将递归改写成非递归有很多种方式，可以用数组，栈，散列表等等，并非必须使用栈，比如经典的斐波那契数列问题，可以用借助数组用动态规划实现，进一步可以用滚动数组优化，最后只需要3个变量即可实现。I错误。
II. 这里利用了栈先进后出的特性，例如函数A中执行过程中嵌套了函数B（也可以是自身），那么这个时候先要把函数A中的一些变量记录下来，就是压入栈中，然后再调用函数B，等函数B执行完毕返回后，回到函数A继续执行，此时将栈中保存的函数A的变量弹出。II正确。
Ⅲ．入栈次序，出栈序列有卡特兰数种，并不唯一，所以无法确定。Ⅲ错误。
Ⅳ．栈是一种受限的线性表，只允许在其一端进行操作。Ⅳ错误。
适用于压缩存储稀疏矩阵的两种存储结构是（ ）。
关于图的存储结构，我们学过邻接矩阵、邻接表、十字链表和邻接多重表。
这边要求压缩稀疏矩阵，所以建议使用 O(|V|+|E|) 的存储结构存储， O(|V|^2) 空间复杂度的邻接矩阵排除，剩选项A和C，十字链表空间复杂度为 O(|V|+|E|) ，正确。剩下的两个概念三元组表和二叉链表在图的存储结构中我们并没有接触过，但是我们可以排除二叉链表，二叉链表就是有两个指针的链表啊，不就是二叉树吗？树是图的一种特例，图的存储结构能存储树，但树的存储结构不能存储图，排除选项C，只剩选项A了。
三元组表的结点存储了行row、列col、值value三种信息，即两个顶点和边权，是主要用来存储稀疏矩阵的一种数据结构。也就是三元组表存储系数矩阵的空间复杂度为 O(|V|+|E|) ，正确。
二叉链表又名左孩子右兄弟表示法，可用于表示树或森林。
要使一棵非空二叉树的先序序列与中序序列相同，其所有非叶结点须满足的条件是（ ）。
前序遍历为“根左右”，中序遍历为“左根右”，非空二叉树的先序序列与中序序列相同，取交集，都为“根右”，所以只有右子树。B正确。非叶结点只有右子树是一棵非空二叉树的先序序列与中序序列相同的充分必要条件。但非叶结点的度均为1是一棵非空二叉树的先序序列与中序序列相同的必要不充分条件。
这里第一步先构造二叉树，本人拓展一下给出以下结论：
已知二叉树的前序遍历序列与中序遍历序列相同。我们可以构造出二叉树。
前序遍历序列和中序遍历序列均为a, b, c。
所有非叶结点只有右子树。B正确。非叶结点只有右子树是一棵非空二叉树的先序序列与中序序列相同的充分必要条件。但非叶结点的度均为1是一棵非空二叉树的先序序列与中序序列相同的必要不充分条件。
已知一棵二叉树的树形如下图所示，其后序序列为e, a, c, b, d, g, f，树中与结点a同层的结点是（ ）。
后序序列是先左子树，接着右子树，最后父结点，递归进行。根结点左子树的叶结点首先被访问，它是e。接下来是它的父结点a，然后是a的父结点c。接着访问根结点的右子树。它的叶结点b首先被访问，然后是b的父结点d，再者是d的父结点g。最后是根结点f。因此d与a同层，B正确。
已知字符集{a, b, c, d, e, f, g, h}，若各字符的哈夫曼编码依次是0100, 10, 0000, 0101, 001, 011, 11, 0001，则编码序列0100011001001011110101的译码结果是（ ）。
哈夫曼编码是前缀编码，各个编码的前缀各不相同，因此直接拿编码序列与哈夫曼编码一一比对即可。序列可分割为0100 011 001 001 011 11 0101，译码结果是 a f e e f g d，D正确。
当然，也可以构造出哈夫曼树，每次从根结点走到叶结点，输出对应字符。
序列可分割为0100 011 001 001 011 11 0101，译码结果是 a f e e f g d，D正确。
已知无向图G含有16条边，其中度为4的顶点个数为3，度为3的顶点个数为4，其他顶点的度均小于3。图G所含的顶点个数至少是（ ）。
A. 10 B. 11 C. 13 D. 15
无向边数的两倍等于各顶点度数的总和。由于其他顶点的度均小于3，所以它们的度至多为2，可列出方程: \( 4n_4 + 3n_3 + 2n_2 = 16 × 2 \) \( n_4 = 3 \) \( n_3 = 4 \) \( n = n_2 + n_3 + n_4 \) 解得: \( n_2 = 4 \) \( n = 11 \) 本题选B。
下列二叉树中，可能成为折半查找判定树（不含外部结点）的是（ ）。
折半查找判定树实际上是一棵二叉搜索树，它的中序遍历序列是一个单调序列。
折半查找即二分查找，假设搜索的有序数组为 A[1:n] ，目标元素为 target，二分查找伪代码如下：
我们尝试构造一棵含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[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，错误。
折半查找规则要统一，要不全部折半向下取整，要不全部折半向上取整。也就是只有一个孩子结点的子树孩子结点固定在一侧，可以断言：下面两个命题必然有一个为真。
命题1对应折半向上取整的情况，命题2对应折半向下取整的情况。
观察最下面一层子树，只有选项A和D符合要求，均满足命题1，继续扩大范围观察，观察根结点所在子树，即整棵树，发现D中出现了右子树结点比左子树结点多的情况，违反命题1，排除。只有A符合要求。
树是B树的一种变形形式。 B+ 树上的叶结点存储关键字以及相应记录的指针，叶结点中将关键字按大小顺序排列，并且相邻叶结点按大小顺序相互链接起来。所有分支结点（可视为索引的索引）中仅包含它的各个子结点（即下一级索引块）中关键字的最大值及指向其子结点的指针。
B+ 树支持两种查找运算：一种是从最小关键字开始的顺序查找，另一种是从根结点开始的多路查找。
在搜索树中查找关键字的时间复杂度与树高 ℎ 有关为 O(ℎ)=O(logn) ，结点越茂盛，树高越低，搜索越快。所以 B+ 树和B树比二叉搜索树更适合运用于数据量很大的系统。对于文件系统， B+ 树相比B树结构更加合理，功能更加强大，适合用于数据库系统。
在内部排序时，若选择了归并排序而没有选择插入排序，则可能的理由是（ ）。
A. 仅Ⅱ B. 仅Ⅲ C. 仅Ⅰ、Ⅱ D. 仅Ⅰ、Ⅲ
归并排序的程序代码比插入排序的程序代码更长。1错误。
归并排序的平均时间复杂度为 O(nlogn) ，插入排序的平均时间复杂度为 O(n^2) 。3正确。
归并排序的空间复杂度为 O(n) ，插入排序的空间复杂度为 O(1) 。2错误。
下列排序方法中，若将顺序存储更换为链式存储，则算法的时间效率会降低的是（ ）。
能够将顺序存储的顺序表修改为链式存储的顺序表进行同样排序的算法有插入排序、选择排序、冒泡排序、归并排序，时间复杂度没有变化。所以1、2、3正确。
希尔排序和堆排序都利用了顺序存储的随机访问特性，而链式存储不支持这种性质，所以时间复杂度会增加，4、5错误。
假定计算机M1和M2具有相同的指令集体系结构（ISA），主频分别为1.5GHz和1.2GHz。在M1和M2上运行某基准程序P，平均CPI分别为2和1，则程序P在M1和M2上运行时间的比值是（ ）。
A. 0.4 B. 0.625 C. 1.6 D. 2.5
本题为简单计算题，执行时间 = 指令条数 × CPI × 时钟周期。 由题意，计算机M1主频$f_1 = 1.5\text{GHz}$，时钟周期$T_1 = 1/f_1$，平均CPI $\text{CPI}_1 = 2$。 计算机M2主频$f_2 = 1.2\text{GHz}$，时钟周期$T_2 = 1/f_2$，平均CPI $\text{CPI}_2 = 1$。 设程序P的指令数为$n$，则程序P在M1和M2上运行时间的比值是 $\frac{n\cdot\text{CPI}_1\cdot T_1}{n\cdot\text{CPI}_2\cdot T_2} = \frac{\text{CPI}_1\cdot f_2}{\text{CPI}_2\cdot f_1} = \frac{2\cdot1.2\text{GHz}}{1\cdot1.5\text{GHz}} = 1.6$。 本题选C。
某计算机主存按字节编址，由4个64M×8位的DRAM芯片采用交叉编址方式构成，并与宽度为32位的存储器总线相连，主存每次最多读写32位数据。若double型变量x的主存地址为804001AH，则读取x需要的存储周期数是（ ）。
该计算机主存由$4$个$64\text{M}×8$位的DRAM芯片采用交叉编址方式构成，即4体低位交叉编址，低$\log_4 = 2$位为模块编号，即4个模块编号为$0,1,2,3$，二进制编号为$00\text{B},01\text{B},10\text{B},11\text{B}$。$x$的数据类型为$\text{double}$，占64位，8个字节，主存按字节编址，所以$x$占8个地址单元。$x$的主存地址为$804001\text{AH}=1000\ 0000\ 0100\ 0000\ 0000\ 0001\ 1010\text{B}$，低2位为$10\text{B}$，也就是$x$从编号为2的模块开始存储。可以画出$x$的存储布局如下：
\[ \begin{array}{|c|c|c|c|c|} \hline 模块编号 & 0 & 1 & 2 & 3 \\ \hline 行i地址单元 & — & — & 804001\text{AH} & 804001\text{BH} \\ \hline 行i+1地址单元 & 804001\text{CH} & 804001\text{DH} & 804001\text{EH} & 804001\text{FH} \\ \hline 行i+2地址单元 & 8040020\text{H} & 8040021\text{H} & — & — \\ \hline \end{array} \] 存储器总线为32位，每个模块占8位，4个模块正好占32位，每次可以按行存取，并行启动4个模块，主存每次最多读写32位数据，满足要求。$x$的内容存储在3行中，所以需要执行3次主存读写数据，每次需要一个存储周期，总共需要3个存储周期。
下列关于数组a的访问局部性的描述中，正确的是（ ）。
时间局部性指的是程序在某个时间点访问的数据或指令很可能在未来的某个时间点再次被访问。换句话说，如果程序在某个时刻访问了一条指令或数据，那么在接下来的一段时间内，程序可能会再次访问相同的指令或数据。这种局部性特性可以通过缓存来提高程序的执行效率。缓存将最近被访问过的数据或指令保存在高速存储器中，以便更快地满足程序的访问需求。
空间局部性指的是程序在某个时间点访问的数据或指令的附近地址上的数据或指令也很可能在接下来的一段时间内被访问。换句话说，如果程序在某个时刻访问了特定的数据或指令，那么在其附近的地址上的数据或指令也很可能在接下来的访问中被访问到。这种局部性特性可以通过预取和数据块传输来提高程序的访问效率。预取将紧邻的数据或指令提前加载到高速缓存中，而数据块传输则是将一块数据同时传输到高速缓存以满足未来的访问。
for循环具有时间局部性，每次迭代调用的指令序列相同，所以第一次迭代的指令在第二次迭代中将再次被访问。每次迭代调用的部分数据相同，分析代码可知，外层for循环每次迭代都会访问a[0]且会访问上一次迭代访问过的元素。
数组占用一段连续的内存区域，所以相邻的数组元素大概率在一个块中，根据内层for循环的代码，可知程序依次访问a[0], a[1], …, a[i]，符合空间局部性的性质。
综上，该C语言程序段时间局部性和空间局部性皆有。
下列寻址方式中，最适合按下标顺序访问一维数组元素的是
A．相对寻址 B．寄存器寻址 C．直接寻址 D．变址寻址
相对寻址以PC为基地址，以指令中的地址为偏移量确定有效地址。A错误。
寄存器寻址则是在指令中指出需要使用的寄存器。B错误。
直接寻址是在指令的地址字段直接指出操作数的有效地址。C错误。
在变址操作时，将计算机指令中的地址与变址寄存器中的地址相加，得到有效地址。在访问数组元素时，指令提供数组首地址，由变址寄存器来定位数据中的各元素。所以它最适合按下标顺序访问一维数组元素。D正确。
某计算机按字节编址，指令字长固定且只有两种指令格式，其中三地址指令29条，二地址指令107条，每个地址字段为6位，则指令字长至少应该是（ ）。
A. 24位 B. 26位 C. 28位 D. 32位
三地址指令有29条，所以它的操作码至少为$\lceil\log_2 29\rceil = 5$位。以5位进行计算，它剩余$32-29=3$种操作码给二地址。而二地址另外多了6位给操作码，因此它的数量最大达$3×64=192$，大于二地址指令数量107，满足题目要求。
以三地址指令为例，操作码占5位，每个地址码占6位，总计$5+3×6=23$位。因为计算机按字节编址，需要是8的倍数，所以指令字长至少应该是$\lceil23/8\rceil × 8 = 24$位。
| 位段范围 | 23~18 | 17~12 | 11~6 | 5~0 | | --- | --- | --- | --- | --- | | 三地址指令 | OP | A1 | A2 | A3 | | 二地址指令 | OP | A1 | A2 | — |
下列关于超标量流水线特性的叙述中，正确的是（ ）。
Ⅱ. 能在一个时钟周期内同时发射多条指令
Ⅲ. 能结合动态调度技术提高指令执行并行性
超标量流水线是指在CUP中有一条以上的流水线，并且每个时钟周期内可以完成一条以上的指令，其实质是以空间换时间。
超标量流水线不影响流水线功能段的处理时间。I错误。
超标量流水线可以将多条可并行执行的指令并行执行。II正确。
超标量流水线不能调整指令的执行顺序，因此通过编译优化技术，把可并行执行的指令搭配起来，提高并行性。III正确。
下列关于主存储器（MM）和控制存储器（CS）的叙述中，错误的是（ ）。
C. MM存储指令和数据，CS存储微指令
D. MM用RAM和ROM实现，CS用ROM实现
主存储器就是我们通常说的主存，在CPU外，存储指令和数据，由RAM和ROM实现。控制存储器用来存放实现指令系统的所有微指令，是一种只读型存储器，机器运行时只读不写，在CPU的控制器内。CS按照微指令的地址访问。B错误。
下列关于指令流水线数据通路的叙述中，错误的是（ ）。
D. 由组合逻辑电路和时序逻辑电路组合而成
生成控制信号的控制部件负责根据当前指令的操作码生成相应的控制信号，用于指导数据通路的操作。
算术逻辑运算部件（ALU）用于执行指令中的算术和逻辑运算。
通用寄存器组用于存储程序执行过程中的数据，供指令使用和保存中间结果。指令寄存器（IR）存储当前正在执行的指令，供指令解码和执行。
组合逻辑电路用于执行组合逻辑功能，它根据输入的信号立即给出相应的输出。在指令流水线中，组合逻辑电路通常用于执行指令解码、操作控制和数据选择等功能。时序逻辑电路则与时间相关，根据时钟信号和状态信息来确定输出。它用于处理与时序相关的操作和状态转换，如时钟同步、状态存储和时序控制等。在指令流水线中，时序逻辑电路用于实现指令流水线各个阶段的时序控制和状态转换。通过组合逻辑电路和时序逻辑电路的组合，指令流水线数据通路能够实现指令的流水线化执行，提高计算机的指令执行效率。
五阶段流水线可分为取指(IF)、译码/取数(ID)、执行(EXE)、存储器读(MEM)、写回(WriteBack)。数字系统中，各个子系统通过数据总线连接形成的数据传送路径称为数据通路，包括程序计数器、算术逻辑运算部件、通用寄存器组、取指部件等，不包括控制部件。B、C、D正确，A错误。
下列关于多总线结构的叙述中，错误的是（ ）。
D. PCI-Express×16采用并行传输方式
多总线结构用速率高的总线连接高速设备用速率低的总线连接低速设备。一般来说，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个差分信号对，用于数据传输，每个差分信号对包括一个发送和一个接收信号。这种插槽设计可以支持更高的数据传输速率和带宽需求，以满足现代图形处理等高性能计算需求。
I/O指令实现的数据传送通常发生在（ ）。
I/O接口是CPU与设备之间的交接面，I/O端口是I/O接口电路中可以被CPU直接访问的寄存器。由于主机和I/O设备的工作方式和工作速度有很大差异，I/O端口就应运而生。在执行一条指令时，CPU使用地址总线选择所请求的I/O端口，使用数据总线在CPU寄存器和端口之间传输数据。D正确。
下列关于多重中断系统的叙述中，错误的是（ ）。
C. 中断请求的产生与当前指令的执行无关
D. CPU通过采样中断请求信号检测中断请求
多重中断系统在保护被中断进程现场时关中断，执行中断处理程序时开中断，B错误。
CPU一般在一条指令执行结束的阶段采样中断请求信号，查看是否存在中断请求，然后决定是否响应中断，A、D正确。
中断请求一般来自CPU以外的事件，异常一般发生在CPU内部，C正确。
假设4个作业到达系统的时刻和运行时间如下表所示。
\[ \begin{array}{|c|c|c|} \hline \text{作业} & \text{到达时刻} & \text{运行时间} \\ \hline \text{J1} & 0 & 3 \\ \hline \text{J2} & 1 & 3 \\ \hline \text{J3} & 1 & 2 \\ \hline \text{J4} & 3 & 1 \\ \hline \end{array} \]
系统在\( t=2 \)时开始作业调度。若分别采用先来先服务和短作业优先调度算法，则选中的作业分别是（ ）。
A. J2、J3 B. J1、J4 C. J2、J4 D. J1、J3
系统在t=2时开始作业调度，此时已经到达的作业有J1、J2和J3。
先来先服务调度算法优先选择到达时刻早的作业，J1、J2和J3中J1到达时刻最早。若采用先来先服务调度算法，则选中J1。
短作业优先调度算法优先选择运行时间短的作业，J1、J2和J3中J3的运行时间最短。若采用短作业优先调度算法，则选中J3。
①返回用户态 ②执行陷入（trap）指令
③传递系统调用参数 ④执行相应的服务程序
A. ②→③→①→④ B. ②→④→③→①
C. ③→②→④→① D. ③→④→②→①
【解析】执行系统调用的过程如下：正在运行的进程先传递系统调用参数，然后由陷入（trap）指令负责将用户态转换为内核态，并将返回地址压入堆栈以备后用，接下来CPU执行相应的内核态服务程序，最后返回用户态。所以选项C 正确。
某计算机按字节编址，其动态分区内存管理采用最佳适应算法，每次分配和回收内存后都对空闲分区链重新排序。当前空闲分区信息如下表所示。
\[ \begin{array}{|c|c|c|c|c|} \hline \text{分区起始地址} & 20\text{K} & 500\text{K} & 1000\text{K} & 200\text{K} \\ \hline \text{分区大小} & 40\text{KB} & 80\text{KB} & 100\text{KB} & 200\text{KB} \\ \hline \end{array} \]
回收起始地址为60K、大小为140KB的分区后，系统中空闲分区的数量、空闲分区链第一个分区的起始地址和大小分别是（ ）。
回收起始地址为60K、大小为140KB的分区后，起始地址为20K、和起始地址为200K的空闲分区合并为一个40KB+140KB+200KB=380KB的新空闲分区，如下图所示：
此时系统中还剩3个空闲分区，空闲分区信息如下表所示。
\[ \begin{array}{|c|c|} \hline \text{分区起始地址} & \text{分区大小} \\ \hline 500\text{K} & 80\text{KB} \\ \hline 1000\text{K} & 100\text{KB} \\ \hline 20\text{K} & 380\text{KB} \\ \hline \end{array} \]
空闲分区链第一个分区的起始地址和大小分别是500K、80KB。
某文件系统的簇和磁盘扇区大小分别为1KB和512B。若一个文件的大小为1026B，则系统分配给该文件的磁盘空间大小是（ ）。
A. 1026B B. 1536B C. 1538B D. 2048B
对于一个文件系统，文件的磁盘空间是以簇 (cluster) 为单位进行分配的。若一个文件的大小为1026B，系统的簇大小为1KB，则系统分配给该文件的簇的数量是 ⌈1026B/1KB⌉=2，磁盘空间大小是1KB×2=2KB=2048B。
下列有关基于时间片的进程调度的叙述中，错误的是（ ）。
A. 时间片越短，进程切换的次数越多，系统开销也越大
B. 当前进程的时间片用完后，该进程状态由执行态变为阻塞态
C. 时钟中断发生后，系统会修改当前进程在时间片内的剩余时间
D. 影响时间片大小的主要因素包括响应时间、系统开销和进程数量等
A正确。因为每个进程只能在一个时间片内执行一段时间，然后切换到下一个进程。这会增加系统开销，因为每次进程切换都需要一定的处理时间。因此，时间片越短，进程切换的次数越多，系统开销也越大。
B错误。当前进程的时间片用完后，并不一定会导致该进程状态由执行态变为阻塞态。在基于时间片的进程调度中，当一个进程的时间片用完后，它的状态会变为就绪态，然后调度程序会选择另一个就绪态的进程来执行。进程的状态从执行态变为阻塞态通常是由于等待某些资源（如 I/O 操作）而无法继续执行。
C正确。进程的时间片不会自己减少，是由时钟中断程序来控制进程的时间片的减少。时钟中断是指每隔一段相同的时间，都会发出一个中断信号， CPU接受到中断信号后触发内核中相应的中断处理程序。时钟中断通常由计算机内部的硬件计时器生成。计时器以固定的时间间隔发送一个中断请求给处理器。这个时间间隔通常是几毫秒，根据操作系统和硬件的不同而有所不同。例如，在Windows系统中，时钟中断的频率为每秒1000次，而在Linux系统中，它通常为每秒100或1000次。
D正确。时间片的大小会影响系统的响应速度和吞吐量。更短的时间片可以更频繁地切换进程，提高对交互性任务的响应时间，但也会增加系统开销。同时，进程数量的增加也会影响时间片的分配情况。因此，影响时间片大小的主要因素包括响应时间、系统开销和进程数量等。
与单道程序系统相比，多道程序系统的优点是（ ）
【解析】多道程序系统通过组织作业（编码或数据）使 CPU总有一个作业可执行，从而提高了 CPU的利用率、系统吞吐量和I/O设备利用率，I、III、IV 是优点。但系统要付出额外的开销来组织作业和切换作业，11错误。所以选D。
下列选项中，磁盘逻辑格式化程序所做的工作是（ ）。
Ⅳ. 对保存空闲磁盘块信息的数据结构进行初始化
磁盘的格式化分为物理格式化和逻辑格式化。
物理格式化又称低级格式化，是对磁盘的物理表面进行处理，在磁盘上建立标准的磁盘记录格式，划分磁道和扇区，记录专用信息，如磁道标志(每个磁道一个)、扇区标志（每个扇区一个）和保证所记录的信息是准确的循环冗余校验 (CRC) 位。
逻辑格式化又称高级格式化，是在磁盘上建立一个系统存储区域，包括引导记录区、文件目录区FCT、文件分配表FAT。磁盘文件的存贮是以簇为单位，簇在磁盘上文件并不是连续存储的，而是由FAT表来保存文件存放簇号顺序。由目录项的起始簇号指出该文件在FAT中的第1个簇号，在这个簇号单元里，记载的是该文件下一簇的簇号，依次类推直至该文件的最后一个簇号。这样通过“簇号链”将文件的存储空间链接在一起。
I错误。对磁盘进行分区即将磁盘划分为一个或多个柱面组成的分区，如C盘、D盘等。分区完成后才能进行逻辑格式化。
II正确。建立文件系统的根目录是逻辑格式化的工作。
III错误。确定磁盘扇区校验码所占位数是物理格式化的工作。
IV正确。对保存空闲磁盘块信息的数据结构进行初始化是逻辑格式化的工作。
某文件系统中，针对每个文件，用户类别分为4类：安全管理员、文件主、文件主的伙伴、其他用户；访问权限分为5种：完全控制、执行、修改、读取、写入。若文件控制块中用二进制位串表示文件权限，为表示不同类别用户对一个文件的访问权限，则描述文件权限的位数至少应为（ ）。
A. 5 B. 9 C. 12 D. 20
答案：D 可以把用户访问权限抽象为一个矩阵，行代表用户，列代表访问权限。这个矩阵有4行5列，1代表true，0代表false，所以需要20位，选D。
若文件f1的硬链接为f2，两个进程分别打开f1和f2，获得对应的文件描述符为fd1和fd2，则下列叙述中，正确的是（ ）。
Ⅲ. fd1和fd2分别指向各自的用户打开文件表中的一项
I错误。f1和f2的具有各自的读写指针，位置不一定相同。
II和III正确。当文件f1和f2是硬链接关系时，它们共享同一个索引节点，但是拥有各自独立的文件描述符。
系统将数据从磁盘读到内存的过程包括以下操作：
A. ③→①→②→④ B. ②→③→①→④
C. ②→①→③→④ D. ①→②→④→③
第一步：初始化DMA控制器并启动磁盘，这些操作通常由设备驱动程序完成。
第二步：DMA控制器从磁盘传输一块数据到内存缓冲区。
第三步：在数据传输完成之后，DMA控制器发出中断请求，通知CPU数据已经准备好了。
假设OSI参考模型的应用层欲发送400B的数据（无拆分），除物理层和应用层之外，其他各层在封装PDU时均引入20B的额外开销，则应用层数据传输效率约为（ ）。
A. 80% B. 83% C. 87% D. 91%
OSI参考模型(Open System Interconnection Reference Model)是一个由国际标准化组织提出的概念模型，旨在为各种计算机互连构成网络提供标准框架。该模型将通信系统划分为七层，从下到上依次为物理层、数据链路层、网络层、传输层、会话层、表示层和应用层。
根据题目条件，应用层要发送400B的数据，每层在封装PDU时会引入20B的额外开销（除物理层和应用层）。
除了应用层和物理层外，共有5个中间层，每个中间层的封装额外开销为20B。所以，总的封装额外开销为 \( 20\ \text{B} × 5 = 100\ \text{B} \)，总共需要发送的数据量为 \( 400\ \text{B} + 100\ \text{B} = 500\text{B} \)。
\[ 应用层数据传输效率 = \frac{实际传输的应用层数据量}{总共需要发送的数据量} = \frac{400\ \text{B}}{500\ \text{B}} = 80\% \]
若信道在无噪声情况下的极限数据传输速率不小于信噪比为30dB条件下的极限数据传输速率，则信号状态数至少是（ ）。
A. 4 B. 8 C. 16 D. 32
根据香农公式\( ^* \)，在被高斯白噪声干扰的信道中，信道的最大数据传输速率为 \[ C = W \log_2\left(1 + \frac{S}{N}\right) \]（单位：比特每秒（bits per second, bps）） 其中 \( W \) 是信道带宽，单位 \( \text{Hz} \)，\( S \) 是信号功率（单位瓦），\( N \) 是噪声功率（单位瓦）。
\( \frac{S}{N} \) 为信号与噪声的功率之比，简称信噪比。信噪比 \( \text{SNR} \) 通常以分贝（\(\text{dB}\)）为单位，满足： \[ \text{SNR} = 10\log_{10}\frac{S}{N} \] 即 \( \frac{S}{N} = 10^{\frac{\text{SNR}}{10}} \)。将 \( \text{SNR} = 30\ \text{dB} \) 代入，得 \( \frac{S}{N} = 1000 \)；再代入香农公式，解得 \( C = W \log_2 1001 \)。
根据奈式准则\( ^* \)，无噪声情况下可获得的最大数据传输速率为 \[ C = 2W \]（单位：波特（Baud），即码元/秒） 其中\( W \) 为带宽（单位 \( \text{Hz} \)）。每个码元可携带的比特数量为 \( \log_2 M \)（\( M \) 为调制技术中可利用的符号数量），因此数据传输速率（单位：bps）为： \[ C = 2W \log_2 M \]
若无噪声下的极限数据传输速率不小于信噪比30dB时的极限速率，则： \[ 2W \log_2 M \geq W \log_2 1001 \] 化简得 \( M \geq \sqrt{1001} \)，取 \( M = 2^{\log_2 \sqrt{1001}} = 32 \)。
在下图所示的网络中，若主机H发送一个封装访问Internet的IP分组的IEEE 802.11数据帧F，则帧F的地址1、地址2和地址3分别是（ ）。
A. 00-12-34-56-78-9a, 00-12-34-56-78-9b, 00-12-34-56-78-9c
B. 00-12-34-56-78-9b, 00-12-34-56-78-9a, 00-12-34-56-78-9c
C. 00-12-34-56-78-9b, 00-12-34-56-78-9c, 00-12-34-56-78-9a
D. 00-12-34-56-78-9a, 00-12-34-56-78-9c, 00-12-34-56-78-9b
本题考察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。
下列IP地址中，只能作为IP分组的源IP地址但不能作为目的IP地址的是（ ）。
A. 0.0.0.0 B. 127.0.0.1
C. 20.10.10.3 D. 255.255.255.255
在IPv4的地址规划中，有一些特殊的IP地址分配。
A 正确。0.0.0.0 是一种保留地址，表示在本网络上的本主机。只能作为源地址，不能作为目的地址。
B 错误。127.0.0.1 用作本地软件的环回测试地址，用于主机本身的测试和通信。既能作为源地址，也能作为目的地址。
C 错误。20.10.10.3 是一个普通地址，既能作为源地址，也能作为目的地址。
D 错误。255.255.255.255 是本网络上的广播地址，只在本网络上进行广播（各路由器均不转发）。只能作为目的地址，不能作为源地址。
直接封装RIP、OSPF、BGP报文的协议分别是（ ）。
A. TCP、UDP、IP B. TCP、IP、UDP
C. UDP、TCP、IP D. UDP、IP、TCP
RIP (Routing Information Protocol) 使用UDP进行直接封装，使用的端口号为520。
OSPF (Open Shortest Path First) 使用IP进行直接封装，使用的协议号为89。
BGP 使用 TCP 进行直接封装，使用的协议号为179。
若将网络21.3.0.0/16划分为128个规模相同的子网，则每个子网可分配的最大IP地址个数是（ ）。
A. 254 B. 256 C. 510 D. 512
网络21.3.0.0/16的网络号占16位，主机号占32-16=16位，要将该网络划分为128个规模相同的子网，子网号占 log2128=7 位，从主机号中划分前 7 位为子网号，剩余16-7=9位为子网的主机号。每个子网地址空间包含的地址数为 29=512 ，从中排除一个主机号位全0的网络地址和一个主机号位全1的广播地址，剩余512-1-1=510就是每个子网可分配的最大IP地址个数。
若甲向乙发起一个TCP连接，最大段长MSS=1KB，RTT=5ms，乙开辟的接收缓存为64KB，则甲从连接建立成功至发送窗口达到32KB，需经过的时间至少是（ ）。
A. 25 ms B. 30 ms C. 160 ms D. 165 ms
本题没有给出慢开始门限 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。
下列关于FTP协议的叙述中，错误的是（ ）。
A. 数据连接在每次数据传输完毕后就关闭
B. 控制连接在整个会话期间保持打开状态
C. 服务器与客户端的TCP 20端口建立数据连接
D. 客户端与服务器的TCP 21端口建立控制连接
FTP (File Transfer Protocol) 是用于在网络上传输文件的标准网络协议。
主动模式（由客户端发起）下，客户端的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端口建立控制连接。
（15分）请设计一个算法，将给定的表达式树（二叉树）转换为等价的中缀表达式（通过括号反映操作符的计算次序）并输出。例如，当下列两棵表达式树作为算法输入时：
输出的中缀表达式分别为 (a+b)∗(c∗(−d)) 和 (a∗b)+(−(c−d)) 。
⑵ 根据设计思想，采用C或C++语言描述算法，关键之处给出注释。（10分）
理由：学生的基本设计思想偏离标准答案。题目要求将表达式树转换为等价的中缀表达式，并通过括号反映操作符的计算次序。标准答案的核心是中序遍历，并在分支结点（非根且有子表达式）两侧加括号。
学生回答提到了“遍历二叉树”“左右孩子为操作数则直接输出”“若左右孩子是符号则将根结点放入堆栈”“优先级更高时直接输出”，这更像是表达式求值或中缀转后缀的思路，而不是表达式树输出中缀表达式的思路。学生没有说明在中序遍历序列中何处加括号，也没有体现“根结点和叶结点不加括号，其他分支结点需加括号”的关键逻辑。因此基本设计思想基本不正确。
由于提到了遍历二叉树并输出，可给1分，但不能给更高分。
理由：代码存在严重逻辑错误，不能实现题目要求，且与标准答案的中序遍历递归思路不一致。
1. 函数定义写成 research tree(BTree tree) ，返回类型不明确，参数也不是标准答案中的指针形式，语法上不成立。按上下文可理解为函数声明/定义错误，属于核心逻辑错误。
2. 使用 while(tree->Left != null || tree->right != null) 循环，但循环体内没有让 tree 向下移动，也没有递归调用，可能导致死循环或根本无法遍历整棵树。
3. 没有实现中序遍历。表达式树转中缀表达式应递归处理左子树、输出根结点、递归处理右子树；学生代码只处理了当前结点的左右孩子，未递归处理子树，因此无法处理多层表达式树。
4. 括号添加逻辑错误。学生仅在左右孩子是大写字母时输出括号，且括号位置不正确；标准答案要求非根分支结点对应的子表达式加括号。例如 (a+b)*(c*(-d)) 中，根结点的左右子树都需要括号，学生代码无法正确产生这些括号。
5. 使用 std::stack 和 push_pop 等栈操作，但表达式树转中缀表达式不需要用栈处理运算符优先级；这里沿用了另外一类算法思路，与题目要求不符。
6. 代码中 Temp 未初始化就访问 Temp->data ，存在空指针/未定义行为问题。
7. 操作数判断仅使用 'A' <= data <= 'Z' ，但题目示例中有 a、b、c、d 等小写字母，判断不完整；不过这不是最主要问题。
因此，该代码未正确实现“表达式树输出中缀表达式并加必要括号”的算法，逻辑错误严重，不能得分。
题目要求输出中缀表达式，对应表达式树（二叉树）的中序遍历序列。但本题难点在于要输出左右括号，所以也融合了二叉树的前序遍历和后序遍历，二叉树的前序遍历、中序遍历、后序遍历本质都是深度优先搜索。
（8分）使用Prim（普里姆）算法求带权连通图的最小（代价）生成树（MST）。请回答下列问题。
⑴ 对下列图G，从顶点A开始求G的MST，依次给出按算法选出的边。（4分）
⑶ 对任意的带权连通图，满足什么条件时，其MST是唯一的？（2分）
学生答案第(1)问写成若干条路径并计算总权值，其中第一条为 \(A \to D \to E \to C \to B\)，对应边为 \((A,D),(D,E),(C,E),(B,C)\)，与标准答案依次选出的边一致，且次序正确，因此该问应给满分4分。其余路径虽不是按Prim算法“依次选出边”的规范表达，但不存在额外扣分必要，按“思路正确不扣分”处理。
学生回答“是唯一”，与标准答案“图G的MST是唯一的”一致，得2分。
学生回答“当边数=结点数时，MST唯一”，该说法错误。带权连通图满足边数=结点数时只能说明它是一棵树加上一条边，但不能保证最小生成树唯一；标准条件是“任意一个环中所包含的边的权值均不相同”。因此本问不得分，得0分。
开始点集 S 和边集 A 为空，从一个任意的顶点开始，并将该顶点加入 S ，然后将距离点集 A 距离（代价）最小的顶点加入到点集 S 中，该带权边加入边集 A 中，直到点集 S 包含图中所有顶点为止。当算法终止时，由点集 S 和边集 A 构成的树就是最小生成树。
题目中给定从A开始， S 可以初始化为{A}。模拟步骤如下：
点集 S 包含图中所有顶点，此时由点集 S 和边集 A 构成的树就是最小生成树。
依次选出的边为：(A,D), (D,E), (C, E), (B, C)。
⑵ 图G的MST是唯一的，该MST包含了图中权值最小的4条边。
⑶ 如果任意的带权连通图的所有边的权值互不相同时，其MST是唯一的。该条件为MST是唯一的的充分不必要条件。
（13分）已知\[ f(n)=\sum_{i = 0}^{n}2^{i}=2^{n + 1}-1=\underbrace{11\cdots1}_{n + 1位}\text{B} \] ，计算f(n)的C语言函数f1如下：
将f1中的int都改为float，可得到计算f(n)的另一个函数f2。假设unsigned和int型数据都占32位，float采用IEEE754单精度标准。请回答下列问题。
(1) 当n=0时，f1会出现死循环，为什么？若将f1中的变量i和n都定义为int型，则f1是否还会出现死循环？为什么？（4分）
(2) f1(23)和f2(23)的返回值是否相等？机器数各是什么（用十六进制表示）？（3分）
(3) f1(24)和f2(24)的返回值分别为33554431和33554432.0，为什么不相等？（1分）
(4) f(31)= $2^{32} - 1$ ，而f1(31)的返回值却为-1，为什么？若使f1(n)的返回值与f(n)相等，则最大的n是多少？（2分）
(5) f2(127)的机器数为7F80 0000H，对应的值是什么？若使f2(n)的结果不溢出，则最大的n是多少？若使f2(n)的结果精确（无舍入），则最大的n是多少？（3分）
学生正确指出当n=0且i、n为unsigned时，n-1会下溢为2³²-1，导致循环条件永真，出现死循环；也正确指出若改为int，n-1为-1，i=0时条件不成立，不会死循环。核心逻辑与标准答案一致，得4分。
学生回答“不相等”，与标准答案“相等”矛盾，且f1(23)机器数写成00FFFFFFH，正确应为00FF FFFFH，数值和十六进制都不正确；f2(23)机器数写成807FFFFFH，正确应为4B7F FFFFH，严重错误。该问不得分，得0分。
学生回答“float溢出失去精度”，虽然表述不够准确（此处不是溢出，而是有效位数不足导致舍入），但说明了float精度不足导致结果不同，与标准答案核心意思“float只有24位有效位，舍入后数值增大”基本一致，可给1分。
学生指出int最大值为2³¹-1，sum溢出，并得出最大n=30，与标准答案一致。虽然对f1(31)返回-1的解释不够完整，但关键结论正确，得2分。
学生识别出7F80 0000H对应+∞，正确；但“不溢出最大n值”给出n=150，错误，正确应为126；“精确最大n值”未明确给出23，只给出“127+23=150”，错误。三问中仅第一问正确，得1分。
虽然f1和f2都是计算的是$f(n)=2^{n+1}-1$，但是由于输入和输出数据类型的限制，实际输出结果可能有出入。
(1) 由于i和n是unsigned型，因此“i <= n-1”是无符号数比较。n=0时，n-1的机器数为全1，值是$2^{32}-1$，为unsigned型可表示的最大数，条件“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)的返回值相等。$f(23)=\underbrace{11\cdots1}_{24位}\text{B}$。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单精度标准，机器数是 $\underbrace{0}_{S}\ \underbrace{10010110}_{E}\ \underbrace{11111111111111111111111}_{M}\text{B}=4B7FFFFFH$。
(3) 当n=24时，$f(24)=\underbrace{11\cdots1}_{25位}\text{B}$。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}\sim2^{31}-1$，溢出，f(31)的二进制形式是32个1，C语言整型用补码表示，得到f1(31)的返回值为-1。因为$f(n)=\underbrace{11\cdots1}_{n+1位}\text{B}$且int型最大可表示数是符号位为0后面31个数值位全为1，即n+1=31，解得n=30，所以使f1(n)的返回值与f(n)相等的最大n值是30。
(5) 7F80 0000H = $\underbrace{0}_{S}\ \underbrace{11111111}_{E}\ \underbrace{00000000000000000000000}_{M}\text{B}$，阶码位全1，尾数位全0，表示无穷大，符号位为0，表示正无穷大，即$+\infty$。 当n=127时，$f(127)=\underbrace{11\cdots1}_{128位}\text{B}$。表示为浮点数 $\underbrace{0}_{S}\ \underbrace{11111110}_{E}\ \underbrace{11111111111111111111111}_{M}\underbrace{(11\cdots1)}_{104位}\text{B}$，括号内为需要舍入的部分，按0舍1入进行舍入后需要右规，阶码加1，得到 $\underbrace{0}_{S}\ \underbrace{11111111}_{E}\ \underbrace{00000000000000000000000}_{M}\text{B}$，该浮点数表示$+\infty$，溢出。 当n=126时，$f(126)=\underbrace{11\cdots1}_{127位}\text{B}$。表示为浮点数 $\underbrace{0}_{S}\ \underbrace{11111110}_{E}\ \underbrace{11111111111111111111111}_{M}\underbrace{(11\cdots1)}_{103位}\text{B}$，括号内为需要舍入的部分，按0舍1入进行舍入后需要右规，阶码加1，得到 $\underbrace{0}_{S}\ \underbrace{11111110}_{E}\ \underbrace{00000000000000000000000}_{M}\text{B}$，阶码11111110B达到IEEE754单精度格式表示的最大阶码。
综上，若使f2(n)的结果不溢出，则最大的n是126。 当n = 24时根据(1)的结果，f2(24)需要舍入。 当n = 23时，$f(23)=\underbrace{11\cdots1}_{24位}\text{B}$。f2(23)为float类型，float采用IEEE754单精度标准，float有1个符号位，8个指数位，23个尾数位，考虑小数点前面省略的1，float有24个有效数值位。所以不需舍入，结果精确。 综上，若使f2(n)的结果精确（无舍入），则最大的n是23。
（10分）在按字节编址的计算机M上，题43中f1的部分源程序（阴影部分）与对应的机器级代码（包括指令的虚拟地址）如下图所示。
其中，机器级代码行包括行号、虚拟地址、机器指令和汇编指令。
(1) 计算机M是RISC还是CISC？为什么？（2分）
(2) f1的机器指令代码共占多少字节？要求给出计算过程。（2分）
(3) 第20条指令cmp通过i减n-1实现对i和n-1的比较。执行f1(0)过程中，当i=0时，cmp指令执行后，进/借位标志CF的内容是什么？要求给出计算过程。（3分）
(4) 第23条指令shl通过左移操作实现了power*2运算，在f2中能否也用shl指令实现power*2？为什么？（3分）
学生答案正确指出计算机M为CISC，理由是“复杂指令集，变长的”，与标准答案“指令长短不一，不符合RISC指令系统特点”一致。得2分。
学生计算错误。标准答案指出f1的机器指令代码从00401020H到0040107FH，共96字节。学生仅计算了几个典型指令的字节数之和，得出7字节，未考虑整个代码段的范围。逻辑错误，不能得满分。得0分。
学生答案部分正确。学生正确理解了n-1=2^n-1，并进行了二进制运算，得出借位标志CF=1，与标准答案一致。但学生表述中使用了“2^n-1”作为n-1的表示（在n位无符号数中正确），且计算过程正确。得3分。
学生答案正确指出不能，理由是f2中变量power是float型，左移会丢失精度，与标准答案“float型机器数含阶码部分，无最高有效数位，整体左移不能实现乘2功能”一致。得3分。
(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。
浮点数运算比整型运算要复杂，耗时也较长。
（7分）假定题44给出的计算机M采用二级分页虚拟存储管理方式，虚拟地址格式如下：
\[ \begin{array}{|c|c|c|} \hline \text{页目录号（10位）} & \text{页表索引（10位）} & \text{页内偏移量（12位）} \\ \hline \end{array} \]
(1) 函数f1的机器指令代码占多少页？（1分）
(2) 取第1条指令（push ebp）时，若在进行地址变换的过程中需要访问内存中的页目录和页表，则会分别访问它们各自的第几个表项（编号从0开始）？（2分）
(3) M的I/O采用中断控制方式。若进程P在调用f1之前通过 scanf() 获取n的值，则在执行 scanf() 的过程中，进程P的状态会如何变化？CPU是否会进入内核态？（4分）
理由：标准答案为“1页”，学生作答为“4页”，与标准答案不一致，且未给出正确的页数判断。该小题考查对虚拟地址结构与页大小的理解：页内偏移量占12位，页大小为2 12 =4KB；函数f1的机器指令代码虚拟地址高20位相同，因此代码在同一页中，仅占1页。学生答案错误，不得分。
理由：标准答案为“页目录的第1个表项，页表的第1个表项”。学生作答为“第一个，第二个，第五个，第七个”，明显与题问要求不符。题目只要求分别写出访问页目录和页表各自的第几个表项，学生给出多个表项编号且无法对应，逻辑错误，不得分。
理由：标准答案要求说明进程P在执行scanf()过程中状态变化：等待输入时从执行态变为阻塞态；输入结束时被唤醒变为就绪态；随后被调度变为运行态；并且CPU会从用户态进入内核态。学生只答出“P从运行态转到就绪态”以及“CPU会进入内核态”，缺少“执行态→阻塞态”和“就绪态→运行态”两个关键状态变化，且“从运行态转到就绪态”并非scanf()等待输入时的正确状态变化，故只能给CPU进入内核态这1分。
(1) 页目录用于寻找页目录的表项，该表项包含页表的位置。页表索引用于寻找页表的表项，该表项包含页的位置。根据虚拟地址格式，页目录号占10位，页表索引占10位，共占 \( 10+10=20 \) 位。函数\( f1 \)的代码段中所有指令的虚拟地址的高20位相同，均为\( 00401\text{H} \)，因此\( f1 \)的机器指令代码在同一页中，仅占用1页。
(2) `push ebp`指令的虚拟地址是 \[ 00401020\text{H} = \underbrace{0000000001}_{页目录号}\underbrace{0000000001}_{页表索引}\underbrace{000000100000}_{页内偏移量} \text{B} \] 页目录号是 \( 00\ 0000\ 0001\text{B}=1 \)，页表索引是 \( 000000\ 0001\text{B}=1 \)，所以，取该指令时访问了页目录的第1（编号从0开始）个表项，在对应的页表中访问了第1（编号从0开始）个表项。
(3) 第一问。在执行`scanf()`的过程中，进程\( P \)因等待输入而从执行态变为阻塞态。输入结束时，\( P \)被中断处理程序唤醒，变为就绪态。\( P \)被调度程序调度，变为运行态。
第二问。中断控制方式是指在计算机系统中，通过中断机制来处理硬件设备或其他外部事件引起的中断请求。在中断控制方式下，计算机系统正常执行的程序可以被中断请求打断，转而执行中断服务程序来处理中断事件。在中断控制方式下，中断事件必须在内核态被处理，以保证对系统资源的管理和保护。所以CPU会进入内核态。
（8分）某进程中有3个并发执行的线程thread1、thread2、thread3，其伪代码如下所示。
请添加必要的信号量和P、V（或wait()、signal()）操作，要求确保线程互斥访问临界资源，并且最大程度地并发执行。
理由：标准答案要求定义3个信号量，分别用于对变量 y 的两组互斥访问（thread1-thread3、thread2-thread3）以及变量 z 的互斥访问。学生仅定义了 mutex_x、mutex_y、mutex_z，其中 mutex_x 用于保护 x，但本题中 x 只被 thread1 读取，并未被其他线程修改，因此不需要互斥信号量；而变量 y 会被 thread1、thread2、thread3 访问和修改，学生只用一个 mutex_y 保护 y，虽然可以保证互斥，但会降低并发度，且未区分“thread1与thread3”和“thread2与thread3”两组互斥关系，因此不完全符合“最大程度并发执行”的要求。变量 z 的保护信号量定义正确，得1分；y 的保护信号量定义存在不足，x 的信号量定义多余，扣2分。
（2）thread1 互斥代码得分及理由（满分约1.67分）
理由：thread1 中访问共享变量 y，应只对 y 加锁。学生使用了 P(mutex_x)、P(mutex_y)，其中 mutex_x 是多余的，会导致不必要的互斥，降低并发度。核心逻辑“对 y 加锁后调用 add(x,y)”是正确的，但未按标准答案只使用 mutex_y1，因此不能给满分，酌情给1分。
（3）thread2 互斥代码得分及理由（满分约1.67分）
理由：thread2 访问共享变量 y 和 z，应该分别对 y、z 加锁。学生使用了 P(mutex_y)、P(mutex_z)，互斥逻辑基本正确，但 mutex_y 是 thread3 也会使用的同一个信号量，会与 thread1 产生不必要的互斥，降低并发度。由于核心互斥正确，但未满足最大并发要求，给1分。
（4）thread3 互斥代码得分及理由（满分约1.67分）
理由：thread3 中先执行 z=add(z,w); 再执行 y=add(y,w);。学生代码中在 z=add(z,w) 和 y=add(y,w) 之间没有释放 mutex_z，而标准答案要求 z=add(z,w) 后立即 V(mutex_z)，然后再对 y 加锁。学生将 P(mutex_z)、P(mutex_y) 连续加锁，直到最后才释放，导致在修改 y 期间仍然占用 mutex_z，其他线程无法访问 z，严重降低并发度，且不符合“最大程度并发执行”的要求。此外，对 y 只使用一个 mutex_y，也未区分 thread1 与 thread2 对 y 的不同互斥需求，逻辑上存在明显不足，因此该部分不得分。
补充说明：学生答案中变量名大小写、X/Y/Z 与 x/y/z 的差异，按识别误写处理，不额外扣分；但核心信号量设计未区分 y 的两组互斥，且 thread3 未及时释放 mutex_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。
（9分）甲乙双方均采用后退N帧协议（GBN）进行持续的双向数据传输，且双方始终采用捎带确认，帧长均为1000 B。\( S_{x,y} \)和\( R_{x,y} \)分别表示甲方和乙方发送的数据帧，其中：x是发送序号；y是确认序号（表示希望接收对方的下一帧序号）；数据帧的发送序号和确认序号字段均为3比特。信道传输速率为100 Mbps，RTT = 0.96 ms。下图给出了甲方发送数据帧和接收数据帧的两种场景，其中\( t_0 \)为初始时刻，此时甲方的发送和确认序号均为0，\( t_1 \)时刻甲方有足够多的数据待发送。
(1) 对于图(a)，\( t_0 \)时刻到\( t_1 \)时刻期间，甲方可以断定乙方已正确接收的数据帧数是多少？正确接收的是哪几个帧（请用\( S_{x,y} \)形式给出）？（3分）
(2) 对于图(a)，从\( t_1 \)时刻起，甲方在不出现超时且未收到乙方新的数据帧之前，最多还可以发送多少个数据帧？其中第一个帧和最后一个帧分别是哪个（请用\( S_{x,y} \)形式给出）？（3分）
(3) 对于图(b)，从\( t_1 \)时刻起，甲方在不出现新的超时且未收到乙方新的数据帧之前，需要重发多少个数据帧？重发的第一个帧是哪个（请用\( S_{x,y} \)形式给出）？（2分）
(4) 甲方可以达到的最大信道利用率是多少？（1分）
学生作答：“2个，51,0 - 53,0”。
标准答案应为“3个，S0,0、S1,0、S2,0”。学生作答中帧数量错误，且序号形式与标准答案不符。尽管存在图片识别误差可能性，但“2个”与“3个”差异明显，且“51,0 - 53,0”无法直接对应到S0,0、S1,0、S2,0，核心逻辑错误。扣3分。
学生作答：“3个，55,3，57,3”。
标准答案应为“5个，第一个帧S5,2，最后一个帧S1,2”。学生作答中帧数量错误，首帧和末帧序号均错误，核心逻辑错误。扣3分。
标准答案应为“3个，重发的第一个帧是S2,3”。学生作答中重发帧数量正确，但第一个重发帧的序号错误，应为S2,3而非S0,0。扣1分。
学生作答：计算过程混乱，最终结果约为88%。
标准答案应为50%。学生计算中信道利用率公式错误、数据帧发送时延计算错误、RTT单位混淆，最终结果错误。扣1分。
采用后退N帧协议(GBN)，发送窗口大小 \( W_T \) 满足 \( 1 < W_T \leq 2^n - 1 \)，接收窗口大小 \( W_R \) 满足 \( W_R = 1 \)。其中 \( n \) 是帧序号的比特数。将 \( n = 3 \) 代入，\( 1 < W_T \leq 7 \)。发送窗口最大为7。可以有 \( 2^3 = 8 \) 个帧序号，即帧编号0～7。
(1) 对于图(a)。 第一问。\( t_0 \) 时刻到 \( t_1 \) 时刻期间，根据乙发送最后一个帧 \( R_{3,3} \)，表示乙希望甲发送3号帧，后退N帧协议(GBN)为累积确认，表明乙已经正确接收甲发送的0～2号帧，\( t_0 \) 时刻到此时刻期间，甲方可以断定乙方已正确接收了3个数据帧。 第二问。此时甲已经发送 \( S_{0,0}, S_{1,0}, S_{2,0}, S_{3,0} \) 和 \( S_{4,1} \)，甲发送的0～2号帧对应 \( S_{0,0}, S_{1,0}, S_{2,0} \)，即正确接收的是 \( S_{0,0}, S_{1,0}, S_{2,0} \)。
(2) 对于图(a)。 第一问。甲的发送窗口最大为7，在 \( t_1 \) 时刻前，甲已经发送 \( S_{0,0}, S_{1,0}, S_{2,0}, S_{3,0} \) 和 \( S_{4,1} \) 共计5个数据帧，其中乙方已正确接收了3个数据帧，还剩2个数据帧情况未知，这2个帧序号依次是3、4，甲可以将发送窗口中的剩余7-2=5个帧全部发送出去，即从 \( t_1 \) 时刻起，甲方最多还可以发送5个数据帧，这5个帧序号依次是5、6、7、0、1。
第二问。甲收到乙发来的$R_{0,1},R_{1,3},R_{3,3}$，即乙发来的0、1、3号帧，其中$S_{4,1}$对$R_{0,1}$进行了确认，即乙发来的0号帧已经被确认，剩余1、3号帧需要确认，因为后退N帧协议（GBN）为累积确认，3号帧没有按序发送，所以甲正确接收乙发来的1号帧，希望接收乙发来的2号帧，所以甲方在不出现超时且未收到乙方新的数据帧之前，可以发送的数据帧为$S_{5,2},S_{6,2},S_{7,2},S_{0,2},S_{1,2}$。其中第一个帧是$S_{5,2}$，最后一个帧是$S_{1,2}$。
第一问。在$t_1$时刻前，甲已经发送$S_{0,0},S_{1,0},S_{2,0},S_{3,2}$和$S_{4,2}$共计5个数据帧，表明甲发送了0~4号数据帧，最后收到乙发送的$R_{2,2}$数据帧，表明乙已经正确接收甲发送的0~1号数据帧，希望接收甲发送的2号数据帧，因为$S_{2,0}$超时，需要发送出错帧及其之后的帧，即甲需要重传2~4号数据帧，即从$t_1$时刻起，甲方在不出现新的超时且未收到乙方新的数据帧之前，需要重发3个数据帧。
第二问。$t_1$时刻前，甲已经正确接收$R_{2,2}$，即乙发来的2号数据帧，希望接收乙发来的3号数据帧，甲需要重传2~4号数据帧，第一个需要重传的是2号数据帧，因此，甲重发的第一个帧是$S_{2,3}$。
从发送方发送一个数据帧到发送方接收到接收方传来的确认认为一个周期。信道利用率为一个周期内发生数据的时间占该周期的比例。
甲发送一个数据帧的时延为 \( t_1 = \frac{数据帧长}{信道速率} = \frac{1000\ \text{B}}{100\ \text{Mbps}} = \frac{1000×8\ \text{bit}}{100×10^6\ \text{bit/s}} = 0.08\ \text{ms} \)，经过一个RTT = 0.96 ms，乙采用等长的数据帧进行捎带确认，接收乙发送一个数据帧的时延为 \( t_2 = t_1 = 0.08\ \text{ms} \)。一个周期 \( T = t_1 + \text{RTT} + t_2 = 1.12\ \text{ms} \)。
在一个周期内，甲可以将发送窗口中的7个数据帧全部发送出去，因此甲的最大信道利用率 \( U = \frac{7t_1}{T} = 50\% \)。