GATE 2018 CS 组 3

25) 考虑一个长连接的 TCP 会话，端到端带宽为 1 Gbps（= 10⁹ 比特/秒）。会话开始时的序列号为 1234。在此序列号可以再次使用的最小时间（以秒为单位，四舍五入到最接近的整数）是 _______。

1. 43
2. 34
3. 36
4. 无

26) 考虑一个矩阵 P，其唯一的特征向量是的倍数。

考虑以下陈述。

(I) P 没有逆矩阵
(II) P 有重根特征值
(III) P 无法对角化

以下哪个选项是正确的？

1. 只有 I 和 III 必然正确
2. 只有 I 和 II 必然正确
3. 只有 II 必然正确
4. 只有 II 和 III 必然正确

27) 令 N 为自然数集。考虑以下集合。

P：有理数集（正数和负数）
Q：从 {0, 1} 到 N 的函数集
R：从 N 到 {0, 1} 的函数集
S：N 的有限子集集。

以上哪些集合是可数的？

1. 只有 Q 和 S
2. 只有 P 和 S
3. 仅 P 和 R
4. 只有 P, Q 和 S

28) 考虑一阶逻辑语句

φ ? ∃s∃t∃u∀v∀w∀x∀y ψ(s, t, u, v, w, x, y)

其中 ψ(s, t, u, v, w, x, y) 是一个不含量词的一阶逻辑公式，仅使用谓词符号，可能包含等号，但不包含函数符号。假设 φ 在一个包含 7 个元素的论域的模型存在。

以下哪个陈述必然正确？

1. 至少存在一个 φ 的模型，其论域大小小于或等于 3。
2. 不存在 φ 的模型，其论域大小小于或等于 3。
3. 不存在 φ 的模型，其论域大小大于 7。
4. φ 的每个模型都有大小为 7 的论域。

29) 考虑以下 C 程序

上述程序的输出是

1. Hi Bye Bye Hi
2. Bye Hi Hi Bye
3. Hi Bye Hi Bye
4. Bye Hi Bye Hi

30) 令 G 为一个简单无向图。令 TD 为 G 的深度优先搜索树。令 TB 为 G 的广度优先搜索树。考虑以下陈述。

(I) G 的边在 TD 中都不是交叉边。（G 中的交叉边是连接两个节点之间的边，在这两个节点中，没有一个是 TD 中的祖先。）
(II) 对于 G 的任意一条边 (u,v)，如果 u 在 TB 中的深度为 i，v 在 TB 中的深度为 j，则 |i - j| = 1。

以上哪个陈述必然为真？

1. 仅 I
2. 仅 II
3. I 和 II
4. 既不是 I 也不是 II

31) 假设将一个 p × q 维的矩阵 G₁ 与一个 q × r 维的矩阵 G₂ 相乘需要 pqr 次标量乘法。计算 n 个矩阵 G₁ G₂ G₃... G_n 的乘积可以通过不同的方式加括号来实现。对于给定的括号化，如果 G_iG_i+1 直接相乘，则称它们为显式计算的对。例如，在矩阵乘法链 G₁ G₂ G₃ G₄ G₅ G₆ 中，使用括号化 (G₁ (G₂ G₃ ))(G₄ (G₅ G₆ ))，G₂ G₃ 和 G₅ G₆ 是唯一显式计算的对。

考虑矩阵乘法链 F₁ F₂ F₃ F₄ F₅，其中矩阵 F₁, F₂, F₃, F₄, 和 F₅ 的维度分别为 2×25, 25×3, 3×16, 16×1, 和 1×1000。在 F₁ F₂ F₃ F₄ F₅ 的括号化中，最小化标量乘法总数的括号化，显式计算的对是

1. 只有 F1 F2 和 F3 F4
2. 只有 F2 F3
3. 只有 F3 F4
4. 只有 F1 F2 和 F4 F5

32) 考虑以下 C 代码。假设 unsigned long int 类型长度为 64 位。

当使用输入 2⁴⁰ 调用 fun 时返回的值是

1. 4
2. 5
3. 6
4. 40