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 →
- Question 1 – Evaluate x(x- x)/(x+ x).
- Question 2 – P, Q, R are subsets of universal set U. Simplify (P Q R)(Pc Q R) Qc Rc.
- Question 3 – 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
- Question 4 – In IEEE floating-point representation, hexadecimal0x00000000 corresponds to
- Question 5 – In the shown Karnaugh map, X denotes a don’t-care. Find the minimal function.
- Question 6 – Let r be the radix. Which r satisfies (121) r=(11) r?
- Question 7 – What is the complexity of the most efficient algorithm to count connected components of an undirected graph with n vertices and m edges?
- Question 8 – 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?
- Question 9 – Which statement is true of \ap p is prime\?
- Question 10 – Which are decidable? I. Whether intersection of two regular languages is infinite. II. Whether a given context-free language is regular. III. Whether…
- Question 11 – Which best describes a handle in LR parsing?
- Question 12 – Some optimizations are performed on intermediate code because
- Question 13 – If L and L are recursively enumerable, L is
- Question 14 – What maximum data size can the application layer pass to TCP below it?
- Question 15 – 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))
- Question 16 – A clustering index is defined on fields that are
- Question 17 – Which system call sends a SYN packet?
- Question 18 – Which values make a=4?
- Question 19 – BFS uses a queue. Which is a possible vertex visitation order for the shown graph?
- Question 20 – Data blocks of a very large Unix file are allocated using
- Question 21 – What minimum number of equal-length subintervals approximates 12 xex\,dx with error at most 1310-6 by the trapezoidal rule?
- Question 22 – Newton–Raphson iteration x n+1=12(x n+R/x n) computes which quantity?
- Question 23 – Which is true for every planar graph on n vertices?
- Question 24 – Let P= 1 i2k,\ i oddi and Q= 1 i2k,\ i eveni, where k is a positive integer. Then
- Question 25 – An extremum is a local minimum or maximum. How many distinct extrema does 3x4-16x3+24x2+37 have?
- Question 26 – Simplify (P+ Q)(P Q+PR)( P R+ Q).
- Question 27 – 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…
- Question 28 – How many of these matrices have eigenvalue1? pmatrix1&0\\0&0pmatrix, pmatrix0&1\\0&0pmatrix, pmatrix1&-1\\1&1pmatrix, pmatrix-1&0\\1&-1pmatrix.
- Question 29 – 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?
- Question 30 – 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…
- Question 31 – Which expressions are equivalent? I. P ∨ ¬Q II. ¬(¬P ∧ Q) III. (P ∧ Q) ∨ (P ∧ ¬Q) ∨ (¬P ∧ ¬Q) IV. (P ∧ Q) ∨ (P ∧ ¬Q) ∨ (¬P ∧ Q)
- Question 32 – For a magnetic disk with concentric tracks, why is seek latency not linearly proportional to seek distance?
- Question 33 – Which are true of auto-increment addressing? I. Useful for self-relocating code. II. Its inclusion in an ISA requires an additional ALU for…
- Question 34 – 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.…
- Question 35 – 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.…
- Question 36 – Which statements are NOT true for a pipelined processor? I. Bypassing handles all RAW hazards. II. Register renaming eliminates all register-carried…
- Question 37 – Overlapping multiple register windows reduce memory accesses for which? I. Function locals/parameters. II. Register saves/restores. III. Instruction…
- Question 38 – In an instruction pipeline, what is the earliest point at which the data TLB can be accessed?
- Question 39 – Let f(n)=2n, g(n)=n!, h(n)=n n. Which asymptotic statement is true?
- Question 40 – What minimum asymptotic number of comparisons determines whether an integer appears more than n/2 times in a sorted n-integer array?
- Question 41 – An order4 B-tree is built from scratch using10 successive insertions. What maximum number of node splits can occur?
- Question 42 – Graph G has n vertices and2n−2 edges partitionable into two edge-disjoint spanning trees. Which is NOT true?
- Question 43 – 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
- Question 44 – 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?
- Question 45 – Run Dijkstra’s single-source shortest-path algorithm from a in the shown directed graph. For which vertices does it compute correct shortest…
- Question 46 – Given postorder P of a BST containing1, 2, …, n, what is the most efficient complexity for determining the unique BST with that traversal?
- Question 47 – A binary heap has n elements; insert n more, not necessarily one at a time. What total time is required?
- Question 48 – Which is false?
- Question 49 – 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…
- Question 50 – Which statements are true? I. Every left-recursive grammar can be converted to right-recursive and vice versa. II. All ε-productions can be removed…
- Question 51 – Match E: declarations precede identifier use; F: formal and actual parameter counts agree; G: arithmetic expressions with matched parentheses; H:…
- Question 52 – 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*.
- Question 53 – 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\*\.
- Question 54 – Which are true? I. A language without globals or nested procedures, but permitting recursion, can use static storage allocation. II. Multilevel access…
- Question 55 – An LALR(1) parser for grammar G can have shift-reduce conflicts if and only if
- Question 56 – In TCP slow start, the congestion-window size
- Question 57 – A class-B network has subnet mask255.255.248.0. What maximum number of hosts per subnet?
- Question 58 – 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?
- Question 59 – Server S calls socket(), bind(), listen(), then is preempted before accept(). Client P subsequently calls socket(), connect() to S. Which event can…
- Question 60 – What is printed by this C program?
- Question 61 – Fill ?1, ?2 to print a newline-terminated input string in reverse order.
- Question 62 – The list contains1, 2, 3, 4, 5, 6, 7. What is its content after this function?
- Question 63 – 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…
- Question 64 – Which statement about synchronous/asynchronous I/O is NOT true?
- Question 65 – Which is NOT true of deadlock prevention/avoidance?
- Question 66 – A process executes the code below. How many child processes are created?
- Question 67 – A processor has36-bit physical and32-bit virtual addresses, 4 KB page frames, and4-byte page-table entries. Three levels index virtual bits30–31,…
- Question 68 – 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(…
- Question 69 – Schemas: Book(Title, Author, Catalog no, Publisher, Year, Price); Collection(Title, Author, Catalog no). FDs: Title Author→Catalog no; Catalog…
- Question 70 – 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…
- Question 71 – 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…
- Question 72 – 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…
- Question 73 – 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…
- Question 74 – Consider the C functions (assume N>n): What are the running times of f1(n), f2(n)?
- Question 75 – Consider the C functions (assume N>n): What values do f1(8), f2(8) return?
- Question 76 – Delayed branching handles control hazards. For all delayed conditional branches, irrespective of whether the condition is true or false,
- Question 77 – A pipelined processor has one branch delay slot. Which instruction can move into it without any other program modification?
- Question 78 – Let xₙ count n-bit binary strings with no consecutive0s. Which recurrence holds?
- Question 79 – Let xₙ count n-bit binary strings containing no consecutive0s, using the recurrence in Q78. What is x₅?
- Question 80 – 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…
- Question 81 – 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…
- Question 82 – For the ER diagram shown, what minimum number of tables represents M, N, P, R1, R2?
- Question 83 – For the ER diagram from Q82, which is a correct attribute set for one resulting table?
- Question 84 – The following erroneous C program attempts binary search in Y[10]: On which input does it fail?
- Question 85 – The following erroneous C program attempts binary search in Y[10]: Which correction makes it work properly?