GATE CSE 2016 Set 2 Question Paper with Solutions & Answer Key

Programming and Data Structures and Engineering Mathematics together made up 29 of 85 marks, up 20 from GATE CSE 2015 Set 2. 27 of 55 questions were NAT, more than in any earlier paper. Discrete Mathematics was the heaviest single topic with 8 marks across 4 questions. Programming and Data Structures moved the most against GATE CSE 2015 Set 2: up 11 marks.

1. Q1 · NAT · 1 mark · Propositional and First-Order LogicConsider the following expressions: (i) false (ii) Q (iii) true (iv) P Q (v) eg Q P The number of expressions given above that are logically implied by P (P ⇒ Q) is …
2. Q2 · NAT · 1 mark · CalculusLet f(x) be a polynomial and g(x) = f'(x) be its derivative. If the degree of (f(x) + f(-x)) is 10, then the degree of (g(x) - g(-x)) is …
3. Q3 · NAT · 1 mark · Graph TheoryThe minimum number of colours that is sufficient to vertex-colour any planar graph is …
4. Q4 · MCQ · 1 mark · Linear AlgebraConsider the systems, each consisting of m linear equations in n variables. I. If m n, then none of these systems has a solution III. If m = n, then there exists a syste…
5. Q5 · NAT · 1 mark · Probability and StatisticsSuppose that a shop has an equal number of LED bulbs of two different types. The probability of an LED bulb lasting more than 100 hours given that it is of Type 1 is 0.7…
6. Q6 · NAT · 1 mark · Linear AlgebraSuppose that the eigenvalues of matrix A are 1, 2, 4. The determinant of (A-1)T is …
7. Q7 · NAT · 1 mark · Number Representation and ArithmeticConsider an eight-bit ripple-carry adder for computing the sum of A and B, where A and B are integers represented in 2’s complement form. If the decimal value of A is on…
8. Q8 · MCQ · 1 mark · Boolean Algebra and MinimizationLet, x1 ⊕ x2 ⊕ x3 ⊕ x4 = 0 where x1, x2, x3, x4 are Boolean variables, and ⊕ is the XOR operator. Which one of the following must always be TRUE?
9. Q9 · NAT · 1 mark · Number Representation and ArithmeticLet X be the number of distinct 16-bit integers in 2’s complement representation. Let Y be the number of distinct 16-bit integers in sign magnitude representation. Then…
10. Q10 · NAT · 1 mark · Instruction Set and Addressing ModesA processor has 40 distinct instructions and 24 general purpose registers. A 32-bit instruction word has an opcode, two register operands and an immediate operand. The n…
11. Q11 · NAT · 1 mark · TreesBreadth First Search (BFS) is started on a binary tree beginning from the root vertex. There is a vertex t at a distance four from the root. If t is the n-th vertex in t…
12. Q12 · NAT · 1 mark · Programming in CThe value printed by the following program is … void f(int* p, int m) { m = m + 5; *p = *p + m; return; } void main() { int i=5, j=10; f(&i, j); printf("%d", i+j); }
13. Q13 · MCQ · 1 mark · Searching, Sorting and HashingAssume that the algorithms considered here sort the input sequences in ascending order. If the input is already in ascending order, which of the following are TRUE? I. Q…
14. Q14 · MCQ · 1 mark · Dynamic ProgrammingThe Floyd-Warshall algorithm for all-pair shortest paths computation is based on (A) Greedy paradigm. (B) Divide-and-Conquer paradigm. (C) Dynamic Programming paradigm.…
15. Q15 · MCQ · 1 mark · Linear Structures, Trees and HeapsN items are stored in a sorted doubly linked list. For a delete operation, a pointer is provided to the record to be deleted. For a decrease-key operation, a pointer is…
16. Q16 · NAT · 1 mark · Regular Expressions and Finite AutomataThe number of states in the minimum sized DFA that accepts the language defined by the regular expression (0+1)*(0+1)(0+1)* is …
17. Q17 · MCQ · 1 mark · Context-Free Grammars and PDAsLanguage L1 is defined by the grammar: S1 → aS1b Language L2 is defined by the grammar: S2 → abS2 Consider the following statements: P: L1 is regular Q: L2 is regular Wh…
18. Q18 · MCQ · 1 mark · Turing Machines and UndecidabilityConsider the following types of languages: L1 : Regular, L2 : Context-free, L3 : Recursive, L4 : Recursively enumerable. Which of the following is/are TRUE? I. L3 ∪ L4 i…
19. Q19 · MCQ · 1 mark · Lexical Analysis, Parsing and SDTMatch the following: (P) Lexical analysis (i) Leftmost derivation (Q) Top down parsing (ii) Type checking (R) Semantic analysis (iii) Regular expressions (S) Runtime env…
20. Q20 · MCQ · 1 mark · Memory Management and Virtual MemoryIn which one of the following page replacement algorithms it is possible for the page fault rate to increase even when the number of allocated frames increases?
21. Q21 · MCQ · 1 mark · File Organization and IndexingB+ Trees are considered BALANCED because (A) the lengths of the paths from the root to all leaf nodes are all equal. (B) the lengths of the paths from the root to all le…
22. Q22 · MCQ · 1 mark · Transactions and Concurrency ControlSuppose a database schedule S involves transactions T1, , Tn. Construct the precedence graph of S with vertices representing the transactions and edges representing the…
23. Q23 · MCQ · 1 mark · Principles of LayeringAnarkali digitally signs a message and sends it to Salim. Verification of the signature by Salim requires (A) Anarkali’s public key. (B) Salim’s public key. (C) Salim’s…
24. Q24 · MCQ · 1 mark · Data Link LayerIn an Ethernet local area network, which one of the following statements is TRUE? (A) A station stops to sense the channel once it starts transmitting a frame. (B) The p…
25. Q25 · MCQ · 1 mark · DNS and HTTPIdentify the correct sequence in which the following packets are transmitted on the network by a host when a browser requests a webpage from a remote server, assuming th…
26. Q26 · MCQ · 2 marks · Discrete MathematicsA binary relation R on N × N is defined as follows: (a,b)R(c,d) if a ≤ c or b ≤ d. Consider the following propositions: P: R is reflexive Q: R is transitive Which one of…
27. Q27 · MCQ · 2 marks · Discrete MathematicsWhich one of the following well-formed formulae in predicate calculus is NOT valid?
28. Q28 · MCQ · 2 marks · Discrete MathematicsConsider a set U of 23 different compounds in a Chemistry lab. There is a subset S of U of 9 compounds, each of which reacts with exactly 3 compounds of U. Consider the…
29. Q29 · NAT · 2 marks · Discrete MathematicsThe value of the expression 1399 mod17, in the range 0 to 16, is …
30. Q30 · NAT · 2 marks · Instruction PipeliningSuppose the functions F and G can be computed in 5 and 3 nanoseconds by functional units UF and UG, respectively. Given two instances of UF and two instances of UG, it i…
31. Q31 · NAT · 2 marks · Instruction Set and Addressing ModesConsider a processor with 64 registers and an instruction set of size twelve. Each instruction has five distinct fields, namely, opcode, two source register identifiers,…
32. Q32 · NAT · 2 marks · Cache Memory and HierarchyThe width of the physical address on a machine is 40 bits. The width of the tag field in a 512 KB 8-way set associative cache is … bits.
33. Q33 · NAT · 2 marks · Instruction PipeliningConsider a 3 GHz (gigahertz) processor with a three-stage pipeline and stage latencies au1, au2, and au3 such that au1 = 3 au2/4 = 2 au3. If the longest pipeline stage i…
34. Q34 · NAT · 2 marks · Binary HeapsA complete binary min-heap is made by including each integer in [1, 1023] exactly once. The depth of a node in the heap is the length of the path from the root of the he…
35. Q35 · MCQ · 2 marks · Programming in CThe following function computes XY for positive integers X and Y. int exp(int X, int Y) { int res = 1, a = X, b = Y; while ( b != 0 ){ if ( b%2 == 0) { a = a*a; b = b/2;…
36. Q36 · MCQ · 2 marks · TreesConsider the following New-order strategy for traversing a binary tree: • Visit the root; • Visit the right subtree using New-order; • Visit the left subtree using New-o…
37. Q37 · NAT · 2 marks · Programming in CConsider the following program: int f(int *p, int n) { if (n Note: max(x, y) returns the maximum of x and y. The value printed by this program is …
38. Q38 · NAT · 2 marks · Dynamic ProgrammingLet A1, A2, A3, and A4 be four matrices of dimensions 10 × 5, 5 × 20, 20 × 10, and 10 × 5, respectively. The minimum number of scalar multiplications required to find th…
39. Q39 · NAT · 2 marks · Asymptotic AnalysisThe given diagram shows the flowchart for a recursive function A(n). Assume that all statements, except for the recursive calls, have O(1) time complexity. If the worst…
40. Q40 · NAT · 2 marks · Binary Search TreesThe number of ways in which the numbers 1, 2, 3, 4, 5, 6, 7 can be inserted in an empty binary search tree, such that the resulting tree has height 6, is … *Note: The he…
41. Q41 · MCQ · 2 marks · Graph TheoryIn an adjacency list representation of an undirected simple graph G = (V, E), each edge (u, v) has two adjacency list entries: [v] in the adjacency list of u, and [u] in…
42. Q42 · MCQ · 2 marks · Regular Expressions and Finite AutomataConsider the following two statements: I. If all states of an NFA are accepting states then the language accepted by the NFA is *. II. There exists a regular language A…
43. Q43 · MCQ · 2 marks · Context-Free Grammars and PDAsConsider the following languages: L1 = {an bm cn+m : m, n ≥ 1} L2 = {an bn c2n : n ≥ 1} Which one of the following is TRUE?
44. Q44 · MCQ · 2 marks · Turing Machines and UndecidabilityConsider the following languages. L1 &= { M M takes at least 2016 steps on some input}, L2 &= { M M takes at least 2016 steps on all inputs} and L3 &= { M M accepts }, w…
45. Q45 · MCQ · 2 marks · ParsingWhich one of the following grammars is free from *left recursion*?
46. Q46 · MCQ · 2 marks · Context-Free Grammars and PDAsA student wrote two context-free grammars G1 and G2 for generating a single C-like array declaration. The dimension of the array is at least one. For example, int a[10][…
47. Q47 · NAT · 2 marks · CPU and I/O SchedulingConsider the following processes, with the arrival time and the length of the CPU burst given in milliseconds. The scheduling algorithm used is preemptive shortest remai…
48. Q48 · MCQ · 2 marks · Concurrency and SynchronizationConsider the following two-process synchronization solution. Process 0 Process 1 --------- --------- Entry: loop while (turn == 1); Entry: loop while (turn == 0); (criti…
49. Q49 · NAT · 2 marks · Concurrency and SynchronizationConsider a non-negative counting semaphore S. The operation P(S) decrements S, and V(S) increments S. During an execution, 20 P(S) operations and 12 V(S) operations are…
50. Q50 · NAT · 2 marks · File SystemsA file system uses an in-memory cache to cache disk blocks. The miss rate of the cache is shown in the figure. The latency to read a block from the cache is 1 ms and to…
51. Q51 · MCQ · 2 marks · Transactions and Concurrency ControlConsider the following database schedule with two transactions, T1 and T2. S = r2(X); r1(X); r2(Y); w1(X); r1(Y); w2(X); a1; a2 where ri(Z) denotes a *read* operation by…
52. Q52 · NAT · 2 marks · SQLConsider the following database table named water : The number of tuples returned by the following SQL query is … with total(name, capacity) as select districtname, sum(…
53. Q53 · NAT · 2 marks · Data Link LayerA network has a data transmission bandwidth of 20 × 106 bits per second. It uses CSMA/CD in the MAC layer. The maximum signal propagation time from one node to another n…
54. Q54 · MCQ · 2 marks · Data Link LayerFor the IEEE 802.11 MAC protocol for wireless communication, which of the following statements is/are TRUE? I. At least three non-overlapping channels are available for…
55. Q55 · NAT · 2 marks · Data Link LayerConsider a 128 × 103 bits/second satellite communication link with one way propagation delay of 150 milliseconds. Selective retransmission (repeat) protocol is used on t…

How many questions were in GATE CSE 2016 Set 2?

GATE CSE 2016 Set 2 had 55 questions for 85 marks: 28 MCQ, 0 MSQ and 27 NAT.

Which subject carried the most marks in GATE CSE 2016 Set 2?

Programming and Data Structures carried the most marks (15 of 85). The top three were Programming and Data Structures (15), Engineering Mathematics (14), Computer Organization and Architecture (9).

Where can I find the GATE CSE 2016 Set 2 answer key?

The answer key table on this page lists the answer to every question of GATE CSE 2016 Set 2. Open any question for its full verified solution.

Is the GATE CSE 2016 Set 2 paper useful for GATE 2027 preparation?

Yes. Solving past GATE CSE papers shows how marks are spread across subjects and which topics repeat. Compare it with other GATE CSE question papers and the topic-wise GATE CSE PYQs.

• GATE CSE 2016 Set 1 question paper
• GATE CSE 2015 Set 2 question paper
• GATE CSE 2017 Set 2 question paper
• All GATE CSE papers →
• GATE CSE Programming and Data Structures PYQs
• GATE CSE Engineering Mathematics PYQs
• GATE CSE Computer Organization and Architecture PYQs