The GATE Grind

GATE 2009 CS – Previous Year Questions with Solutions

All 60 questions of GATE 2009 CS with answers and explanations. Read each question, then practise it by topic or as a full paper.

60 questions worth 100 marks in all (20 1-mark, 40 2-mark). Subjects covered: Engineering Mathematics (10), Operating System (9), Algorithms (8), Theory of Computation (6), Computer Networks (6), Databases (5), Computer Organization and Architecture (4), Programming and Data Structures (4).

Practise this paper in The GATE Grind →

  1. Question 1 (1 mark, Multiple choice) – Which one of the following is NOT necessarily a property of a group?
  2. Question 2 (1 mark, Multiple choice) – What is the chromatic number of an n-vertex simple connected graph which does not contain any odd-length cycle? Assume n2.
  3. Question 3 (1 mark, Multiple choice) – Which one of the following is TRUE for any simple connected undirected graph with more than 2 vertices?
  4. Question 4 (1 mark, Multiple choice) – Consider the binary relation R = (x, y), (x, z), (z, x), (z, y) on x, y, z. Which one of the following is TRUE?
  5. Question 5 (1 mark, Multiple choice) – (1217) 8 is equivalent to
  6. Question 6 (1 mark, Multiple choice) – What is the minimum number of gates required to implement the Boolean function AB+C if we have to use only 2-input NOR gates?
  7. Question 7 (1 mark, Multiple choice) – How many 32K × 1 RAM chips are needed to provide a memory capacity of 256 K-bytes?
  8. Question 8 (1 mark, Multiple choice) – A CPU generally handles an interrupt by executing an interrupt service routine
  9. Question 9 (1 mark, Multiple choice) – In which one of the following page replacement policies may Belady’s anomaly occur?
  10. Question 10 (1 mark, Multiple choice) – The essential content(s) in each entry of a page table is/are
  11. Question 11 (1 mark, Multiple choice) – What is the number of swaps required to sort n elements using selection sort, in the worst case?
  12. Question 12 (1 mark, Multiple choice) – The grammar S aSa bSb a b generates which language over a, b?
  13. Question 13 (1 mark, Multiple choice) – Which statements are correct regarding the Bellman–Ford shortest-path algorithm? P. Always finds a negative-weighted cycle, if one exists. Q. Finds…
  14. Question 14 (1 mark, Multiple choice) – Let A belong to NP. Which statement is TRUE?
  15. Question 15 (1 mark, Multiple choice) – Which language over 0, 1 is described by (0+1)*0(0+1)*0(0+1)*?
  16. Question 16 (1 mark, Multiple choice) – Which one of the following is FALSE?
  17. Question 17 (1 mark, Multiple choice) – Match Group 1 with Group 2. Group 1: P. Regular expression; Q. Pushdown automata; R. Dataflow analysis; S. Register allocation. Group 2: 1. Syntax…
  18. Question 18 (1 mark, Multiple choice) – Consider the program below. What value is printed?
  19. Question 19 (1 mark, Multiple choice) – Software module coupling categories are I. Content; II. Common; III. Control; IV. Stamp; V. Data. Rank them from strongest (least desirable) to…
  20. Question 20 (1 mark, Multiple choice) – Consider this HTML table definition. Give the number of rows in each column and the number of columns in each row.
  21. Question 21 (2 marks, Multiple choice) – An unbalanced die with faces numbered 1 to 6 is thrown. The probability that the face value is odd is 90% of the probability it is even. Every…
  22. Question 22 (2 marks, Multiple choice) – For the composition table of a cyclic group below, which choice is correct? * a b c d --- --- --- --- --- a a b c d b b a d c c c d b a d d c a b
  23. Question 23 (2 marks, Multiple choice) – Which logical formula most appropriately represents “Gold and silver ornaments are precious”? G(x): x is a gold ornament; S(x): x is a silver…
  24. Question 24 (2 marks, Multiple choice) – The binary operation □ has this truth table. Which expression is equivalent to P ∨ Q? P Q P □ Q --- --- --- T T T T F T F T F F F T
  25. Question 25 (2 marks, Multiple choice) – Evaluate 0/41- x1+ x\,dx.
  26. Question 26 (2 marks, Multiple choice) – Which formulae are equivalent? I. ¬∀x P(x) II. ¬∃x P(x) III. ¬∃x ¬P(x) IV. ∃x ¬P(x)
  27. Question 27 (2 marks, Multiple choice) – An FSM has state bits A, B, one input and one output as shown below. Starting at A=0, B=0, what is the minimum input-string length that takes it to…
  28. Question 28 (2 marks, Multiple choice) – A four-stage pipeline requires the following cycles per instruction. How many cycles execute the loop? Instruction S1 S2 S3 S4 --- --- --- --- --- I1…
  29. Question 29 (2 marks, Multiple choice) – A 4-way set-associative cache, initially empty, has 16 cache blocks. Main memory has 256 blocks. Requests are 0, 255, 1, 4, 3, 8, 133, 159, 216, 129,…
  30. Question 30 (2 marks, Multiple choice) – Resources R1, R2, R3, R4 have 3, 2, 3, 2 units respectively. Allocation is non-preemptive; a request is not entertained unless completely satisfied.…
  31. Question 31 (2 marks, Multiple choice) – A disk has 100 cylinders. Requests arrive in this order: 4, 34, 10, 7, 19, 73, 2, 15, 6, 20. The head is at cylinder50 and moving to an adjacent…
  32. Question 32 (2 marks, Multiple choice) – The diagram shows process states in a uniprocessor system. Assume there are always ready processes. Which statements are TRUE? I. A process making…
  33. Question 33 (2 marks, Multiple choice) – Critical-section entry/exit are implemented with test-and-set; X starts at0. Which statements are TRUE? I. Deadlock-free. II. Starvation-free. III.…
  34. Question 34 (2 marks, Multiple choice) – Why is a multilevel page table preferred over a single-level page table for virtual-to-physical translation?
  35. Question 35 (2 marks, Multiple choice) – For a constant c, T(n)=n for n3, and T(n)=T(n/3)+cn otherwise. What is the time complexity?
  36. Question 36 (2 marks, Multiple choice) – Insert 12, 18, 13, 2, 3, 23, 5, 15 into an empty length10 hash table, using h(k)=k mod10, open addressing and linear probing. Which resultant table is…
  37. Question 37 (2 marks, Multiple choice) – What is the maximum height of an AVL tree with7 nodes? A one-node tree has height0.
  38. Question 38 (2 marks, Multiple choice) – For the graph shown, which is NOT a possible sequence of edges added by Kruskal’s minimum-spanning-tree algorithm?
  39. Question 39 (2 marks, Multiple choice) – Quicksort chooses the (n/4)th smallest element as pivot for n elements using an O(n)-time selection algorithm. What is its worst-case time complexity?
  40. Question 40 (2 marks, Multiple choice) – Let L=L 1 L 2, where L 1=\am bm c an bn m,n0\ and L 2=\ai bj ck i,j,k0\. Then L is
  41. Question 41 (2 marks, Multiple choice) – The DFA shown accepts all strings over 0, 1 that
  42. Question 42 (2 marks, Multiple choice) – Which statements are TRUE? I. Some programming languages have parsing algorithms of complexity less than Θ(n³). II. A language allowing recursion can…
  43. Question 43 (2 marks, Multiple choice) – Transactions are T1: R1[x] W1[x] W1[y] and T2: R2[x] R2[y] W2[y]. Which schedules are conflict-serializable? S1: R1[x] R2[x] R2[y] W1[x] W1[y] W2[y]…
  44. Question 44 (2 marks, Multiple choice) – An initially empty B+ tree has internal-node order3 (maximum tree pointers per internal node) and leaf order2 (maximum data items per leaf). Insert…
  45. Question 45 (2 marks, Multiple choice) – Let schemas R=a, b, c, S=c. Which queries are equivalent? I. R-S(r)- R-S(( R-S(r) s)- R-S,S(r)) II. \t t R-S(r) u s( v r(u=v[S] t=v[R-S]))\ III. \t t…
  46. Question 46 (2 marks, Multiple choice) – In RSA the private and public keys are (e, n) and (d, n), respectively, where n=pq for large primes p, q; n is public, p, q private. Let 0<M<n and…
  47. Question 47 (2 marks, Multiple choice) – Opening a TCP connection uses an initial sequence number from a time-of-day clock that runs even while the host is down. Its low-order32 bits are…
  48. Question 48 (2 marks, Multiple choice) – Let G(x) be a CRC generator polynomial. Which condition ensures detection of an odd number of erroneous bits?
  49. Question 49 (2 marks, Multiple choice) – Which statements are TRUE? I. A context diagram depicts the system as a single bubble. II. External entities should be clearly identified at all DFD…
  50. Question 50 (2 marks, Multiple choice) – Which statements about a module control-flow graph’s cyclomatic complexity are TRUE? I. It equals the maximum number of linearly independent circuits…
  51. Question 51 (2 marks, Multiple choice) – A disk has63 sectors per track, 10 platters with2 recording surfaces each, and1000 cylinders. Sector addresses are ⟨c, h, s⟩: cylinder, surface,…
  52. Question 52 (2 marks, Multiple choice) – A disk has63 sectors per track, 10 platters with2 recording surfaces each, and1000 cylinders. Sector addresses are ⟨c, h, s⟩: cylinder, surface,…
  53. Question 53 (2 marks, Multiple choice) – A subsequence deletes any number of elements while preserving order. X[m], Y[n] are sequences of lengths m, n, indexed from0. Let l(i, j) be their…
  54. Question 54 (2 marks, Multiple choice) – A subsequence deletes any number of elements while preserving order. X[m], Y[n] are sequences of lengths m, n, indexed from0. Let l(i, j) be their…
  55. Question 55 (2 marks, Multiple choice) – Relations: Suppliers(sid:integer, sname:string, city:string, street:string), Parts(pid:integer, pname:string, color:string), Catalog(sid:integer,…
  56. Question 56 (2 marks, Multiple choice) – Relations: Suppliers(sid:integer, sname:string, city:string, street:string), Parts(pid:integer, pname:string, color:string), Catalog(sid:integer,…
  57. Question 57 (2 marks, Multiple choice) – Frames of1000 bits are sent over a 106 bps duplex link. Propagation time is25 ms. Frames maximally pack the link in transit, with no gap between…
  58. Question 58 (2 marks, Multiple choice) – Frames of1000 bits are sent over a 106 bps duplex link. Propagation time is25 ms. Frames maximally pack the link in transit, with no gap between…
  59. Question 59 (2 marks, Multiple choice) – Consider a binary max-heap implemented as an array. Which array is a max-heap?
  60. Question 60 (2 marks, Multiple choice) – Consider a binary max-heap implemented as an array. Starting with the correct heap from Q59, what array remains after two delete-max operations?