GATE 2016 CS 组 2

答案： A

说明

最坏情况发生在未返回路径需要最长路径的时候。在这里，通过调用 A(n)，我们得到 A(n/2) 5 次，所以递归关系将是

A(n) = 5A(n/2) + O(1)

因此，通过应用主定理来解决这个递归关系，我们得到

情况 1：a > b^k
        a = 5, b = 2, f(n) = O(1), _nlog_ba = _nlog₂5
        A(n) = _nlog_ba = _nlog₂5 = 2.32

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

答案： B

说明

根据问题，我们需要 BST 树的高度为 6，并且我们有七个不同的数字可以插入 BST。为了获得高度 6，我们必须将 1 或 7 放在根节点。除了根节点，我们在每个级别都有两个选项，即节点是左节点还是右节点。

因此，BST 的总数 = 1 * 26 = 64

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

答案： B

说明

为了表示一个图，如果我们使用矩阵，那么设置孪生指针的最有效算法的时间复杂度将是 O(n²)。现在，如果我们使用邻接表，它将是

2(边 + 顶点) = 2(m+n) = O(m+n)。

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

答案： B

说明

陈述 I 为假，因为没有提及状态之间的转换。在 NFA 中，不能定义所有状态都具有所有符号的转换。

陈述 II 为真，因为我们知道空语言 (A = Φ) 是正则的，所以它与任何其他语言的交集都是 Φ。因此，A ∩ B 是正则的。

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

答案： B

说明

已知,

L1 = {aⁿ b^m c^n+m : m, n ≥ 1}
L2 = {aⁿ bⁿ c²ⁿ : n ≥ 1}

L1 是上下文无关的。可以设计 PDA，使其将 a 推入堆栈，然后将 b 推入堆栈，并

弹出 a 和 b，用于每个 c。当输入中没有剩余的 c，并且堆栈为空时，该语言将被接受。

L₂ 不是上下文无关的。它是上下文敏感语言

{aⁿ bⁿ: n ≥ 1} 也是上下文无关的。但是当我们检查 a 和 b 与 c 的相等性时，使用 PDA 的堆栈内存是不可能的。

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

答案：C

说明

L₁ = {| M 在某些输入上至少需要 2016 步}：在 L₁ 中，一旦我们找到在 2016 步内接受的字符串，我们就可以停止给出任何字符串的输入。

L₂ = {M | M 在所有输入上至少需要 2016 步}：在 L₂ 中，我们需要检查所有可能的输入，其长度小于 2016，而这个字符串是一个有限的字符串集合。

从上面可以清楚地看到，对于 L₁ 和 L₂，机器肯定会停止。因此，L₁ 和 L₂ 都是递归的。

L₃ = {M | M 接受 ε}：L₃ 是不可判定的，因为 M 接受 ε。所以 L₃ 不是递归的。

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

答案： B

说明

选项 A 由于产生式规则：A->Aa，具有直接左递归。

选项 C 由于产生式规则：S-> Aa 和 A->Sc，具有间接左递归

选项 D 具有间接左递归，因为：A-> Bd 和 B-> Ae

选项 B 没有任何递归（既不是直接也不是间接左递归）。

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

答案： A

说明

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