## Friday, 11 March 2016

### GATE Computer Science and IT Solved Paper 2015 Session 1 - Part 5

41.

42.       Suppose L={p, q, r, s, t} is a lattice represented by the following Hasse diagram:
For any x,y ε L not necessarily distinct, x V y and x Ʌ y are join and meet of x, y, respectively. Let L3={(x,y,z): x,y,z ε L } be the set of all ordered triplets of the elements of L. Let pr be the probability that an element (x,y,z) ε L3 chosen equiprobably satisfies xV(yɅz) = (xVy) Ʌ (xVz). Then
(A) pr = 0            (B) pr = 1
(C) 0<pr≤1/5      (D) 1/5<pr<1
43.       Consider the operations
f(X,Y,Z) = X’YZ + XY’ + Y’Z’ and g(X,Y,Z) = X’YZ + X’YZ’ + XY
Which one of the following is correct?
(A) Both {f} and {g} are functionally complete
(B) Only {f} is functionally complete
(C) Only {g} is functionally complete
(D) Neither {f} nor {g} is functionally complete
44.       Let G be a connected planar graph with 10 vertices. If the number of edges on each face is three, then the number of edges in G is .................
45.       Let an represent the number of bit strings of length n containing two consecutive 1s. What is the recurrence relation for an?
(A) an-2+an-1+2n-2              (B) an-2+2an-1+2n-2
(C) 2an-2+an-1+2n-2           (D) 2an-2+2an-1+2n-2

46.       A variable x is said to be live at a statement Si in a program if the following three conditions hold simultaneously:
i. There exists a statement Sj that uses x
ii. There is a path from Si to Sj in the flow graph corresponding to the program
iii. The path has no intervening assignment to x including at Si and Sj
The variables which are live both at the statement in basic block 2 and at the statement in basic block 3 of the above control flow graph are
(A) p, s, u           (B) r, s, u
(C) r, u               (D) q, v
47.       The least number of temporary variables required to create a three-address code in static single assignment form for the expression q + r / 3 + s – t * 5 + u * v /w is .........................
48.       Consider an Entity-Relationship (ER) model in which entity sets E1 and E2 are connected by an m : n relationship R12. E1 and E3 are connected by a 1 : n (1 on the side of E1 and n on the side of E3) relationship R13.
E1 has two single-valued attributes a11 and a12 of which a11 is the key attribute. E2 has two single-valued attributes a21 and a22 of which a21 is the key attribute. E3 has two single-valued attributes a31 and a32 of which a31 is the key attribute. The relationships do not have any attributes.
If a relational model is derived from the above ER model, then the minimum number of relations that would be generated if all the relations are in 3NF is ................
49.       Consider the DFAs M and N given below. The number of states in a minimal DFA that accepts the language L(M) ∩ L(N) is ....................
50.    Consider the NPDA <Q = {q0,q1,q2}, Σ = {0,1}, Γ = {0,1,}, δ, q0, , F = {q2}> where (as per usual convention) Q is the set of states, Σ is the input alphabet, Γ is the stack alphabet, δ is the state transition function, q0 is the initial state, is the initial stack symbol, and F is the set of accepting states. The state transition is as follows:
Which one of the following sequences must follow the string 101100 so that the overall string is accepted by the automaton?
(A) 10110          (B) 10010
(C) 01010          (D) 01001