2017 年 408 真题
本节正在编写中，敬请期待。
选择题
数据结构
1
下列函数的时间复杂度是（ ）。
int func(int n) {
int i = 0, sum = 0;
while(sum < n)
sum += ++i;
return i;
}
sum += ++i; 相当于 ++i; sum = sum + i; 进行到第 k 趟循环， sum = (l+k)*k/2 。显然需要进 行 $O(n^{1/2})$ 趟循环，因此这也是该函数的时间复杂度。
2
下列关于栈的叙述中，错误的是（ ）。
（1）采用非递归方式重写递归程序时必须使用栈
（2）函数调用时，系统要用栈保存必要信息
（3）只要确定了入栈次序，即可确定出栈次序
（4）栈是一种受限的线性表，允许在其两端进行操作
I 的反例：计算斐波拉契数列迭代实现只需要一个循环即可实现。 III 的反例：入栈序列 为 1 、 2, 进行如下操作 PUSH 、 PUSH 、 POP 、 POP, 出栈次序为 2 、 1; 进行如下操作 PUSH 、 POP 、 PUSH 、 POP, 出栈次序为 1 、 2 。 IV, 栈是一种受限的线性表，只允许在一端进行操作。 因此 II 正确。
3
适用于压缩存储稀疏矩阵的两种存储结构是（）
三元组表的结点存储了行 row 、列 col 、值 value 三种信息，是主要用来存储稀疏矩阵的一种 数据结构。十字链表将行单链表和列单链表结合起来存储稀疏矩阵。邻接矩阵空间复杂度达 $O(n^{2})$, 不适千存储稀疏矩阵。二叉链表又名左孩子右兄弟表示法，可用千表示树或森林。因此 A 正确。
4
要使一颗非空二叉树的先序序列与中序序列相同，其所有非叶节点须满足的条件是（）
先序序列是先父结点，接着左子树，然后右子树。中序序列是先左子树，接着父结点，然 后右子树，递归进行。如果所有非叶结点只有右子树，先序序列和中序序列都是先父结点，然 后右子树，递归进行，因此 B 正确。
5
已知一颗二叉树的树形如下图所示，其后序序列为 e，a，c，b，d，g，f，树中与结点 a 同层的结点是（）
后序序列是先左子树，接着右子树，最后父结点，递归进行。根结点左子树的叶结点首先 被访问，它是 e 。接下来是它的父结点 a, 然后是 a 的父结点 c 。接着访问根结点的右子树。它 的叶结点 b 首先被访问，然后是 b 的父结点 d, 再者是 d 的父结点 g 。最后是根结点 f。因此 d 与 a 同层， B 正确。
6
已知字符集{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 fee f g d, 选项 D 正确。
7
已知无向图 G 含有 16 条边，其中度为 4 的顶点个数为 3，度为 3 的顶点个数为 4，其他顶点的度均小于 3。图 G 所含的顶点个数至少是（）
无向图边数的两倍等于各顶点度数的总和。由于其他顶点的度均小于 3, 可以设它们的度 都为 2, 设它们的数量是 X, 可列出方程 4x3 + 3x4 + 2x = 16x2, 解得 x = 3。4 + 3 + 3 = 11, B 正确。
8
下列二叉树中，可能成为折半查找判定树（不含外部结点）的是（）
折半查找判定树实际上 是一棵二叉排序树，它的中 序序列是一个有序序列。可以在树结点 上依次填上相应的元素，符合折半查找规则的树即是所求。 B 选项 4、5 相加除 2 向上取整，7、8 相加除 2 向下取整，矛盾。C 选项，3、4 相加除 2 向上取整，6、7 相加除 2 向下取整，矛盾。D 选项，I、10 相加除 2 向下取整，6、7 相加除 2 向上取整，矛盾。A 符合折半查找规则 ，因此正确。
9
下列应用中，适合使用 B+树的是（）
B+树是应文件系统所需而产生的 B-树的变形， 前者比后者更加适用于实际应用中的操作 系统的文件索引和数据库索引，因为前者磁盘读写代价更低，查询效率更加稳定。编译器中的 词法分析使用有穷自动机和语法树。 网络中的路由表快速查找主要靠高速缓存、 路由表压缩技 术和快速查找算法。系统一 般使用空闲空间链表管理磁盘空闲块。所以 B 正确。
10
在内部排序时，若选择了归并排序而没有选择插入排序，则可能的理由是（）
归并排序的程序代码更短
归并排序的占用空间更少
归并排序的运行效率更高
归并排序代码比选择插入排序更复杂，前者空间复杂度是 $O(n)$, 后者是 $O(1)$。但是前者时 间复杂度是 $O(nlogn)$, 后者是 $O(n^{2})$。 所以 B 正确。
11
下列排序方法中，若将顺序存储更换为链式存储，则算法的时间效率会降低的是（）
插入排序 2.选择排序 3.起泡排序 4.希尔排序 5.堆排序
插入排序、选择排序、起泡排序原本时间复杂度是 O(n2), 更换为链式存储 后的时间复杂度 还是 O(n2)。希尔排序和堆排序都利用了顺序存储的随机访问特性，而链式存储不支持这种性质， 所以时间复杂度会增加，因此选 D。
组成原理
12
假定计算机 M1 和 M2 具有相同的指令集体系结构（ISA），主频分别为 1.5GHz 和 1.2GHz。在 M1 和 M2 上运行某基准程序 P，平均 CPI 分别为 2 和 1，则程序 P 在 M1 和 M2 上运行时间的比值是（ ）。
运行时间＝指令数 xCPI/主频。Ml 的时间＝指令数 x2/1.5, M2 的时间＝指令数 xl/1.2, 两者之比为(2/1.5):(1/1.2) = 1.6。故选 C。
13
某计算机主存按字节编址，由 4 个 64M×8 位的 DRAM 芯片采用交叉编址方式构成，并与宽度为 32 位的存储器总线相连，主存每次最多读写 32 位数据。若 double 型变量 x 的主存地址为 804001AH，则读取 x 需要的存储周期数是（ ）。
由 4 个 DRAM 芯片采用交叉编址方式构成主存可知主存地址最低二位表示该字节存储的芯片编号。double 型变量占 64 位， 8 个字节。 它的主存地址 804 001 AH 最低二位是 10, 说明它从编号为 2 的 芯片开始存储（编号从 0 开始）。一 个存储周期可以对所有芯片各读取一个字节，因此需要 3 轮， 故选 C。
14
某 C 语言程序段如下：
for (i = 0; i <= 9; i++) {
temp = 1;
for (j = 0; j <= i; j++) {
temp *= a[j];
}
sum += temp;
}
下列关于数组 a 的访问局部性的描述中，正确的是（ ）。
时间局部性是一 旦一 条指令被执行， 则在不久的将来 它可能再次被执行。 空间局部性是一 旦一个存储单元被访问， 那么它附近的存储单元也很快被访问。显然， 这里的循环指令本身具 有时间局部性， 它对数组 a 的访问具有空间局部性， 故选 A。
15
下列寻址方式中，最适合按下标顺序访问一维数组元素的是
在变址操作时， 将计算机指令中的地址与变址寄存器中的地址相加， 得到有效地址， 指令 提供数组首地址， 由变址寄存器来定位数据中的各元素。所以它最适合按下标顺序访问一 维数 组元素， 故选 D。
相对寻址以 PC 为基地址， 以指令中的地址为偏移量确定有效地址。 寄存器寻址则是在指 令中指出需要使用的寄存器。直接寻址是在指令的地址字段直接指出操作数的有效地址。
16
某计算机按字节编址，指令字长固定且只有两种指令格式，其中三地址指令 29 条，二地址指令 107 条，每个地址字段为 6 位，则指令字长至少应该是（ ）。
三地址指令有 29 条， 所以它的操作码至少为 5 位。以 5 位进行计算， 它剩余 32 - 29 = 3 种操作码给二地址。而二地址另外多了 6 位给操作码， 因此它的数量最大达 3x64 = 192。所以 指令字长最少为 23 位， 因为计算机按字节编址 ， 需要是 8 的倍数， 所以指令字长至少应该是 24 位， 故选 A。
17
下列关于超标量流水线特性的叙述中，正确的是（ ）。
Ⅰ. 能缩短流水线功能段的处理时间
Ⅱ. 能在一个时钟周期内同时发射多条指令
Ⅲ. 能结合动态调度技术提高指令执行并行性
超标量是 指在 CPU 中有一条以上的流水线， 并且每个时钟周期内可以完成一 条以上的指 令，其实质是以空间换时间。I 错误，它不影响流水线功能段的处理时间； II、III 正确。故选 C。
18
下列关于主存储器（MM）和控制存储器（CS）的叙述中，错误的是（ ）。
主存储器就是我们通常说的主存， 在 CPU 外， 存储指令和数据， 由 RA M 和 ROM 实现。 控制存储器用来存放实现 指令系统的所有微指令， 是一 种只读型存储器， 机器运行时只读不写， 在 CPU 的控制器内。cs 按照微指令的地址访问， 所以 B 错误。
19
下列关于指令流水线数据通路的叙述中，错误的是（ ）。
五阶段流水线可分为取指(IF)、译码／取数(ID)、执行(EXC)、存储器读(MEM)、写回 (Write Back)。数字系统中， 各个子系统通过数据总线连接形成的数据传送路径称为数据通路， 包括程序计数器 、算术逻辑运算部件 、通用寄存器组、取指部件等， 不包括控制部件， 故选 A。
20
下列关于多总线结构的叙述中，错误的是（ ）。
多总线结构用速率高的总线连接高速设备用速率低的总线连接低速设备。一般来说，CPU 是计算机的核心， 是计算机中速度最快的设备之一， 所以 A 正确。突发传送方式把多个数据单 元作为一 个独立传输处理， 从而最大化设备的吞吐量。现实中一般用支待突发传送方式的总线 提高存储器的读写效率，B 正确。各总线通过桥接器相连， 后者起流量交换作用。PCI-Express 总线都采用串行数据包传输数据， 所以选 D。
21
I/O 指令实现的数据传送通常发生在（ ）。
I/0 端口又称 I/0 接口， 是 CPU 与设备之间的交接面。 由于主机和 I/0 设备的工作方式和 工作速度有很大差异，1/0 端口就应运而生。在执行一 条指令时，CPU 使用地址总线 选择所请 求的 I/0 端口， 使用数据总线在 CPU 寄存器和端口之间传输数据。所以选 D。
22
下列关于多重中断系统的叙述中，错误的是（ ）。
多重中断系统在保护被中断进程现场时关中断， 执行中断处理程序时开中断，B 错误。 CPU 一 般在 一 条指令执行结束的阶段采样 中断请求信号，查看是否存在中断请求，然后决定 是否响应 中断 ，A、D 正确。中断请求一 般来自 CPU 以外的事件，异常一 般发生在 CPU 内部， C 正确。
操作系统
23
假设 4 个作业到达系统的时刻和运行时间如下表所示。
| 作业 | 达到时刻 t | 运行时间 |
|---|---|---|
| $J_1$ | 0 | 3 |
| $J_2$ | 1 | 3 |
| $J_3$ | 1 | 2 |
| $J_4$ | 3 | 1 |
系统在 t=2 时开始作业调度。若分别采用先来先服务和短作业优先调度算法，则选中的作业分别是
先来先服务 调度算法是作业来得越早，优先级越高，因此会选择 JI。短作业优先调度算法 是作业运行时间越短，优先级越高，因此会选择 J3。所以 D 正确。
24
执行系统调用的过程包括如下主要操作：
①返回用户态 ②执行陷入（trap）指令
③传递系统调用参数 ④执行相应的服务程序
正确的执行顺序是（ ）。
执行 系统调用的过程是这样的：正在运行的进程先传递系统调用参数，然后由陷入(trap) 指令负责将用户态转化为内核态，并将返回地址压入堆栈以备后用 ，接下来 CPU 执行相应的内 核态服务程 序，最后返回 用户态。所以 C 正确。
25
某计算机按字节编址，其动态分区内存管理采用最佳适应算法，每次分配和回收内存后都对空闲分区链重新排序。当前空闲分区信息如下表所示。
| 分区起始地址 | 20K | 500K | 1000K | 200K |
| 分区大小 | 40KB | 80KB | 100KB | 200KB |
回收起始地址为 60K、大小为 140KB 的分区后，系统中空闲分区的数量、空闲分区链第一个分区的起始地址和大小分别是（ ）。
回收起始地址为 60K、大小为 140KB 的分区时，它与表中 第一 个分区和第四个分区合并， 成 为起始地址为 20K、大小为 380KB 的分区，剩余 3 个空闲分区。在回收内存后，算法 会对空 闲分区链按分区大小由小到大进行 排序，表中的第二个分区排第一。所以选择 B。
26
某文件系统的簇和磁盘扇区大小分别为 1KB 和 512B。若一个文件的大小为 1026B，则系统分配给该文件的磁盘空间大小是（ ）。
绝大多 数操作系统为改善磁盘访问时间，以簇为单位进行 空间分配 ，因此选 D。
27
下列有关基于时间片的进程调度的叙述中，错误的是（ ）。
进程 切换带来系统开销，切换次数越多，开销越大，A 正确。 当前进程的时间片用完后， 它的状态由执行态变为就绪态，B 错误。时钟中断是系统中特定的周期性时钟节拍。 操作系统 通过它来确定时间间隔，实现 时间的延时和任务的超时 ，C 正确。现代操作系统为了保证性能 最优，通常根据响应时间、系统开销、进程数量、进程运行时间、进程切换开销等因素确定 时 间片大小， D 正确。
28
与单道程序系统相比，多道程序系统的优点是（ ）
Ⅰ.CPU 利用率高
Ⅱ.系统开销小
Ⅲ.系统吞吐量大
Ⅳ.I/O 设备利用率高
多道程序系统通过组织作业（编码或数据 ）使 CPU 总有一 个作业可执行 ，从而提高了 CPU 的利用率、系统吞吐量和 1/0 设备利用率，I、III、IV 是优点。但系统要付出额外的开销来组织 作业和切换作业，II 错误。所以选 D。
29
下列选项中，磁盘逻辑格式化程序所做的工作是（ ）。
Ⅰ. 对磁盘进行分区
Ⅱ. 建立文件系统的根目录
Ⅲ. 确定磁盘扇区校验码所占位数
Ⅳ. 对保存空闲磁盘块信息的数据结构进行初始化
一个新的磁盘是一 个空白版，必须分成扇区以便磁盘控制器能读和写，这个过程称为低级 格式化（或物理格式化）。低级格式化为磁盘的每个扇区采 用特别的数据结构，包括校验码，III 错误。 为了使用 磁盘 存储文件，操作系统还需要将其数据结构记录在 磁盘上。这 分为两步。第 一 步是将磁盘 分为由一 个或多个柱面组成的分区，每个分区可以作为一 个独立的磁盘 ，I 错误。 在分区之后，第二步是逻辑格式化（创建文件系统）。在这 一 步，操作系统将初始的文件系统数 据结构存储到磁盘上。这些数据结构 包括空闲和已分配的空间和一 个初始 为空的目录，II、IV 正确。所以选 B。
30
某文件系统中，针对每个文件，用户类别分为 4 类：安全管理员、文件主、文件主的伙伴、其他用户；访问权限分为 5 种：完全控制、执行、修改、读取、写入。若文件控制块中用二进制位串表示文件权限，为表示不同类别用户对一个文件的访问权限，则描述文件权限的位数至少应为（ ）。
可以把用户访问权限抽象为一 个矩阵，行代表用户 ，列代表访问权限。这个矩阵有 4 行 5 列，1 代表 true, 0 代表 false, 所以需要 20 位， 选 D。
31
若文件 f1 的硬链接为 f2，两个进程分别打开 f1 和 f2，获得对应的文件描述符为 fd1 和 fd2，则下列叙述中，正确的是（ ）。
Ⅰ. f1 和 f2 的读写指针位置保持相同
Ⅱ. f1 和 f2 共享同一个内存索引结点
Ⅲ. fd1 和 fd2 分别指向各自的用户打开文件表中的一项
硬链接指通过索引结点进行连接。一个文件在 物理存储器上有一 个索引节点号。存在多个 文件名指向同 一个索引节点，II 正确。 两个进程各自维护自己的文件描述符，III 正确，I 错误。 所以选择 B。
32
系统将数据从磁盘读到内存的过程包括以下操作：
① DMA 控制器发出中断请求
② 初始化 DMA 控制器并启动磁盘
③ 从磁盘传输一块数据到内存缓冲区
④ 执行“DMA 结束”中断服务程序
正确的执行顺序是（ ）。
在开始 DMA 传输时，主机向内存写入 DMA 命令块 ，向 DMA 控制器写入该命令块的地 址，启动 1/0 设备。 然后，CP U 继续其他工作， DMA 控制器则继续下去直接操作内存总线， 将地址放到总线上 开始传输。当整个传输完成后，DMA 控制器中断 CPU。因此执行顺序是 2, 3, l, 4, 选 B。
计算机网络
33
假设 OSI 参考模型的应用层欲发送 400B 的数据（无拆分），除物理层和应用层之外，其他各层在封装 PDU 时均引入 20B 的额外开销，则应用层数据传输效率约为（ ）。
OSI 参考模型共 7 层，除去物理层和应用 层，剩五层。 它们会向 PD U 引入 20Bx5 = lOOB 的额外开销。 应用层是最顶层 ，所以它 的数据传输效率为 400B/500B=80%, 选 A。
34
若信道在无噪声情况下的极限数据传输速率不小于信噪比为 30dB 条件下的极限数据传输速率，则信号状态数至少是（ ）。
可用奈奎斯特采样定理计算无噪声情况下的极限数据传输速率， 用香农第二定理计算有噪信道极限数据传输速率。 $2W log_{2}N \ge W log_{2}(1 + S/N)$, $W$ 是信道带宽，$N$ 是信号状态数 ，$S/N$ 是信噪比，将数据代入计算可得 $N \ge 32$, 选 D。 分贝数= $10 log_{10}(S/N)$。
35
在下图所示的网络中，若主机 H 发送一个封装访问 Internet 的 IP 分组的 IEEE 802.11 数据帧 F，则帧 F 的地址 1、地址 2 和地址 3 分别是（ ）。
IEEE 802.11 数据帧有四种子类型，分别是 IBSS 、 From AP、 ToAP、 WDS。 这里的数据帧 F 是从笔记本电脑发送往访问接入点(AP),所以属于 To AP 子类型。这种帧地址 l 是 RA (BSSID), 地址 2 是 SA, 地址 3 是 DA。 RA 是 Receiver Address 的缩写，BSSI D 是 basic service set identifier 的缩写，SA 是 source address 的缩写，DA 是 destination address 的缩写。 因此地址 1 是 AP 的 MAC, 地址 2 是 H 的 MAC, 地址 3 是 R 的 MAC, 选 B。
36
下列 IP 地址中，只能作为 IP 分组的源 IP 地址但不能作为目的 IP 地址的是（ ）。
根据 RFC 文档描述，0.0.0.0/32 可以作为本主机在本网络上的源地址。 127.0.0.1 是回送地 址，以它 为目的 IP 地址的数据将被立即返回到本机。200.10.10.3 是 C 类 IP 地址。255.255.255.255 是广播地址。
37
直接封装 RIP、OSPF、BGP 报文的协议分别是（ ）。
RIP 是一种分布式的基于距离向量的路由选择协议，通过广播 U DP 报文来交换路由信息。 OSPF 是一个内部网关协议，不使用 传输协议，如 UDP 或 TCP, 而是直接用 IP 包封装它的数 据。 BGP 是一个外部网关协议， 用 TCP 封装它的数据。 因此选 D。
38
若将网络 21.3.0.0/16 划分为 128 个规模相同的子网，则每个子网可分配的最大 IP 地址个数是（ ）。
这个网络有 16 位的主机号，平均分成 128 个规模相同的子网，每个子网有 7 位的子网号，9 位的主机号。除去一个网络地址和广播地址，可分配的最大 1P 地址个数是 29-2=512-2=510, 故选 C。
39
若甲向乙发起一个 TCP 连接，最大段长 MSS=1KB，RTT=5ms，乙开辟的接收缓存为 64KB，则甲从连接建立成功至发送窗口达到 32KB，需经过的时间至少是（ ）。
按照慢开始算法，发送窗口 = min{ 拥塞窗口，接收窗口｝，初始的拥塞窗口为最大报文段 长度 1KB 海经过一个 RTT, 拥塞窗口翻倍，因此需至少经过 5 个 RTT, 发送窗口才能达到 32KB, 所以选 A。 这里假定乙能及时处理接收到的数据，空闲的接收缓存 ≥ 32KB。
40
下列关于 FTP 协议的叙述中，错误的是（ ）。
FTP 协议使用控制连接和数据连接，控制连接存在于整个 FTP 会话过程中，数据连接在每 次文件传输时才建立，传输结束就关闭，A 和 B 是正确的。默认情况下 FTP 协议使用 TCP 20 端口进行 数据连接，TCP 21 端口进行控制连接。 但是是否使用 TCP 20 端口建立数据连接与传 输模式 有关，主动方式使用 TCP20 端口， 被动方式由服务器和客户端自行协商决定，C 错， D 对。所以选 C。
解答题
数据结构
41
请设计一个算法，将给定的表达式树（二叉树）转换为等价的中缀表达式（通过括号反映操作符的计算次序）并输出。例如，当下列两棵表达式树作为算法输入时：
输出的中缀表达式分别为 (a+b)∗(c∗(−d)) 和 (a∗b)+(−(c−d)) 。
二叉树结点的定义如下：
typedef struct node{
char data[10]; // 存储操作数或操作符
struct node *left, *right;
}BTree;
要求：
(1) 给出算法的基本设计思想。
(2) 根据设计思想，采用 C 或 C++语言描述算法，关键之处给出注释。
42
使用 Prim（普里姆）算法求带权连通图的最小（代价）生成树（MST）。请回答下列问题。
(1) 对下列图 G，从顶点 A 开始求 G 的 MST，依次给出按算法选出的边。
(2) 图 G 的 MST 是唯一的吗？
(3) 对任意的带权连通图，满足什么条件时，其 MST 是唯一的？
组成原理
43
已知，计算 f(n)的 C 语言函数 f1 如下：
int f1(unsigned n) {
int sum=1, power=1;
for(unsigned i=0; i<= n -1; i ++) {
power * = 2;
sum += power;
}
return sum ;
}
将 f1 中的 int 都改为 float，可得到计算 f(n)的另一个函数 f2。假设 unsigned 和 int 型数据都占 32 位，float 采用 IEEE754 单精度标准。请回答下列问题。
(1) 当 n=0 时，f1 会出现死循环，为什么？若将 f1 中的变量 i 和 n 都定义为 int 型，则 f1 是否还会出现死循环？为什么？
(2) f1(23)和 f2(23) 的返回值是否相等？机器数各是什么（用十六进制表示）？
(3) f1(24)和 f2(24) 的返回值分别为 33554431 和 33554432.0，为什么不相等？
(4) f(31)= 2^32−1 ，而 f1(31)的返回值却为-1，为什么？若使 f1(n)的返回值与 f(n)相等，则最大的 n 是多少？
(5) f2(127)的机器数为 7F80 0000H，对应的值是什么？若使 f2(n)的结果不溢出，则最大的 n 是多少？若使 f2(n)的结果精确（无舍入），则最大的 n 是多少？
44
在按字节编址的计算机 M 上，题 43 中 f1 的部分源程序（阴影部分）与对应的机器级代码（包括指令的虚拟地址）如下图所示。
int f1(unsigned n)
1 00401020 55 push ebp
... ... ...
for (unsigned i = 0; i <= n-1; i++) {
... ... ...
20 0040105E 39 4D F4 cmp dword ptr [ebp-0Ch],ecx
... ... ...
power *= 2;
... ... ...
23 00401066 D1 E2 shl edx,1
... ... ...
return sum;
... ... ...
35 0040107F C3 ret
其中，机器级代码行包括行号、虚拟地址、机器指令和汇编指令。
请回答下列问题。
(1) 计算机 M 是 RISC 还是 CISC？为什么？
(2) f1 的机器指令代码共占多少字节？要求给出计算过程。
(3) 第 20 条指令 cmp 通过 i 减 n-1 实现对 i 和 n-1 的比较。执行 f1(0)过程中，当 i=0 时，cmp 指令执行后，进/借位标志 CF 的内容是什么？要求给出计算过程。
(4) 第 23 条指令 shl 通过左移操作实现了 power2 运算，在 f2 中能否也用 shl 指令实现 power2？为什么？
操作系统
45
假定题 44 给出的计算机 M 采用二级分页虚拟存储管理方式，虚拟地址格式如下：
页目录号（位）页表索引（位）页内偏移量（位）页目录号（10 位）页表索引（10 位）页内偏移量（12 位）
请针对题 43 的函数 f1 和题 44 中的机器指令代码，回答下列问题。
(1) 函数 f1 的机器指令代码占多少页？
(2) 取第 1 条指令（push ebp）时，若在进行地址变换的过程中需要访问内存中的页目录和页表，则会分别访问它们各自的第几个表项（编号从 0 开始）？
(3) M 的 I/O 采用中断控制方式。若进程 P 在调用 f1 之前通过 scanf() 获取 n 的值，则在执行 scanf() 的过程中，进程 P 的状态会如何变化？CPU 是否会进入内核态？
46
某进程中有 3 个并发执行的线程 thread1、thread2、thread3，其伪代码如下所示。
//复数的结构类型定义
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;
w=add(x,y);
...
}
thread2
{
cnum w;
w=add(y,z);
...
}
thread3
{
cnum w;
w.a=1;
w.b=2;
z=add(z,w);
y=add(y,w);
...
}
请添加必要的信号量和 P、V（或 wait()、signal()）操作，要求确保线程互斥访问临界资源，并且最大程度地并发执行。
计算机网络
47
甲乙双方均采用后退 N 帧协议 (GBN) 进行持续的双向数据传输，且双方始终采用捎带确认，帧长均为 1000 B。 Sx,y 和 Rx,y 分别表示甲方和乙方发送的数据帧，其中：x 是发送序号；y 是确认序号（表示希望接收对方的下一帧序号）；数据帧的发送序号和确认序号字段均为 3 比特。信道传输速率为 100 Mbps，RTT = 0.96 ms。下图给出了甲方发送数据帧和接收数据帧的两种场景，其中 t0 为初始时刻，此时甲方的发送和确认序号均为 0， t1 时刻甲方有足够多的数据待发送。
请回答下列问题。
(1) 对于图(a)， t0 时刻到 t1 时刻期间，甲方可以断定乙方已正确接收的数据帧数是多少？正确接收的是哪几个帧（请用 Sx,y 形式给出）？
(2) 对于图(a)，从 t1 时刻起，甲方在不出现超时且未收到乙方新的数据帧之前，最多还可以发送多少个数据帧？其中第一个帧和最后一个帧分别是哪个（请用 Sx,y 形式给出）？
(3) 对于图(b)，从 t1 时刻起，甲方在不出现新的超时且未收到乙方新的数据帧之前，需要重发多少个数据帧？重发的第一个帧是哪个（请用 Sx,y 形式给出）？
(4) 甲方可以达到的最大信道利用率是多少？