# (Paper) GATE Question Paper : Information Technology

### GATE Question Paper : Information Technology

**Q.1 — Q.30 Carry One Mark Each**

**1. A bag contains 10 blue marbles, 20 green marbles and 30 red marbles. A marble is drawn from the bag, its colour recorded and it is put back in the bag. This process is repeated 3 times. The probability that no two of the marbles drawn have the same colour is**

(A) 36

(B) 6

(C) 4

(D) 3

**2. If the trapezoidal method is used to evaluate the integral [x2dx, then the value obtained • 1 1 1**

(A) is always >

(B) is always <

(C) is always =

(D) may be greater or lesser than

**3. The determinant of the matrix givën.below is**

0 1 0 2

—1 1 1 3

0 0 0 1

1 —2 0 1

(A) -1

(B) 0

(C) 1

(D) 2

**A D V E R T I S E M E N T**

**4. Let L be a regular language and M be a context free language,both over the alphabet. Let LCand MCdenote the complements of L and M respectively. Which of the following statements about the language LC u MC is TRUE?**

(A) It is necessarily regular but not necessarily context free

(B) It is necessarily context free

(C) It is necessarily non-regular

(D) None of the above

**5. Which of the following statements is TRUE about the regular expression 01*0?**

(A) It represents a finite set of finite strings.

(B) It represents an infinite set of finite strings.

(C) It represents a finite set of infinite strings.

(D) It represents an infinite set of infinite strings.

**6. The language {oi 21 n 1061 is:**

(A) regular

(B) context free but not regular

(C) context free but its complement is not context free

(D) not context free

**7. Which of the following expressions is equivalent to (A $ B) $ C**

(A) (A+B+C)(A++)

(B) (A+B+C)(A++C)

(C) ABC+A(B$C)+B(A$C)

(D) None of the above

**8. Using Booth’s algorithm for multiplication, the multiplier — 57 will be recorded as**

(A) 0 —1 0 0 1 0 0 -1

(B) 1 1 0 0 0 1 1 1

(C) 0 -1 0 0 1 0 0 0

(D) 0 1 0 0 -1 0 0 1

**9. A dynamic RAM has a memory cycle time of 64 nsec. It has to be refreshed 100 times per msec and each refresh takes 100 nsec. What percentage of the memory cycle time is used for refreshing?**

(A) 10

(B) 6.4

(C) 1

(D)0.64

**10. A two-way switch has three terminals a, b and c. In ON position (logic value 1) a is connected to b, and in OFF position, a is connected to c. two of these two way switches Si and S2 are connected to a bulb as shown below.**

**Which of the following expressions, if true, will always result in the lighting of the bulb?**

(A) Si.S2

(B) Si+S2

(C) Si$S2

(D)Si$S2

**11. How many pulses are needed to change the contents of a 8 bit up-counter from 10101100 to 00100111 (rightmost bit is the LSB)?**

(A) 134

(B) 133

(C) 124

(D) 123

**12. The numbers 1, 2, n are inserted in a binary search tree in some order. In the resulting tree, the right subtree of the root contains p nodes. The first number to be inserted in the tree must be**

(A) p

(B) p + 1

(C) n - p

(D)n — p + 1

**13. A function f defined on stacks of integers satisfies the following properties. f(q5) = Oand f (push(S,i)) = max(f (S),0)+ifor all stacks S and integers i. If a stack S contains the integers 2, -3, 2, -1, 2 in order from bottom to top, what is f(s)?**

(A) 6

(B) 4

(C) 3

(D) 2

**14. In a depth first traversal of a graph G with n vertices, k edges are marked as tree edges. The number of connected components in G is**

(A) k

(B) k + 1

(C) n — k - 1

(D)n - k

**15. In the following table, the left column contains the names of standard graph algorithm, and the right column contains the time complexities of the algorithms. Match each algorithm with its time complexity.**

(1) Bellman Ford algorithm (A) 0 (mlog n)

(2) Kruskal’s algorithm (B) 0 (n3)

(3) Floyd-Warshall algorithm (C) 0 (nm)

(4) Topological Sorting (D) 0 (n + m)

(A)1-C2-A3-B4-D

(B)1-B2-D3-C4-A

(C)1-C2-D3-A4-B

(D)1-B2-A3-C4-D