2017 年真题
下列函数的时间复杂度是（ ）。
int func(int n) {
int i = 0, sum = 0;
while(sum < n)
sum += ++i;
return i;
}
A. (O(n)) B. (O(\sqrt{n})) C. (O(\log_2 n)) D. (O(n\log_2 n))
[tag_link]
正确答案：B
sum += ++i;相当于++i; sum = sum + i;进行到第 k 趟循环，sum = (1+k)*k/2。显然需要进行O(n1/2)趟循环，因此这也是该函数的时间复杂度。
下列关于栈的叙述中，错误的是（ ）。
I. 采用非递归方式重写递归程序时必须使用栈
II. 函数调用时，系统要用栈保存必要信息
III. 只要确定了入栈次序，即可确定出栈次序
IV. 栈是一种受限的线性表，允许在其两端进行操作
A. 仅 I B. 仅 I、II、III C. 仅 I、III、IV D. 仅 II、III、IV
[tag_link]
正确答案：C
I 的反例：计算斐波拉契数列迭代实现只需要一个循环即可实现。 III 的反例：入栈序列为 1、2, 进行如下操作 PUSH、PUSH、POP、POP，出栈次序为 2、1；进行如下操作 PUSH、POP、PUSH、POP，出栈次序为 1、2。 IV，栈是一种受限的线性表，只允许在一端进行操作。 因此 II 正确。
适用于压缩存储稀疏矩阵的两种存储结构是（）
A. 三元组表和十字链表 B. 三元组表和邻接矩阵 C. 十字链表和二叉链表 D. 邻接矩阵和十字链表
[tag_link]
正确答案：A
三元组表 的结点存储了行 row、列 col、值 value 三种信息，是主要用来存储稀疏矩阵的一种 数据结构。十字链表将行单链表和列单链表结合起来存储稀疏矩阵。邻接矩阵空间复杂度达O(n2), 不适用于存储稀疏矩阵。二叉链表又名左孩子右兄弟表示法，可用于表示树或森林。因此 A 正确。
要使一颗非空二叉树的先序序列与中序序列相同，其所有非叶节点须满足的条件是（）
A. 只有左子树 B. 只有右子树 C. 结点的度均为 1 D. 结点的度均为 2
[tag_link]
正确答案：B
先序序列是根左右，中序序列是左根右，递归进行。如果所有非叶结点只有右子树，先序序列和中序序列都是先父结点，然后右子树，递归进行，因此 B 正确。
已知一颗二叉树的树形如下图所示，其后序序列为 e，a，c，b，d，g，f，树中与结点 a 同层的结点是（）
A. c B. d C. f D. g
[tag_link]
正确答案：B
后序序列是先左子树，接着右子树，最后父结点，递归进行。根结点左子树的叶结点首先被访问，它是 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 的译码结果是（ ）。
A. a c g a b f h B. a d b a g b b C. a f b e a g d D. a f e e f g d
[tag_link]
正确答案：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
[tag_link]
正确答案：B
结论
图 (G) 至少含有 11 个顶点，选项 B 正确。
推导
握手定理给出所有顶点度数之和 (2|E|=2\times16=32)。已知度为 4 和度为 3 的顶点贡献
[ 3\times4+4\times3=24。 ]
剩余顶点的度小于 3，且为了让顶点数尽可能少，应让它们尽量取最大的允许度数 2。设这样的顶点有 (x) 个，则 (24+2x=32)，解得 (x=4)。所以顶点总数至少为 (3+4+4=11)。
易错点
“度小于 3”意味着最大只能取 2，不能把余下度数 8 用 3 个顶点平均分摊；那会使每个顶点的度达到 (8/3)，且有顶点度为 3，违反条件。先用握手定理算余量，再用最大允许度数求最少顶点数。
下列二叉树中，可能成为折半查找判定树（不含外部结点）的是（）
A. 树 A B. 树 B C. 树 C D. 树 D
[tag_link]
正确答案：A
折半查找判定树 实际上是一棵 二叉排序树，它的中序序列是一个有序序列。可以在树结点上依次填上相应的元素，判断哪颗树符合折半查找的规则。折半查找树由于其中序遍历是一个升序序列，因此相比于在以往的序列中进行二分查找，折半查找二叉树的优点在于不用自己去找中点，而是直接将要查找的关键字与根节点相比，小的话再和根节点的左子节点（又是相应的左子树中点，更加方便）比较，大的话则是和根节点的右子节点比较。而对于这道题的解题思路就在于向上或向下取整的问题，也就是说如果升序序列是偶数个，那么中点应该偏左多右少还是左少右多。但是很显然应该进行一个统一，像 B 和 C 选项中间的对称部分明显就是选择了不同的策略。D 则由根节点左子树 4 个节点而点右子树 5 个节点可以确定用的是向下取整策略，但是我们再看它的左子节点在左子树中对应的中点左边 2 个数，右边一个数，明显是向上取整策略，策略没有统一，所以是错的。
下列应用中，适合使用 B+ 树的是（）
A. 编译器中的词法分析 B. 关系数据库系统中的索引 C. 网络中的路由表快速查找 D. 操作系统的磁盘空闲块管理
[tag_link]
正确答案：B
B+ 树 是应文件系统所需而产生的 B 树 的变形，前者比后者更加适用于实际应用中的操作系统的文件索引和数据库索引，因为前者磁盘读写代价更低，查询效率更加稳定。编译器中的词法分析使用有穷自动机和语法树。网络中的路由表快速查找主要靠高速缓存、路由表压缩技术和快速查找算法。系统一 般使用空闲空间链表管理磁盘空闲块。所以 B 正确。
在内部排序时，若选择了归并排序而没有选择插入排序，则可能的理由是（）
Ⅰ. 归并排序的程序代码更短Ⅱ. 归并排序的占用空间更少Ⅲ. 归并排序的运行效率更高
A. 仅 Ⅱ B. 仅 Ⅲ C. 仅 Ⅰ、Ⅱ D. 仅 Ⅰ、Ⅲ
[tag_link]
正确答案：B
参考 排序算法复杂度 ，归并排序代码比选择插入排序更复杂，前者空间复杂度是O(n), 后者是O(1)。但是前者时间复杂度是O(nlogn), 后者是O(n2)。所以 B 正确。
下列排序方法中，若将顺序存储更换为链式存储，则算法的时间效率会降低的是（）
Ⅰ. 插入排序 Ⅱ. 选择排序 Ⅲ. 起泡排序 Ⅳ. 希尔排序 Ⅴ. 堆排序
A. 仅 Ⅰ、Ⅱ B. 仅 Ⅱ、Ⅲ C. 仅 Ⅲ、Ⅳ D. 仅 Ⅳ、Ⅴ
[tag_link]
正确答案：D
插入排序、选择排序、冒泡原本时间复杂度是O(n2)，更换为链式存储后的时间复杂度还是O(n2)。希尔排序和堆排序都利用了顺序存储的随机访问特性，而链式存储不支持这种性质，所以时间复杂度会增加，因此选 D。
假定计算机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
[tag_link]
正确答案：C
运行时间 = 指令数 x CPI / 主频。M1 的时间 = 指令数 x 2 / 1.5，M2 的时间 = 指令数 x 1 / 1.2，两者之比为 (2/1.5):(1/1.2) = 1.6。故选 C。
某计算机主存按字节编址，由4个64M×8 位的DRAM芯片采用交叉编址方式构成，并与宽度为32 位的存储器总线相连，主存每次最多读写32位数据。若double 型变量x 的主存地址为804001AH, 则读 取x 需要的存储周期数是()。
A.1 B.2 C.3 D.4
[tag_link]
正确答案：C
由 4 个 DRAM 芯片采用 交叉编址方式 构成主存可知主存地址最低二位表示该字节存储的芯片编号。double 型变量占 64 位，8 个字节。它的主存地址 804001AH 最低二位是 10，说明它从编号为 2 的 芯片开始存储（编号从 0 开始）。一个存储周期可以对所有芯片各读取���个字节，因此需要 3 轮，故选 C。
某 C 语言程序段如下：
for (i = 0; i <= 9; i++) {
temp = 1;
for (j = 0; j <= i; j++)
temp *= a[j];
sum += temp;
}
下列关于数组 a 的访问局部性的描述中，正确的是（ ）。
A. 时间局部性和空间局部性皆有 B. 无时间局部性，有空间局部性 C. 有时间局部性，无空间局部性 D. 时间局部性和空间局部性皆无
[tag_link]
正确答案：A
时间局部性 是一旦一条指令被执行，则在不久的将来它可能再次被执行。空间局部性 是一旦一个存储单元被访问，那么它附近的存储单元也很快被访问。显然，这里的循环指令本身具有时间局部性，它对数组 a 的访问具有空间局部性，故选 A。
下列寻址方式中，最适合按下标顺序访问一维数组元素的是()。
A. 相对寻址 B. 寄存器寻址 C. 直接寻址 D. 变址寻址
[tag_link]
正确答案：D
在 变址寻址 时，将计算机指令中的地址与变址寄存器中的地址相加，得到有效地址，指令提供数组首地址，由变址寄存器来定位数据中的各元素。所以它最适合按下标顺序访问一维数组元素，故选 D。相对寻址以 PC 为基地址，以指令中的地址为偏移量确定有效地址。寄存器寻址则是在指令中指出需要使用的寄存器。直接寻址是在指令的地址字段直接指出操作数的有效地址。
某计算机按字节编址，指令字长固定且只有两种指令格式，其中三地址指令29条，二地址指令107条， 每个地址字段为6位，则指令字长至少应该是()。
A. 24 位 B. 26 位 C. 28 位 D. 32 位
[tag_link]
正确答案：A
三地址指令有 29 条，所以它的操作码至少为 5 位。以 5 位进行计算，它剩余 32-29=3 种操作码给二地址。而二地址另外多了 6 位给操作码，因此它的数量最大达 3x64=192。所以指令字长最少为 23 位，因为计算机按字节编址，需要是 8 的倍数，所以指令字长至少应该是 24 位，故选 A。
下列关于超标量流水线特性的叙述中，正确的是()。
I. 能缩短流水线功能段的处理时间
Ⅱ.能在一个时钟周期内同时发射多条指令
Ⅲ.能结合动态调度技术提高指令执行并行性
A. 仅Ⅱ B. 仅Ⅰ、Ⅲ C. 仅Ⅱ、Ⅲ D. Ⅰ、Ⅱ和Ⅲ
[tag_link]
正确答案：C
超标量流水线 是指在 CPU 中有一条以上的流水线，并且每个时钟周期内可以完成一条以上的指令，其实质是以空间换时间。I 错误，它不影响流水线功能段的处理时间；II、III 正确。故选 C。
下列关于主存储器( MM) 和控制存储器( CS) 的叙述中，错误的是()。
A.MM 在CPU外 ，CS在 CPU内 B. MM按地址访问，CS 按内容访问 C.MM 存储指令和数据，CS 存储微指令 D.MM 用RAM 和ROM 实现，CS 用ROM实现
[tag_link]
正确答案：B
主存储器就是我们通常说的主存，在 CPU 外，存储指令和数据，由 RAM 和 ROM 实现。控制存储器 用来存放实现指令系统的所有微指令，是一种只读型存储器，机器运行时只读不写，在 CPU 的控制器内。CS 按照微指令的地址访问，所以 B 错误。
下列关于指令流水线数据通路的叙述中，错误的是()。
A. 包含生成控制信号的控制部件 B. 包含算术逻辑运算部件( ALU) C. 包含通用寄存器组和取指部件 D. 由组合逻辑电路和时序逻辑电路组合而成
[tag_link]
正确答案：A
五阶段流水线 可分为取指（IF）、译码／取数（ID）、执行（EXC）、存储器读（MEM）、写回（Write Back）。数字系统中，各个子系统通过数据总线连接形成的数据传送路径称为 数据通路 ，包括程序计数器、算术逻辑运算部件、通用寄存器组、取指部件等，不包括控制部件，故选 A。
下列关于多总线结构的叙述中，错误的是()。
A. 靠近CPU 的总线速度较快 B. 存储器总线可支持突发传送方式 C. 总线之间须通过桥接器相连 D.PCI-Express__×16采用并行传输方式
[tag_link]
正确答案：D
多总线结构 用速率高的总线连接高速设备用速率低的总线连接低速设备。一般来说，CPU 是计算机的核心，是计算机中速度最快的设备之一，所以 A 正确。突发传送方式把多个数据单元作为一个独立传输处理，从而最大化设备的吞吐量。现实中一般用支待突发传送方式的总线提高存储器的读写效率，B 正确。各总线通过桥接器相连，后者起流量交换作用。PCI-Express 总线都采用 串行 数据包传输数据，所以选 D。
I/O 指令实现的数据传送通常发生在()。
A. I/O 设备和 I/O 端口之间 B. 通用寄存器和 I/O 设备之间 C. I/O 端口和 I/O 端口之间 D. 通用寄存器和 I/O 端口之间
[tag_link]
正确答案：D
I/O 端口 是 CPU 与设备之间的交接面。由于主机和 I/0 设备的工作方式和工作速度有很大差异，I/O 端口就应运而生。在执行一条指令时，CPU 使用地址总线选择所请求的 I/O 端口，使用数据总线在 CPU 寄存器和端口之间传输数据。所以选 D。
下列关于多重中断系统的叙述中，错误的是（ ）。
A. 在一条指令执行结束时响应中断 B. 中断处理期间 CPU 处于关中断状态 C. 中断请求的产生与当前指令的执行无关 D. CPU 通过采样中断请求信号检测中断请求
[tag_link]
正确答案：B
多重中断 系统在保护被中断进程现场时关中断，执行中断处理程序时开中断，B 错误。CPU 一般在一条指令执行结束的阶段采样中断请求信号，查看是否存在中断请求，然后决定是否响应中断，A、D 正确。中断请求一般来自 CPU 以外的事件，异常一般发生在 CPU 内部，C 正确。
假设 4 个作业到达系统的时刻和运行时间如下表所示。
| 作业 | 达到时刻 t | 运行时间 |
|---|---|---|
| J1 | 0 | 3 |
| J2 | 1 | 3 |
| J3 | 1 | 2 |
| J4 | 3 | 1 |
系统在 t=2 时开始作业调度。若分别采用先来先服务和短作业优先调度算法，则选中的作业分别是（ ）。
A. J2、J3 B. J1、J4 C. J2、J4 D. J1、J3
[tag_link]
正确答案：D
先来先服务 是作业来得越早，优先级越高，因此会选择J1。 最短作业优先 是作业运行时间越短，优先级越高，因此会选择J3。所以 D 正确。
执行系统调用的过程包括如下主要操作：
①返回用户态 ②执行陷入（trap）指令
③传递系统调用参数 ④执行相应的服务程序
正确的执行顺序是（ ）。
A. ②→③→①→④ B. ②→④→③→① C. ③→②→④→① D. ③→④→②→①
[tag_link]
正确答案：C
执行 系统调用 的过程是这样的：正在运行的进程先传递系统调用参数，然后由 陷入指令 负责将用户态转化为内核态，并将返回地址压入堆栈以备后用，接下来 CPU 执行相应的内核态服务程序，最后返回用户态。所以 C 正确。
某计算机按字节编址，其动态分区内存管理采用最佳适应算法，每次分配和回收内存后都对空闲分区链重新排序。当前空闲分区信息如下表所示。
| 分区起始地址 | 20K | 500K | 1000K | 200K |
|---|---|---|---|---|
| 分区大小 | 40KB | 80KB | 100KB | 200KB |
回收起始地址为 60K、大小为 140KB 的分区后，系统中空闲分区的数量、空闲分区链第一个分区的起始地址和大小分别是（ ）。
A. 3、20K、380KB B. 3、500K、80KB C. 4、20K、180KB D. 4、500K、80KB
[tag_link]
正确答案：B
参考 动态内存内存回收过程 ，回收起始地址为 60K、大小为 140KB 的分区时，它与表中第一个分区和第四个分区合并，成为起始地址为 20K、大小为 380KB 的分区，剩余 3 个空闲分区。在回收内存后，算法会对空闲分区链按分区大小由小到大进行排序，表中的第二个分区排第一。所以选择 B。
某文件系统的簇和磁盘扇区大小分别为 1KB 和 512B。若一个文件的大小为 1026B，则系统分配给该文件的磁盘空间大小是（ ）。
A. 1026B B. 1536B C. 1538B D. 2048B
[tag_link]
正确答案：D
在文件系统中，磁盘空间以簇为单位分配，每个簇的大小为 1KB（1024B）。而磁盘扇区大小为 512B，但分配时只考虑簇的整数倍。
下列有关基于时间片的进程调度的叙述中，错误的是（ ）。
A. 时间片越短，进程切换的次数越多，系统开销也越大 B. 当前进程的时间片用完后，该进程状态由执行态变为阻塞态 C. 时钟中断发生后，系统会修改当前进程在时间片内的剩余时间 D. 影响时间片大小的主要因素包括响应时间、系统开销和进程数量等
[tag_link]
正确答案：B
进程切换带来系统开销，切换次数越多，开销越大，A 正确。当前进程的时间片用完后，它的状态由执行态变为就绪态，B 错误。时钟中断是系统中特定的周期性时钟节拍。操作系统通过它来确定时间间隔，实现时间的延时和任务的超时，C 正确。现代操作系统为了保证性能最优，通常根据响应时间、系统开销、进程数量、进程运行时间、进程切换开销等因素确定 时间片大小，D 正确。
与单道程序系统相比，多道程序系统的优点是（ ）
Ⅰ.CPU 利用率高
Ⅱ.系统开销小
Ⅲ.系统吞吐量大
Ⅳ.I/O 设备利用率高
A. 仅Ⅰ、Ⅲ B. 仅Ⅰ、Ⅳ C. 仅Ⅱ 、Ⅲ D. 仅Ⅰ、Ⅲ、Ⅳ
[tag_link]
正确答案：D
多道程序系统通过组织作业（编码或数据）使 CPU 总有一个作业可执行，从而提高了 CPU 的利用率、系统吞吐量和 I/O 设备利用率，I、III、IV 是优点。但系统要付出额外的开销来组织作业和切换作业，II 错误。所以选 D。
下列选项中，磁盘逻辑格式化程序所做的工作是（ ）。
Ⅰ. 对磁盘进行分区
Ⅱ. 建立文件系统的根目录
Ⅲ. 确定磁盘扇区校验码所占位数
Ⅳ. 对保存空闲磁盘块信息的数据结构进行初始化
A. 仅Ⅱ B. 仅Ⅱ、Ⅳ C. 仅Ⅲ、Ⅳ D. 仅Ⅰ、Ⅱ、Ⅳ
[tag_link]
正确答案：B
一个新的磁盘是一个空白盘，必须分成扇区以便磁盘控制器能读和写，这个过程称为 物理格式化 。低级格式化为磁盘的每个扇区采用特别的数据结构，包括校验码，III 错误。为了使用磁盘存储文件，操作系统还需要将其数据结构记录在磁盘上。这分为两步。第一步是将磁盘分为由一个或多个柱面组成的分区，每个分区可以作为一个独立的磁盘，I 错误。在分区之后，第二步是 逻辑格式化 （创建文件系统）。在这一步，操作系统将初始的文件系统数据结构存储到磁盘上。这些数据结构包括空闲和已分配的空间和一个初始 为空的目录，II、IV 正确。所以选 B。
某文件系统中，针对每个文件，用户类别分为 4 类：安全管理员、文件主、文件主的伙伴、其他用户；访问权限分为 5 种：完全控制、执行、修改、读取、写入。若文件控制块中用二进制位串表示文件权限，为表示不同类别用户对一个文件的访问权限，则描述文件权限的位数至少应为（ ）。
A. 5 B. 9 C. 12 D. 20
[tag_link]
正确答案：D
可以把用户访问权限抽象为一个矩阵，行代表用户，列代表访问权限。这个矩阵有 4 行 5 列，1 代表 true，0 代表 false，所以需要 20 位，选 D。
若文件 f1 的硬链接为 f2，两个进程分别打开 f1 和 f2，获得对应的文件描述符为 fd1 和 fd2，则下列叙述中，正确的是（ ）。
Ⅰ. f1 和 f2 的读写指针位置保持相同
Ⅱ. f1 和 f2 共享同一个内存索引结点
Ⅲ. fd1 和 fd2 分别指向各自的用户打开文件表中的一项
A. 仅Ⅲ B. 仅Ⅱ、Ⅲ C. 仅Ⅰ、Ⅱ D. Ⅰ、Ⅱ和Ⅲ
[tag_link]
正确答案：B
背景知识：
- 硬链接：f1 和 f2 是同一个 inode 的两个目录项（即它们指向同一个文件的 inode），共享 相同的索引节点（inode） 和数据块。
- 打开文件的过程：每个进程在打开文件时会创建：
- 一个对应的 用户级打开文件表项（即
fd指向它） - 用户打开文件表项再指向 系统级打开文件表项（Open File Table）
- 系统级表项包含文件的读写偏移量（读写指针）和对 inode 的引用分析选项：Ⅰ. f1 和 f2 的读写指针位置保持相同❌ 错误。虽然 f1 和 f2 是同一个文件（硬链接），但两个进程分别打开它们时，会在系统级打开文件表中生成两个不同的表项，每个表项维护独立的文件偏移量（读写指针），所以互不影响。Ⅱ. f1 和 f2 共享同一个内存索引结点✅ 正确。硬链接的本质就是多个目录项共享同一个 inode。即使路径不同（f1 和 f2），它们最终指向的是同一个 inode。Ⅲ. fd1 和 fd2 分别指向各自的用户打开文件表中的一项✅ 正确。每个进程维护自己的文件描述符表（用户级文件表），
fd1和fd2分别是两个不同进程打开文件得到的描述符，它们自然是指向各自进程的用户打开文件表项。Ⅱ 和 Ⅲ 正确，因此，正确答案为 B。
系统将数据从磁盘读到内存的过程包括以下操作：
① DMA 控制器发出中断请求
② 初始化 DMA 控制器并启动磁盘
③ 从磁盘传输一块数据到内存缓冲区
④ 执行“DMA 结束”中断服务程序
正确的执行顺序是（ ）。
A. ③→①→②→④ B. ②→③→①→④ C. ②→①→③→④ D. ①→②→④→③
[tag_link]
正确答案：B
在开始 DMA 传输时，主机向内存写入 DMA 命令块，向 DMA 控制器写入该命令块的地址，启动 I/O 设备。然后，CPU 继续其他工作，DMA 控制器则继续下去直接操作内存总线，将地址放到总线上开始传输。当整个传输完成后，DMA 控制器中断 CPU。因此执行顺序是 ②→③→①→④ 选 B。
假设 OSI 参考模型的应用层欲发送 400B 的数据（无拆分），除物理层和应用层之外，其他各层在封装 PDU 时均引入 20B 的额外开销，则应用层数据传输效率约为（ ）。
A. 80% B. 83% C. 87% D. 91%
[tag_link]
正确答案：A
OSI 参考模型共 7 层，除去物理层和应用层，剩五层。它们会向 PDU 引入 20Bx5 = 100B 的额外开销。应用层是最顶层，所以它的数据传输效率为 400B/500B=80%，选 A。
若信道在无噪声情况下的极限数据传输速率不小于信噪比为 30dB 条件下的极限数据传输速率，则信号状态数至少是（ ）。
A. 4 B. 8 C. 16 D. 32
[tag_link]
正确答案：D
可用 奈奎斯特定理 计算无噪声情况下的极限数据传输速率，用 香农定理 计算有噪信道极限数据传输速率。2Wlog2 N≥Wlog2 (1+S/N)，W是信道带宽，N是信号状态数，S/N是信噪比，将数据代入计算可得N≥32，选 D。（注意 分贝数=10log10 (S/N)。）
在下图所示的网络中，若主机 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
[tag_link]
正确答案：B
IEEE 802.11 数据帧有四种子类型，分别是 IBSS、From AP、ToAP、WDS。这里的数据帧 F 是从笔记本电脑发送往访问接入点（AP），所以属于 To AP 子类型。这种帧地址 l 是 RA (BSSID)，地址 2 是 SA，地址 3 是 DA。RA 是 Receiver Address 的缩写，BSSID 是 basic service set identifier 的缩写，SA 是 source address 的缩写，DA 是 destination address 的缩写。因此地址 1 是 AP 的 MAC，地址 2 是 H 的 MAC，地址 3 是 R 的 MAC，选 B。
下列 IP 地址中，只能作为 IP 分组的源 IP 地址但不能作为目的 IP 地址的是（ ）。
A. 0.0.0.0 B. 127.0.0.1 C. 200.10.10.3 D. 255.255.255.255
[tag_link]
正确答案：A
0.0.0.0/32 可以作为本主机在本网络上的源地址。127.0.0.1 是 loopback 地址，以它为目的 IP 地址的数据将被立即返回到本机。200.10.10.3 是 C 类 IP 地址。255.255.255.255 是广播地址。
直接封装 RIP、OSPF、BGP 报文的协议分别是（ ）。
A. TCP、UDP、IP B. TCP、IP、UDP C. UDP、TCP、IP D. UDP、IP、TCP
[tag_link]
正确答案：D
参考 路由协议对比 ，RIP 是一种分布式的基于距离向量的路由选择协议，通过广播 UDP 报文来交换路由信息。OSPF 是一个内部网关协议，不使用传输协议，如 UDP 或 TCP，而是直接用 IP 包封装它的数据。BGP 是一个外部网关协议，用 TCP 封装它的数据。因此选 D。
若将网络 21.3.0.0/16 划分为 128 个规模相同的子网，则每个子网可分配的最大 IP 地址个数是（ ）。
A. 254 B. 256 C. 510 D. 512
[tag_link]
正确答案：C
这个网络有 16 位的主机号，平均分成 128 个规模相同的子网，每个子网有 7 位的子网号，9 位的主机号。除去一个网络地址和广播地址，可分配的最大 IP 地址个数是 29-2=512-2=510，故选 C。
若甲向乙发起一个 TCP 连接，最大段长 MSS=1KB，RTT=5ms，乙开辟的接收缓存为 64KB，则甲从连接建立成功至发送窗口达到 32KB，需经过的时间至少是（ ）。
A. 25 ms B. 30 ms C. 160 ms D. 165 ms
[tag_link]
正确答案：A
按照 慢开始算法 ，发送窗口 = min{ 拥塞窗口，接收窗口｝，初始的拥塞窗口为最大报文段长度 1KB 海经过一个 RTT，拥塞窗口翻倍，因此需至少经过 5 个 RTT，发送窗口才能达到 32KB，所以选 A。这里假定乙能及时处理接收到的数据，空闲的接收缓存 ≥ 32KB。
下列关于 FTP 协议的叙述中，错误的是（ ）。
A. 数据连接在每次数据传输完毕后就关闭 B. 控制连接在整个会话期间保持打开状态 C. 服务器与客户端的 TCP 20 端口建立数据连接 D. 客户端与服务器的 TCP 21 端口建立控制连接
[tag_link]
正确答案：C
FTP 协议使用控制连接和数据连接，控制连接存在于整个 FTP 会话过程中，数据连接在每次文件传输时才建立，传输结束就关闭，A 和 B 是正确的。默认情况下 FTP 协议使用 TCP 20 端口进行数据连接，TCP 21 端口进行控制连接。但是是否使用 TCP 20 端口建立数据连接与传输模式有关，主动方式使用 TCP20 端口，被动方式由服务器和客户端自行协商决定，C 错，D 对。所以选 C。
请设计一个算法，将给定的表达式树（二叉树）转换为等价的中缀表达式（通过括号反映操作符的计算次序）并输出。例如，当下列两棵表达式树作为算法输入时：
输出的中缀表达式分别为 (a+b)*(c*(−d)) 和 (a*b)+(−(c−d)) 。
二叉树结点的定义如下：
typedef struct node{
char data[10]; // 存储操作数或操作符
struct node *left, *right;
} BTree;
要求：
(1) 给出算法的基本设计思想。
(2) 根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。
[tag_link]
1）算法的基本设计思想表达式树的中序序列加上必要的括号即为等价的中缀表达式。可以基于二叉树的中序遍历策略得到所需的表达式。（3 分）表达式树中分支结点所对应的子表达式的计算次序，由该分支结点所处的位置决定。为得到正确的中缀表达式，需要在生成遍历序列的同时，在适当位置增加必要的括号。显然，表达式的最外层（对应根结点）及操作数（对应叶结点）不需要添加括号。（2 分）
2）算法实现（10 分）
void preorder(node *root, int depth) {
if (!root) {
return;
}
bool isRoot = (depth == 1);
bool isLeaf = (!root->left && !root->right);
if (!isRoot && !isLeaf) {
printf("(");
}
preorder(root->left, depth+1);
printf("%s", root->data);
preorder(root->right, depth+1);
if (!isRoot && !isLeaf) {
printf(")");
}
}
void solve(node *root) {
preorder(root, 1);
}
将二叉树的中序遍历递归算法稍加改造即可得本题答案。除根结点和叶结点外，遍历到其他结点时在遍历其左子树之前加上左括号，在遍历完右子树后加上右括号。【评分说明】①若考生设计的算法满足题目的功能要求，则（1)、(2) 根据所实现算法的策略及输出结果给分，评分标准见下表。
| 分数 | 备注 |
|---|---|
| 15 | 采用中序遍历算法且正确，括号嵌套正确，层数适当 |
| 14 | 采用中序遍历算法且正确，括号嵌套正确，但括号嵌套层数过多。例如，表达式最外层加上括号，或操作数加括号，如 (a) |
| 11 | 采用中序遍历算法，但括号嵌套层数不完全正确。例如，左右括号数量不匹配 |
| 9 | 采用中序遍历算法，但没有考虑括号 |
| ≤7 | 其他 |
②若考生采用其他方法得到正确结果，可参照①的评分标准给分。③如果程序中使用了求结点深度等辅助函数，但没有给出相应的实现过程，只要考生进行了必要的说明，可不扣分。④若在算法的基本设计思想描述中因文字表达没有清晰反映出算法思路，但在算法实现中能够表达出算法思想且正确的，则可参照①的标准给分。⑤若算法的基本设计思想描述或算法实现中部分正确，可参照①中各种情况的相应给分标准酌情给分。
使用 Prim（普里姆）算法求带权连通图的最小（代价）生成树（MST）。请回答下列问题。
(1) 对下列图 G，从顶点 A 开始求 G 的 MST，依次给出按算法选出的边。
(2) 图 G 的 MST 是唯一的吗？
(3) 对任意的带权连通图，满足什么条件时，其 MST 是唯一的？
[tag_link]
1）Prim 算法 属于贪心策略。算法从一个任意的顶点开始，一直长大到覆盖图中所有顶点为止。算法每一步在连接树集合 S 中顶点和其他顶点的边中，选择一条使得树的总权重增加最小的边加入集合 S。当算法终止时，S 就是最小生成树。① S 中顶点为 A，候选边为 (A,D),(A,B),(A,E)，选择 (A,D) 加入 S。② S 中顶点为 A,D，候选边为 (A,B),(A,E),(D,E),(C,D)，选择 (D,E) 加入 S。③ S 中顶点为 A,D,E，候选边为 (A,B),(C,D),(C,E)，选择 (C,E) 加入 S。④ S 中顶点为 A,D,E,C，候选边为 (A,B),(B,C)，选择 (B,C) 加入 S。⑤ S 就是最小生成树。依次选出的边为 (A,D),(D,E),(C,E),(B,C)（4 分）【评分说明】每正确选对一条边且次序正确，给 1 分。若考生选择的边正确，但次序不完全正确，酌情给分。
2）图 G 的 MST 是唯一的。（2 分）第一小题的最小生成树包括了图中权值最小的四条边，其他边都比这四条边大，所以此图的 MST 唯一。
3）当带权连通图的任意一个环中所包含的边的权值均不相同时，其 MST 是唯一的。（2 分）此题不要求回答充分必要条件，所以回答一个限制边权值的充分条件即可。【评分说明】①若考生答案中给出的是其他充分条件，例如“带权连通图的所有边的权值均不相同”，同样给分。②若考生给出的充分条件对图的顶点数和边数做了某些限制，例如，限制了图中顶点的个数（顶点个数少于 3 个）、限制了图的形状（图中没有环）等，则最高给 1 分。③答案部分正确，酌情给分。
已知f(n)=∑i=0n 2i=2n+1−1=11⋯1 B，计算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)=232−1，而 f1(31) 的返回值却为 -1，为什么？若使 f1(n) 的返回值与 f(n) 相等，则最大的 n 是多少？
(5) f2(127) 的机器数为 7F80 0000H，对应的值是什么？若使 f2(n) 的结果不溢出，则最大的 n 是多少？若使 f2(n) 的结果精确（无舍入），则最大的 n 是多少？
[tag_link]
1）由于i和n是 unsigned 型，故i≤n−l是无符号数比较，n=0时，n−1的机器数为全1，值是232−1，为 unsigned 型可表示的最大数，条件i≤n−1永真，因此出现死循环。（2 分）若i和n改为 int 类型则不会出现死循环。（1 分）因为i≤n−1是带符号整数比较，n=0时，n−1的值是−1，当i=0时条件i≤n−1不成立，此时退出 for 循环。（1 分）
2）f1(23) 与 f2(23) 的返回值相等。（1 分）f(23) =223+1−1=224−1，它的二进制形式是24个1。int 占32位，没有溢出。float 有1个符号位，8个指数位，23个底数位，23个底数位可以表示24位的底数。所以两者返回值相等。f1(23) 的机器数是 00FF FFFFH。（1 分）f2(23) 的机器数是 4B7F FFFFH。（1 分）显而易见前者是24个1，即00000000111111111111111111111111(2)，后者符号位是0，指数位为23+12710 =100101102，底数位是111111111111111111111112。
3）当 n=24 时，f(24) = 1 1111 1111 1111 1111 1111 1111 B，而 float 型数只有 24 位有效位，舍入后数值增大，所以 f2(24) 比 f1(24) 大 1。（1 分）【评分说明】只要说明 f2(24) 需舍入处理即可给分。
4）显然 f(31) 已超出了 int 型数据的表示范围，用 f1(31) 实现时得到的机器数为 32 个 1，作为 int 型数解释时其值为 -1，即 f1(31) 的返回值为 -1。（1 分）因为 int 型最大可表示数是 0 后面加 31 个 1，故使 f1(n) 的返回值与 f(n) 相等的最大 n 值是 30。（1 分）【评分说明】对于第二问，只要给出 n=30 即可给分。
5）IEEE754 标准用“阶码全 1、尾数全 0”表示 无穷大。2 返回值为 f1oat 型，机器数 7F800000H 对应的值是+∞。（1 分）当 n=126 时，f(126) =2127−1=1.1…1×2126，对应阶码为 127+126=253，尾数部分舍入后阶码加 1，最终阶码为 254，是 IEEE754 单精度格式表示的最大阶码。故使 2 结果不溢出的最大 n 值为 126。（1 分）当 n=23 时，f(23) 为 24 位 1，f1oat 型数有 24 位有效位，所以不需舍入，结果精确。故使 f2 获得精确结果的最大 n 值为 23。（1 分）【评分说明】对于第二问，只要给出 n=23，即可给分。对于第三问，只要给出 n=126，即可给分。
在按字节编址的计算机 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？为什么？
[tag_link]
（1）M 为 CISC。（1 分）M 的指令长短不一，不符合 RISC 指令系统特点。（1 分）
（2）f1 的机器代码为 96B。（1 分）因为 f1 的第一条指令 “push ebp” 所在的虚拟地址为 0040 1020H，最后一条指令 “ret” 所在的虚拟地址为 0040 107FH，所以，f1 的机器指令代码长度为：0040 107FH - 0040 1020H + 1 = 60H = 96B（1 分）
（3）CF = 1。（1 分）cmp 指令实现 i 与 n-1 的比较功能，进行的是减法运算。在执行 f1(0) 过程中，n=0，当 i=0 时，i=0000 0000H，并且 n-1=FFFF FFFFH。因此，当执行第 20 条指令时，在补码加/减运算器中执行的是 “0 - FFFF FFFFH” 的操作，即：0000 0000H + 0000 0000H + 1 = 0000 0001H。此时，进位输出 C=0，减法运算时的借位标志 CF = C ⊕ 1 = 1。（2 分）
（4）f2 中不能用 shl 指令实现 power * 2。（1 分）因为 shl 指令用来将一个整数的所有有效位作为一个整体左移；而 f2 中的变量 power 是 float 型，其机器数中不包含最高有效位，但包含了阶码部分，将其作为一个整体左移时并不能实现 “乘 2” 的功能。因此在 f2 中不能用 shl 指令实现 power * 2。（2 分）浮点数运算比整型运算要复杂，耗时也较长。
假定题 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 是否会进入内核态？
[tag_link]
1）函数 1 的代码段中所有指令的虚拟地址的高 20 位相同，因此 1 的机器指令代码在同一页中，仅占用 1 页。（1 分）页目录号用于寻找页目录的表项，该表项包含页表的位置。页表索引用于寻找页表的表项，该表项包含页的位置。
2）push ebp 指令的虚拟地址的最高 10 位（页目录号）为 0000000001，中间 10 位（页表索引）为 0000000001，所以，取该指令时访问了页目录的第 1 个表项，（1 分）在对应的页表中访问了第 1 个表项。（1 分）
3）在执行 scanf0 的过程中，进程 P 因等待输入而从执行态变为阻塞态。（1 分）输入结束时，P 被中断处理程序唤醒，变为就绪态。（1 分）P 被调度程序调度，变为运行态。（1 分）CPU状态会从用户态变为内核态。（1 分）
某进程中有 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()）操作，要求确保线程互斥访问临界资源，并且最大程度地并发执行。
[tag_link]
先找出线程对在各个变量上的互斥、并发关系。如果是一读一写或两个都是写，那么这就是互斥关系。每一个互斥关系都需要一个信号量进行调节。
// 冲突：
// t1 和 t3 关于 y 有读写冲突
// t2 和 t3 关于 y, z 都有读写冲突
// 解决 t1 和 t3 关于 y 读写冲突
semaphore y_mutex1 = 1;
semaphore y_mutex2 = 1;
semaphore z_mutex = 1;
// 全局变量 x y z
cnum x, y, z;
thread1()
{
cnum w;
// 读 x, y
P(y_mutex1);
w = add(x, y);
V(y_mutex1);
// ...
}
thread2()
{
cnum w;
// 读 y, z
P(z_mutex);
P(y_mutex2);
w = add(y, z);
V(y_mutex2);
V(z_mutex);
// ...
}
thread3()
{
cnum w;
w.a = 1;
w.b = 1;
// 写 z
P(z_mutex);
z = add(z, w);
V(z_mutex);
// 写 y
P(y_mutex1);
P(y_mutex2);
y = add(y, w);
V(y_mutex2);
V(y_mutex1);
// ...
}
【评分标准】① 各线程与变量之间的互斥、并发情况及相应评分见下表。
| 变量/线程对 | thread1 和 thread2 | thread2 和 thread3 | thread3 和 thread4 | 给分 |
|---|---|---|---|---|
| x | 不共享 | 不共享 | 不共享 | 1 分 |
| y | 同时读 | 读写互斥 | 读写互斥 | 3 分 |
| z | 不共享 | 读写互斥 | 不共享 | 1 分 |
② 考生仅使用一个互斥信号量，互斥代码部分的得分最多给 2 分。③ 答案部分正确，酌情给分。
甲乙双方均采用后退 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) 甲方可以达到的最大信道利用率是多少？
[tag_link]
1）6 时刻到 t 时刻期间，甲方可以断定乙方已正确接收了 3 个数据帧，（1 分）分别是S0,0,S1,0,S2,0（1 分）。R3,3说明乙发送的数据帧确认号是 3，即希望甲发送序号 3 的数据帧，说明乙已经接收了序号为 0~2 的数据帧。
2）从t1时刻起，甲方最多还可以发送 5 个数据帧（1 分），其中第一个帧是S5,2（1 分），最后一个数据帧是S1,2（1 分）。发送序号 3 位，有 8 个序号。在 GBN 协议中，序号个数 ≥ 发送窗口 + 1，所以这里发送窗口最大为 7。此时已发送了S3,0和S4,1，所以最多还可以发送 5 个帧。
3）甲方需要重发 3 个数据帧（1 分），重发的第一个帧是S2,3（1 分）。在 GBN 协议中，接收方发送了 N 帧后，检测出错，则需要发送出错帧及其之后的帧。S2,0超时，所以重发的第一帧是S2。已收到乙的R2帧，所以确认号应为 3。 $$ \frac{7 \times \frac{8 \times 1000}{100 \times 10^6}}{0.96 \times 10^{-3} + 2 \times \frac{8 \times 1000}{100 \times 10^6}} \times 100% = 50% $$
4）甲方可以达到的最大信道利用率是U= 发送数据的时间/从开始发送第一帧到收到第一个确认帧的时间 =N⋅Td/(Td+RTT+Ta)U是信道利用率，N是发送窗口的最大值，Td是发送一数据帧的时间，RTT是往返时间，Ta是发送一确认帧的时间。这里采用捎带确认，Td=Ta。【评分说明】答案部分正确，酌情给分。