GATE 2016 CS 集合 1-6 - Tpoint Tech

41) DMA 控制器的data count寄存器的大小为 16 位。处理器需要将 29,154 千字节的文件从磁盘传输到主存。内存是字节可寻址的。 DMA 控制器从处理器获取系统总线控制权以将文件从磁盘传输到主存所需的最小次数是__________。

452
456
1823
465

答案： B

说明

给定，DMA 控制器的数据计数寄存器的大小 = 16 位

由于内存是字节可寻址的，因此可以在一个周期内传输的数据 = 2¹⁶ 字节 = 64 千字节

现在，要传输的文件大小 = 29154 千字节

因此，DMA 控制器需要从处理器获取系统总线控制权以将文件从磁盘传输到主存的最小次数（周期）= (29154/64) = 456

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

42) 4 级流水线的各个阶段延迟分别为 800、500、400 和 300 皮秒。第一阶段（延迟 800 皮秒）被替换为功能等效的设计，该设计涉及两个阶段，各自的延迟分别为 600 和 350 皮秒。流水线的吞吐量增加百分比为__________。

33 或 34
31 或 32
43
35

答案： A

说明

给定，第一阶段涉及两个阶段，各自的延迟分别为 600 和 350 皮秒

流水线1 的吞吐量 (T1) = 1/最大延迟 = 1/800

流水线2 的吞吐量 (T2) = 1/最大延迟 = 1/600

吞吐量增加百分比 = (T2-T1)/T2 * 100

= ( (1/600) - (1/800) ) / (1/800) * 100

= 200/600 * 100

= 33.33%

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

43) 考虑一个用于添加两个 n 位整数的进位超前加法器，该加法器使用扇入最多为 2 的门构建。使用此加法器执行加法所需的时间为

Θ(1)
Θ(log(n))
Θ( √n)
Θ(n)

答案： B

说明

如果扇入 = 输入数量，则超前进位生成器在恒定时间内给出输出。
假设，计算需要 O(1) 时间
c₄ = g₃ + p₃g₂ + p₃p₂g₁ + p₃p₂p₁g₀ + p₃p₂p₁p₀c₀，如果存在带有 5 个输入的 OR 门。
现在，如果我们有 8 个输入，以及一个带有 2 个输入的 OR 门，要构建一个带有 8 个输入的 OR 门，则我们需要在 level-1 中使用 4 个门，在 level-2 中使用 2 个门，在 level-3 中使用 1 个门。因此，对于每个级别，有 3 个门延迟。
类似地，如果由 2 输入门构造 n 输入门，则总延迟将为 O(log n)。
因此，选项 (B) 将是正确答案。

44) 以下函数计算包含在大小为 n 的整数数组 p[] 中的最大值 (n >= 1)。

int max(int *p, int n)
{
	int a=0, b=n-1;
	while (__________) 
	{
		if (p[a] <= p[b]) 
		{ 
			a = a+1; 
		}<
		else
		{
			 b = b-1; 
		}
	}
	return p[a];
}

缺少的循环条件是

a != n
b != 0
b > (a + 1)
b != a

答案： D

说明

根据问题，程序从 a[0] 和 a[n-1] 开始比较数组的内容，然后条件必须直到两者在某个点相遇，而该点将是 a=b。因此循环条件必须是 b != a。

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

45) 以下 C 程序的输出是什么？

void count(int n)
{
	static int d=1;
	printf("%d", n);
	printf("%d", d);
	d++;
	if(n>1) count(n-1);
	printf("%d", d);
}
void main()
{
	count(3);
}

3 1 2 2 1 3 4 4 4
3 1 2 1 1 1 2 2 2
3 1 2 2 1 3 4
3 1 2 1 1 1 2

答案： A

说明

在上面的函数中，count(3) 将打印 n 和 d 的值。因此将打印 3 1。现在 d 将递增并变为 2。然后将调用 count(2)，它打印 n 和 d 的值，即 2 2。现在，d 将变为 3。然后将调用 count(1)，它打印 n 和 d 的值，即 1 3。然后 d 将变为 4。现在，它将返回并打印 d 的最终递增值，即 4，三次。

因此，上述函数将打印如下内容：3 1 2 2 1 3 4 4 4。因此，选项 (A) 将是正确的答案。

46) 当参数按引用传递并且假设动态作用域时，以下伪代码的输出是什么？

a=3;
void n(x) {x = x * a; print(x);}
void m(y) {a = 1; a = y - a; n(a); print(a);}
void main() {m(a);}

6, 2
6, 6
4, 2
4, 4

答案： D

说明

在上面的伪代码中，我们可以看到“a=3”和“a=1”声明了新变量，其中一个在全局空间中，另一个在局部空间中。

主函数调用 m(a)。由于主函数中没有局部变量 'a'，因此 'a' 是全局变量。

在函数 m 中，我们有 "a=1"，它为其赋值 1，而 "a=y?a" 将 3?1=2 赋值给 'a'。

现在，在函数 n(x) 中，使用了 'a'，并且根据动态作用域，这个 'a' 来自 'm()'。所以，"x=x∗a" 将 "2∗2=4" 赋值给 "x"，并打印 4。通过引用传递，m() 中的 "a" 也更新为 4。因此它将给出 4 4。

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

47) 用于二叉堆数据结构的运算符 delete(i) 被设计用于删除第 i 个节点中的项目。假设堆在数组中实现，并且 i 指的是数组的第 i 个索引。如果堆树的深度为 d（从根到最远叶的路径上的边数），那么在删除元素后，重新修复堆的有效时间复杂度是多少？

O(1)
O(d)，但不是 O(1)
O(2^d )，但不是 O(d)
O(d2^d)，但不是 O(2^d )

答案： B

说明

我们知道堆的高度，无论是最小堆还是最大堆，复杂度都是 O(log n) 或 O(d)。对于这个问题，我们使用堆数据结构的 delete_min() 操作来实现 delete(i) 操作。我们必须清空数组中索引 i 处节点的值，并将其替换为堆中最后一个叶节点的值，然后递减堆大小。因此重新修复 O(log n) 或 O(d)，但不是 O(1)，因为树不包含仅一个节点元素，并且堆重新修复的复杂度对于平均或最坏情况为 O(log n)，对于最佳情况为 O(1)。

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

48) 考虑一个加权无向图，有 4 个顶点，其中边 {i, j} 的权重由矩阵 W 中的条目 Wij 给出。

Gate 2016 CS set 1