GATE 2018 CS 组 3

答案：C

说明

(i) 31.500 可以表示为：

(31.5)₁₀ = (11111.100)₂
        = 2⁴ + 2³ + 2² + 2¹ + 2⁰ + 2^-1
        = 16 + 8 + 4 + 2 + 1 + 0.5 = (31.05)₁₀

(ii) 0.875 可以表示为：

(0.875)10 = (00000.111)2
        = 2^-1 + 2^-2 + 2^-3
        = 0.50 + 0.25 + 0.125
        = (0.875)₁₀

我们无法用无符号 8 位定点二进制数表示 (iii) 和 (iv)。

因此，正确答案是选项 C。

答案： B

说明

已知,
物理地址空间 = 2^p 字节
字长 = 2^w 字节（即，每个字的大小为 2^W 字节）
缓存大小 = 2ⁿ 字节
标签大小 = 2^X 字节
偏移位 = M
块大小 = 2^m 字 = 2^m * 2^w 字节 = 2(^m+w) 字节

由于它是 K 路组相联缓存，缓存中的每个组将包含 K 个块。

行数 = 缓存大小 / 块大小 = 2(^n-m-w)
组数 = 行数 / K = 2(^n-m-w)/K

我们知道，

标签位数 = 主内存位数 - 组位数 - 偏移位数
   x = P - W - (N - M - W - log2k ) - M
         = P - W - N + M + W + log₂k - M
         = P - N + log₂k

答案： B

说明

I. 考虑：
   { a^m bⁿ c^p d^q | m + p = n + q, 其中 m, n, p, q ≥ 0}
   m + p = n + q 或 m-n = q-p。

给定语言中的字符串是 --> {ε ab, ad, bc, cd, abcd, abbc, aabb, aadd, acdd, bbcc, ccdd, aaabdd, aaabbd, bcccdd, aabcdd, ........}

从以上可以看出，给定语言是上下文无关文法，因此可以为该文法设计下推自动机 (PDA)。

II. 考虑：
   { a^m bⁿ c^p d^q | m = n 且 p = q, 其中 m, n, p, q ≥ 0}
   因为 m = n 且 p = q

给定语言中的字符串是 --> { ε, ab, cd, abcd, aabbcd, abccdd, aaabbbccdd, .......}

从以上可以看出，给定语言是上下文无关文法，因此可以为该文法设计下推自动机 (PDA)。

III. 考虑：
   { a^m bⁿ c^p d^q | m = n = p 且 p ≠ q, 其中 m, n, p, q ≥ 0}
   m=n=p 且 p ≠ q

它不是上下文无关文法。因此无法为该文法设计下推自动机 (PDA)。

IV. 考虑：
   { a^m bⁿ c^p d^q | mn = p + q, 其中 m, n, p, q ≥ 0}
   mn = p+q，不是上下文无关的。

它不是上下文无关文法。因此无法为该文法设计下推自动机 (PDA)。

因此，选项 (B) 是正确答案。

答案： D

说明

-> 在第一个选项中，无限制文法的成员资格问题（即 REL）是不可判定的，因为可能进入无限循环。

-> 在第二个选项中，每个正则语言都是 REL（不可判定），但 REL 可能正则也可能不正则。

-> 在第三个选项中，没有给出文法的类型，因此 REL 中的等价问题是不可判定的。

-> 在第四个选项中，每个正则语言都是确定性 CFL，这是一个琐碎的属性，是可判定的。

因此，选项 (D) 是正确答案。

答案： D

说明

给定字符串 = bbaacabc

最长的可能前缀是 bbaac，它可以从 T3 获得。abc 是另一个可能的前缀，它将从 T3 获得。因此，正确选项是 D。

答案： A

说明

因为我们知道，出现在较低级别的运算符会先计算。因此 $ 具有更高的优先级和左结合性。而 # 是右结合性。

因此，选项 (A) 是正确答案。

答案： A

说明

可用 (3, 3, 0)，可以满足 P0 或 P2 的请求。

如果我们选择 P0 <3, 3, 0>。那么完成后，我们将拥有 (3, 3, 0) + (1, 0, 1) = (4, 3, 1)
如果我们选择 P2 <0, 3, 0>。那么完成后，我们将拥有 (4, 3, 1) + (1, 0, 3) = (5, 3, 4)
如果我们选择 P1 <1, 0, 2>。那么完成后，我们将拥有 (5, 3, 4) + (1, 1, 2) = (6, 4, 6)
如果我们选择 P3 <3, 4, 1>。那么完成后，我们将拥有 (6, 4, 6) + (2, 0, 0) = (8, 4, 6)

因此，执行顺序是：P0->P2->P1->P3。那么系统处于安全状态。

因此，选项 (A) 是正确答案。

答案：C

说明

已知,
Empty = 0（表示已填充的槽数）。
Full = N（可用空槽数）
Mutex = 1

在生产者-消费者问题中，当缓冲区中的槽为空时，生产者会放置一个项，当缓冲区已满时，它会等待。在给定的问题中，当缓冲区中有可用槽时，full 将为 0；当缓冲区中没有可用槽时，P：full。

现在，当生产者将一个项放入缓冲区时，这意味着缓冲区中消费者开始读取的可用槽数增加。所以 Q：empty。

同样，当缓冲区中没有可供消耗的项时，消费者会等待。这可以通过 wait(empty) 来表示。所以 R：empty

一旦消费者消耗了一个项，这意味着缓冲区中可供生产者写入的可用槽数增加了。所以 S：full。

因此，选项 (C) 必须是正确答案。