Indian Institute of Technology Mumbai (IIT-M) 2008 M.E Information Technology GATE - Question Paper

printf(”i=%d, &%i”,i,&i); is
(a) 3
(b) 26
(c) 10
(d) 21
1.18. Which of the subsequent derivations does a top-down parser use while parsing an input
string? The input is presumed to be scanned in left to right order.
(a) Leftmost derivation
(b) Leftmost derivation traced out in reverse
(c) Rightmost derivation
(d) Rightmost derivation traced out in reverse
1.19. Which of the subsequent need not necessarily be saved on a situation switch
ranging from processes?
(a) General purpose registers
(b) Translation look-aside buffer
(c) Program counter
(d) All of the above
1.20. Let m[0]...m[4] be mutexes (binary semaphores) and P[0] .... P[4] be processes.
Suppose every process P executes the following:
wait (m;wait (m[(i+1) mode 4]);
release (m); release (m[(i+1)mod 4]);
This could reason
(a) Thrashing
(b) Deadlock
(c) Starvation, but not deadlock
(d) None of the above
1.21. B -trees are preferred to binary trees in databases because
(a) Disk capacities are greater than memory capacities
(b) Disk access is much slower than memory access
(c) Disk data transfer rates are much less than memory data transfer rates
(d) Disks are more reliable than memory
1.22. provided the relations
employee (name, salary, deptno), and
department (deptno, deptname, address)
Which of the subsequent queries cannot be expressed using the basic relational algebra
operations (G,t,x,N,u,n,—)?
(a) Department address of every employee
(b) Employees whose name is the identical as their department name
(c) The sum of all employees’ salaries
(d) All employees of a provided department
2. This ques. consists of TWENTY-SIX multiple ques. of 2 marks every. For every
ques. (2.1 — 2.26), 4 possible options (A, B, C and D) are given, out of which ONLY
ONE is accurate. Indicate the accurate ans in the boxes corresponding to the ques. only
on the 2nd sheet of the ans book.
2.1 X,Y and Z are closed intervals of unit length on the real line. The overlap of X and Y is half
a unit. The overlap of Y and Z is also half a unit. Let the overlap of X and Z be k units. Which
of the subsequent is true?
(a) k must be 1
(b) k must be 0
(c) k can take any value ranging from 0 and 1
(d) None of the above
2.2. E1 and E2 are events in a probability space satisfying the subsequent constraints:
• Pr(E1) = Pr(E2)
• Pr(E1uE2)=1
• E1 and E2 are independent
The value of Pr(E1), the probability of the event E1, is
(a) 0
(b)
(c)
(d) 1
2.3. Let S=ilog21 and
100
andT=f xlog2xdx
Which of the subsequent statements is true?
(a) S>T
(b) S=T
(c) S T
(d) 2S < T
2.4. A polynomial p(x) satisfies the following:
p(1) = p(3) = p(5) = 1
p(2) = p(4) = -1
The minimum degree of such a polynomial is
(a) 1
(b) 2
(c) 3
(d) 4
2.5. A relation R is described on the set of integers as x Ry iff (x+y) is even. Which of
the subsequent statements is true?
(a) R is not an equivalence relation
(b) R is an equivalence relation having one equivalence class
(c) R is an equivalence relation having two equivalence classes
(d) R is an equivalence relation having three equivalence classes
2.6. Let P(S) denotes the powerset of set S. Which of the subsequent is always true?
(a) P(P(S))=P(S)
(b) P(S) nP(P(S)) = {Ø}
(c) P(S) nS = P(S)
(d) S P(S)
2.7. Let a, b, c, d be propositions. presume that the equivalence a -* (b V-b) and b -* c hold.
Then the truth-value of the formula (a A b) — (a A c) v d is always
(a) actual
(b) False
(c) identical as the truth-value of b
(d) identical as the truth-value of d
2.8. What can be stated about a regular language L over {a} whose minimal finite state
automation has 2 states?
(a) L must be {aIn is odd}
(b) L must be {aIn is even}
(c) L must be {aI0}
(d) Either L must be {aIn is odd}, or L must be {aI n is even}
2.9. Consider the subsequent decision problems:
(P1) Does a provided finite state machine accept a provided string
(P2) Does a provided situation free grammar generate an infinite number of stings
Which of the subsequent statements is true?
(a) Both (P1) and (P2) are decidable
(b) Neither (P1) nor (P2) are decidable
(c) Only (P1) is decidable
(d) Only (P2) is decidable
2.10. The simultaneous equations on the Boolean variables x, y, z and w, x+y+z= 1
xy = 0
xz + w = 1
xy+ W=0
have the subsequent solution for x, y, z and w, respectively:
(a) 0100
(b) 1101
(c) 1011
(d)1000

Earning:   Approval pending.