The GATE Grind

GATE 2008 CS – Previous Year Questions with Solutions

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

85 questions worth 150 marks in all (20 1-mark, 65 2-mark). Subjects covered: Engineering Mathematics (16), Computer Organization and Architecture (11), Theory of Computation (10), Programming and Data Structures (10), Algorithms (9), Databases (7), Operating System (7), Computer Networks (6).

Practise this paper in The GATE Grind →

  1. Question 1 (1 mark, Multiple choice) – Evaluate x(x- x)/(x+ x).
  2. Question 2 (1 mark, Multiple choice) – P, Q, R are subsets of universal set U. Simplify (P Q R)(Pc Q R) Qc Rc.
  3. Question 3 (1 mark, MTA) – The system x 1+x 2+2x 3=1, x 1+2x 2+3x 3=2, x 1+4x 2+ x 3=4 has a unique solution. The only possible value(s) for α is/are
  4. Question 4 (1 mark, Multiple choice) – In IEEE floating-point representation, hexadecimal0x00000000 corresponds to
  5. Question 5 (1 mark, Multiple choice) – In the shown Karnaugh map, X denotes a don’t-care. Find the minimal function.
  6. Question 6 (1 mark, Multiple choice) – Let r be the radix. Which r satisfies (121) r=(11) r?
  7. Question 7 (1 mark, Multiple choice) – What is the complexity of the most efficient algorithm to count connected components of an undirected graph with n vertices and m edges?
  8. Question 8 (1 mark, Multiple choice) – For the circuit shown, f 1= m(4,5,6,7,8), f 3= m(1,6,15) and f= m(1,6,8,15). What is f 2?
  9. Question 9 (1 mark, Multiple choice) – Which statement is true of \ap p is prime\?
  10. Question 10 (1 mark, Multiple choice) – Which are decidable? I. Whether intersection of two regular languages is infinite. II. Whether a given context-free language is regular. III. Whether…
  11. Question 11 (1 mark, Multiple choice) – Which best describes a handle in LR parsing?
  12. Question 12 (1 mark, Multiple choice) – Some optimizations are performed on intermediate code because
  13. Question 13 (1 mark, Multiple choice) – If L and L are recursively enumerable, L is
  14. Question 14 (1 mark, Multiple choice) – What maximum data size can the application layer pass to TCP below it?
  15. Question 15 (1 mark, Multiple choice) – Which tuple-relational-calculus expression is equivalent to t r(P(t))? I. t r(P(t)) II. t r(P(t)) III. t r( P(t)) IV. t r( P(t))
  16. Question 16 (1 mark, Multiple choice) – A clustering index is defined on fields that are
  17. Question 17 (1 mark, Multiple choice) – Which system call sends a SYN packet?
  18. Question 18 (1 mark, Multiple choice) – Which values make a=4?
  19. Question 19 (1 mark, Multiple choice) – BFS uses a queue. Which is a possible vertex visitation order for the shown graph?
  20. Question 20 (1 mark, Multiple choice) – Data blocks of a very large Unix file are allocated using
  21. Question 21 (2 marks, Multiple choice) – What minimum number of equal-length subintervals approximates 12 xex\,dx with error at most 1310-6 by the trapezoidal rule?
  22. Question 22 (2 marks, Multiple choice) – Newton–Raphson iteration x n+1=12(x n+R/x n) computes which quantity?
  23. Question 23 (2 marks, Multiple choice) – Which is true for every planar graph on n vertices?
  24. Question 24 (2 marks, Multiple choice) – Let P= 1 i2k,\ i oddi and Q= 1 i2k,\ i eveni, where k is a positive integer. Then
  25. Question 25 (2 marks, Multiple choice) – An extremum is a local minimum or maximum. How many distinct extrema does 3x4-16x3+24x2+37 have?
  26. Question 26 (2 marks, Multiple choice) – Simplify (P+ Q)(P Q+PR)( P R+ Q).
  27. Question 27 (2 marks, Multiple choice) – Aishwarya studies CS or mathematics daily. After a CS day the probability of mathematics next day is0.6; after a mathematics day the probability of CS…
  28. Question 28 (2 marks, Multiple choice) – How many of these matrices have eigenvalue1? pmatrix1&0\\0&0pmatrix, pmatrix0&1\\0&0pmatrix, pmatrix1&-1\\1&1pmatrix, pmatrix-1&0\\1&-1pmatrix.
  29. Question 29 (2 marks, Multiple choice) – X is normal with mean1 and variance4. Y is normal with mean−1 and unknown variance. If P(X-1)=P(Y2), what is Y’s standard deviation?
  30. Question 30 (2 marks, Multiple choice) – fsa(x) means x is a finite-state automaton; pda(y) means y is a pushdown automaton; equivalent(a, b) means language equivalence. Which formula…
  31. Question 31 (2 marks, Multiple choice) – Which expressions are equivalent? I. P ∨ ¬Q II. ¬(¬P ∧ Q) III. (P ∧ Q) ∨ (P ∧ ¬Q) ∨ (¬P ∧ ¬Q) IV. (P ∧ Q) ∨ (P ∧ ¬Q) ∨ (¬P ∧ Q)
  32. Question 32 (2 marks, Multiple choice) – For a magnetic disk with concentric tracks, why is seek latency not linearly proportional to seek distance?
  33. Question 33 (2 marks, Multiple choice) – Which are true of auto-increment addressing? I. Useful for self-relocating code. II. Its inclusion in an ISA requires an additional ALU for…
  34. Question 34 (2 marks, Multiple choice) – Which must be true for RFE (return from exception) on a general-purpose processor? I. It must be a trap instruction. II. It must be privileged. III.…
  35. Question 35 (2 marks, Multiple choice) – Which are necessary for inclusion between cache levels L1 and L2? I. L1 write-through. II. L2 write-through. III. L2 associativity greater than L1.…
  36. Question 36 (2 marks, Multiple choice) – Which statements are NOT true for a pipelined processor? I. Bypassing handles all RAW hazards. II. Register renaming eliminates all register-carried…
  37. Question 37 (2 marks, Multiple choice) – Overlapping multiple register windows reduce memory accesses for which? I. Function locals/parameters. II. Register saves/restores. III. Instruction…
  38. Question 38 (2 marks, Multiple choice) – In an instruction pipeline, what is the earliest point at which the data TLB can be accessed?
  39. Question 39 (2 marks, Multiple choice) – Let f(n)=2n, g(n)=n!, h(n)=n n. Which asymptotic statement is true?
  40. Question 40 (2 marks, Multiple choice) – What minimum asymptotic number of comparisons determines whether an integer appears more than n/2 times in a sorted n-integer array?
  41. Question 41 (2 marks, Multiple choice) – An order4 B-tree is built from scratch using10 successive insertions. What maximum number of node splits can occur?
  42. Question 42 (2 marks, Multiple choice) – Graph G has n vertices and2n−2 edges partitionable into two edge-disjoint spanning trees. Which is NOT true?
  43. Question 43 (2 marks, Multiple choice) – Quicksort has a pivot routine splitting every list so each side contains at least one-fifth of the elements. If T(n) counts sorting comparisons, then
  44. Question 44 (2 marks, Multiple choice) – Subset sum: given n positive integers S and positive W, determine whether a subset sums to W. Algorithm Q takes O(nW) time. Which is false?
  45. Question 45 (2 marks, Multiple choice) – Run Dijkstra’s single-source shortest-path algorithm from a in the shown directed graph. For which vertices does it compute correct shortest…
  46. Question 46 (2 marks, Multiple choice) – Given postorder P of a BST containing1, 2, …, n, what is the most efficient complexity for determining the unique BST with that traversal?
  47. Question 47 (2 marks, Multiple choice) – A binary heap has n elements; insert n more, not necessarily one at a time. What total time is required?
  48. Question 48 (2 marks, Multiple choice) – Which is false?
  49. Question 49 (2 marks, MTA) – Automata Y, Z have start1 and final2. Y transitions: 1:a→1, b→2; 2:a→2, b→1. Z:1:a→2, b→2;2:a→1, b→1. Which table is their product Z×Y? P starts, R is…
  50. Question 50 (2 marks, Multiple choice) – Which statements are true? I. Every left-recursive grammar can be converted to right-recursive and vice versa. II. All ε-productions can be removed…
  51. Question 51 (2 marks, Multiple choice) – Match E: declarations precede identifier use; F: formal and actual parameter counts agree; G: arithmetic expressions with matched parentheses; H:…
  52. Question 52 (2 marks, Multiple choice) – Match the shown NFAs P, Q, R, S with regular expressions: 1. +0(01*1+00)*01*; 2. +0(10*1+00)*0; 3. +0(10*1+10)*1; 4. +0(10*1+10)*10*.
  53. Question 53 (2 marks, Multiple choice) – Which are regular sets? I. \an b2m n0,m0\; II. \an bm n=2m\; III. \an bm n m\; IV. \xcy x,y\a,b\*\.
  54. Question 54 (2 marks, Multiple choice) – Which are true? I. A language without globals or nested procedures, but permitting recursion, can use static storage allocation. II. Multilevel access…
  55. Question 55 (2 marks, Multiple choice) – An LALR(1) parser for grammar G can have shift-reduce conflicts if and only if
  56. Question 56 (2 marks, Multiple choice) – In TCP slow start, the congestion-window size
  57. Question 57 (2 marks, Multiple choice) – A class-B network has subnet mask255.255.248.0. What maximum number of hosts per subnet?
  58. Question 58 (2 marks, Multiple choice) – A computer on a10 Mbps network is regulated by a token bucket filled at2 Mbps, initially full with16 megabits. For how long can it transmit at10 Mbps?
  59. Question 59 (2 marks, Multiple choice) – Server S calls socket(), bind(), listen(), then is preempted before accept(). Client P subsequently calls socket(), connect() to S. Which event can…
  60. Question 60 (2 marks, Multiple choice) – What is printed by this C program?
  61. Question 61 (2 marks, Multiple choice) – Fill ?1, ?2 to print a newline-terminated input string in reverse order.
  62. Question 62 (2 marks, Multiple choice) – The list contains1, 2, 3, 4, 5, 6, 7. What is its content after this function?
  63. Question 63 (2 marks, Multiple choice) – Counting semaphore s uses P: decrement s, wait if s<0; V: increment s, wake one waiter if s≤0. Binary primitives Pb, Vb implement it as below. What…
  64. Question 64 (2 marks, Multiple choice) – Which statement about synchronous/asynchronous I/O is NOT true?
  65. Question 65 (2 marks, Multiple choice) – Which is NOT true of deadlock prevention/avoidance?
  66. Question 66 (2 marks, Multiple choice) – A process executes the code below. How many child processes are created?
  67. Question 67 (2 marks, Multiple choice) – A processor has36-bit physical and32-bit virtual addresses, 4 KB page frames, and4-byte page-table entries. Three levels index virtual bits30–31,…
  68. Question 68 (2 marks, Multiple choice) – Relations R(P, Q, R1, R2, R3), S(P, Q, S1, S2) both have key P, Q. Which queries are equivalent? I. P(R S) II. P(R) P(S) III. P( P,Q(R) P,Q(S)) IV. P(…
  69. Question 69 (2 marks, Multiple choice) – Schemas: Book(Title, Author, Catalog no, Publisher, Year, Price); Collection(Title, Author, Catalog no). FDs: Title Author→Catalog no; Catalog…
  70. Question 70 (2 marks, Multiple choice) – A file has16384 records, 32 bytes each; key field6 bytes. File is ordered by a nonkey field and unspanned. Blocks1024 bytes, block pointers10 bytes. A…
  71. Question 71 (2 marks, Multiple choice) – A machine has a2-way set-associative64 KB cache, 16-byte blocks, 32-bit virtual addresses, 4 KB pages. double is8 bytes. ARR[1024][1024] begins at…
  72. Question 72 (2 marks, Multiple choice) – A machine has a2-way set-associative64 KB cache, 16-byte blocks, 32-bit virtual addresses, 4 KB pages. double is8 bytes. ARR[1024][1024] begins at…
  73. Question 73 (2 marks, Multiple choice) – A machine has a2-way set-associative64 KB cache, 16-byte blocks, 32-bit virtual addresses, 4 KB pages. double is8 bytes. ARR[1024][1024] begins at…
  74. Question 74 (2 marks, MTA) – Consider the C functions (assume N>n): What are the running times of f1(n), f2(n)?
  75. Question 75 (2 marks, Multiple choice) – Consider the C functions (assume N>n): What values do f1(8), f2(8) return?
  76. Question 76 (2 marks, Multiple choice) – Delayed branching handles control hazards. For all delayed conditional branches, irrespective of whether the condition is true or false,
  77. Question 77 (2 marks, Multiple choice) – A pipelined processor has one branch delay slot. Which instruction can move into it without any other program modification?
  78. Question 78 (2 marks, Multiple choice) – Let xₙ count n-bit binary strings with no consecutive0s. Which recurrence holds?
  79. Question 79 (2 marks, MTA) – Let xₙ count n-bit binary strings containing no consecutive0s, using the recurrence in Q78. What is x₅?
  80. Question 80 (2 marks, Multiple choice) – Given positive integers S=\a 1,,a n\ and positive W, subset sum asks whether some subset sums to W. Boolean X[i, j], with n rows and W+1 columns…
  81. Question 81 (2 marks, Multiple choice) – Given positive integers S=\a 1,,a n\ and positive W, subset sum asks whether some subset sums to W. Boolean X[i, j], with n rows and W+1 columns…
  82. Question 82 (2 marks, Multiple choice) – For the ER diagram shown, what minimum number of tables represents M, N, P, R1, R2?
  83. Question 83 (2 marks, Multiple choice) – For the ER diagram from Q82, which is a correct attribute set for one resulting table?
  84. Question 84 (2 marks, Multiple choice) – The following erroneous C program attempts binary search in Y[10]: On which input does it fail?
  85. Question 85 (2 marks, Multiple choice) – The following erroneous C program attempts binary search in Y[10]: Which correction makes it work properly?