答案：C

说明

根据规则，一个有 4 个顶点的图将有 3 条边的生成树。这里，权重为 1 和 2 的边必须包含在最小生成树 (MST) 中，我们还剩下选择一条边，其权重为 3、4、5 和 6。根据问题，我们必须使 MST 的权重最大化。因此，我们选择权重为 3 的边，使其形成一个环，因此被排除。现在我们选择权重为 4 的边，它可以包含在该图的 MST 中。因此，可能的最大权重是 1+2+4 = 7。

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

答案： B

说明

陈述 1 是错误的。我们可以看到下面的图中，边权重 3 - 4 - 5 形成一个环，其中 3 是最轻的边，但不能包含在 MST 中。

陈述 2 是正确的。在上面的图中，1-2-3 是一个环，3 是最重的边。如果最重的边在一个环中，那么我们总是会排除它，因为如果发现环，这意味着我们可以有其他低成本边的选择。

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

答案： D

说明

当队列元素按降序排序时，while 循环将运行最大次数。假设队列元素最初是 16、15、14、13、......、2、1。现在根据问题，16 将首先被推入栈中，因此栈顶是 16，Head(Q) 是 15。因此，16 将从栈中弹出并入队到队列中。两次迭代后，队列元素将是：15、14、13、....、2、1、16，栈将为空。

类似地，剩余的每个元素 15、14、13、......、2 都将推入栈中，然后立即从栈中弹出并入队到队列中。30 次迭代后，栈将为空，队列包含 1、16、15、14、......、2 等元素。现在 1 将从队列中出队并推入栈中。一旦 1 推入栈中，它就无法再次弹出。由于当前队列中没有小于 1 的元素，因此无法弹出 1。这里总迭代次数是 31，所以在 31 次迭代后，队列是 = 16、15、14、....、2，栈包含 1。

再次使用类似的逻辑，我们可以看到再经过 29 次迭代，即总计 = 31+29，队列将变为 16、15、14、......、3，栈包含 1、2。这里 2 是栈顶元素，它将永远留在栈中。

以类似的方式执行上述步骤，我们可以看到，在 31+29+27+25+....+1 次迭代后，队列将为空。因此，这是一个公差为 2 的等差数列。

因此，和 = (16∗(1+31))/2 = 16∗32/2 = 256。因此选项 (D) 将是正确答案。

答案： D

说明

G₁ 产生字符串 b, ab, bb, aab, abb, bbb, ... 即 a^mbⁿ, m≥0 且 n>0 (因为 a 的数量不确定，a 和 b 的数量是独立的，但只有 b 是可能的)。

G₂ 产生字符串 a, b, aa, ab, bb, aaa, aab, abb, bbb, ... 即 a^mbⁿ, m>0 或 n>0 (因为它必须至少有一个 a 或一个 b)。

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

答案： D

说明

PDA 在第一个最终状态接受的字符串是 aⁿ, n≥0，PDA 在第二个最终状态接受的字符串是 aⁿbⁿ, n≥0。因此 PDA 接受的语言是

L = {aⁿ|n≥0}∪{aⁿbⁿ|n≥0}

该语言是确定性上下文无关语言 (CFL)，由确定性 PDA (dpda 已给出) 接受，而不是正则语言，因为我们需要一个栈来实现它。因此它不能被 FA 接受。

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

答案：C

说明

X 是递归语言，所以 X' 也是递归的。Y 是递归可枚举但非递归语言，所以 Y' 不是递归可枚举语言。

设 W 和 Z 是另外两个语言，使得 Y' 归约到 W，Z 归约到 X'

现在取 Y' 归约到 W (Y' --> W)：我们知道递归可枚举语言的补集不是递归可枚举的。所以 W 不是递归可枚举的。

再次取 Z 归约到 X' (Z--> X')：由于 Z ≤ X' 是递归的。(规则：如果 Z 可归约到 X'，且 X' 是递归的，则 Z 是递归的。) 因此选项 (B) 和 (D) 被排除。

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

答案：C

说明

已知,
   表达式 = 2 - 5 + 1 - 7 ∗ 3
   现在，求解表达式得到
       = 2 - 5 + 1 - 7 * 3
       = 2 - 6 - 7 * 3
       = 2 - (-1) * 3
       = 3 * 3
       = 9

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

答案：C

说明

我们知道自底向上分析器从下到上构建语法树。它从给定的字符串构建到起始符号。在给定的问题中，给定字符串是 aab，起始符号是 S。因此过程是从 aab 开始并到达 S。因此，

S→aA 打印 1
A→aSb 打印 3
A→aab 打印 2

现在，由于自底向上分析器将以相反的顺序工作，因此它将打印 231。因此选项 (C) 是正确答案。