2008 M.E. Information Technology Indian Institute of Technology Mumbai M.E Information Technology GATE QUestions University Question paper
Indian Institute of Technology Mumbai M.E Information Technology GATE QUestions
SECTION - A
1. This question consists of TWENTY-THREE multiple questions of ONE mark each. For each
question
(1.1 — 1.23), four possible alternatives (A, B, C and D) are given, out of which ONLY ONE is
correct. Indicate the correct answer in the boxes corresponding to the questions only on the
FIRST sheet of the answer book.
1.1 The minimum number of cards to be dealt from an arbitrarily shuffled deck of 52 cards to
guarantee that three cards are from some same suit is
(a) 3
(b) 8
(c) 9
(d) 12
1.2 The determinant of the matrix
2 0 0 0
8 1 7 2.
2 0 2 0
9 0 6 1
(a) 4
(b) 0
(C) 15
(d) 20
1.3 Let S and T be language over ={a,b} represented by the regular expressions (a+b*)* and
(a+b)*, respectively. Which of the following is true?
(a) ScT
(b) TcS
(c) S=T
(d) SnT=Ø
1.4 Let L denotes the language generated by the grammar S - OSO/00. Which of the following
is true?
(a) L = O
(b) L is regular but not O
(c) L is context free but not regular
(d) L is not context free
1.5 The number 43 in 2's complement representation is
(a) 01010101
(b) 11010101
(c) 00101011
(d) 10101011
1.6 To put the 8085 microprocessor in the wait state
(a) lower the HOLD input
(b) lower the READY input
(c) raise the HOLD input
(d) raise the READY input
1.7 Comparing the time Ti taken for a single instruction on a pipelined CPU with time T2 taken
on a non-pipelined but identical CPU, we can say that
(a) Ti = T2
(b) Ti > T2
(c) Ti
(d) Ti is T2 plus the time taken for one instruction fetch cycle
1.8 The 8085 microprocessor responds to the present of an interrupt
(a) as soon as the TRAP pin becomes ‘high'
(b) by checking the TRAP pin for ‘high' status at the end of each instruction each
(c) by checking the TRAP pin for ‘high' status at the end of the execution of each instruction.
(d) by checking the TRAP pin for ‘high' status at regular intervals.
1.9 The most appropriate matching for the following pairs
X: Indirect addressing 1: Loops
Y: Immediate addressing 2: Pointers
Z: Auto decrement addressing 3. Constants
is
(a) X—3 Y—2 Z-i
(b) X—i Y—3 Z-2
(c) X—2 Y—3 Z-i
(d) X—3 Y—i Z-2
1.10 The following C declarations
struct node{
mti:
float j;
struct node *s[iO];
define s to be
(a) An array, each element of which is a pointer to a structure of type node
(b) A structure of 2 fields, each field being a pointer to an array of 10 elements
(c) A structure of 3 fields: an integer, a float, and an array of 10 elements
(d) An array, each element of which is a structure of type node
1.11 The most appropriate matching for the following pairs
X: m=malloc(5); m= NULL; 1: using dangling pointers
Y: free(n); n->value=5; 2: using uninitialized pointers
Z: char *p; *p'a'; 3. lost memory is:
(a) X—1 Y—3 Z-2
(b) X—2 Y—1 Z-3
(C) X—3 Y—2 Z-1
(d) X—3 Y—1 Z-2
1.12 The most appropriate matching for the following pairs
X: depth first search 1: heap
Y: breadth-first search 2: queue
Z: sorting 3: stack
is:
(a) X—1 Y—2 Z-3
(b) X—3 Y—1 Z-2
(c) X—3 Y—2 Z-1
(d) X—2 Y—3 Z-1
1.13 Consider the following nested representation of binary trees: (X Y Z) indicates Y and Z
are the left and right sub stress, respectively, of node X. Note that Y and Z
may be NULL, or further nested. Which of the following represents a valid binary
tree?
(a) (1 2 (4 5 6 7))
(b) (1 (2 3 4) 5 6) 7)
(c) (1 (2 3 4)(5 6 7))
(d) (1 (2 3 NULL) (4 5))
1.14 Let s be a sorted array of n integers. Let t(n) denote the time taken for the most efficient
algorithm to determined if there are two elements with sum less than 1000 in s. which of the
following statements is true?
(a) t (n) is 0(1)
(b) n t(n) n log2 n
(c) n log2 n t(n)
(d) t(n) =
1.15 Aliasing in the context of programming languages refers to
(a) multiple variables having the same memory location
(b) multiple variables having the same value
(c) multiple variables having the same identifier
(d) multiple uses of the same variable
1.16 Assume that objects of the type short, float and long occupy 2 bytes, 4 bytes and 8
bytes, respectively. The memory requirement for variable t, ignoring alignment
considerations, is
(a) 22 bytes
(b) 14 bytes
(c) 18 bytes
(d) 10 bytes
1.17 The number of tokens in the following C statement
printf("i=%d, &%i",i,&i); is
(a) 3
(b) 26
(c) 10
(d) 21
1.18. Which of the following derivations does a top-down parser use while parsing an input
string? The input is assumed 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 following need not necessarily be saved on a context switch
between 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 each process P executes the following:
wait (m;wait (m[(i+1) mode 4]);
release (m); release (m[(i+1)mod 4]);
This could cause
(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. Given the relations
employee (name, salary, deptno), and
department (deptno, deptname, address)
Which of the following 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 same as their department name
(c) The sum of all employees' salaries
(d) All employees of a given department
2. This question consists of TWENTY-SIX multiple questions of TWO marks each. For each
question (2.1 — 2.26), four possible alternatives (A, B, C and D) are given, out of which ONLY
ONE is correct. Indicate the correct answer in the boxes corresponding to the questions only
on the SECOND sheet of the answer 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 following is true?
(a) k must be 1
(b) k must be 0
(c) k can take any value between 0 and 1
(d) None of the above
2.2. E1 and E2 are events in a probability space satisfying the following 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 following 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 defined on the set of integers as x Ry iff (x+y) is even. Which of
the following statements is true?
(a) R is not an equivalence relation
(b) R is an equivalence relation having 1 equivalence class
(c) R is an equivalence relation having 2 equivalence classes
(d) R is an equivalence relation having 3 equivalence classes
2.6. Let P(S) denotes the powerset of set S. Which of the following 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. Assume 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) True
(b) False
(c) Same as the truth-value of b
(d) Same as the truth-value of d
2.8. What can be said about a regular language L over {a} whose minimal finite state
automation has two 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 following decision problems:
(P1) Does a given finite state machine accept a given string
(P2) Does a given context free grammar generate an infinite number of stings
Which of the following 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 following solution for x, y, z and w, respectively:
(a) 0100
(b) 1101
(c) 1011
(d)1000
Return to question paper search
|