GATE 2016 CS (CS2) – Previous Year Questions with Solutions
All 65 questions of GATE 2016 CS (CS2) with answers and explanations. Read each question, then practise it by topic or as a full paper.
Practise this paper in The GATE Grind →
- Question 1 – The man who is now Municipal Commissioner worked as .
- Question 2 – Nobody knows how the Indian cricket team is going to cope with the difficult and seamer-friendly wickets in Australia. Choose the closest meaning of…
- Question 3 – Find the odd word: mock, deride, praise, jeer.
- Question 4 – Pick the odd sequence.
- Question 5 – In a quadratic function, roots α and β satisfy αβ = 4. Find (n+n)/(-n+-n).
- Question 6 – Among 150 faculty members, 55 are connected through Facebook and 85 through WhatsApp. Thirty have neither account. How many are connected only through…
- Question 7 – Computers were invented for performing only high-end useful computations. However, it is no understatement that they have taken over our world today.…
- Question 8 – All hill-stations have a lake. Ooty has two lakes. Which can be inferred? (i) Ooty is not a hill-station. (ii) No hill-station can have more than one…
- Question 9 – Each cell in the shown 2 × 4 rectangular grid is a rectangle. How many rectangles are present?
- Question 10 – Choose the expression for f(x) in the graph.
- Question 11 – Consider (i) false, (ii) Q, (iii) true, (iv) P Q, (v) Q P. How many are logically implied by P(P Q)?
- Question 12 – Let f(x) be a polynomial and g(x)=f(x). If f(x)+f(−x) has degree 10, find the degree of g(x)−g(−x).
- Question 13 – Find the minimum number of colours sufficient to vertex-colour every planar graph.
- Question 14 – Consider systems of m linear equations in n variables. I: If m < n, all such systems have a solution. II: If m > n, none has a solution. III: If m =…
- Question 15 – A shop has equal numbers of two LED bulb types. The probabilities of lasting more than 100 hours are 0.7 for type 1 and 0.4 for type 2. Find the…
- Question 16 – A has eigenvalues 1, 2 and 4. Find ((A-1)T).
- Question 17 – An eight-bit ripple-carry adder computes A + B for two’s-complement integers. A = 1. Find the decimal B that causes the longest sum-settling latency.
- Question 18 – Boolean variables satisfy x 1 x 2 x 3 x 4=0. Which must hold?
- Question 19 – X is the number of distinct 16-bit two’s-complement integers; Y is the number of distinct 16-bit sign-magnitude integers. Find X − Y.
- Question 20 – A processor has 40 instructions, 24 general-purpose registers and a 32-bit instruction with an opcode, two register operands and one immediate…
- Question 21 – BFS starts at the root of a binary tree. A vertex t is at distance four. If t is the n-th vertex visited, find the maximum n.
- Question 22 – What does this C program print?
- Question 23 – Algorithms sort in ascending order. On an already ascending input, which are true? I: Quicksort takes (n2). II: Bubblesort takes (n2). III: Mergesort…
- Question 24 – Which paradigm underlies Floyd–Warshall all-pairs shortest paths?
- Question 25 – N records are in a sorted doubly linked list. Node pointers are supplied for delete and decrease-key. An algorithm performs, in order, (N) deletes, O(…
- Question 26 – How many states are in a smallest DFA for (0+1)*(0+1)(0+1)*?
- Question 27 – S 1 aS 1b generates L₁ and S 2 abS 2 generates L₂. P says L₁ is regular; Q says L₂ is regular. Which is true?
- Question 28 – L₁ is regular, L₂ context-free, L₃ recursive and L₄ recursively enumerable. Which hold? I: L 3 L 4 is recursively enumerable. II: L 2 L 3 is…
- Question 29 – Match P: lexical analysis; Q: top-down parsing; R: semantic analysis; S: runtime environments, with (i) leftmost derivation, (ii) type checking, (iii)…
- Question 30 – Which page replacement algorithm can have an increased fault rate when more frames are allocated?
- Question 31 – B+ trees are considered balanced because
- Question 32 – For a serializable schedule, precedence-graph vertices represent transactions and directed edges represent conflicts. Which vertex ordering yields an…
- Question 33 – Anarkali digitally signs a message and sends it to Salim. What does Salim need to verify the signature?
- Question 34 – Which Ethernet LAN statement is true?
- Question 35 – A host has just restarted and its browser requests a remote webpage. Order the listed packets.
- Question 36 – On N N, (a,b)R(c,d) iff a ≤ c or b ≤ d. P: R is reflexive. Q: R is transitive. Which is true?
- Question 37 – Which predicate-calculus formula is NOT valid?
- Question 38 – There are 23 distinct compounds U. Each of nine compounds in S reacts with exactly three compounds of U. Which always holds? I: Every compound in U∖S…
- Question 39 – Evaluate 1399 17 as an integer from 0 through 16.
- Question 40 – F takes 5 ns and G takes 3 ns on their functional units. Two instances of each unit are available. Ignoring other delays, find the minimum time for…
- Question 41 – A processor has 64 registers and 12 instructions. Each instruction contains opcode, two source-register fields, one destination-register field and a…
- Question 42 – Physical addresses are 40 bits. A 512 KB cache is eight-way set-associative. Find tag width in bits.
- Question 43 – A 3 GHz three-stage pipeline has latencies 1=3 2/4=2 3. The longest stage is split into two equal stages. Ignoring register delay, find the new…
- Question 44 – A complete binary min-heap contains each integer 1 through 1023 once. Root depth is zero. Find the greatest depth of integer 9.
- Question 45 – This function computes XY for positive integers. Which invariant holds before every loop iteration?
- Question 46 – New-order traversal visits root, then right subtree in New-order, then left subtree in New-order. Find it for the tree of postfix expression “3 4 * 5…
- Question 47 – What does this program print? max returns the larger argument.
- Question 48 – Matrices A₁,A₂,A₃,A₄ have dimensions 10×5, 5×20, 20×10 and 10×5. Find the minimum scalar-multiplication count for A₁A₂A₃A₄ using ordinary matrix…
- Question 49 – The flowchart defines recursive function A(n). Other statements cost O(1). If worst-case time is O(n), find the least α to two decimal places.
- Question 50 – How many insertion orders of 1,2,3,4,5,6,7 give a binary search tree of height six? A single-node tree has height zero.
- Question 51 – Each edge of a simple undirected graph has two adjacency-list entries, one at each endpoint. A twin pointer connects these entries. With n vertices, m…
- Question 52 – I: If every NFA state is accepting, the accepted language is Σ*. II: There exists a regular language A such that A∩B is regular for every language B.…
- Question 53 – L 1=\anbmcn+m:m,n1\ and L 2=\anbnc2n:n1\. Which holds?
- Question 54 – Let L₁=⟨M⟩: M takes at least 2016 steps on some input, L₂=⟨M⟩: M takes at least 2016 steps on all inputs, L₃=⟨M⟩: M accepts ε, with ⟨M⟩ encoding a…
- Question 55 – Which grammar has no left recursion?
- Question 56 – Start symbol D and terminals int, ;, id, [, ], num generate one C-like array declaration with at least one dimension, such as int a[10][3];. G₁: D →…
- Question 57 – Preemptive shortest-remaining-time-first schedules P₁:(arrival 0, burst 10), P₂:(3,6), P₃:(7,1), P₄:(8,3), all in ms. Find mean turnaround time.
- Question 58 – Shared turn starts at zero. Process 0 waits while turn == 1, enters its critical section, then sets turn = 1. Process 1 waits while turn == 0, enters…
- Question 59 – A nonnegative counting semaphore S uses P (decrement, blocking if unavailable) and V (increment). During execution twenty P and twelve V operations…
- Question 60 – A disk-block cache has the plotted miss rates. Cache read latency is 1 ms and disk read latency 10 ms. Checking presence is negligible. Available…
- Question 61 – S = r₂(X); r₁(X); r₂(Y); w₁(X); r₁(Y); w₂(X); a₁; a₂, where r,w mean read/write and a means abort. Which statement is true?
- Question 62 – Table water schemes has (scheme no,district name,capacity): (1,Ajmer,20), (1,Bikaner,10), (2,Bikaner,10), (3,Bikaner,20), (1,Churu,10), (2,Churu,20),…
- Question 63 – A 20×10⁶ bit/s CSMA/CD network has maximum one-way propagation 40 μs. Find the minimum frame size in bytes.
- Question 64 – For IEEE 802.11 wireless MAC: I: At least three nonoverlapping channels are available. II: RTS–CTS is used for collision detection. III: Unicast…
- Question 65 – A 128×10³ bit/s satellite link has one-way propagation 150 ms. Selective-repeat ARQ sends 1 KB frames. Ignore ACK transmission time. Find the smallest…