GATE Question Papers: Computer Science and Engineering 2006 (CS)

www.sk4education.com

GATE question papers: Computer Science and Engineering 2006 (CS)

Q.1 - Q.20 Carry One Mark Each

1. Consider the polynomial p(x) = a0 + a1x + a2x2 + a3x2, where ai ¹ 0, "i. The minimum number of multiplications needed to evaluate p on an input x is:

(A) 3 (B) 4 (C) 6 (D) 9

2. Let X, Y, Z be sets of sizes x, y and z respectively. Let W X Y = × and E be the set of all subsets of W. The number of functions from Z to E is:

(A) (B) Z ´ 2xy (C) (D) 2xyz

3. The set {1, 2, 3, 5, 7, 8, 9} under multiplication modulo 10 is not a group. Given below are four plausible reasons. Which one of them is false?

(A) It is not closed (B) 2 does not have an inverse

4. A relation R is defined on ordered pairs of integers as follows:

(x, y) R (u, v) if x < u and y > v. Then R is:

(A) Neither a Partial Order nor an Equivalence Relation

(B) A Partial Order but not a Total Order

(D) An Equivalence Relation

5. For which one of the following reasons does Internet Protocol (IP) use the time- to-live (TTL) field in the IP datagram header?

(A) Ensure packets reach destination within that time

(B) Discard packets that reach later than that time

(D) Limit the time for which a packet gets queued in intermediate routers.

6. Consider three CPU-intensive processes, which require 10, 20 and 30 time units and arrive at times 0, 2 and 6, respectively. How many context switches are needed if the operating system implements a shortest remaining time first scheduling algorithm? Do not count the context switches at time zero and at the end.

(A) 1 (B) 2 (C) 3 (D) 4

7. Consider the following grammar.

S ® S * E

S ® E

E ® F + E

E ® F

F ® id

Consider the following LR (0) items corresponding to the grammar above.

(i) S ® S * × E

(ii) E ® F × + E

(iii) E ® F + × E

Given the items above, which two of them will appear in the same set in the canonical sets-of-items for the grammar?

(A) (i) and (ii) (B) (ii) and (iii)

8. You are given a free running clock with a duty cycle of 50% and a digital waveform f which changes only at the negative edge of the clock. Which one of the following circuits (using clocked D flip-flops) will delay the phase of f by 180°?

(A)

(B)

(C)

(D)

9. A CPU has 24-bit instructions. A program starts at address 300 (in decimal). Which one of the following is a legal program counter (all values in decimal)?

(A) 400 (B) 500 (C) 600 (D) 700

10. In a binary max heap containing n numbers, the smallest element can be found in time

(A) O (n) (B) O (log n) (C) O (log log n) (D) O(1)

11. Consider a weighted complete graph G on the vertex set {v1, v2, ..., vn} such that the weight of the edge (vi, vj) is 2|i - j|. The weight of a minimum spanning tree of G is:

(A) n - 1 (B) 2n - 2 (C) (D) n2

12. To implement Dijkstra's shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure to be used is:

(A) Queue (B) Stack (C) Heap (D) B-Tree

13. A scheme for storing binary trees in an array X is as follows. Indexing of X starts at 1 instead of 0. the root is stored at X[1]. For a node stored at X[i], the left child, if any, is stored in X[2i] and the right child, if any, in X[2i+1]. To be able to store any binary tree on n vertices the minimum size of X should be

(A) log2 n (B) n (C) 2n + 1 (D) 2n - 1

14. Which one of the following in place sorting algorithms needs the minimum number of swaps?

(A) Quick sort (B) Insertion sort (C) Selection sort (D) Heap sort

15. Consider the following C-program fragment in which i, j and n are integer variables.

for (i = n, j = 0; i > 0; i /= 2, j +=i);

Let val (j) denote the value stored in the variable j after termination of the for loop. Which one of the following is true?

(A) val (j) = q (log n) (B) val (j) q ()

16. Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible to S and S is polynomial-time reducible to R. Which one of the following statements is true?

(A) R is NP-complete (B) R is NP-hard

17. An element in an array X is called a leader if it is greater than all elements to the right of it in X. The best algorithm to find all leaders in an array

(A) Solves it in linear time using a left to right pass of the array

(B) Solves it in linear time using a right to left pass of the array

(D) Solves it in time q (n2)

18. We are given a set X = {x1, ..... xn} where xi = 2i. A sample S Í X is drawn by selecting each xi independently with probability pi = . The expected value of the smallest number in sample S is:

(A) (B) 2 (C) (D) n

19. Let L1 = {0n+m 1n 0m | n, m ³ 0},

L2 = {0n+m 1n+m 0m | n, m ³ 0}, and

L3 {0n+m 1n+m 0n+m | n, m ³ 0}.

Which of these languages are not context free?

(A) L1 only (B) L3 only (C) L1 and L2 (D) L2 and L3

20. Consider the following log sequence of two transactions on a bank account, with initial balance 12000, that transfer 2000 to a mortgage payment and then apply a 5% interest.

1. T1 start

2. T1 B old=1200 new=10000

3. T1 M old=0 new=2000

4. T1 commit

5. T2 start

6. T2 B old=10000 new=10500

7. T2 commit

Suppose the database system cra shes just before log record 7 is written. When the system is restarted, which one statement is true of the recovery procedure?

(A) We must redo log record 6 to set B to 10500

(B) We must undo log record 6 to set B to 10000 and then redo log records 2 and 3

(D) We can apply redo and undo operations in arbitrary order because they are idempotent.

Q.21 - Q.75 Carry Two Marks Each

21. For each element in a set of size 2n, an unbiased coin is tossed. The 2n coin tosses are independent. An element is chosen if the corresponding coin toss were head. The probability that exactly n elements are chosen is:

(A) (B) (C) (D)

22. Let E, F and G be finite sets.

Let X = (E Ç F) - (F Ç G) and Y = (E - (E Ç G)) - (E - F).

Which one of the following is true?

(A) X Ì Y (B) X É Y

23. F is an n ´ n real matrix. b is an n ´ 1 real vector. Suppose there are two n ´ 1 vectors, u and v such that , u ¹ v and Fu = b, Fv = b. Which one of the following statements is false?

(A) Determinant of F is zero

(B) There are an infinite number of solutions to Fx = b

(D) F must have two identical rows

24. Given a set of elements N = {1, 2, ..., n} and two arbitrary subsets A Í N and B Í N, how many of the n! permutations p from N to N satisfy min (p (A)) = min (p(B)), where min(S) is the smallest integer in the set of integers S, and p(S) is the set of integers obtained by applying permutation p to each element of S?

(A) (n - |A È B|) |A| |B| (B) (|A|2 + |B|2) n2

25. Let S = {1, 2, 3, ..., m}, m > 3. Let X1 ... Xn be subsets of S each of size 3. Define a function f from S to the set of natural numbers as, f(i) is the number of sets Xj that contain the llement i. That is f(i) = |{j|i Î Xj|}|. Then is

(A) 3m (B) 3n (C) 2m + 1 2n + 1

26. Which one of the first order predicate calculus statements given below correctly express the following English statement?

Tigers and lions attack if they are hungry or threatened.

(A) "x [(tiger (x) Ù lion (x)) ® {(hungry (x) Ú threatened (x)) ® attacks (x)}]

(A) "x [(tiger (x) Ú lion (x)) ® {(hungry (x) Ú threatened (x)) Ù attacks (x)}]

(A) "x [(tiger (x) Ú lion (x)) ® {(hungry (x) ® hungry (x) Ú threatened (x))}]

(A) "x [(tiger (x) Ú lion (x)) ® {(hungry (x) Ú threatened (x)) ® attacks (x)}]

27. Consider the following propositional statements:

P1: ((A Ù B) ® C)) º ((A ® C) Ù (B ® C))

P2: ((A Ú B) ® C)) º ((A ® C) Ú (B ® C))

Which one of the following is true?

(A) P1 is a tautology, but not P2

(B) P2 is a tautology, but not P1

(D) Both P1 and P2 are not tautologies

28. A logical binary relation , is defined as follows: W

A / B / A B
True / True / True
True / False / True
False / True / False
False / False / True

Let ~ be the unary negation (NOT) operator, with higher precedence then .

Which one of the following is equivalent to A Ù B?

(A) (~ A B) (B) ~ (A ~ B)

29. If s is a string over (0 + 1)* then let n0 (s) denote the number of 0's in s and n1(s) the number of 1's in s. Which one of the following languages is not regular?

(A) L = {S Î (0 + 1) * | n0 (s) is a 3-digit prime}

(B) L = {S Î (0 + 1) * | for every prefix s¢ of s, |n0 (s¢) - n1 (s¢) | £ 2}

(D) L = {S Î (0 + 1) * | n0 (s) mod 7 = n1 (s) mod 5 = 0}

30. For S Î (0 + 1) * let d(s) denote the decimal value of s (e.g. d (101) = 5).

Let L = {s Î (0 + 1) * | d(s) mod 5 = 2 and (s) mod 7 ¹ 4}

Which one of the following statements is true?

(A) L is recursively enumerable, but not recursive

(B) L is recursive, but not context-free

(D) L is regular

31. Let SHAM3 be the problem of finding a Hamiltonian cycle in a graph G = (V, E) with |V| divisible by 3 and DHAM3 be the problem of determining if a Hamiltonian cycle exists in such graphs. Which one of the following is true?

(A) Both DHAM3 and SHAM3 are NP-hard

(B) SHAM3 is NP-hard, but DHAM3 is not

(D) Neither DHAM3 nor SHAM3 is NP-hard

32. Consider the following statements about the context free grammar

G = {S ® SS, S ® ab, S ® ba, S ®Î }

I. G is ambiguous

II. G produces all strings with equal number of a's and b's

III. G can be accepted by a deterministic PDA.

Which combination below expresses all the true statements about G?

(A) I only

(B) I and III only

(D) I, II and III

33. Let L1 be a regular language, L2 be a deterministic context-free language and L3 a recursively enumerable, but not recursive, language. Which one of the following statements is false?

(A) L1 Ç L2 is a deterministic CFL

(B) L3 Ç L1 is recursive

(D) L1 Ç L2 Ç L3 is recursively enumerable

34. Consider the regular language L = (111 + 11111) * . The minimum number of states in any DFA accepting this languages is:

(A) 3 (B) 5 (C) 8 (D) 9

35.

Consider the circuit above. Which one of the following options correctly represents f (x, y, z)?

(A) (B) (C)