GATE 2017 CS 组 2

答案： B

说明

已知，总磁带驱动器 = 9

在表中，我们可以看到当前分配的磁带驱动器 = 7

所以，可用的磁带驱动器是：9 - 7 = 2

现在我们首先将剩余的磁带驱动器分配给需要2个的进程P3。执行后它将释放3个磁带驱动器。所以新的可用磁带驱动器是：3 + 2 = 5

然后进程P1需要4个磁带驱动器。所以它将 next 执行并释放3个磁带驱动器。所以新的可用磁带驱动器是：3 + 5 = 8。

最后，进程P2将执行。因此，所有进程都处于安全状态，没有死锁。安全。因此，安全序列将是 P3→P2→P1 或 P3→P1→P2。所以选项(B)是正确的答案。

答案： A

说明

已知,
   Code1 = 00000, Code2 = 01011, Code3 = 10101, Code4 = 11110
汉明距离 -> 两个向量之间不同的位数。

所有汉明距离的最小值 = 3 (Code1 = 00000，Code2 = 01011)
所以，p = 3
现在，为了找到码可以纠正的最大错误比特数，我们需要汉明距离 = 2d + 1
所以，2d + 1 = 3
   d = 1

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

答案： D

说明

已知,
   带宽(B) = 10⁶比特/秒
   距离(D) = 10000公里 = 10,000,000米 = 10⁷米
   传播速度(V) = 2 x 10⁸ 米/秒
   数据长度(L) = 50,000字节 = 50,000 x 8比特
∴ 传输时间(p) = L / B
         = (50, 000 * 8 ) / 10⁶
         = 40 / 100 = 0.4 = 400毫秒
∴ 传播时间(q) = D / V
         = 10⁷ / (2 * 10⁸)
         = 1 / 20 = 0.05 = 50毫秒
因此，选项 (D) 是正确答案。

答案： B

说明

已知,

前序：12, 8, 6, 2, 7, 9, 10, 16, 15, 19, 17, 20

在BST中，前序遍历的第一个节点始终是根节点。BST将始终按升序给出。所以对应的二叉树如下所示-

∴ 后序遍历：2, 7, 6, 10, 9, 8, 15, 17, 20, 19, 16, 12

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

答案：C

说明

已知，x= = (y * q + r)

根据题意，x=被除数，y=除数，q=商，r=余数

现在，为了通过重复减法来除一个数，商应该为0，并且每次减法都应该增加。因此，如果q = 0，r = x。所以选项(C)是正确的答案。

答案：C

说明

在上题中，我们需要检查内层for循环的内层语句printf("%d %d," i, j);执行了多少次。内层for循环依赖于i。所以，

对于i=1，语句运行n次。因此，对于第i次迭代，语句运行θ(n/i)次。

因此，fun的时间复杂度（以θ表示法表示）是

n- 1/1 + n-1/2 + n-1/3 +...........+ n-1/n-1 +1
n/1+n/2+n/3+......+n/n-1 -log(n-1)
n{1/1+1/2+1/3+.....+1/n-1}-log(n-1)
nlog(n-1)-log(n-1)
nlog(n-1)
nlogn
因此，选项 (C) 将是正确的答案。

答案：C

说明

已知，α (q2,aba)
所以，起始状态是：q2
首先找到q2的Epsilon闭包 = {q2,q0}
然后，在'a'上找到转换：q0------------->q1
             q2------------->'Ø ' (即无)
找到'q1'的epsilon闭包= {q1,q2,q0}
然后，在'b'上找到转换：q1------------->q3
             q0------------->q0
             q2------------->'Ø '
现在，找到'q0'的epsilon闭包：{q0,q2}和'q3'的epsilon闭包：{q3}
找到'q0'联合'q3'的epsilon闭包：{q3}
然后，在'a'上找到转换：q0------------->q1
             q2------------->'Ø '
             q3------------->'Ø '
再次，找到'q1'的epsilon闭包：{q1,q0,q2}

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

答案： D

说明

L₁是上下文有关语言。

L₂是上下文无关语言。

在L₃中，不确定何时弹出b并推入a，因为这里比较的是三个连续的终结符。所以它不是上下文无关语言。由于给定语言是CFL，所以它也是递归的。

L₄是确定性上下文无关语言，因为我们确定先将a推入堆栈，并在看到b时确定从堆栈中弹出a。

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