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

Engineering Mathematics and Programming and Data Structures together made up 24 of 85 marks, down 6 from GATE CSE 2015 Set 1. 26 of 55 questions were NAT, more than in any earlier paper. Context-Free Grammars and PDAs was the heaviest single topic with 5 marks across 3 questions. Engineering Mathematics moved the most against GATE CSE 2015 Set 1: down 5 marks.

1. Q1 · NAT · 1 mark · Propositional and First-Order LogicLet p, q, r, s represent the following propositions. p: x ∈ {8, 9, 10, 11, 12} q: x is a composite number r: x is a perfect square s: x is a prime number The integer x ≥…
2. Q2 · MCQ · 1 mark · Recurrence RelationsLet an be the number of n-bit strings that do NOT contain two consecutive 1s. Which one of the following is the recurrence relation for an?
3. Q3 · NAT · 1 mark · Calculuslimx → 4 (sin(x-4))/(x-4) = …
4. Q4 · NAT · 1 mark · Probability and StatisticsA probability density function on the interval [a, 1] is given by 1/x2 and outside this interval the value of the function is zero. The value of a is …
5. Q5 · NAT · 1 mark · Linear AlgebraTwo eigenvalues of a 3 × 3 real matrix P are (2 + √(-1)) and 3. The determinant of P is …
6. Q6 · MCQ · 1 mark · Boolean Algebra and MinimizationConsider the Boolean operator # with the following properties: x\#0 = x, x\#1 = x, x\#x = 0 and x\# x = 1. Then x\#y is equivalent to
7. Q7 · NAT · 1 mark · Number Representation and ArithmeticThe 16-bit 2's complement representation of an integer is 1111 1111 1111 0101; its decimal representation is …
8. Q8 · NAT · 1 mark · Combinational and Sequential CircuitsWe want to design a synchronous counter that counts the sequence 0-1-0-2-0-3 and then repeats. The minimum number of J-K flip-flops required to implement this counter is…
9. Q9 · NAT · 1 mark · Cache Memory and HierarchyA processor can support a maximum memory of 4 GB, where the memory is word-addressable (a word consists of two bytes). The size of the address bus of the processor is at…
10. Q10 · MCQ · 1 mark · Linear Structures, Trees and HeapsA queue is implemented using an array such that ENQUEUE and DEQUEUE operations are performed efficiently. Which one of the following statements is CORRECT (n refers to t…
11. Q11 · NAT · 1 mark · Graph TraversalsConsider the following directed graph: The number of different topological orderings of the vertices of the graph is …
12. Q12 · MCQ · 1 mark · Programming in CConsider the following C program. void f(int, short); void main() { int i = 100; short s = 12; short *p = &s; … ; // call to f() } Which one of the following expressions…
13. Q13 · MCQ · 1 mark · Searching, Sorting and HashingThe worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:
14. Q14 · MCQ · 1 mark · Graph Traversals, MSTs and Shortest PathsLet G be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increased by the same value, then which of the following stat…
15. Q15 · NAT · 1 mark · Programming in CConsider the following C program. #include void mystery(int *ptra, int *ptrb) { int *temp; temp = ptrb; ptrb = ptra; ptra = temp; } int main() { int a=2016, b=0, c=4, d=…
16. Q16 · MCQ · 1 mark · Context-Free Grammars and PDAsWhich of the following languages is generated by the given grammar? S aS bS
17. Q17 · MCQ · 1 mark · Turing Machines and UndecidabilityWhich of the following decision problems are undecidable? I. Given NFAs N1 and N2, is L(N1) ∩ L(N2) = ? II. Given a CFG G = (N, , P, S) and a string x ∈ *, does x ∈ L(G)…
18. Q18 · MCQ · 1 mark · Regular Expressions and Finite AutomataWhich one of the following regular expressions represents the language: the set of all binary strings having two consecutive 0s and two consecutive 1s?
19. Q19 · NAT · 1 mark · Intermediate Code GenerationConsider the following code segment. x = u - t; y = x * v; x = y + w; y = t - z; y = x * y; The minimum number of total variables required to convert the above code segm…
20. Q20 · MCQ · 1 mark · CPU and I/O SchedulingConsider an arbitrary set of CPU-bound processes with unequal CPU burst lengths submitted at the same time to a computer system. Which one of the following process sched…
21. Q21 · MCQ · 1 mark · Integrity Constraints and Normal FormsWhich of the following is NOT a superkey in a relational schema with attributes V, W, X, Y, Z and primary key V Y?
22. Q22 · MCQ · 1 mark · Transactions and Concurrency ControlWhich one of the following is NOT a part of the ACID properties of database transactions?
23. Q23 · MCQ · 1 mark · Integrity Constraints and Normal FormsA database of research articles in a journal uses the following schema. (VOLUME, NUMBER, STARTPAGE, ENDPAGE, TITLE, YEAR, PRICE) The primary key is (VOLUME, NUMBER, STAR…
24. Q24 · MCQ · 1 mark · DNS and HTTPWhich one of the following protocols is NOT used to resolve one form of address to another one?
25. Q25 · MCQ · 1 mark · DNS and HTTPWhich of the following is/are example(s) of stateful application layer protocols? (i) HTTP (ii) FTP (iii) TCP (iv) POP3
26. Q26 · NAT · 2 marks · CombinatoricsThe coefficient of x12 in (x3 + x4 + x5 + x6 + )3 is …
27. Q27 · NAT · 2 marks · CombinatoricsConsider the recurrence relation a1 = 8, an = 6n2 + 2n + an-1. Let a99 = K × 104. The value of K is …
28. Q28 · NAT · 2 marks · Sets, Relations, Lattices and GroupsA function f : N+ → N+, defined on the set of positive integers N+, satisfies the following properties: f(n) = f(n/2) if n is even f(n) = f(n+5) if n is odd Let R = {i ∃…
29. Q29 · NAT · 2 marks · Probability and StatisticsConsider the following experiment. Step 1. Flip a fair coin twice. Step 2. If the outcomes are (TAILS, HEADS) then output Y and stop. Step 3. If the outcomes are either…
30. Q30 · MCQ · 2 marks · Combinational and Sequential CircuitsConsider the two cascaded 2-to-1 multiplexers as shown in the figure. The minimal sum of products form of the output X is
31. Q31 · NAT · 2 marks · I/O Interface, Interrupts and DMAThe size of the data count register of a DMA controller is 16 bits. The processor needs to transfer a file of 29,154 kilobytes from disk to main memory. The memory is by…
32. Q32 · NAT · 2 marks · Instruction PipeliningThe stage delays in a 4-stage pipeline are 800, 500, 400 and 300 picoseconds. The first stage (with delay 800 picoseconds) is replaced with a functionally equivalent des…
33. Q33 · MCQ · 2 marks · ALU DesignConsider a carry lookahead adder for adding two n-bit integers, built using gates of fan-in at most two. The time to perform addition using this adder is (A) (1) (B) (lo…
34. Q34 · MCQ · 2 marks · Programming in CThe following function computes the maximum value contained in an integer array p[] of size n (n ≥ 1). int max(int *p, int n) { int a=0, b=n-1; while ( … ) { if (p[a] Th…
35. Q35 · MCQ · 2 marks · RecursionWhat will be the output of the following C program? void count(int n){ static int d=1; printf("%d ", n); printf("%d ", d); d++; if(n>1) count(n-1); printf("%d ", d); } v…
36. Q36 · MCQ · 2 marks · Runtime EnvironmentsWhat will be the output of the following pseudo-code when parameters are passed by reference and dynamic scoping is assumed? a=3; void n(x) {x = x * a; print(x);} void m…
37. Q37 · MCQ · 2 marks · Binary HeapsAn operator delete(i) for a binary heap data structure is to be designed to delete the item in the i-th node. Assume that the heap is implemented in an array and i refer…
38. Q38 · NAT · 2 marks · Shortest PathsConsider the weighted undirected graph with 4 vertices, where the weight of edge {i, j} is given by the entry Wij in the matrix W. W = 0 & 2 & 8 & 5 2 & 0 & 5 & 8 8 & 5…
39. Q39 · NAT · 2 marks · Minimum Spanning TreesLet G be a complete undirected graph on 4 vertices, having 6 edges with weights being 1, 2, 3, 4, 5, and 6. The maximum possible weight that a minimum weight spanning tr…
40. Q40 · MCQ · 2 marks · Minimum Spanning TreesG = (V,E) is an undirected simple graph in which each edge has a distinct weight, and e is a particular edge of G. Which of the following statements about the minimum sp…
41. Q41 · NAT · 2 marks · Linear Structures, Trees and HeapsLet Q denote a queue containing sixteen numbers and S be an empty stack. Head(Q) returns the element at the head of the queue Q without removing it from Q. Similarly Top…
42. Q42 · MCQ · 2 marks · Context-Free Grammars and PDAsConsider the following context-free grammars: G1: S → aS | B, B → b | bB G2: S → aA | bB, A → aA | B | , B → bB | Which one of the following pairs of languages is genera…
43. Q43 · MCQ · 2 marks · Context-Free Grammars and PDAsConsider the transition diagram of a PDA given below with input alphabet = {a,b} and stack alphabet = {X, Z}. Z is the initial stack symbol. Let L denote the language ac…
44. Q44 · MCQ · 2 marks · Turing Machines and UndecidabilityLet X be a recursive language and Y be a recursively enumerable but not recursive language. Let W and Z be two languages such that Y reduces to W, and Z reduces to X (re…
45. Q45 · NAT · 2 marks · ParsingThe attributes of three arithmetic operators in some programming language are given below. The value of the expression 2 - 5 + 1 - 7 * 3 in this language is …
46. Q46 · MCQ · 2 marks · Syntax-Directed TranslationConsider the following Syntax Directed Translation Scheme (SDTS), with non-terminals {S, A} and terminals {a, b}. S & aA & { print 1 } S & a & { print 2 } A & Sb & { pri…
47. Q47 · NAT · 2 marks · Memory Management and Virtual MemoryConsider a computer system with 40-bit virtual addressing and page size of sixteen kilobytes. If the computer system has a one-level page table per process and each page…
48. Q48 · NAT · 2 marks · CPU and I/O SchedulingConsider a disk queue with requests for I/O to blocks on cylinders 47, 38, 121, 191, 87, 11, 92, 10. The C-LOOK scheduling algorithm is used. The head is initially at cy…
49. Q49 · NAT · 2 marks · Memory Management and Virtual MemoryConsider a computer system with ten physical page frames. The system is provided with an access sequence (a1, a2, , a20, a1, a2, , a20), where each ai is a distinct virt…
50. Q50 · MCQ · 2 marks · Concurrency and SynchronizationConsider the following proposed solution for the critical section problem. There are n processes: P0 Pn-1. In the code, function pmax returns an integer not smaller than…
51. Q51 · MCQ · 2 marks · Transactions and Concurrency ControlConsider the following two phase locking protocol. Suppose a transaction T accesses (for read or write operations), a certain set of objects {O1, , Ok}. This is done in…
52. Q52 · MCQ · 2 marks · Network SecurityConsider that B wants to send a message m that is digitally signed to A. Let the pair of private and public keys for A and B be denoted by Kx- and Kx+ for x = A, B, resp…
53. Q53 · NAT · 2 marks · IPv4 FragmentationAn IP datagram of size 1000 bytes arrives at a router. The router has to forward this packet on a link whose MTU (maximum transmission unit) is 100 bytes. Assume that th…
54. Q54 · NAT · 2 marks · TCP Flow and Congestion ControlFor a host machine that uses the token bucket algorithm for congestion control, the token bucket has a capacity of 1 megabyte and the maximum output rate is 20 megabytes…
55. Q55 · NAT · 2 marks · Data Link LayerA sender uses the Stop-and-Wait ARQ protocol for reliable transmission of frames. Frames are of size 1000 bytes and the transmission rate at the sender is 80 Kbps (1Kbps…

How many questions were in GATE CSE 2016 Set 1?

GATE CSE 2016 Set 1 had 55 questions for 85 marks: 29 MCQ, 0 MSQ and 26 NAT.

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

Engineering Mathematics carried the most marks (13 of 85). The top three were Engineering Mathematics (13), Programming and Data Structures (11), Computer Networks (10).

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

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

Is the GATE CSE 2016 Set 1 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 2 question paper
• GATE CSE 2015 Set 1 question paper
• GATE CSE 2017 Set 1 question paper
• All GATE CSE papers →
• GATE CSE Engineering Mathematics PYQs
• GATE CSE Programming and Data Structures PYQs
• GATE CSE Computer Networks PYQs