# 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 ................