GATE 2016 CS 组 2

答案：C

说明

已知,
删除 - Θ(1)
插入 - O(N)
查找 - Θ(N)
减键 - Θ(N)
现在，从使用以上信息，我们得到
Θ(N) ∗ Θ(1) + O(logN) ∗ O(N) + O(logN) ∗ Θ(N) + Θ(N) ∗ Θ(N)
同样，通过使用渐近记号的属性，并在移除较低项后，我们得到 O(N²)

答案： D

说明

给定，(0 + 1)∗ (0 + 1)(0 + 1)∗
(0 + 1) (0 + 1)∗ (因为，R∗ . R∗ = R∗)
(0 + 1 )+

现在，如果我们绘制 DFA，那么我们只需要两个状态。因此 DFA 将是

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

答案：C

说明

S₁ → aS₁b|ε
语言 L₁ 生成语法，因为 a 的数量应等于 b 的数量。在这种字符串中，所有 a 都应在所有 b 之前。生成的语法是
L₁ = {aⁿbⁿ|n≥0}
因此，给定的语法属于上下文无关语言，而不是正则语言。因此，P 为假。

S₂ → abS₂|ε
语言 L₂ 生成语法，因为 a 的数量应等于 b 的数量。但在这种创建的字符串中，a 和 b 的顺序不同。生成的语法是
L₂={(ab)ⁿ|n≥0}
因此，给定的语法属于具有正则表达式 (ab)∗ 的正则语言。因此，Q 为真。
因此，选项 (C) 将是正确的答案。

答案： D

说明

声明 1：由于 L₃ 是递归的，因此 L₃' 也将是递归的。由于递归语言在并集下是封闭的，因此 L₃' U L₄ 也是递归的。

声明 2：由于 L₂ 是上下文无关语言。L₂' 不一定是 CFL，但它可以是递归的。由于 L₃ 是递归的，因此 L₂ U L₃ 也是递归的，因为递归语言在并集下是封闭的。

声明 3：L₁∗ 是正则的，因为正则语言在闭包下是封闭的。L₂ 是上下文无关的。正则语言和上下文无关语言的交集是上下文无关语言。因此 L₁∗ ∩ L₂ 是上下文无关的。

声明 4：L₂' 可能或可能不是上下文无关的，因为 CFL 在补集下不是封闭的。因此 L₁ ∪ L₂' 可能或可能不是上下文无关的。因此，它不为真。

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

答案： B

说明

词法分析使用正则表达式。
自顶向下解析使用最左推导生成字符串。
类型检查在语义分析阶段完成。
激活记录在运行时加载到堆栈内存中。

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

答案： D

说明

根据 Belady 异常，它证明在使用先进先出 (FIFO) 页面替换算法时，增加页面帧的数量会导致页面错误的数量增加。因此选项 (D) 是正确的答案。

答案： A

说明

B⁺ 树是一种自平衡树数据结构。在 B⁺ 树中，所有叶节点的深度（从根到叶的长度）都相同。这通过插入和删除操作成为可能。在此操作中，我们以一种方式执行插入，即如果我们增加了插入后的树的高度，那么我们需要从根增加高度。类似地，如果我们在删除后必须降低高度，那么我们需要将根移动一个级别。这种类型的插入和删除确保了每个叶节点的深度相同。因此选项 (A) 将是正确的答案。

答案： A

说明

我们知道，只有当给定的图不包含任何循环时，串行计划才有可能，这确保了该计划不会发生冲突的可串行化。此外，具有拓扑排序的图必须是一个无环图。并且 BFS 可以用于循环图和无环图。因此选项 (A) 将是正确的答案。