# 2020年全国硕士研究生招生考试计算机科学与技术学科联考计算机学科专业基础综合试题
# 一、单项选择题：1~40小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项符合题意要求。
1. 将一个 $10 * 10$ 对称矩阵 M 的上三角部分的元素素 $m_{ij} (1 \leqslant i \leqslant j \leqslant 10)$ 按列优先存入 C语言的一维数组 N 中, 元素 $m_{7,2}$ 在 N 中的下标是:
A、15
B、16
C、22
D、23
2. 对空栈 S 进行 Push 与 Pop 操作，入栈序列 a, b, c, d, e 经过 Push，Push，Pop，Push，Pop，Push，Pop 操作后得到的出栈序列是
A、b,a,c
B、b,a,e
C、b,c,a
D、b,c,e
3. 对, 任意一棵高度为 5 且有 10 个节点的二叉树, 若采用顺序存储结构保存, 每个结点占 1 个存储单元 (仅存放结点的数据信息), 则存放该二叉树需要的存储单元数量至少是:
A、31
B、16
C、15
D、10
4. 已知森林 F 及与之对应的二叉树 T，若 F 的先根遍历序列是 a, b, c, d, e, f，中根遍历序列是 b, a, d, f, e, c 则 T 的后根遍历序列是：
A、b,a,d,f,e,c
B、b,d,f,e,c,a
C、b,f,e,d,c,a
D、f,e,d,c,b,a
5. 下列给定的关键字输入序列中，不能生成如下二叉排序树的是：
A、4，5，2，1，3
B、4，5，1，2，3
C、4，2，5，3，1
D、4，2，1，3，5
6. 修改递归方式实现的图的深度优先搜索（DFS）算法，将输出（访问）定点信息的语句移到退出递归前（即执行输出语句后立刻退出递归）。采用修改后的算法遍历有向无环图 G，若输出结果中包含 G 中的全部顶点，则输出的顶点序列是 G 的：
A、拓扑有序序列
B、逆拓扑有序序列
C、广度优先搜索序列
D、深度优先搜索序列
7. 已知无向图 G 如下所示，使用克鲁斯卡尔（Kruskal）算法求图 G 的最小生成树，加入到最小生成树中的边依次是：
A、(b,f)(b,d)(a,e)(c,e)(b,e)
B、(b,f)(b,d)(b,e)(a,e)(e,c)
(不确定最后一个括号的内容)
C、(a,e)(b,e)(c,e)(b,d)(b,f)
D、(a,e)(c,e)(b,e)(b,f)(b,d)
8. 若使用AOE网估算工程进度，则下列叙述中正确的是：
A、关键路径是从原点到汇点边数最多的一条路径
B、关键路径是从原点到汇点路径长度最长的路径
C、增加任一关键活动的时间不会延长工程的工期
D、缩短任一关键活动的时间将会缩短工程的工期
9. 下列关于大根堆（至少含 2 个元素）的叙述中正确的是：
1. 可以将堆看成一棵完全二叉树
II. 可采用顺序存储方式保存堆；
III. 可以将堆看成一棵二叉排序树;
IV. 堆中的次大值一定在根的下一层。
A、I, II
B、I, II, IV
C、Ⅱ,Ⅲ
D、II,III,IV
10. 依次将关键字 5, 6, 9, 13, 8, 2, 12, 15 插入初始为空的 4 阶 B 树后，根节点中包含的关键字是：
A、8
B、6,9
C、8, 13
D、9, 12
11. 对大部分元素已有序的数组进行排序时，直接插入排序比简单选择排序效率更高，其原因是：
1、直接插入排序过程中元素之间的比较次数更少
II、直接插入排序过程中所需要的辅助空间更少
III、直接插入排序过程中元素的移动次数更少
A、I
B、III
C、Ⅰ,Ⅱ
D、I,II,III
12. 下列给出的部件中其位数（宽度）一定与机器字长相同的是：
1、ALU；
II、指令寄存器；
III、通用寄存器；
IV、浮点寄存器
A、I, II
B、I, III
C、Ⅱ,Ⅲ
D、II,III,IV
13. 已知带符号整数用补码表示, float 型数据用 IEEE 754 标准表示, 假定变量 $x$ 的类型只能是 int 或 float。当 $x$ 的机器数为 C8000000H时, $x$ 的值可能是:
A、-7×2²7
B、-216
C、 $2^{17}$
D、 $25 \times 2^{27}$
14. 在按字节编址，采用小端方式的 32 位计算机中，按边界对齐方式为以下 C 语言结构型变量 a 分配存储空间。
Struct record{
short x1;
int x2;
}a;
若 a 的首地址为 2020 FE00H，a 的成员变量 x2 的机器数为 12340000H，则其中 34H 所在存储单元的地址是：
A、2020 FE03H
B、2020 FE04H
C、2020 FE05H
D、2020 FE06H
15. 下列关于 TLB 和 Cache 的叙述中错误的是:
A、命中率与程序局部性有关；
B、缺失后都需要去访问主存；
C、缺失处理都可以由硬件实现；
D、都由DRAM存储器组成。
16. 某计算机采用 16 位定长指令字格式, 操作码位数和寻址方式位数固定, 指令系统有 48 条指令, 支持直接、间接、立即、相对 4 种寻址方式, 单地址指令中直接寻址方式可寻址范围是:
A、0~225;
B、0~1023;
C、-128~127;
D、-512~511;
17. 下列给出的处理器类型中理想情况下 CPI 为 1 的是:
I、单周期CPU； II、多周期CPU；
III、基本流水线 CPU; IV 超标量流水线 CPU
A、I, II;
B、I,III;
C、II,IV;
D、III,IV;
18. 下列关于“自陷”（Trap，也称陷阱）的叙述中错误的是：
A、自陷是通过陷阱指令预先设定的一类外部中断事件；
B、自陷可用于实现程序调试时的断点设置和单步跟踪；
C、自陷发生后 CPU 将转去执行操作系统内核相应程序；
D、自陷处理完成后返回到陷阱指令的下一条指令执行。
19. QPI 总线是一种点对点全工双周同步串行总线，总线上的设备可同时接收和发送信息，每个方向可同时传输 20 位信息（16 位数据+4 位校验位），每个 QPI 数据包有 80 位信息，分 2 个时钟周期传送，每个时钟周期传递 2 次，因此 QPI 总线带宽为每秒传送次数*2B*2。若 QPI 时钟频率为 $2.4\mathrm{GHz}$ ，则总线带宽为：
A、4.8
B、9.6
C、19.2
D、38.4
（单位GB/s）
20. 下列事件中属于外部中断事件的是：
I、访存时缺页；II、定时器延时（不确定）；III、网络数据包到达
A、I,II;
B、I,II,IV;
C II,III;
D II,III,IV.
21. 外部中断包括不可屏蔽中断（NMI）和可屏蔽中断，下列关于外部中断的叙述中错误的是：
A、CPU 处于关中断状态时也能响应 NMI 请求；
B、一旦可屏蔽中断请求信号有效，CPU 将立即响应；
C、不可屏蔽中断的优先级比可屏蔽中断的优先级高；
D、可通过中断屏蔽字改变可屏蔽中断的处理优先级。
22. 若设备采用周期挪用 DMA 方式进行输入输出，每次 DMA 传送的数据块大小为 512 字节，相应的 I/O 接口中有一个 32 位数数据缓冲寄存器，对于数据输入过程，下列叙述中错误的是：
A、每准备好 32 位数据，DMA 控制器就发出一次总线请求；
B、相对于 CPU，DMA 控制器的总线使用权的优先级更高；
C、在整个数据块的传送过过程中，CPU 不可以访问主存储器；
D、数据块传送结束时，会产生“DMA 传送结束”的中断请求。
23. 若多个进程共享同一个文件 F，则下列叙述中正确的是：
A、个进程只能用“读”方式打开文件 F;
B、在系统打开文件表中仅有一个表项包含 F 的属性；
C、各进程的用户打开文件表中关于 F 的表项内容相同；
D、进程关闭 F 时系统删除 F 在系统打开文件表中的表项。
24. 下列选项中支持文件长度可变，随机访问的磁盘存储空间分配方式是：
A、索引分配；
B、链接分配；
C、连续分配；
D、动态分区分配。
25. 下列与中断相关的操作中，由操作系统完成的是：
I、保存被中断程序的中断点 II、提供中断服务
III、初始化中断向量表
IV、保存中断屏蔽字
A、I,II;
B、I,II,IV;
C III,IV;
D II,III,IV.
26. 下列与进程调度有关的因素中在设计多级反馈队列调度算法时需要考虑的是:
I 就绪队列的数量 II 就绪队列的优先级
III 各就绪队列的调度算法 IV 进程在就绪队列间的迁移条件
A、I,II;
B、III,IV;
C、II,III,IV;
D I,II,III,IV
27. 某系统中有 A,B 两类资源各 6 个, t 时刻资源分配及需求情况如下表所示
| 进程 | A已分配数量 | B已分配数量 | A需求总量 | B需求总量 |
| P1 | 2 | 3 | 4 | 4 |
| P2 | 2 | 1 | 3 | 1 |
| P3 | 1 | 2 | 3 | 4 |
t时刻安全检测结果是：
A、存在安全序列 P1,P2,P3;
B、存在安全序列 P2,P1,P3;
C、存在安全序列 P2,P3,P1;
D、不存在安全序列。
28. 下列因素影响请求分页系统有效（平均）访存时间的是：
1、缺页率；
II、磁盘读写时间；
III、内存访问时间；
IV 执行缺页处理程序的 CPU 时间；
A、Ⅱ,Ⅲ
B、I,IV
C、I,III,IV
D、I,II,III,IV
29. 下列关于父进程与子进程的叙述中错误的是:
A、父进程与子进程可以并发执行
B、父进程与子进程共享虚拟地址空间
C、父进程与子进程有不同的进程控制块
D、父进程与子进程不能同时使用同一临界资源
30. 对于具备设备独立性的系统下列叙述中错误的是：
A、可以使用文件名访问物理设备；
B、用户程序使用逻辑设备与物理设备之间的映射关系
D、更换物理设备后必须修改访问该设备的应用程序。(缺一个选项)
31. 某文件系统的目录由文件名和索引节点号构成。若每个目录项长度为 64 字节, 其中 4个字节存放索引节点号, 60 个字节存放文件名。文件名由小写英文字母构成, 则该文件系统能创建的文件数量的上限为:
A、 $2^{26}$
B、 $2^{32}$
C、 $2^{60}$
D、 $2^{64}$
32. 下列准则中实现临界区互斥机制必须遵循的是：
I、两个进程不能同时进入临界区
II、允许进程访问空闲的临界资源
III、进程等待进入临界区的时间是有限的
IV、不能进入临界区的执行态进程立即放弃CPU
A、I,IV
B、II,III
C、I,II,III
D、I,III,IV
33. 下图描述的协议要素是:
I、语法 II、语义 III、时序
A. I
B. II
C. III
D. I, II, III
34. 下列关于虚电路网络的叙述中错误的是：
A、可以确保数据分组传输顺序
B、需要为每条虚电路预分配带宽
C、建立虚电路时需要进行路由选择
D、依据虚电路号（VCID）进行数据分组转发
35. 下图所示的网络冲突域和广播域的个数分别是：
A、2，2;
B、2，4；
C、4, 2;
D、4，4;
36. 假设主机采用停-等协议向主机乙发送数据帧, 数据帧长与确认帧长均为 1000B。数据传输速率是 10kbps, 单项传播延时是 200ms。则甲的最大信道利用率:
A、80%;
B、66.7%;
C、44.4%;
D、40%
37. 某 IEEE 802.11 无线局域网中主机 H 与 AP 之间发送或接收 CSMA/CA 帧的过程如下图所示，在 H 或 AP 发送帧前所等待的帧间间隔时间（IFS）中最长的是：
A、IFS1
B、IFS2
C、IFS3
D、IFS4
38. 若主机甲与主机乙已建立一条 TCP 连接，最大段长（MSS）为 1KB，往返时间（RTT）为 2ms，则在不出现拥塞的前提下，拥塞窗口从 8kB 增长到 32KB 所需的最长时间是：
A、4ms B、8ms
C、24ms
D、48ms
39. 若主机甲与主机乙建立 TCP 连接时发送的 SYN 段中的序号为 1000，在断开连接时，甲发送给乙的 FIN 段中的序号为 5001，则在无任何重传的情况下，甲向乙已经发送的应用层数据的字节数为：
A、4002
B、4001
C、4000
D、3999
40. 假设下图所示网络中的本地域名服务器只提供递归查询服务，其他域名的服务器均只提供迭代查询服务；局域网内主机访问 Internet 上各服务器的往返时间 (RTT) 均为 10ms，忽略其他各种时延，若主机 H 通过超链接 http://www.acb.com/index.html，请求浏览纯文本 Web 页 index.html，则从点击超链接开始到浏览器接收到 index.html 页面为止，所需最短、最长时间分别是：
A、10ms, 40ms
B、10ms,50ms
C、20ms,40ms
D、20ms,50ms
# 二、综合应用题：41~47小题，共70分。
41. 定义三元组 $(a, b, c)$ （ $a, b, c$ 均为正数）的距离 $D = |a - b| + |b - c| + |c - a|$ . 给定 3 个非空整数集合 S1, S2, S3，按升序分别存储在 3 个数组中。请设计一个尽可能高效的算法，计算并输出所有可能的三元组 $(a, b, c)$ （ $a \in S1, b \in S2, c \in S3$ ）中的最小距离。例如 $S1 = \{-1, 0, 9\}$ , $S2 = \{-25, -10, 10, 11\}$ , $S3 = \{2, 9, 17, 30, 41\}$ 则最小距离为 2，相应的三元组为 $(9, 10, 9)$ 要求：
(1)给出算法的基本设计思想;
(2)根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释；
(3)说明你所设计算法的时间复杂度和空间复杂度。
42. 若任一个字符的编码都不是其他字符编码的前缀，则称这种编码具有前缀特性。现有某字符集（字符个数 $\geqslant 2$ ）的不等长编码，每个字符的编码均为二进制的 0, 1 序列，最长为 L 位，且具有前缀特性。请回答下列问题：
(1) 哪种数据结构适宜保存上述具有前缀特性的不等长编码？
(2) 基于你所设计的数据结构, 简述从 $0 / 1$ 串到字符串的译码过程
(3) 简述判定某字符集的不等长编码是否具有前缀特性的过程
43. 有实现 $x*y$ 的两个 C 语言函数如下：
```c
unsigned umul ( unsigned x, unsigned y) { return x*y; } int imul ( int x, int y ) { return x*y; }
```
假定某计算机 M 中 ALU 只能进行加减运算和逻辑运算。请回答:
(1) 若 M 的指令系统中没有乘法指令, 但有加法、减法和位移等指令, 则在 M 上也能实现上述两个函数中的乘法运算, 为什么?
(2) 若 M 的指令系统中有乘法指令, 则基于 ALU、位移器、寄存器以及相应控制逻辑实现乘法指令时, 控制逻辑的作用是什么?
(3) 针对以下 3 种情况: (a) 没有乘法指令; (b) 有使用 ALU 和位移器实现的乘法指令; (c) 有使用阵列乘法器实现的乘法指令, 函数 umul()在哪种情况下执行时间最长?哪种情况下执行的时间最短? 说明理由
(4) n 位整数乘法指令可保存 2n 位乘积, 当仅取低 n 位作为乘积时, 其结果可能会发生溢出。当 $n = 32, x = 2^{31} - 1$ , $y = 2$ 时, 带符号整数乘法指令和无符号整数乘法指令得到的 $x * y$ 的 2n 位乘积分别是什么 (用十六进制表示)? 此时函数 umul() 和 imul() 的返回结果是否溢出? 对于无符号整数乘法运算, 当仅取乘积的低 n 位作为乘法结果时, 如何用 2n 位乘积进行溢出判断?
44. 假定主存地址为 32 位, 按字节编址, 指令 Cache 和数据 Cache 与主存之间均采用 8 路组相联映射方式, 直写 (Write Through) 写策略和 LRU 替换算法, 主存块大小为 64B, 数据区容量各为 $32 \mathrm{KB}$ 。开始时 Cache 均为空, 请回答下列问题:
(1) Cache 每一行中标记 (Tag)、LRU 位各占几位? 是否有修改位?
(2) 有如下 C 语言程序段:
$$
\begin{array}{l} f o r (k = 0; k < 1 0 2 4; k + +) \\ S [ k ] = 2 * s [ k ]; \\ \end{array}
$$
若数组 S 及其变量 k 均为 int 型，int 型数据占 4B，变量 k 分配在寄存器中，数组 s 在主存中的起始地址为 008000C0H，则该程序段执行过程中，访问数组 S 的数据 Cache 缺失次数为多少？
(3) 若 CPU 最先开始的访问操作是读取主存单元 0001003H 中的指令, 简要说明从 Cache 中访问该指令的过程, 包括 Cache 缺失处理过程。
45. 现有 5 个操作 A、B、C、D 和 E，操作 C 必须在 A 和 B 完成后执行，操作 E 必须在 C 和 D 完成后执行，请使用信号量的 wait(), signal(), 操作（P、V 操作）描述上述操作之间的同步关系，并说明所用信号量及其初值。
46. 某 32 位系统采用基于二级页表的请求分页存储管理方式, 按字节编址, 页目录项和页表项长度均为 4 字节, 虚拟地址结构如下:
| 页目录号（10位） | 页号（10位） | 页内偏移量（12位） |
某 C 程序中数组 a[1024][1024]的起始虚拟地址为 1080 0000H，数组元素占 4 字节，该程序运行时，其进程的页目录起始物理地址为 0020 1000H，请回答下列问题：
(1) 数组元素 a[1][2]的虚拟地址是什么? 对应的页目录号和页号分别是什么? 对应的页目录项的物理地址是什么? 若该目录项中存放的页框号为 00301H, 则 a[1][2]所在页对应的页表项的物理地址是什么?
(2) 数组 a 在虚拟地址空间中所占区域是否必须连续? 在物理地址空间中所占区域是否必须连续?
(3) 已知数组 a 按行优先方式存放, 若对数组 a 分别按行遍历和按列遍历, 则哪一种遍历方式的局部性更好?
47. 某校园网有两个局域网，通过路由器 R1、R2 和 R3 互联后接入 Internet，S1 和 S2 为以太网交换机，局域网采用静态 IP 地址配置，路由器部分接口以及各主机的 IP 地址如图所示：
假设NAT转换表结构为：
请回答下列问题：
(1) 为使 H2 和 H3 能够访问 Web 服务器 (使用默认端口号), 需要进行什么配置?
(2) 若 H2 主动访问 Web 服务器时, 将 HTTP 请求报文封装到 IP 数据报 P 中发送,则 H2 发送 P 的源 IP 地址和目的 IP 地址分别是? 经过 R3 转发后, P 的源 IP 地址和目的 IP 地址分别是? 经过 R2 转发后, P 的源 IP 地址和目的 IP 地址分别是?
# 2020年计算机学科专业基础综合试题
# 参考答案
# 选择题：
1. 将一个 $10 * 10$ 对称矩阵 M 的上三角部分的元素素 $m_{ij} (1 \leqslant i \leqslant j \leqslant 10)$ 按列优先存入 C 语言的一维数组 N 中, 元素 $m_{7,2}$ 在 N 中的下标是:
A、15
B、16
C、22
D、23
【答案】C
【解析】
上三角矩阵列优先的存储模式：先存储具有一个元素第一列，再存储具有两个元素的第二列，以此类推
$m_{7,2}$ 说明 1-6 列均已存满，，故此元素是第 $1 + 2 + 3 + 4 + 5 + 6 + 2$ 个被存储单元
【注意!】C语言数组的下标从0开始
故 $m_{7,2}$ 在 $\mathrm{N}$ 中的下标为 $23 - 1 = 22$ ，即 $\mathrm{N}[22]$
2. 对空栈 S 进行 Push 与 Pop 操作，入栈序列 a, b, c, d, e 经过 Push，Push，Pop，Push，Push，Pop 操作后得到的出栈序列是
A、b,a,c
B、b,a,e
C、b,c,a
D、b,c,e
【 】D
【解析】
| 操作 | 执行该操作后的栈(左侧为栈底) | 出栈元素 |
| Push | a | |
| Push | ab | |
| Pop | a | b |
| Push | ac | |
| Pop | a | c |
| Push | ad | |
| Push | ade | |
| Pop | ad | e |
3. 对于任意一棵高度为 5 且有 10 个节点的二叉树, 若采用顺序存储结构保存, 每个结点占 1 个存储单元 (仅存放结点的数据信息), 则存放该二叉树需要的存储单元数量至少是:
A、31
B、16
C、15
D、10
【答案】A
【解析】
本二叉树使用顺序结构存储时，为了保证任意性，其1-5层的所有节点（包括空节点）全部都要被存储起来，即考虑成一棵5层的满二叉树，存储单元大小为 $1 + 2 + 4 + 8 + 16 = 31$
4. 已知森林 F 及与之对应的二叉树 T，若 F 的先根遍历序列是 a, b, c, d, e, f，中根遍历序列是 b, a, d, f, e, c 则 T 的后根遍历序列是：
A、b,a,d,f,e,c
B、b,d,f,e,c,a
C、b,f,e,d,c,a
D、f,e,d,c,b,a
【答案】C
【解析】
任何 $n$ 个不同节点的二叉树, 都可由它的中序序列和先序序列唯一确定。
# 此二叉树T对应的后根遍历序列是bfedca
5. 下列给定的关键字输入序列中，不能生成如下二叉排序树的是：
A、4，5，2，1，3
B、4，5，1，2，3
C、4, 2, 5, 3, 1
D、4, 2, 1, 3, 5
【答案】B
【解析】基本概念题。
B 选项构造出的二叉排序树
6. 修改递归方式实现的图的深度优先搜索（DFS）算法，将输出（访问）定点信息的语句移到退出递归前（即执行输出语句后立刻退出递归）。采用修改后的算法遍历有向无环图 G，若输出结果中包含 G 中的全部顶点，则输出的顶点序列是 G 的：
A、拓扑有序序列
B、逆拓扑有序序列
C、广度优先搜索序列
D、深度优先搜索序列
【答案】B
【解析】
DFS 是一个递归算法, 在遍历的过程中, 先访问的点被压入栈底。拓扑有序是指如果点 U 到点 V 有一条弧, 则在拓扑序列中 U 一定在 V 之前。深度优先算法搜索路径恰恰是一条弧, 栈的输出是从最后一个被访问点开始输出, 最后一个输出的点是第一个被访问的点。所以是逆拓扑有序序列
7. 已知无向图 G 如下所示，使用克鲁斯卡尔（Kruskal）算法求图 G 的最小生成树，加入到最小生成树中的边依次是：
A、(b,f)(b,d)(a,e)(c,e)(b,e)
B、(b,f)(b,d)(b,e)(a,e)(e,c)
(不确定最后一个括号的内容)
C、(a,e)(b,e)(c,e)(b,d)(b,f)
D、(a,e)(c,e)(b,e)(b,f)(b,d)
【答案】A
【解析】
Kruskal 算法：按权值递增次序选择合适的边构造最小生成树
基本思想：按照权值的递增顺序选择 n-1 条边，并保证这 n-1 条边不构成回路。
具体做法：首先构造一个只含 $n$ 个顶点的森林，然后依权值从小到大从连通网中选择边加入到森林中，并使森林中不产生回路，直至森林变成一棵树为止。
第1步：选取边
边 $< b,f>$ 的权值最小，因此将它加入到最小生成树中。
第2步：选取边
上一步操作之后，边的权值最小，将它加入到最小生成树结果中。
第3步：选取边
上一步操作之后，边 $< d, f>$ 的权值最小，但 $< d, f>$ 会和已有的边构成回路；因此，跳过边 $< d, f>$ ，将边 $< a, e>$ 它加入到最小生成树中。
第4步：选取边
上一步操作之后，边的权值最小，将它加入到最小生成树中。
第5步：选取边
上一步操作之后，边的权值最小，将它加入到最小生成树中。
此时，最小生成树构造完成，它包括的边是： $< b, f > < b, d > < a, e > < c, e > < b, e >$
8. 若使用AOE网估算工程进度，则下列叙述中正确的是：
A、关键路径是从原点到汇点边数最多的一条路径
B、关键路径是从原点到汇点路径长度最长的路径
C、增加任一关键活动的时间不会延长工程的工期
D、缩短任一关键活动的时间将会缩短工程的工期
【答案】B
【解析】基础概念题。
关键路径（critical path）：在AOE网中，从源点到汇点的所有路径中具有最大路径长度的路径
9. 下列关于大根堆（至少含 2 个元素）的叙述中正确的是：
1. 可以将堆看成一棵完全二叉树
II. 可采用顺序存储方式保存堆；
III. 可以将堆看成一棵二叉排序树;
IV. 堆中的次大值一定在根的下一层。
【答案】B
【解析】基础概念题
堆（Heap）具有以下特点：
1) 完全二叉树
2) 存储的值是偏序
大根堆 (Max-heap): 父节点的值大于或等于子节点的值
一般用数组（顺序结构）来表示堆
10. 依次将关键字 5, 6, 9, 13, 8, 2, 12, 15 插入初始为空的 4 阶 B 树后，根节点中包含的关键字是：
A、8
B、6，9
C、8，13
D、9, 12
【答案】B
【解析】
B 树是一种平衡的多路搜索树, 结点最大的孩子数目称为 B 树的阶。一个 m 阶 B 树具有如下属性:
1. 定义任意非叶子结点最多只有 M 个儿子；且 M>2
2. 根结点的儿子数为 $[2, M]$
3. 除根结点以外的非叶子结点的儿子数为 $[M / 2, M]$
4. 每个结点存放至少 M/2-1（取上整）和至多 M-1 个关键字；（至少 2 个关键字）
5.非叶子结点的关键字个数 = 指向儿子的指针个数 -1
6.非叶子结点的关键字：K[1], K[2], ..., K[M-1]；且 K[i] < K[i+1]
7.非叶子结点的指针：P[1], P[2], ..., P[M]; 其中 P[1]指向关键字小于 K[1]的子树，P[M]指向关键字大于 K[M-1]的子树，其它 P[i]指向关键字属于(K[i-1], K[i])的子树
8.所有叶子结点位于同一层
最后生成的B树
11. 对大部分元素已有序的数组进行排序时，直接插入排序比简单选择排序效率更高，其原因是：
1、直接插入排序过程中元素之间的比较次数更少
II、直接插入排序过程中所需要的辅助空间更少
III、直接插入排序过程中元素的移动次数更少
A、I B、III C、I,II D、I,II,III
【答案】A
【解析】基础概念题
直接插入排序与简单选择排序相比
1) 直接插入排序元素比较次数少
2) 简单选择排序移动的元素少
3) 均为就地排序，空间复杂度均为 $O(1)$
12. 下列给出的部件中其位数（宽度）一定与机器字长相同的是：
I、ALU； II、指令寄存器； III、通用寄存器； IV、浮点寄存器
A、I, II B、I, III C、II, III D、II, III, IV
【答案】B
【解析】基础概念题
机器字长：是指计算机进行一次整数运算所能处理的二进制的位数，通常与CPU的寄存器位数，加法器有关
13. 已知带符号整数用补码表示, float 型数据用 IEEE 754 标准表示, 假定变量 $x$ 的类型只能是 int 或 float。当 $x$ 的机器数为 C8000000H 时, $x$ 的值可能是:
A、-7×2²⁷ B、-2¹⁶ C、2¹⁷ D、25×2²⁷
【答案】A
【解析】基础概念题
C800 0000H = 1100 1000 0000 0000 0000 0000 0000 0000
若为 float 转化为 1100100000000000000000000000000000H = -2
32位单精度形式
若为 int, 则对 C8000000H 求补, 得 B8000000H, 即 $-7 \times 2^{27}$
14. 在按字节编址，采用小端方式的 32 位计算机中，按边界对齐方式为以下 C 语言结构型变量 a 分配存储空间。
Struct record{
short x1;
int x2;
}a;
若 a 的首地址为 2020 FE00H，a 的成员变量 x2 的机器数为 12340000H，则其中 34H 所在存储单元的地址是：
A、2020 FE03H
B、2020 FE04H
C、2020 FE05H
D、2020 FE06H
【答案】D
【解析】
按边界对齐方式和小端方式存储时，对应a的存放方式为
$\times 1\;{00}\mathrm{H}$
$\mathrm{x}2\;{00}\mathrm{H}$
34H
12H
a 的首地址为 2020 FE00H, 34H 所在存储单元为 2020 FE00H + 6 = 2020 FE06H
15. 下列关于 TLB 和 Cache 的叙述中错误的是:
A、命中率与程序局部性有关；
B、缺失后都需要去访问主存；
C、缺失处理都可以由硬件实现；
D、都由DRAM存储器组成。
【答案】D
【解析】Cache 由 SRAM 组成，TLB 由 SRAM 或相联存储器组成
16. 某计算机采用 16 位定长指令字格式, 操作码位数和寻址方式位数固定, 指令系统有 48 条指令, 支持直接、间接、立即、相对 4 种寻址方式, 单地址指令中直接寻址方式可寻址范围是:
A、0~225;
B、0~1023;
C、-128~127;
D、-512~511;
【答案】A
【解析】
48条指令需要6位OP位，4种寻址方式需要2位寻址位，剩余16-6-2=8位由于主存地址非负，故寻址范围为0-255
17. 下列给出的处理器类型中理想情况下 CPI 为 1 的是:
I、单周期 CPU； II、多周期 CPU；
III、基本流水线 CPU； IV 超标量流水线 CPU
A、I, II;
B、1,III;
C、II,IV;
D、III,IV;
【答案】B
【解析】
CPI (Clock cycle Per Instruction): 每条计算机指令执行所需的时钟周期
CPI = 执行程序所需要的时钟周期数 / 所执行的指令条数
I: 令指令周期 $=$ 时钟周期, 则 $\mathrm{CPI} = 1$
II: 多周期 CPU 的 CPI 不可能是 1
III：理想情况下每个时钟周期均可执行一条指令
IV: 每时钟周期内可以完成一条以上的指令
18. 下列关于“自陷”（Trap，也称陷阱）的叙述中错误的是：
A、自陷是通过陷阱指令预先设定的一类外部中断事件；
B、自陷可用于实现程序调试时的断点设置和单步跟踪；
C、自陷发生后 CPU 将转去执行操作系统内核相应程序;
D、自陷处理完成后返回到陷阱指令的下一条指令执行。
【答案】A
【解析】自陷是内中断
19. QPI 总线是一种点对点全工双周同步串行总线，总线上的设备可同时接收和发送信息，每个方向可同时传输 20 位信息（16 位数据+4 位校验位），每个 QPI 数据包有 80 位信息，分 2 个时钟周期传送，每个时钟周期传递 2 次，因此 QPI 总线带宽为每秒传送次数*2B*2。若 QPI 时钟频率为 $2.4\mathrm{GHz}$ ，则总线带宽为：
A、4.8
B、9.6
C、19.2
D、38.4
（单位 GB/s）
【答案】C
【解析】2.4G(频率) * 2(每个时钟周期传递两次) * 2(全双工) * 2B/S = 19.2GB/s
20. 下列事件中属于外部中断事件的是：
I、访存时缺页；II、定时器延时（不确定）；III、网络数据包到达
【答案】C
【解析】访存缺页属于内部中断
21. 外部中断包括不可屏蔽中断（NMI）和可屏蔽中断，下列关于外部中断的叙述中错误的是：
A、CPU 处于关中断状态时也能响应 NMI 请求；
B、一旦可屏蔽中断请求信号有效，CPU 将立即响应；
C、不可屏蔽中断的优先级比可屏蔽中断的优先级高；
D、可通过中断屏蔽字改变可屏蔽中断的处理优先级。
【答案】B
【解析】
A：[关中断] 在中断服务过程中为了保护中断现场不被新的中断所打断，在保护现
场的过程中，CPU 不应响应更高级中断源的中断请求,但不可屏蔽中断通过 NMI 控制,不受中断标志位的影响，即使在关中断的情况下也会被响应。
B：CPU相应终端必须满足以下三个条件：
(1) 中断源有中断请求
(2) CPU 允许中断及开中断
(3) 一条指令执行完毕且没有更紧迫的任务
C：一般来说，在中断判优过程中，不可屏蔽中断优于可屏蔽中断
D：正确
22. 若设备采用周期挪用 DMA 方式进行输入输出，每次 DMA 传送的数据块大小为 512 字节，相应的 I/O 接口中有一个 32 位数数据缓冲寄存器，对于数据输入过程，下列叙述中错误的是：
A、每准备好 32 位数据，DMA 控制器就发出一次总线请求；
B、相对于 CPU，DMA 控制器的总线使用权的优先级更高；
C、在整个数据块的传送过过程中，CPU 不可以访问主存储器；
D、数据块传送结束时，会产生“DMA 传送结束”的中断请求。
【答案】A/C？
【解析】
A: DMA 的传送是以块为单位的
C: DMA 与主存相互并行, DMA 工作期间不影响 CPU 的工作
23. 若多个进程共享同一个文件 F，则下列叙述中正确的是：
A、个进程只能用“读”方式打开文件 F;
B、在系统打开文件表中仅有一个表项包含 F 的属性；
C、各进程的用户打开文件表中关于 F 的表项内容相同；
D、进程关闭 F 时系统删除 F 在系统打开文件表中的表项。
【答案】B
【解析】
A: 各进程既可以用读方式打开文件 F, 也可用写方式打开文件 F
B: 系统打开文件表只有一张, 正确
C：打开文件表关于同样一个文件的表项内容不一定相同
D: 进程关闭 F 时会使 F 的引用计数 -1, 引用计数 =0 时才会删除表项
24. 下列选项中支持文件长度可变，随机访问的磁盘存储空间分配方式是：
A、索引分配；
B、链接分配；
C、连续分配；
D、动态分区分配。
【答案】A
【解析】
B：链接分配不支持随机访问
C：连续分配不支持长度可变
D：动态分区配置是内存管理方式
25. 下列与中断相关的操作中，由操作系统完成的是：
1、保存被中断程序的中断点
II、提供中断服务
# III、初始化中断向量表
# IV、保存中断屏蔽字
A、I,II;
B、I,II,IV;
C III,IV;
D
II,III,IV.
【答案】D
【解析】
中断点的保存需要由软硬件保存寄存器内容、由硬件保存 PC、由 OS 保存 PSW
26. 下列与进程调度有关的因素中在设计多级反馈队列调度算法时需要考虑的是:
# 就绪队列的数量
# II 就绪队列的优先级
# III 各就绪队列的调度算法
# IV 进程在就绪队列间的迁移条件
A、I,II;
B、III,IV;
C、II,III,IV;
D I,II,III,IV
【答案】D
【解析】
多级反馈队列调度算法是时间片轮转调度算法与优先级调度算法的综合与发展，需要综合考虑队列数量，优先级、调度算法及进程在队列间的迁移条件。
# 27. 某系统中有 A,B 两类资源各 6 个, t 时刻资源分配及需求情况如下表所示
| 进程 | A已分配数量 | B已分配数量 | A需求总量 | B需求总量 |
| P1 | 2 | 3 | 4 | 4 |
| P2 | 2 | 1 | 3 | 1 |
| P3 | 1 | 2 | 3 | 4 |
t时刻安全检测结果是：
A、存在安全序列 P1
B、存在安全序列 P2,P1,P3;
C、存在安全序列 P2
D、不存在安全序列。
【答案】B
【解析】
$$
\begin{array}{l} \begin{array}{r l r l r l r} & 4 & 4 & 2 & 3 & 2 & 1 \\ \text {N e e d} = \text {M a x} - \text {A l l o c a t i o n} = & 3 & 1 & - 2 & 1 = & 1 & 0 \\ & 3 & 4 & 1 & 2 & 2 & 2 \end{array} \\ \text {A v a i l a b l e} = (1, 0) \\ \end{array}
$$
故此时只能满足进程P2的需求
释放 P2 所占的资源, Available = $(0,0) + (3,1) = (3,1)$ , 仅能满足 P1 的需求
释放 P1 所占的资源, Available = $(1,0) + (4,4) = (5,1)$ , 可以满足 P3 的需求
故安全序列为P2,P1,P3
# 28. 下列因素影响请求分页系统有效（平均）访存时间的是：
1、缺页率；
II、磁盘读写时间；
III、内存访问时间；
IV 执行缺页处理程序的 CPU 时间；
A、Ⅱ,Ⅲ
B、I,IV
C、I、III、IV
D、I,II,III,IV
【答案】D
【解析】
I、缺页率影响缺页中断发生的频率
II、磁盘读写时间影响慢表和物理地址的访问时间
III、访存时间影响缺页中断的处理时间
# IV、CPU时间影响缺页中断的处理时间
29. 下列关于父进程与子进程的叙述中错误的是:
A、父进程与子进程可以并发执行
B、父进程与子进程共享虚拟地址空间
C、父进程与子进程有不同的进程控制块
D、父进程与子进程不能同时使用同一临界资源
【答案】B
【解析】父进程不与子进程共享虚拟地址空间
30. 对于具备设备独立性的系统下列叙述中错误的是：
A、可以使用文件名访问物理设备；
B、用户程序使用逻辑设备与物理设备之间的映射关系
D、更换物理设备后必须修改访问该设备的应用程序。(缺一个选项)
【答案】D
【解析】访问设备的驱动程序与具体设备无关
31. 某文件系统的目录由文件名和索引节点号构成。若每个目录项长度为 64 字节, 其中 4个字节存放索引节点号, 60 个字节存放文件名。文件名由小写英文字母构成, 则该文件系统能创建的文件数量的上限为:
A、 $2^{26}$
B、 $2^{32}$
C、 $2^{60}$
D、 $2^{64}$
【答案】B
【解析】
创建的文件数量上限 $=$ 索引节点数量上限，索引节点为 4 个字节 32 位，故最多 $2^{32}$ 个索引节点，即最多创建 $2^{32}$ 个文件
32. 下列准则中实现临界区互斥机制必须遵循的是：
1、两个进程不能同时进入临界区
II、允许进程访问空闲的临界资源
III、进程等待进入临界区的时间是有限的
IV、不能进入临界区的执行态进程立即放弃CPU
A、Ⅰ,Ⅳ
B、II,III
C、Ⅰ,Ⅱ,Ⅲ
D、I、III,IV
【答案】C
【解析】
临界区资源的互斥准则：
(1) 空闲让进 $\rightarrow \mathrm{II}$
② 忙则等待 $\rightarrow 1$
(3) 有限等待 $\rightarrow \mathrm{III}$
(4) 让权等待
33. 下图描述的协议要素是:
1、语法
II、语义
III、时序
A. I
B. II
C. III
D. I, II, III
【答案】C
【解析】
协议由语法、语义和同步(时序)三部分组成。语法规定了传输数据的格式；语义规定了所要完成的功能，即需要发出何种控制信息、完成何种动作以及做出何种应答；同步规定了执行各个操作的条件、时序关系等，即时间实现顺序的详细说明。
该图显然描述的是各操作的执行顺序，并未描述传输数据的格式或所要完成的功能。
34. 下列关于虚电路网络的叙述中错误的是：
A、可以确保数据分组传输顺序
B、需要为每条虚电路预分配带宽
C、建立虚电路时需要进行路由选择
D、依据虚电路号（VCID）进行数据分组转发
【答案】B
【解析】不需要为每条虚电路预分配带宽
35. 下图所示的网络冲突域和广播域的个数分别
A、2，2；
B、2，4；
C、4，2;
D、4，4；
【答案】C
【解析】
路由器可以隔离广播域与网络冲突域，交换机只能隔离冲突域，集线器均不能隔离
36. 假设主机采用停-等协议向主机乙发送数据帧，数据帧长与确认帧长均为1000B。数据传输速率是10kbps，单项传播延时是200ms。则甲的最大信道利用率：
A、 $80\%$
B、66.7%；
C、44.4%;
D、40%
【答案】D
【解析】
发送时间 $t = 1000 * 8 \mathrm{~b} / 10 \mathrm{~kbps} = 800 \mathrm{~ms}$
发送周期 $T = 200 \mathrm{~ms} * 2 + 800 \mathrm{~ms} * 2 = 2000 \mathrm{~ms}$
信道利用率 $= \frac{t}{T} * 100\% = 40\%$
37. 某 IEEE 802.11 无线局域网中主机 H 与 AP 之间发送或接收 CSMA/CA 帧的过程如下图所示，在 H 或 AP 发送帧前所等待的帧间间隔时间（IFS）中最长的是：
A、IFS1
B、IFS2
C、IFS3
D、IFS4
【答案】A
【解析】
IEEE802.11使用3种帧间隔IFS：
1.分布式协调帧间隔DIFS：最长的IFS，优先级最低，用于异步帧竞争访问的时延
2. 点协调帧间隔 PIFS：中等长度，优先级居中，在 PCF 操作中使用
3. 短帧间隔SIFS：最短，优先级最高，用于需要立即响应的操作
图中IFS1对应DIFS，IFS2、IFS3、IFS4对应SIFS
38. 若主机甲与主机乙已建立一条 TCP 连接，最大段长（MSS）为 1KB，往返时间（RTT）为 2ms，则在不出现拥塞的前提下，拥塞窗口从 8kB 增长到 32KB 所需的最长时间是：
A、4ms
B、8ms
C、24ms
D、48ms
【答案】D
【解析】当慢开始门限 ssthresh 时，拥塞窗口从一开始就采取拥塞避免算法即“加法增大”，即每个轮次的拥塞窗口 +1，此时可求得题目所需的最长时间为
(32-8) $\star 2 \mathrm{~ms} = 48 \mathrm{~ms}$
39. 若主机甲与主机乙建立 TCP 连接时发送的 SYN 段中的序号为 1000 , 在断开连接时,甲发送给乙的 FIN 段中的序号为 5001 , 则在无任何重传的情况下, 甲向乙已经发送的应用层数据的字节数为:
A、4002
B、4001
C、4000
D、3999
【答案】C
【解析】
SYN=1000，则数据传输时的起始序号为1001，字节数 $=$ FIN-1001=4000
40. 假设下图所示网络中的本地域名服务器只提供递归查询服务，其他域名的服务器均只提供迭代查询服务；局域网内主机访问 Internet 上各服务器的往返时间 (RTT) 均为 10ms，忽略其他各种时延，若主机 H 通过超链接 http://www.acc.com/index.html，请求浏览纯文本 Web 页 index.html，则从点击超链接开始到浏览器接收到 index.html 页面为止，所需最短、最长时间分别是：
A、10ms, 40ms
B、10ms,50ms
C、20ms,40ms
D、20ms,50ms
【答案】D
【解析】
最短时间：本地域名服务器存在域名与 IP 地址的映射
主机向本地域名服务器递归查询 10s + 数据传输 10ms = 20ms
最长时间：本地域名服务器不存在映射，需要迭代查询各级域名服务器3次
10ms + 迭代查询 3 次 30ms + 数据传输 10ms = 50ms
大题
41. 定义三元组 $(a, b, c)$ $(a, b, c$ 均为正数）的距离 $D = |a - b| + |b - c| + |c - a|$ . 给定 3 个非空整数集合 S1, S2, S3, 按升序分别存储在 3 个数组中。请设计一个尽可能高效的算法，计算并输出所有可能的三元组 $(a, b, c)$ $(a \in S1, b \in S2, c \in S3)$ 中的最小距离。例如 $S1 = \{-$
1, 0, 9}, S2 = \{-25, -10, 10, 11\}, S3 = \{2, 9, 17, 30, 41\} 则最小距离为 2，相应的三元组为（9，10，9）要求：
(1)给出算法的基本设计思想；
(2)根据设计思想，采用 C 或 $\mathrm{C}++$ 语言描述算法，关键之处给出注释；
(3)说明你所设计算法的时间复杂度和空间复杂度。
【解析】
方法一
【暴力法】
三层 for 循环，时间复杂度为 $O(l * m * n)$ ， $l, m, n$ 分别为集合 S1, S2, S3 的长度评分标准：7 分
方法二
假设当前遍历到的这三个数组中的元素分别为a[i],b[j],c[k]，并且有a[i] $< =$ b[j]< $= c[k]$ ，则最小距离为D1 $= |a[i] - b[j]| + |b[j] - c[k]| + |c[k] - a[i]|$ ，那么接下来有三种情况：
1. 接下来求a[i], b[j], c[k+1]的最小距离，因为c[k+1] >= c[k]，所以，此时的最小距离为D2，肯定大于D1
D2>D1
2. 接下来求a[i], b[j+1], c[k]的最小距离，如果b[j+1] <= c[k]，则最小距离不变，如果 b[j+1] > c[k]，此时的最小距离为D2肯定必定大于D1
3.接下来求a[i+1],b[j],c[k]的最小距离，在该种情况下D才有可能减小！
【因此只需移动最小的元素a[i]！】
所以，整体的思路是开始得出三个数组第一个元素的最小距离，接下来移动最小三个元素中最小元素的下标，与之前得到的最小距离比较，看是否需要更新最小距离，直到遍历完三个数组
【时间复杂度为 $O(l + m + n)$ 】
42. 若任一个字符的编码都不是其他字符编码的前缀, 则称这种编码具有前缀特性。现有某字符集 (字符个数 $\geqslant 2$ ) 的不等长编码, 每个字符的编码均为二进制的 0, 1 序列, 最长为 L 位, 且具有前缀特性。请回答下列问题:
(1) 哪种数据结构适宜保存上述具有前缀特性的不等长编码？
(2) 基于你所设计的数据结构，简述从 0/1 串到字符串的译码过程
(3) 简述判定某字符集的不等长编码是否具有前缀特性的过程
【解析】考点：前缀编码，赫夫曼(Huffman)树
(1) 二叉树或赫夫曼树
普通的二叉树也可以设计前缀编码，赫夫曼树会使总长最小，是对前者的优化。
(2) 将所有的字符信息存储到二叉树的叶子结点上, 且约定左分支表示字符 '0', 右分支表示字符 '1', 则可将根节点到叶子结点的路径上分支字符组成的字符串作为该叶子结点字符的编码。从根节点出发将 $0 / 1$ 串沿着分支探查下去, 遇到带有信息的叶子结点即为一个字符, 然后再从根节点出发, 以此类推直至 $0 / 1$ 串全部译码为字符串。
(3) 只需判定存储有字符信息的节点是否全部为叶子结点即可。若存储有某个字符信息的节点非叶子结点，即有子节点，那么它的 0/1 编码一定是它孩子节点 0/1 编码的前缀，违反了前缀特性。
43. 有实现 $x*y$ 的两个 C 语言函数如下：
```c
unsigned umul ( unsigned x, unsigned y)
{ return x*y; }
int imul ( int x, int y )
{ return x*y; }
```
假定某计算机 M 中 ALU 只能进行加减运算和逻辑运算。请回答:
(1) 若 M 的指令系统中没有乘法指令, 但有加法、减法和位移等指令, 则在 M 上也能实现上述两个函数中的乘法运算, 为什么?
(2) 若 M 的指令系统中有乘法指令, 则基于 ALU、位移器、寄存器以及相应控制逻辑实现乘法指令时, 控制逻辑的作用是什么?
(3) 针对以下 3 种情况: (a) 没有乘法指令; (b) 有使用 ALU 和位移器实现的乘法指令; (c) 有使用阵列乘法器实现的乘法指令, 函数 umul()在哪种情况下执行时间最长?哪种情况下执行的时间最短? 说明理由
(4) n 位整数乘法指令可保存 2n 位乘积, 当仅取低 n 位作为乘积时, 其结果可能会发生溢出。当 $n = 32, x = 2^{31} - 1, y = 2$ 时, 带符号整数乘法指令和无符号整数乘法指令得到的 $x * y$ 的 2n 位乘积分别是什么 (用十六进制表示)? 此时函数 umul() 和 imul() 的返回结果是否溢出? 对于无符号整数乘法运算, 当仅取乘积的低 n 位作为乘法结果时, 如何用 2n 位乘积进行溢出判断?
# 【解析】
(1) 乘法运算也可以通过加法操作和移位操作实现
$x * y$ 可视为 $y$ 个 $x$ 或 $x$ 个 $y$ 相加的结果
(2) 实现相加和移位的控制
(3) 最长: a 最短: c
a) 情况下执行时间最长，需要利用其他指令来实现乘法功能
b) 情况下使用了 ALU 与位移器, 由多次相加及位移操作串行实现乘法操作
c) 情况使用阵列乘法器做并行乘法运算，时间显然最快
(4) 带符号整数指令乘法: $7FFF \, FFFFH * 2 = 00000000 FFFF \, FFEH$
无符号整数指令乘法： $7FFF$ FFFFH $\times 2 = 00000000$ FFFF FFEH
umul()返回 FFFF FFFFEH 未溢出
imul()返回 FFFF FFFEH 有溢出(结果成了负数)
高 $n$ 位全 0 则未产生溢出, 否则产生溢出
44. 假定主存地址为 32 位, 按字节编址, 指令 Cache 和数据 Cache 与主存之间均采用 8 路组相联映射方式, 直写 (Write Through) 写策略和 LRU 替换算法, 主存块大小为 64B, 数据区容量各为 $32 \mathrm{KB}$ 。开始时 Cache 均为空, 请回答下列问题:
(1) Cache 每一行中标记 (Tag)、LRU 位各占几位? 是否有修改位?
(2）有如下C语言程序段：
$$
f o r (k = 0; k < 1 0 2 4; k + +)
$$
$$
S [ k ] = 2 * s [ k ];
$$
若数组 S 及其变量 k 均为 int 型，int 型数据占 4B，变量 k 分配在寄存器中，数组 s 在主存中的起始地址为 008000C0H，则该程序段执行过程中，访问数组 S 的数据 Cache 缺失次数为多少？
(3) 若 CPU 最先开始的访问操作是读取主存单元 0001003H 中的指令, 简要说明从 Cache 中访问该指令的过程, 包括 Cache 缺失处理过程。
【解析】
(1) 主存地址为 32 位, 其中 6 位为块内地址
标记：32-6-6=20位
LRU：3位
直写写策略无修改位
(2) 在该程序的执行过程中，产生一次缺失时会更新 Cache 中的 16 块，之后的 15 次访问均命中 Cache，故平均每 16 次访问 Cache 就会产生一次缺失，K 的范围为 1024，即共 1024 次访问 Cache，Cache 缺失次数 $= 1024 / 16 = 64$ 次
(3) CPU 访指的大致过程:
CPU发出读请求时，若访存地址在Cache中命中，就将此地址转换成Cache地址，直接对Cache进行读操作，与主存无关；若Cache不命中，则仍需访问主存，并把此字所在的一块一次性从主存调入Cache，若此时Cache已满，就根据LRU替换算法，用这个块替换Cache中的一块信息。
45. 现有 5 个操作 A、B、C、D 和 E，操作 C 必须在 A 和 B 完成后执行，操作 E 必须在 C 和 D 完成后执行，请使用信号量的 wait(), signal(), 操作 (P、V 操作) 描述上述操作之间的同步关系，并说明所用信号量及其初值。
【解析】
```txt
semaphore A $=$ B $= C = D = E = 0$
A()
{ 完成行为A; V(A);
}
B()
{ 完成行为B; V(B);
}
C()
{ P(A); P(B); 完成行为C; V(C);
}
D()
{ 完成行为D; v(D);
}
E()
{ P(C); P(D); 完成行为E; V(E);
```
46. 某 32 位系统采用基于二级页表的请求分页存储管理方式, 按字节编址, 页目录项和页表项长度均为 4 字节, 虚拟地址结构如下:
| 页目录号（10位） | 页号（10位） | 页内偏移量（12位） |
某 C 程序中数组 a[1024][1024]的起始虚拟地址为 1080 0000H, 数组元素占 4 字节,该程序运行时, 其进程的页目录起始物理地址为 0020 1000H, 请回答下列问题:
(1) 数组元素 a[1][2]的虚拟地址是什么? 对应的页目录号和页号分别是什么? 对应的页目录项的物理地址是什么? 若该目录项中存放的页框号为 00301H, 则 a[1][2]所在页对应的页表项的物理地址是什么?
(2) 数组 a 在虚拟地址空间中所占区域是否必须连续? 在物理地址空间中所占区域是否必须连续?
(3) 已知数组 a 按行优先方式存放, 若对数组 a 分别按行遍历和按列遍历, 则哪一种遍历方式的局部性更好?
# 【解析】
(1) 页面大小 $= 2^{12} \mathrm{~B} = 4 \mathrm{KB}$ , 数组元素占 4 字节, 每个页面存放 1K 个数组元素, 1080000H 的虚页号为 1080H, 注意到二维数组 a 的一行的元素个数与每个页面存放的元素个数相同, 故 a[0] 存放的虚页号为 1080H, a[1] 存放的虚页号为 1081H, a[1][2] 的虚拟地址为 $10810000 \mathrm{H} + 2 * 4 = 10810008 \mathrm{H}$
1081 0008H = 0001 0000 1000 0001 0000 0000 0000 1000，对应的页目录号为66,
页号为 16
页目录的长度为 4B, 66 号页目录项的物理地址是 00201000H + 66*4 = 00201108H 该目录项中存放的页框号是 00301H, 则该页框的起始地址是 00301000H, a[1][2] 所在页面的页号为 16 , 每个页表项为 4B , 对应的页表项物理地址为 00301000H+16*4 = 00301040H
(2) 在虚拟地址空间中所占区域必须连续，在物理地址空间中所占区域可以不连续
(3) 按行遍历的局部性更好，二维数组 a 的一行的元素个数与每个页面存放的元素个数相同，故一行的所有元素均可以存放在同一个页面中，行遍历时遍历同一行中的所有元素访问的是同一个页面。
47. 某校园网有两个局域网，通过路由器 R1、R2 和 R3 互联后接入 Internet，S1 和 S2 为以太网交换机，局域网采用静态 IP 地址配置，路由器部分接口以及各主机的 IP 地址如图所示：
假设NAT转换表结构为：
请回答下列问题：
(1) 为使 H2 和 H3 能够访问 Web 服务器 (使用默认端口号), 需要进行什么配置?
(2) 若 H2 主动访问 Web 服务器时, 将 HTTP 请求报文封装到 IP 数据报 P 中发送,则 H2 发送 P 的源 IP 地址和目的 IP 地址分别是? 经过 R3 转发后, P 的源 IP 地址和目的 IP 地址分别是? 经过 R2 转发后, P 的源 IP 地址和目的 IP 地址分别是?
# 【解析】
(1) 注：H2和H3应是19216812的台式机与19216813的笔记本
路由器R2需要开启NAT服务，对应的NAT转换表做如下配置：
| 外网 | 内网 |
| IP地址 | 端口号 | IP地址 | 端口号 |
| 203.10.2.6 | 默认端口号 | 192.168.1.2 | 80 |
| 203.10.2.6 | 默认端口号 | 192.168.1.3 | 80 |
(2) H2 发送 P 的源 IP 地址: 192.168.1.2 目的 IP 地址: 203.10.2.2
R3发送P的源IP地址：203.10.2.6 目的IP地址：203.10.2.2
R2发送P的源IP地址：203.10.2.6 目的IP地址：192.168.1.2