GATE 2013

答案：a

说明

结合性

在集合 S 上定义的二元运算 * 如果满足以下条件，则称为可结合的：

对于所有 a, b, c ∈S，a * (b * c) = (a * b) * c。

交换性

在集合 S 上定义的二元运算 * 如果满足以下条件，则称为可交换的：

对于所有 a, b, ∈ S，a * b = b * a。

在这种情况下，组合元素的顺序无关紧要。

解决方案

这里在整数集上的二元运算定义为 x ⊕ y = x^2 + y^2。
关于可交换性：x ⊕ y = y ⊕ x。

左侧 => x ⊕ y = x^2 + y^2
右侧 => y ⊕ x = y^2 + x^2
左侧 = 右侧。因此可交换。

关于可结合性：x ⊕ (y ⊕ z) = (x ⊕ y) ⊕ z

左侧 => x ⊕ (y ⊕ z) = x ⊕ (y^2 + z^2) = x^2 + (y^2 + z^2)^2

右侧 => (x ⊕ y) ⊕ z = (x^2 + y^2) ⊕ z = (x^2 + y^2)^2 + z^2

因此，左侧 ≠ 右侧，所以不可结合。

另一种解决方案

可交换，因为 xy 总是与 yx 相同。

不可结合，因为 (xy)z 是 (x^2 + y^2)^2 + z^2，而 x(yz) 是 x^2 + (y^2 + z^2)^2。

答案：a

说明

首先，在处理这个问题之前，你应该了解行列式的基本性质
对于这类问题。

1) 应用任何行或列变换都不会改变行列式。

2) 如果交换任意两行，行列式符号会改变。

A = | 1 x x^2 |
| 1 y y^2 |
| 1 z z^2 |

证明选项 (b)

=> 应用列变换 C2 -> C2 + C1

C3 -> C3 + C1

=> det(A) = | 1 x + 1 x^2 + 1 |
| 1 y + 1 y^2 + 1 |
| 1 z + 1 z^2 + 1 |

证明选项 (c)，

=> 应用行变换 R1 -> R1 - R2

R2 -> R2 - R3

=> det(A) = | 0 x - y x^2 - y^2 |
| 0 y - z y^2 - z^2 |
| 1 z z^2 |

证明选项 (d)，

=> 应用行变换 R1 -> R1 + R2

R2 -> R2 + R3

=> det(A) = | 2 x + y x^2 + y^2 |
| 2 y + z y^2 + z^2 |
| 1 z z^2 |

答案：b

说明

二进制补码是二进制数上的一个数学运算，它是一个基数补码的例子。它在计算中用作带符号数表示的一种方法。

N 位数的二进制补码定义为其相对于 2^N 的补码；一个数与其二进制补码之和为 2^N。例如，对于三位二进制数 010₂，其二进制补码为 110₂，因为 010₂ + 110₂ = 1000₂ = 8₁₀，等于 2³。二进制补码是通过翻转位并加一来计算的。

对于 n 位 2's 补码数字，数字的范围是 -(2^(n-1)) 到 +(2^(n-1) - 1)

答案：a

说明

由于有多个输出，并且输出数量少于输入数量，因此这是一个优先级编码器。

当输入有效时，V=1，对于优先级编码器，它会检查遇到的第一个高位。除了所有位至少有一位是高位之外，“x”表示“不关心”，因为我们已经找到一个高位。所以答案是 (A)。

答案：b

解释：为了按升序排序元素，选择排序总是从剩余的未排序数组中选择最大元素，并将其与剩余数组的最后一个元素进行交换。因此，它进行的交换次数为 n-1，即 O(n)

答案：c

解释：插入一个元素，我们首先需要搜索它的位置。对于像下面这样的倾斜树，搜索操作可能需要 O(n)。

要插入 50，我们将不得不遍历所有节点。

答案：a

说明

： L1 L2* U L1*

L1 L2* 的结果是 **Φ**。

{ **Φ**} 表示空语言。**Φ** 与任何其他语言的连接是 **Φ**。它在乘法中起 0 的作用。

L1* = **Φ***，即 { **ε** }。

**Φ** 和 { **ε** } 的并集是 { **ε** }

答案：c

说明

问题中给出了一个没有 ε 和单元产生式的文法（即 A -> ? 和 A -> a 类型）。

为了获得最大的归约次数，我们应该确保在每个中间式中只有一个终结符被归约。由于没有单元产生式，因此最后 2 个标记将只花费 1 次操作。因此，在每个中间式中，我们都可以通过一个产生式归约 2 个标记。例如，如果我们的文法是 S -> AA，A -> a，则我们可以归约 4 个标记的字符串 abcd。S -> AA -> Aa -> aa，或者S -> AA -> AA -> aA -> aa，所以我们最多可以归约 n/2 次。

因此，为了归约长度为 n 的输入字符串，先使用 n-2 次归约操作归约 n-2 个标记，然后使用具有 . 的产生式归约最后 2 个标记。所以总共是 n-2+1 = n-1 次归约操作。

假设字符串是 abcd。（n = 4）。

我们可以写出接受该字符串的文法如下：

S -> aB

B -> bC

C -> cd

上述最右推导是

S -> aB （归约 3）

-> abC （归约 2）

-> abcd （归约 1）

我们可以看到这里没有任何单元或 ε 产生式。因此有 3 次归约。

我们可以通过另一个不产生单元或 ε 产生式的文法得到更少的归约次数，

S -> abA

A-> cd

上述最右推导是

S -> abA （归约 2）

-> abcd （归约 1）

因此有 2 次归约。

但我们对了解最大归约次数感兴趣，这来自第一个文法。因此，总共 3 次归约作为最大值，即 (n - 1)，因为这里 n = 4。

因此，选项 B。

答案：b

解释：调度算法的工作方式类似于轮转调度，时间片为 T。一个进程的轮次到来并且它执行了 T 个单位后，它的等待时间将达到最低，并且它将在其他所有进程都获得了 T 个单位的令牌后再次轮到它。因此，这种算法等同于轮转调度。

答案：c

解释：可以通过 XML 轻松猜出答案。XML 用于信息表示。

答案：b

说明

选项 A 可能导致死锁。想象一下这种情况，进程 X 已获得 a，进程 Y 已获得 b，进程 Z 已获得 c 和 d。现在存在循环等待。

选项 C 也可能导致死锁。想象一下这种情况，进程 X 已获得 b，进程 Y 已获得 c，进程 Z 已获得 a。现在存在循环等待。

选项 D 也可能导致死锁。想象一下这种情况，进程 X 已获得 a 和 b，进程 Y 已获得 c。X 和 Y 相互循环等待。

以选项 A 为例，这里所有 3 个进程都是并发的，所以 X 将获得信号量 a，Y 将获得 b，Z 将获得 c，现在 X 被阻塞等待 b，Y 被阻塞等待 c，Z 获得 d 并被阻塞等待 a。因此，这将导致死锁。

类似地，人们可以找出 B) 的完成顺序是 Z、X 然后是 Y。

答案：c

说明

语言的识别器是识别该语言的机器。
语言的判定器是判定该语言的机器。

两种类型的机器在接受状态下对属于该语言的字符串停止。
判定器在字符串不属于该语言时也会停止。
识别器可能在字符串不属于该语言时停止，也可能不停止。

在所有输入上
判定器必须停止（在接受或拒绝状态下）
识别器可能在某些字符串上停止，也可能不停止（问：在哪些字符串上？）

如果某个图灵机可以判定一个语言，则该语言是图灵可判定的（或可判定的）。也称为递归语言。

如果某个图灵机可以识别一个语言，则该语言是图灵可识别的。也称为递归可枚举语言。

递归（图灵可判定）语言在以下方面是封闭的：
Kleene 星号、连接、并集、交集、补集和集合差。

递归可枚举语言在 Kleene 星号、连接、并集、交集下是封闭的。它们在补集或集合差下不封闭。

答案：a

说明

1. 我们可以使用 BFS 或 DFS 来查找无向图中是否存在环。例如，请参阅用于检测无向图中环的 DFS 基础实现。时间复杂度为 O(V + E)，它是多项式的。
2. 如果一个问题属于 P，那么它肯定属于 NP（可以在多项式时间内验证）。请参阅 NP 完全性。
3. 正确。NP 完全性。

答案：c

解释：Bellman-Ford 算法的时间复杂度为 O(VE)，其中 V 是顶点数，E 是边数。对于具有 n 个顶点的完全图，V = n，E = O(n²)。因此，总时间复杂度变为 O(n³)。

答案：a

说明

缓存中的组数 = v。因此，主内存块 j 将映射到组 (j mod v)，该组将是缓存行 (j mod v) * k 到 (j mod v) * k + (k - 1) 中的任意一行。
(关联性不影响映射——k 路关联意味着一个块有 k 个位置，因此减少了替换的可能性。)

答案：d

说明

选项 C 也是正确的。

选项 D x'⊕y' = x"y' + x'y" = xy' + x'y = x⊕y ≠ x⊙y

因此选项 (D) 是错误的。

答案：a

说明

一个函数在某个点 c 处是连续的，

f(x) 定义为 x > c 的值为 f(x) 定义为 x < c 的值 = f(x) 定义为 x = c 的值

选项 A 中的所有值都是 2

答案：d

说明

梯形法则

dx = h/2[(y0 - yn) +2(y1 + y2+ . . . . . . . . . . . . + yn-1)

其中 h = b - a/n

这里 y0, yn => 极端纵坐标

a = 下限

b = 上限

这里 h = 3 - 0 / 10 = 0.3（宽度）

dx = 0.3 / 2 [(0 + 9) +2(0.009 + 0.36 + . . . . . . . . . . . . . . . . . . . . . . . . . . . . + 7.29)]

= 0.3 / 2 [ 9 + 2(25.65)]

= 0.3 / 2 [ 9 + 51.3]

= 9.045

答案：选项 (D)

由于区间是均匀的，应用梯形法则的均匀网格公式。

答案：c

解释：长度为 3 的循环可以由 3 个顶点形成。从 8 个顶点中选择 3 个顶点总共有 8C3 种方式。一对顶点之间存在边的概率是 1/2。因此，长度为 3 的无序循环的期望数量 = (8C3) * (1 / 2) ^ 3 = 7

答案：c

说明

P 对于无向图是正确的，因为添加一条边总是会使两个顶点的度数增加 1。

Q 是正确的：如果我们考虑度数之和并减去所有偶数度数，我们将得到一个偶数，因为每条边都会使度数之和增加 2。因此，奇数度顶点的总数必须是偶数。

答案：a

解释：在图论的数学领域，无向图 G 的线图是另一个图 L(G)，它表示 G 的边之间的邻接关系。L(G) 的构建方式如下：为 G 中的每条边创建一个 L(G) 中的顶点；对于 G 中有公共顶点的任意两条边，在 L(G) 中创建它们对应顶点之间的边。

答案：d

说明

F(x) => x 是我的朋友

P(x) => x 是完美的

D 是正确答案。

A. 存在一些不是完美的我的朋友。

B. 有些人不是我的朋友且是完美的。

C. 存在一些人既不是我的朋友也不是完美的。

D. 不存在是我的朋友且是完美的任何人。

答案：d

说明

MBR - 内存缓冲区寄存器（存储正在传入和传出即时访问存储器的数​​据）

MAR - 内存地址寄存器（保存需要访问的数​​据的内存位置。）

PC - 程序计数器（它包含当前时间正在执行的指令的地址）

第一条指令将 PC 的值放入 MBR。

第二条指令将地址 X 放入 MAR。

第三条指令将地址 Y 放入 PC。

第四条指令将 MBR 的值（即旧 PC 值）放入内存。

现在从第一条和第四条指令可以看出，控制流不是顺序的，并且 PC 的值被存储在内存中，以便控制可以再次回到它离开执行的地址。

这种行为在中断处理中很常见。X 可以是内存中包含中断服务例程开始地址的位置地址。
Y 可以是中断服务例程的开始地址。

在条件跳转的情况下（如选项 C），只有 PC 会被更新为目标地址，并且不需要将旧 PC 值存储到内存中。

在指令获取和操作数获取的情况下（如选项 A 和 B），PC 值不会存储在其他任何地方。

因此选项 D。

答案：d

说明

文件大小为 42797KB = 4279 * 2^10B = 85594 * 2^9B。

现在一个扇区 = 512B

所以文件将存储在 85594 个扇区中，即我们需要跨越 85594 个扇区。

文件起始位置是

需要跨越的柱面数 = 85594 / (16 * 64) = 85594 / 1024 ≈ 83.58 => 83 个柱面

需要跨越的剩余扇区数 = 85594 - (83 * 16 * 64) = 85594 - 85000 - 128 = 85594 - 85192 = 402

需要跨越的磁头数 = 9

因此，为了跨越 9 个磁头，我们需要再跨越一个柱面，因为文件是从磁头 9 开始的，而一个柱面中的磁头数为 16，所以

需要跨越的柱面数 = 83 + 1 = 84

所以柱面号 1200 + 84 = 1284

答案：c

说明

heapify() 方法的时间复杂度

让我们从 heapify() 方法开始，因为我们还需要它来构建堆。

在 heapify() 函数中，我们从上到下遍历树。大小为 n 的二叉树的高度（不包括根）最多为 log₂ n，即如果元素数量翻倍，树只增加一个级别。

因此，heapify() 函数的复杂度为 O(log n)。

buildHeap() 方法的时间复杂度

为了最初构建堆，heapify() 方法被调用为每个父节点——向后，从最后一个节点开始，到树根结束。

大小为 n 的堆有 n / 2（向下取整）个父节点。

由于 heapify() 方法的复杂度如上所示为 O(log n)，因此 buildHeap() 方法的复杂度最多为* O(n log n)。

* 在接下来的一个部分中，我将展示 buildHeap() 方法的时间复杂度实际上是 O(n)。由于这不会改变整体时间复杂度，因此执行此深入分析并非强制性。

Heapsort 的总时间复杂度

heapify() 方法被调用 n-1 次。因此，修复堆的总复杂度也为 O(n log n)。

因此，这两个子算法都具有相同的时间复杂度。所以

Heapsort 的时间复杂度为：O(n log n)

答案：b

解释：这里我们必须说出返回的 k 值，而不是时间复杂度。

外层循环运行 n / 2 次。

内层循环运行 logn 次。（2 ^ k = n => k = logn）。

现在看看内层循环中的 k 值，n 被加到 k 中，运行 logn 次，因为内层循环运行 logn 次。

因此，总时间复杂度是内层循环乘以外层循环复杂度，即 (n 用于外层，nlogn 用于内层) n * logn。

因此，内层循环运行一次后的 k 值为 n^2logn。

答案：d

说明

(D) 是错误的。

L1 是正则的，因此其补集也应该是正则的。

L1 是形式为 0^* 1^* 0^* 的正则语言。另一方面，L2 是 CFL，因为它可以从以下 CFG 推导出来：
L2 = { 0^p 1^q 0^r | p, q, r > 0 且 p ≠ r }
S -> AC | CA
C -> 0C0 | B
A -> 0A | 0
B -> 1B | ε
如果为 L2 构建 CFG 比较困难，可以直观地将其简化为一个更简单的问题。L2 与一个已知的 CFL L3 = { a^m b^l | m ≠ n } 非常相似。

(A) L2 是上下文无关的，这是正确的 [正确]

(B) L1 与 L2 的交集是上下文无关的，这是正确的，因为 L1 是正则语言而 L2 是 CFL。RL 与 CFL 的并集总是 CFL。因此 [正确]

(C) L2 的补集是递归的，这是正确的，因为 CFL 的补集肯定是 CSL（上下文相关语言），而 CSL 又是一个递归语言的子集。因此 [正确]

(D) L1 的补集是上下文无关但不是正则的，这是错误的，因为正则语言的闭包定律。RL 的补集总是 RL。因此 [错误]

答案：d

说明

1 是正确的。L(A) 是正则的，其补集也应该是正则的。正则语言也是上下文无关的。

2 是正确的。

3 是错误的，DFA 可以最小化为两个状态。第二个状态是最终状态，并且在遇到 0 之后我们会到达第二个状态。

4 显然是错误的，因为 DFA 接受单个 0。

答案：d

说明

临界区，其中进程可能正在更改公共变量、更新表、写入文件并执行其他功能。重要的问题是，如果一个进程在其临界区执行，则不允许任何其他进程在其临界区执行。每个进程必须请求进入其临界区的权限。信号量是用于同步的工具，它用于解决临界区问题，即不允许两个进程同时运行，为了解决这个问题，使用了两个信号操作，称为 wait 和 signal，用于消除临界区的互斥。作为无符号的、最重要的同步原语之一，因为您可以构建许多其他原语。递减信号量称为获取或锁定它，递增称为释放或解锁。

解决方案

由于信号量的初始值为 2，因此两个进程可以同时进入临界区——这是不好的，我们可以看到原因。
假设 X 和 Y 是进程。X 将 x 加 1，Z 将 x 减 2。现在，Z 存储回，然后 X 存储回。因此，x 的最终值为 1 而不是 -1，并且两个 Signal 操作使信号量值再次变为 2。所以，现在 W 和 Z 也可以像这样执行，x 的值可以是 2，这是任何执行顺序中的最大可能值。（如果信号量初始化为 1，进程将正确执行，我们将得到最终
x 的值为 -2。）

选项 (D) 是正确答案。

另一种解决方案

进程可以以多种方式运行，以下是一种 x 达到最大值的案例。信号量 S 初始化为 2。
进程 W 执行 S = 1，x = 1，但它不更新 x 变量。
然后进程 Y 执行 S = 0，它递减 x，现在 x = -2 并且 signal 信号量 S = 1
现在进程 Z 执行 s = 0，x = -4，signal 信号量 S = 1
现在进程 W 更新 x = 1，S = 2。然后进程 X 执行 X = 2
所以正确选项是 D

另一种解决方案

S 是一个计数信号量，初始化为 2，即两个进程可以进入由 S 保护的临界区。W、X 读取变量，加 1 并写回。Y、Z 读取变量，减 2 并写回。
每当 Y 或 Z 运行时，计数就会减少 2。因此，为了获得最大的总和，我们应该将变量复制到其中一个增加计数的进程中，同时，同时运行的递减进程应该在内存中写回的内容可以被递增进程覆盖。因此，实际上递减永远不会发生。

答案：c

说明

M = 0 表示此数据包是原始数据包所有片段中的最后一个。因此，答案是 A 或 C。

已知 HLEN 字段为 10。标头长度是 32 位字的数量。因此，标头长度 = 10 * 4 = 40 字节。

此外，给定总长度 = 400。

总长度指示数据包的总长度，包括标头。

因此，不包括标头的报文长度 = 400 - 40 = 360 字节。

最后一个字节地址 = 2400 + 360 - 1 = 2759（因为编号从 0 开始）。

答案：a

说明

答案是“无变化”。

内聚性是指模块元素属于在一起的程度。

耦合是软件模块之间相互依赖的方式和程度。

M1 和 M2 之间的耦合 = (外部链接数) /

(模块数)

= 2 / 2

= 1 模块内聚性 = (内部链接数) / (方法数)

M1 的内聚性 = 8 / 4 = 2

M2 的内聚性 = 6 / 3 = 2

将方法 m 移动到 M2 后，我们得到以下结果：

耦合 = 2 / 2 = 1

M1 的内聚性 = 6 / 3 = 2

M2 的内聚性 = 8 / 4 = 2

答案：c

说明

这里的目的是既不发生死锁，也不使二元信号量的值大于一。

A 会导致死锁。

B 可能会使信号量的值在 1 到 n 之间增加。

D 在某些情况下可能会将信号量 R 和 S 的值增加到 2。

答案：d

说明

给定的两个 LR(1) 项集是

X -> c.X, c / d

X -> .cX, c / d

X -> .d, c / d

并且

X -> c.X, $

X -> .cX, $

X -> .d, $

逗号后的符号/终结符是前视符号。

这些是 LR(1)（LR(1) 也称为 CLR(1)）项集。

LALR(1) 解析器将 LR(1) 项集组合起来，这些项集在它们的第一个分量方面相同，但在它们的第二个分量方面不同。

在 LR(1) 项集 (A -> B, c) 的产生式规则中，A -> B 是第一分量，而前视符号集，即这里的 c，是第二分量。

现在我们可以看到，在给定的集合中，对应产生式规则的第一分量在两个集合中是相同的，它们只在第二分量（即它们的前视符号）上有所不同，因此我们可以合并这些集合以形成一个单一的集合，该集合将是

X -> c.X, c/d/$

X -> .cX, c/d/$

X -> .d, c/d/$

这是为了减少解析器状态的总数。

现在我们可以检查给定的陈述。

陈述 1：该陈述是错误的，因为合并已经完成，因为第二个分量即前视符号是不同的。

陈述 2：在合并后的集合中，我们看不到任何移位-归约冲突（因为不可能发生归约，当出现 P -> q. 形式的产生式时才可能发生归约）。

陈述 3：在合并后的集合中，我们看不到任何归约-归约冲突（原因同上，不可能发生归约，因此没有 R-R 冲突的可能性）。

陈述 4：该陈述也是错误的，因为 goto 是在非终结符符号上进行的，而不是在终结符符号上进行的，而 c 是一个终结符符号。

因此，所有陈述都是错误的，选项 D。

答案：d

说明

• 第一个是 CFG 的空性；CFG 是否为空，这个问题是可判定的。
• 第二个是 CFG 的所有内容；CFG 是否会生成所有可能的字符串（CFG 的完备性），这个问题是不可判定的。
• 第三个是 REC 的正则性；TM 生成的语言是否是正则的，是不可判定的。
• 第四个是正则的等价性；DFA 和 NFA 生成的语言是否相同是可判定的。

第二个和第三个是不可判定的。因此，选项 (D) 是正确的。

答案：b

说明

由于 c 是按值传递而 x 是按引用传递，因此所有函数都将具有相同的 x 副本，但 c 的副本不同。

f(5, 5) = f(x, 4) * x = f(x, 3) * x * x = f(x, 2) * x * x * x = f(x, 1) * x * x * x * x = 1 * x * x * x * x = x^4

由于每次函数调用 x 都会增加，所以在 f(x, 2) 调用后它变成 9。因此，表达式 x^4 的值为 9^4，即 6561。

答案：d

说明

为了从给定的遍历序列构建二叉树，其中一个遍历序列必须是中序。另一个遍历序列可以是前序或后序。我们知道二叉搜索树的中序遍历总是按升序排列，因此中序遍历将是给定前序遍历的升序，即 10, 15, 20, 23, 25, 30, 35, 39, 42。现在我们必须从给定的中序和前序遍历构建一棵树。

答案：b

解释：由于队列最初是空的，while 循环的条件永远不会为真。因此，时间复杂度为 ⊝(n)。

答案：b

说明

流水线必须停顿直到 l4 的 Ei 阶段完成，ss Ei 阶段将指示是否采取分支。

然后 l4(WO) 和 l9(Fi) 可以并行进行，之后是后续指令。

因此，直到 l4(Ei) 完成：7 个周期 * (10 + 1) ns = 77ns

从 l4(WO) 或 l9(Fi) 到 l12(WO)：8 个周期 * (10 + 1)ns = 88ns

总计 = 77 + 88 = 165 ns

答案：b

说明

RAM 芯片大小 = 1k × 8 [每字 8 位，共 1024 字]

要构建的 RAM = 16k × 16

所需芯片数量 = (16k x 16) / ( 1k x 8) = (16 x 2)

[垂直方向有 16 个芯片，每个芯片水平方向有 2 个芯片]

因此，要从 16 个垂直芯片中选择一个芯片，我们需要一个 4 x 16 的解码器。

可用的解码器是 2 x 4 解码器

要构建的是 4 x 16 解码器

因此需要 4 + 1 = 5 个解码器。

答案：(A) (D)

说明

给定陈述是：**¬ ∃ x ( ∀ y(α) ∧ ∀ z(β) )**

其中 ¬ 是否定运算符，∃ 是存在量词，意思是“存在”，∀ 是全称量词，意思是“对于所有”，而 α、β 可以被视为谓词。

这里我们可以对给定的陈述应用一些命题逻辑和一阶逻辑的标准结果，如下所示。

[结果 1：¬(∀x P(x)) <=> ∃ x ¬P(x)，即“对于所有”的否定给出“存在”，否定也应用于量词的作用域，即这里的 P(x)。同样，“存在”的否定给出“对于所有”，否定也应用于量词的作用域]

[结果 2：¬ ( A ∧ B ) = ( ¬A ∨ ¬B ) ] - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -(1)

[结果 3：¬P ∨ Q <=> P -> Q ] - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - (2)

[结果 4：如果 P -> Q，那么根据逆否命题的结果，¬Q -> ¬P]

现在我们需要按如下方式使用这些结果：

¬ ∃ x ( ∀y(α) ∧ ∀z(β) ) - - - - - - - - - - - - - - - - - - - - - [ 给定 ]

=> ∀ x (¬∀y(α) ∨ ¬∀z(β) ) - - - - - - - - - - - - - - - - - [ 应用 **结果 1** & **结果 2** 后 ]

=> ∀ x ( ∀y(α) -> ¬∀z(β) ) - - - - - - - - - - - - - - - - -[应用 **结果 3** 后 ]

=> **∀ x ( ∀ y(α) -> ∃ z(¬β) )** - - - - - - - - - - - - - - - - -[应用 **结果 1** 后] 这与陈述 C 相同。

因此，给定陈述在逻辑上等同于陈述 C。

现在，我们还可以证明给定陈述在逻辑上等同于选项 B 中的陈述。

让我们看看如何！

上面推导出的陈述是

∀ x ( ∀y(α) -> ∃z(¬β) )

现在这个陈述可以写成（或等同于）

=> **∀ x ( ∀ z(β) -> ∃ y(¬α) )** - - - - - - - - - - - - - - - - - - - - - - - - - -[应用 **结果 4** 后]

并且这个陈述与陈述 B 相同。

因此，给定陈述在逻辑上也是等同的

与陈述 B。

所以，我们可以得出结论，给定陈述**不**在逻辑上等同于

陈述 **A** 和 **D**。

因此，正确答案是选项 A 和选项 D。但在 GATE 2013 中，所有人都因这道题而得分。

答案：b

说明

r1. . . . . . . r2

a. . . . . . . b . . . . . . . c = a + b

a. . . . . . . x = c * c

a.......x......但我们必须将 c 存储到内存中，因为我们不知道 x 是否大于 a . . . . . . . 或不是

y.......x......y = a * a

选择 x > a 的最佳情况，最小溢出 = 1

答案：b

说明

请注意，为了解决上述问题，我们不允许代码运动。

因此，我们将逐行分析代码，并确定执行上述代码片段所需的寄存器数量。

假设寄存器编号为 R1、R2、R3 和 R4。分析如下表所示：

因此，根据以上分析，我们可以得出结论，执行上述代码片段最少需要 4 个寄存器。

答案：b

解释：只有测试用例 3 和 4 能够捕获缺陷。当一个旧字符被替换为一个新字符，而新字符又被另一个新字符替换时，代码无法正常工作。这种情况不会发生在测试用例 (1) 和 (2) 中，它只发生在情况 (3) 和 (4) 中。

答案：c

说明

Test Case 1
abcde
abbcd

Test Case 2
abcde
addde

Test Case 3
abcde
aacde

答案：c

说明

设页面大小为 'x' 位。T1 的大小 = 2^x 字节

(这是因为 T1 恰好占用一个页面)

现在，T1 中的条目数 = (2^x) / 4（因为每个页表条目是 32 位或 4 字节大小）

T1 中的条目数 = 第二级页表数量（因为每个 I 级页表条目存储 II 级页表的基址）

第二级页表的总大小 = ((2^x) / 4) * (2^x)

类似地，II 级页表中的条目数 = III 级页表数量 = ((2^x) / 4) * ((2^x) / 4)

第三级页表的总大小 = ((2^x) / 4) * ((2^x) / 4) * (2^x)

类似地，所有 III 级页表中的总条目数（页面数）= ((2^x) / 4) * ((2^x) / 4) * ((2^x) / 4) = 2^(3x - 6)

虚拟内存大小 = 2^46

虚拟内存中的页面数 = (2^46) / (2^x) = 2^(46 - x)

III 级页表中的总页面数 = 虚拟内存中的页面数。2^(3x - 6) = 2^(46 - x)

3x - 6 = 46 - x => 4x = 52 => x = 13

这意味着页面大小为 13 位，或页面大小 = 2^13 字节 = 8 KB

答案：c

说明

1 MB 16 路组相联虚拟索引物理标记缓存（**VIPT**）。

缓存块大小为 64 字节。

块数 = 2^20 / 2^6 = 2^14。

组数 = 2^14 / 2^4 = 2^10。

VA(46)

+- - - - - - - - - - - - - - - - -+

标签(30) , 组(10) , 块偏移(6)

+- - - - - - - - - - - - - - - - -+

在 VIPT 中，如果页面偏移的位数 = (组 + 块偏移)，那么只需要一种页面颜色。

但是我们需要 8 种颜色，因为缓存组索引和物理页号重叠的位数是 3，所以需要 2^3 种页面颜色。

因此选项 c 是答案。

答案：a

说明

让我们使用关系模式 R(A, B, C, D, E, F, G, H) 和 FD F = {CH → G, A → BC, B → CFH, E → A, F → EG} 来计算候选键。

使用所有 FD 的 RHS，我们推断出 D 没有被任何给定的 FD 确定，因此属性 D 肯定会是所有可能的候选键的一部分。

1. 计算 D 的闭包，即 D+ = D - - - - - - - - - - - (a)
2. 计算 D 的闭包，即 DA+ = D A B C F H E G - - - - - - - - - - - (b)
3. 计算 D 的闭包，即 DB+ = D B C F H E G A - - - - - - - - - - - (c)
4. 计算 D 的闭包，即 DC+ = DC - - - - - - - - - - - (d)
5. 计算 D 的闭包，即 DE+ = D E A B C F H G - - - - - - - - - - - (e)
6. 计算 D 的闭包，即 DF+ = D F E G A B C H - - - - - - - - - - - (f)
7. 计算 D 的闭包，即 DG+ = DG - - - - - - - - - - - (g)
8. 计算 D 的闭包，即 DH+ = DH - - - - - - - - - - - (h)

候选键是 AD、BD、ED 和 FD。根据第二范式的定义，没有非主属性可以部分依赖于表的键。该表不在第二范式中，因为非主属性依赖于候选键的子集。

候选键是 AD、BD、ED 和 FD。在以下所有 FD 中，非主属性都依赖于部分候选键。

A -> BC
B -> CFH
F -> EG.

答案：b

说明

Nadir 的意思是“下方”

1. 天文学：天球上观测者正下方的点，与天顶相对。

2. 最低点：他们财富的低谷。

答案：a

解释：弥漫（diffuseness）的意思是广泛传播。

答案：c

说明

这是一个递减的等差数列，公差的绝对值为 2。数列为 44, 42, 40 ... 0, -2, -4 ...

如果我们计算到 0 或 2 的和，则和最大。

所以，使用等差数列求和公式，和为 506。

答案：a

说明

如果你是一只鸟，你会在天上飞翔。

条件从句和主句

第一、第二和第三种条件句

条件句的用法

第一种条件句

1. 性质：开放条件，条件中所说的情况是可能的。
2. 时间：此条件指现在或将来的时间。
   例：If he is late, we will have to go without him. (如果他迟到，我们将不得不没有他离开。)
   If my mother knows about this, we are in serious trouble. (如果我妈妈知道这件事，我们就麻烦大了。)

第二种条件句

1. 性质：不真实（不可能）或不大可能的情况。
2. 时间：现在；时态是过去时，但我们谈论的是现在，就是现在。
   例：If I knew her name, I would tell you. (如果我知道她的名字，我会告诉你的。)
   If I were you, I would tell my father. (如果我是你，我会告诉我爸爸。)
   比较：If I become president, I will change the social security system. (Said by a presidential candidate) (如果我当总统，我将改变社会保障制度。（一位总统候选人说的）)
   If I became president, I would change the social security system. (Said by a schoolboy: improbable) (如果我当了总统，我就会改变社会保障制度。（一个学童说的：不大可能）)
   If we win this match, we are qualified for the semifinals. (如果我们赢得这场比赛，我们就获得了半决赛资格。)
   If I won a million pounds, I would stop teaching. (improbable) (如果我赢得一百万英镑，我会停止教学。（不大可能）)

第三种条件句

1. 性质：不真实
2. 时间：过去（所以我们谈论的是过去没有发生的情况。）例如：If you had warned me, I would not have told your father about that party. (But you didn't, and I have). (如果你当时警告我，我就不会把那个派对的事告诉你的父亲了。（但你没有，我告诉了。）)

答案：c

说明

正确的句子是“She is a European.”

“an”适用于那些发音以 a, e, i, o, u 开头的词。

这里的发音是“Yuropean”（E 不发音；有“Y”的声音），类似于“a University”。

因此是a European。

答案：b

说明

(√ 2 - √ 1) / (√ 2 + √ 1) (√ 2 - √ 1) + (√ 3 - √ 2) / (√ 2 + √ 2) (√ 3 - √2) + . . . . . . . . . . . . .

化简为

(√ 2 - √ 1) + (√ 3 -√ 2) + . . . . . . . . (√ 81 - √ 80)

再次化简为：√81 - √1，即 8

答案：d

说明

共有 90 个两位数，其中 13 个能被 7 整除，它们是 14, 21, 28, 35, 42, 49, 56, 63, 70, 77, 84, 91, 98。

因此，选出的数字不能被 7 整除的概率 = 1 - 13 / 90 = 77/ 90。

所以，选项 (D) 是正确的。

答案：d

解释： A、B、C 均无意义。

只有选项 D“没有逆境可以让人放弃希望”与给定的信息相关。

答案：c

解释：设总距离为 D

总时间 = D(1 / 2 * 60 + 1 / 4 * 30 + 1 / 4 * 10) = D / 24

平均速度 = 总距离 / 总时间 = 24

答案：b

解释：成本与每人每天的工资和工作时间成正比。

工资增加 1/5，工作时间减少 1/24。

所以成本变为 (当前成本) * (1 + 1 / 5) * (1 - / 24) = 13200 * (6 / 5) * (23 / 24) = 15180

答案：b

说明

最小生成树（MST）或最小权重生成树是指对于一个加权、连通且无向的图，其权重小于或等于所有其他生成树权重的生成树。

在选项 (A) 中，树的权重为 103，但它不是图的子图，因为在原始图中节点 (6) 和 (7) 之间没有边。

在选项 (B) 中，树的权重为 99

在选项 (C) 中，树的权重为 127

在选项 (D) 中，树的权重为 106

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