GATE 2018 CS 组 3

49) 一个布尔函数 F 的最小项列表形式如下。

F(P, Q, R, S) = ∑ m(0, 2, 5, 7, 9, 11) + d(3, 8, 10, 12, 14)

其中，m 表示最小项，d 表示无关项。函数 F 的必包含素蕴含式的数量是 ______。

1. 4
2. 1
3. 2
4. 3

50) RISC 处理器的指令流水线具有以下阶段：指令取指 (IF)、指令译码 (ID)、操作数取指 (OF)、执行操作 (PO) 和写回 (WB)。IF、ID、OF 和 WB 阶段对于每条指令都花费 1 个时钟周期。考虑一个由 100 条指令组成的序列。在 PO 阶段，40 条指令每条花费 3 个时钟周期，35 条指令每条花费 2 个时钟周期，其余 25 条指令每条花费 1 个时钟周期。假设没有数据冒险，也没有控制冒险。

完成指令序列执行所需的时钟周期数是 ______。

1. 219
2. 220
3. 229
4. 224

51) 一个处理器有 16 个整数寄存器（R0, R1, ... , R15）和 64 个浮点寄存器（F0, F1,... , F63）。它使用 2 字节指令格式。指令有四种类别：Type-1、Type-2、Type-3 和 Type-4。Type-1 类别包含四条指令，每条有 3 个整数寄存器操作数（3Rs）。Type-2 类别包含八条指令，每条有 2 个浮点寄存器操作数（2Fs）。Type-3 类别包含十四条指令，每条有一个整数寄存器操作数和一个浮点寄存器操作数（1R+1F）。Type-4 类别包含 N 条指令，每条有一个浮点寄存器操作数（1F）。

N 的最大值是 __________。

1. 32
2. 34
3. 30
4. 36

52) 给定一个语言 L，定义 Lⁱ 如下

        L⁰ = {ε}
     Lⁱ = L^i-1 * L for all i > 0

语言 L 的阶数定义为最小的 k，使得 L^k = L^k+1。

考虑由以下自动机接受的语言 L1（在字母表 0 上）。

L1 的阶数是 _____。

1. -2
2. 1
3. 2
4. 无

53) 考虑一个存储磁盘，有 4 个盘片（编号 0, 1, 2 和 3），200 个磁道（编号 0, 1, ... , 199），以及每个磁道 256 个扇区（编号 0, 1, ... , 255）。磁盘控制器同时收到以下 6 个形式为 [扇区号, 磁道号, 盘片号] 的磁盘请求

[120, 72, 2] , [180, 134, 1] , [60, 20, 0] , [212, 86, 3] , [56, 116, 2] , [118, 16, 1]

目前磁头位于 80 号磁道的 100 号扇区，并正朝向更高的磁道号移动。在移动 100 个磁道时平均功耗为 20 毫瓦，并且反转磁头方向一次的功耗为 15 毫瓦。与旋转延迟和磁头在不同盘片之间切换相关的功耗可忽略不计。

使用最短寻道时间优先 (SSTF) 磁盘调度算法来满足所有上述磁盘请求的总功耗（单位为毫瓦）是 _______。

1. 80
2. 85
3. 87
4. 88

54) 考虑一个 IP 数据包，长度为 4,500 字节，其中包含一个 20 字节的 IPv4 头部和一个 40 字节的 TCP 头部。该数据包被转发到一个支持最大传输单元 (MTU) 为 600 字节的 IPv4 路由器。假设此数据包所有传出片段中的 IP 头部长度均为 20 字节。假设第一个片段中存储的碎片偏移值是 0。

第三个片段中存储的碎片偏移值是 _______。

1. 72
2. 142
3. 144
4. 无

55) 考虑一个简单的通信系统，其中多个节点通过共享广播介质（如以太网或无线）连接。系统中的节点使用以下载波侦听式介质访问协议。一个节点在接收到要传输的数据包后，会侦听介质 5 个单位的时间。如果节点在此期间未检测到任何其他传输，则在下一个时间单位开始传输其数据包。如果节点检测到其他传输，它会等待直到该其他传输完成，然后再次开始侦听 5 个单位的时间。一旦它们开始传输，节点就不会进行任何冲突检测，即使发生冲突也会继续传输。所有传输持续 20 个单位的时间。假设传输信号在介质中的传播速度为每单位时间 10 米。

假设系统有两个节点 P 和 Q，它们之间的距离为 d 米。P 在成功完成其载波侦听阶段后，于 t=0 时开始传输数据包。节点 Q 在 t=0 时有一个要传输的数据包，并开始侦听介质。

Q 成功避免其提议传输与 P 的正在进行的传输发生冲突的最大距离 d（以米为单位，四舍五入到最接近的整数）是 _____。

1. 52
2. 60
3. 55
4. 50

56) “他们从哪里拿书？_________ 拿 _________ 的书从 _________。” 填入以上句子空白处的最佳单词是

1. Their, they're, there
2. They're, their, there
3. There, their, they're
4. They're, there,there