GATE 2017 CS 组 1

答案： D

说明

已知,

(¬ p) → (¬ q)

现在，

=> ¬ (¬ p) ∨ (¬ q) { 我们知道，x → y = ¬ (x) ∨ y }
=> (¬ ¬ p) ∨ (¬ q)
=> (p) ∨ (¬ q) { 因为双重否定律 }
=> (¬ q) ∨ (p) (这等价于语句 (iii))
=> (q) → (p) { 因为 x → y = ¬ (x) ∨ y } (这等价于语句 (ii))

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

答案： B

说明

已知,

一阶逻辑语句 --> F: ∀x (∃y R(x, y))

现在，逐一检查这些语句是否可以由 F 推导出来

(i) ∃y (∃x R(x, y))
           这是正确的。因为我们有 ∀x (∃y R(x, y)) → ∃x (∃y R(x, y)) → ∃y (∃x R(x, y))。

(ii) ∃y (∀x R(x, y))
           这是错误的。因为我们有 ∀x (∃y R(x, y)) ← ∃y (∀x R(x, y))。

(iii) ∀y (∃x R(x, y))
           这是错误的。因为 ∃y 不能推导出 ∀y。

(iv) ∼∃x (∀y ∼R(x, y))
           这是正确的。因为 ∼∃x (∀y ∼R(x, y)) = ∀x (∼ ∃y ∼ R(x, y)) = ∀x (∃y ∼∼(x, y)) = ∀x (∃y R(x, y))。

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

答案：C

说明

∑_ic_i a_i = 0 且 ∃_i : c_i ≠ 0 表明 A [ a₁, a₂, ...., a_n] 的列向量是线性相关的。且矩阵 A 的行列式为零。

因此，对于系统 Ax = b，

系数矩阵 A 的秩 = 增广矩阵 (A / B) 的秩 = k (k< n)

所以，系统 Ax = b 有无穷多解。

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

答案： B

说明

10 是常数，所以它的增长率为 0。而且，它不受 n 值的影响。

√n 的增长速度快于 log 但慢于线性。(考虑 √n² / √n = √n，而 log(n²)logn = 2)

n：其增长率为线性。

log₂n：增长率为对数。因为在渐近增长中，底数无关紧要。

100 / n：这里增长率随 n 减小。

因此，100/n < 10 < log2n < √n < n

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

答案：C

说明

Kruskal 算法用于找到连接森林中任意两棵树的最轻 (最贪婪) 的边。因此，它是一种贪心技术。

QuickSort 是一种分而治之算法。在每次迭代中，它选择一个元素作为枢轴，并将给定数组围绕选定的枢轴值进行分区。在这个过程中，我们将问题分解为子问题，求解它们，然后合并。因此，它是分而治之。

Floyd-Warshall 使用动态规划方法。它用于使用动态规划解决所有对最短路径问题。

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

答案： B

说明

给定节点数 (n) = 15

我们知道，当树完全倾斜时，二叉搜索树的高度将最大。

所以，最大高度 = n - 1
                        = 15 - 1
                       = 14

而当树是完全完整的树时，二叉搜索树的高度将最小。

所以，最小高度 = log₂(n+1) - 1
                             = log₂(15+1) - 1
                               = log₂(16) - 1
                               = 4?1
                               = 3

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

答案： D

说明

最小数值 = 0

i 位可能的最大数值 = 2ⁱ - 1
                                            = 2⁴ - 1
                                            = 16-1
                                            = 15

f 位可能的最大数值 = 1 - 2^-f
                                           = 1- 2^-4
                                           = 1- 1/2^-4
                                           = 1-1/16
                                           = 15/16

现在，范围 = 2ⁱ - 1 + 1 - 2^-f
                  = 2ⁱ - 2^-f

因此，最大范围 = 0 到 2ⁱ - 2^-f

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

答案： B

说明

根据问题，m 和 n 是有效的列表，但没有明确说明列表是空的还是非空的。所以我们有两种情况

情况 1：如果列表不是 NULL
例如

在 join 操作之前
     m =1->2->3->4->5->null
     n =6->7->8->9->null

在 join 操作之后
     1->2->3->4->5->null
     6->7->8->9->1->2->3->4->5->null

情况 2：如果列表是 NULL
   那么连接和引用 m 和 n 将会产生 NULL 指针问题。
因此，选项 (B) 是正确答案。