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 →
- Question 1 – Which one of the following is NOT necessarily a property of a group?
- Question 2 – What is the chromatic number of an n-vertex simple connected graph which does not contain any odd-length cycle? Assume n2.
- Question 3 – Which one of the following is TRUE for any simple connected undirected graph with more than 2 vertices?
- Question 4 – Consider the binary relation R = (x, y), (x, z), (z, x), (z, y) on x, y, z. Which one of the following is TRUE?
- Question 5 – (1217) 8 is equivalent to
- Question 6 – 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?
- Question 7 – How many 32K × 1 RAM chips are needed to provide a memory capacity of 256 K-bytes?
- Question 8 – A CPU generally handles an interrupt by executing an interrupt service routine
- Question 9 – In which one of the following page replacement policies may Belady’s anomaly occur?
- Question 10 – The essential content(s) in each entry of a page table is/are
- Question 11 – What is the number of swaps required to sort n elements using selection sort, in the worst case?
- Question 12 – The grammar S aSa bSb a b generates which language over a, b?
- Question 13 – Which statements are correct regarding the Bellman–Ford shortest-path algorithm? P. Always finds a negative-weighted cycle, if one exists. Q. Finds…
- Question 14 – Let A belong to NP. Which statement is TRUE?
- Question 15 – Which language over 0, 1 is described by (0+1)*0(0+1)*0(0+1)*?
- Question 16 – Which one of the following is FALSE?
- Question 17 – Match Group 1 with Group 2. Group 1: P. Regular expression; Q. Pushdown automata; R. Dataflow analysis; S. Register allocation. Group 2: 1. Syntax…
- Question 18 – Consider the program below. What value is printed?
- Question 19 – Software module coupling categories are I. Content; II. Common; III. Control; IV. Stamp; V. Data. Rank them from strongest (least desirable) to…
- Question 20 – Consider this HTML table definition. Give the number of rows in each column and the number of columns in each row.
- Question 21 – 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…
- Question 22 – 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
- Question 23 – 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…
- Question 24 – 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
- Question 25 – Evaluate 0/41- x1+ x\,dx.
- Question 26 – Which formulae are equivalent? I. ¬∀x P(x) II. ¬∃x P(x) III. ¬∃x ¬P(x) IV. ∃x ¬P(x)
- Question 27 – 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…
- Question 28 – A four-stage pipeline requires the following cycles per instruction. How many cycles execute the loop? Instruction S1 S2 S3 S4 --- --- --- --- --- I1…
- Question 29 – 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,…
- Question 30 – Resources R1, R2, R3, R4 have 3, 2, 3, 2 units respectively. Allocation is non-preemptive; a request is not entertained unless completely satisfied.…
- Question 31 – 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…
- Question 32 – The diagram shows process states in a uniprocessor system. Assume there are always ready processes. Which statements are TRUE? I. A process making…
- Question 33 – Critical-section entry/exit are implemented with test-and-set; X starts at0. Which statements are TRUE? I. Deadlock-free. II. Starvation-free. III.…
- Question 34 – Why is a multilevel page table preferred over a single-level page table for virtual-to-physical translation?
- Question 35 – For a constant c, T(n)=n for n3, and T(n)=T(n/3)+cn otherwise. What is the time complexity?
- Question 36 – 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…
- Question 37 – What is the maximum height of an AVL tree with7 nodes? A one-node tree has height0.
- Question 38 – For the graph shown, which is NOT a possible sequence of edges added by Kruskal’s minimum-spanning-tree algorithm?
- Question 39 – 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?
- Question 40 – 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
- Question 41 – The DFA shown accepts all strings over 0, 1 that
- Question 42 – Which statements are TRUE? I. Some programming languages have parsing algorithms of complexity less than Θ(n³). II. A language allowing recursion can…
- Question 43 – 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]…
- Question 44 – An initially empty B+ tree has internal-node order3 (maximum tree pointers per internal node) and leaf order2 (maximum data items per leaf). Insert…
- Question 45 – 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…
- Question 46 – 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…
- Question 47 – 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…
- Question 48 – Let G(x) be a CRC generator polynomial. Which condition ensures detection of an odd number of erroneous bits?
- Question 49 – 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…
- Question 50 – Which statements about a module control-flow graph’s cyclomatic complexity are TRUE? I. It equals the maximum number of linearly independent circuits…
- Question 51 – A disk has63 sectors per track, 10 platters with2 recording surfaces each, and1000 cylinders. Sector addresses are ⟨c, h, s⟩: cylinder, surface,…
- Question 52 – A disk has63 sectors per track, 10 platters with2 recording surfaces each, and1000 cylinders. Sector addresses are ⟨c, h, s⟩: cylinder, surface,…
- Question 53 – 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…
- Question 54 – 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…
- Question 55 – Relations: Suppliers(sid:integer, sname:string, city:string, street:string), Parts(pid:integer, pname:string, color:string), Catalog(sid:integer,…
- Question 56 – Relations: Suppliers(sid:integer, sname:string, city:string, street:string), Parts(pid:integer, pname:string, color:string), Catalog(sid:integer,…
- Question 57 – 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…
- Question 58 – 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…
- Question 59 – Consider a binary max-heap implemented as an array. Which array is a max-heap?
- Question 60 – Consider a binary max-heap implemented as an array. Starting with the correct heap from Q59, what array remains after two delete-max operations?