GATE 2018 CS 组 3

答案：C

说明

根据问题，我们必须使用 LOJ（左外连接操作），通过属性 B，该属性是表 s 的主键和表 r 的外键。

因此，我们需要在连接的左表（即表 r）上应用条件 σB<5，因为左外连接 (LOJ) 返回左表中所有不与右表匹配的值以及来自内连接的所有值。

所以，选项 (C) 是正确答案。

答案： B

说明

rollno, courseid -> email

rollno, courseid 是一个超键，并且该关系没有传递依赖。因此，它在 3NF 中。

email -> rollno

对于 BCNF，每个决定因素都应该是候选键。这里 email 是决定因素，但不是候选键。因此，给定的模式不在 BCNF 中。

答案： D

说明

已知,
y = 顶点的度数
z = 连通分量的数量
根据问题，当且仅当 u 的标签可以通过交换 v 的标签中的两个相邻数字获得时，顶点 u 和 v 之间存在一条边。

交换数字的集合将是 {(1, 2), (2, 3), ......(99, 100)}，这将等于 99 个这样的集合。因此，边的数量 = 99，每个顶点将有 99 条与其对应的边。

假设一个图有 3! 个顶点，那么它的顶点将是 {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}....

我们以顶点 {123} 为例，它的度数将是 2，因为它将连接到另外两个顶点，即 {213} 和 {132}。

所以，每个顶点的度数 (y) = 99

答案： B

说明

P(H_G | H_D) = P(H_G?H_D) / P(H_D)
     = P(H_D | H_G) * P(H_G) / P(H_D)
      = 0.40 * 0.2 * 1 / P(H_D)。

P(H_D) = P(H_D | H_G).P(H_G) + P(H_D | M_G).P(M_G) + P(H_D | L_G).P(L_G)
     = 0.4 * 0.2 + 0.1 * 0.5 + 0.01 * 0.3
     = 0.133

∴ P(H_G | H_D) = 0.40 * 0.2 * 1 / P(H_D)
     = 0.080.133
     = 0.6015

因此正确选项是 (B)。

答案： A

说明

开始时，将调用 count(1024, 1024)，x/2 将减小 x 的值。在这里，'*' 将打印十次。当 count=10 时，x 的值将变为 1。一旦 x 达到 1，将调用 count(1024,y-1)。现在，它将执行直到 y 的值变为 1，即在第 1023 次调用时。

在这里，对于每个 y，count() 被递归调用，并且对于每个 y，count() 被调用 10 次。

因此，

print 语句的执行次数 = 1023 * 10
                                                                                     = 10230

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

答案： A

说明

首先，将最小元素 1 设置为根。现在还剩下 6 个元素。左子树将有 3 个元素，并且每个左子树组合可以以 2! 种方式设计。

       = ⁶C₃ * 2! * 2!
       = (6 * 5 * 4 / 3 * 2 * 1) * 2 * 2
       = 20 * 2 * 2
       = 80

答案： A

说明

为了最大化 G 的最小权重生成树的数量，x 的值应该为 5，因为它有另外两个角顶点的选择，这将使 MST 的数量最大化。

根据 Kruskal 算法求 MST

首先选择权重为 1 和 3 的边

现在，权重为 4 的边将创建一个循环，因此不会被选择。

现在，两个选定的顶点都有 2 - 2 种选择来选择顶点。选择权重为 4 和 5 的边，将得到 2*2 = 4 个 MST。

因此，MST 的总数量为 2*2 = 4

答案： B

说明

根据问题，按价值/重量的降序对它们进行排序

现在，开始挑选物品。
首先挑选物品 4，剩余重量 = 11-2 = 9 公斤。
其次，物品 1 不能被挑选，因为重量是 10 公斤 > 9 公斤。
第三，物品 3 可以被挑选，因为 4 公斤 < 9 公斤，剩余重量 = 9-4 = 5 公斤

再次，物品 2 不能被挑选，因为 7 公斤 > 5 公斤。

因此，只挑选了物品 3 和物品 4。

所以，V_greedy = 24+20 = 44
V_optimal - V_greedy = 60-44 = 16 答案。