GATE 2017 CS 组 2

答案：C

说明

给定的正则语言 L = {w₁aw₂ | w₁, w₂ ∈{a,b}* , |w₁| = 2, w₂>=3}

因此，接受L的最小确定性有限自动机是

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

答案： A

说明

假设A，B分别表示P，Q申请工作的事件

根据题目，

P(A) = 1/4.......................(1)
P(A/B) = 1/2...................(2)
P(B/A) = 1/3...................(3)
P(A/B) = P(A∩B ) / P(B) = 1/2 ............(4)
P(B/A) = P(A∩B ) / P(A) = 1/3.............(5)
从(1)式可得，
   P(B/A) = P(A∩B ) / (1/4) = 1/3
因此，P(A∩B) = 1/12.............(6)
从(4)式和(6)式可得，
   P(B) = 1/6.....................(7)
现在，
     P(A'/B) = P(A'∩B') / P(B)
         = 1 - P(A ∪ B) / 1 - P(B)
         = 1 - [ P(A) + P(B) - P(A∩B) ] / 1 - P(B)
         = 1 - [ 1/4 + 1/6 - 1/12 ] / 1- 1/6
         = 2/3 * 6/5
         = 4/5

答案：C

说明

简化每个选项中的表达式，我们得到

选项A：wx + w(x+y) + x(x+y) = x + wy
左边
   wx + wx + wy + xx + xy
   wx + wy + x + xy
   x (1+ w + y) + wy
   x + wy == 右侧

选项B：(wx'(y + z'))' + w'x = w' + x + y'z
左边
   (wx'(y + z'))' + w'x
   应用德摩根定律，我们得到
   w' + x + y'z + w'x
   w' (1 + x) + x + y'z   [∵ 1 + x = 1]
   w'+x+y'z == 右侧

选项D：(w+y)(wxy+wyz) = wxy+wyz
左边
   (w+y)(wxy+wyz)
   wxy + wyz + wxy + wyz
   wxy + wyz == 右侧

从上面可以看出，第三个选项(c)不正确。因此，选项(C)是正确的答案。

答案： A

说明

已知,

f(w, x, y, z) = Σ_m(0,1,2,3,7,8,10) + Σ_d(5,6,11,15)

从上面可以看出，最小乘积和(POS) = (w' + z' )( x' + z )

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

答案： A

说明

已知,
   L1的访问时间 = 1
   L2的访问时间 = 8
   L1缓存的未命中惩罚 (2*L2) = 18*2 = 2*x
   L2缓存的未命中惩罚 (x) = 18
   AMAT (平均内存访问时间) = 2

现在，AMAT = L1的访问时间 + (L1的未命中率 * L1的未命中惩罚)，其中L1的未命中惩罚 = L2的访问时间 + (L2的未命中率 * L2的未命中惩罚)

例如：
2 = 1+ 2 * x * (8 + x * 18)
或者，2x (8 + 18x) = 1
   16 x + 36 x² = 1
   36 x² + 16x - 1 = 0
解上述方程，我们得到
   x = 0.111

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

答案： B

说明

已知,
T(n) = 2T (√n ) + 1
= 2T (n^1/2 ) + 1
令n = 2^x
T( 2x ) = 2T ( 2^x/2 ) + 1
= 2T ( x/2 ) + 1
现在，应用主定理
T(n) = aT(n/b) + f(n)，其中a >= 1且b > 1
所以，a=2, b=2, k=0，满足条件
T( 2^x ) = θ(_xlog_ba ) = θ (xlog22 ) = θ(x)
= θ (log n)

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

答案： B

说明

gx(z)在z=1处的导数给出期望E(X)

因此，对gy(z)关于z求导，并在z=1处求值

E(Y) = g'_y(z)|_z=1 = ((1-β+βz)^N)'|_z=1= Nβ(1-β+βz)^N-1|_z=1= Nβ(1-β+β)^N-1 = Nβ

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

答案：C

说明

由于给定的文法是左递归的，因此需要去除左递归。

假设文法形式为：A→Aα|β，那么去除左递归后应写为

A→βA'
A'→αA'∣ε
由于文法表达式是
E→E - T∣T (这里α是"-T"，β是"T")
T→T + F∣F (这里α是"+F"，β是"F")
F→(E)∣id (它没有左递归)

去除左递归后，文法将是
      E→TE'
      E'→-TE'∣ε
      T→FT'
      T'→+FT'∣ε
      F→(E)∣id

现在用X替换E'，用Y替换T'。我们得到
      E→TX
      X→-TX∣ε
      T→FY
      Y→+FY∣ε
      F→(E)∣id

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