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

Engineering Mathematics and Theory of Computation together made up 24 of 85 marks, up 2 from GATE CSE 2020. 18 of 55 questions were NAT, the most since 2020. Probability and Statistics was the heaviest single topic with 5 marks across 3 questions. Compiler Design moved the most against GATE CSE 2020: up 4 marks.

1. Q1 · MCQ · 1 mark · Minimum Spanning TreesLet G be a connected undirected weighted graph. Consider the following two statements. S1 : There exists a minimum weight edge in G which is present in every minimum spa…
2. Q2 · MCQ · 1 mark · Binary HeapsLet H be a binary min-heap consisting of n elements implemented as an array. What is the worst case time complexity of an optimal algorithm to find the maximum element i…
3. Q3 · MCQ · 1 mark · Lexical Analysis, Parsing and SDTConsider the following ANSI C program: int main() { Integer x; return 0; } Which one of the following phases in a seven-phase C compiler will throw an error?
4. Q4 · MCQ · 1 mark · Number Representation and ArithmeticThe format of the single-precision floating-point representation of a real number as per the IEEE 754 standard is as follows: Which one of the following choices is corre…
5. Q5 · MCQ · 1 mark · Combinational and Sequential CircuitsWhich one of the following circuits implements the Boolean function given below? f(x, y, z) = m0 + m1 + m3 + m4 + m5 + m6, where mi is the ith minterm.
6. Q6 · MCQ · 1 mark · Integrity Constraints and Normal FormsConsider the following statements S1 and S2 about the relational data model: S1: A relation scheme can have at most one foreign key. S2: A foreign key in a relation sche…
7. Q7 · MCQ · 1 mark · TCP Flow and Congestion ControlConsider the three-way handshake mechanism followed during TCP connection establishment between hosts P and Q. Let X and Y be two random 32-bit starting sequence numbers…
8. Q8 · MCQ · 1 mark · Searching, Sorting and HashingWhat is the worst-case number of arithmetic operations performed by recursive binary search on a sorted array of size n?
9. Q9 · MCQ · 1 mark · Regular Expressions and Finite AutomataLet L ⊆ {0, 1}* be an arbitrary regular language accepted by a minimal DFA with k states. Which one of the following languages must necessarily be accepted by a minimal…
10. Q10 · MCQ · 1 mark · Programming in CConsider the following ANSI C program. #include int main(){ int arr[4][5]; int i, j; for (i=0; i What is the output of the above program?
11. Q11 · MSQ · 1 mark · Sets, Relations and FunctionsConsider the following sets, where n ≥ 2: S1: Set of all n × n matrices with entries from the set {a, b, c} S2: Set of all functions from the set {0, 1, 2, , n2 - 1} to…
12. Q12 · MSQ · 1 mark · Regular and Context-Free LanguagesLet L1 be a regular language and L2 be a context-free language. Which of the following languages is/are context-free?
13. Q13 · MSQ · 1 mark · Intermediate Code GenerationIn the context of compilers, which of the following is/are NOT an intermediate representation of the source program?
14. Q14 · MSQ · 1 mark · CPU and I/O SchedulingWhich of the following statement(s) is/are correct in the context of CPU scheduling?
15. Q15 · MSQ · 1 mark · Propositional and First-Order LogicChoose the correct choice(s) regarding the following propositional logic assertion S: S : ((P Q) → R) → ((P Q) → (Q → R))
16. Q16 · NAT · 1 mark · TreesConsider a complete binary tree with 7 nodes. Let A denote the set of first 3 elements obtained by performing Breadth-First Search (BFS) starting from the root. Let B de…
17. Q17 · NAT · 1 mark · Regular Expressions and Finite AutomataConsider the following deterministic finite automaton (DFA). The number of strings of length 8 accepted by the above automaton is …
18. Q18 · NAT · 1 mark · Number Representation and ArithmeticIf x and y are two decimal digits and (0.1101)2 = (0.8xy5)10, the decimal value of x + y is …
19. Q19 · NAT · 1 mark · Cache Memory and HierarchyConsider a set-associative cache of size 2KB (1KB = 210 bytes) with cache block size of 64 bytes. Assume that the cache is byte-addressable and a 32-bit address is used…
20. Q20 · NAT · 1 mark · I/O Interface, Interrupts and DMAConsider a computer system with DMA support. The DMA module is transferring one 8-bit character in one CPU cycle from a device to memory through cycle stealing at regula…
21. Q21 · NAT · 1 mark · File Organization and IndexingA data file consisting of 1,50,000 student-records is stored on a hard disk with block size of 4096 bytes. The data file is sorted on the primary key RollNo. The size of…
22. Q22 · NAT · 1 mark · Probability and StatisticsFor a given biased coin, the probability that the outcome of a toss is a head is 0.4. This coin is tossed 1,000 times. Let X denote the random variable whose value is th…
23. Q23 · NAT · 1 mark · Programming in CConsider the following ANSI C function: int SomeFunction(int x, int y) { if ((x == 1) || (y == 1)) return 1; if (x == y) return x; if (x > y) return SomeFunction(x - y,…
24. Q24 · NAT · 1 mark · Linear AlgebraSuppose that P is a 4 × 5 matrix such that every solution of the equation Px = 0 is a scalar multiple of [2 5 4 3 1]T. The rank of P is …
25. Q25 · NAT · 1 mark · CalculusSuppose that f R → R is a continuous function on the interval [-3, 3] and a differentiable function in the interval (-3, 3) such that for every x in the interval, f'(x)…
26. Q26 · MCQ · 2 marks · Greedy AlgorithmsConsider the string abbccddeee . Each letter in the string must be assigned a binary code satisfying the following properties: 1. For any two letters, the code assigned…
27. Q27 · MCQ · 2 marks · Cache Memory and HierarchyAssume a two-level inclusive cache hierarchy, L1 and L2, where L2 is the larger of the two. Consider the following statements. S1 : Read misses in a write through L1 cac…
28. Q28 · MCQ · 2 marks · Combinational and Sequential CircuitsSuppose we want to design a synchronous circuit that processes a string of 0's and 1's. Given a string, it produces another string by replacing the first 1 in any subseq…
29. Q29 · MCQ · 2 marks · Probability and StatisticsIn an examination, a student can choose the order in which two questions (QuesA and QuesB) must be attempted. - If the first question is answered wrong, the student gets…
30. Q30 · MCQ · 2 marks · Local OptimisationConsider the following ANSI C code segment: z = x + 3 + y->f1 + y->f2; for (i = 0; i i) { p = p + x + 3; q = q + y->f1; } else { p = p + y->f2; q = q + x + 3; } } Assume…
31. Q31 · MCQ · 2 marks · SQLThe relation scheme given below is used to store information about the employees of a company, where empId is the key and deptId indicates the department to which the em…
32. Q32 · MCQ · 2 marks · Transactions and Concurrency ControlLet S be the following schedule of operations of three transactions T1, T2 and T3 in a relational database system: R2(Y), R1(X), R3(Z), R1(Y), W1(X), R2(Z), W2(Y), R3(X)…
33. Q33 · MCQ · 2 marks · Probability and StatisticsA bag has r red balls and b black balls. All balls are identical except for their colours. In a trial, a ball is randomly drawn from the bag, its colour is noted and the…
34. Q34 · MCQ · 2 marks · Data Link LayerConsider the cyclic redundancy check (CRC) based error detecting scheme having the generator polynomial X3 + X + 1. Suppose the message m4 m3 m2 m1 m0 = 11000 is to be t…
35. Q35 · MCQ · 2 marks · Programming in CConsider the following ANSI C program: #include #include struct Node{ int value; struct Node *next;}; int main(){ struct Node *boxE, *head, *boxN; int index = 0; boxE =…
36. Q36 · MCQ · 2 marks · Turing Machines and UndecidabilityConsider the following two statements about regular languages: S1: Every infinite regular language contains an undecidable language as a subset. S2: Every finite languag…
37. Q37 · MCQ · 2 marks · Linear AlgebraFor two n-dimensional real vectors P and Q, the operation s(P, Q) is defined as follows: s(P, Q) = Σi=1n (P[i] · Q[i]) Let L be a set of 10-dimensional non-zero real vec…
38. Q38 · MCQ · 2 marks · Data Flow AnalysesFor a statement S in a program, in the context of liveness analysis, the following sets are defined: USE(S) : the set of variables used in S IN(S) : the set of variables…
39. Q39 · MCQ · 2 marks · Asymptotic AnalysisFor constants a ≥ 1 and b > 1, consider the following recurrence defined on the non-negative integers: T(n) = a · T ((n)/(b) ) + f(n) Which one of the following options…
40. Q40 · MSQ · 2 marks · Integrity Constraints and Normal FormsSuppose the following functional dependencies hold on a relation U with attributes P, Q, R, S, and T: P &→ QR RS &→ T Which of the following functional dependencies can…
41. Q41 · MSQ · 2 marks · Regular and Context-Free LanguagesFor a string w, we define wR to be the reverse of w. For example, if w = 01101 then wR = 10110. Which of the following languages is/are context-free?
42. Q42 · MSQ · 2 marks · Concurrency and SynchronizationConsider the following multi-threaded code segment (in a mix of C and pseudo-code), invoked by two processes P1 and P2, and each of the processes spawns two threads T1 a…
43. Q43 · MSQ · 2 marks · DeadlockConsider a computer system with multiple shared resource types, with one instance per resource type. Each instance can be owned by only one process at a time. Owning and…
44. Q44 · MSQ · 2 marks · Instruction Set and Addressing ModesIf the numerical value of a 2-byte unsigned integer on a little endian computer is 255 more than that on a big endian computer, which of the following choices represent(…
45. Q45 · MSQ · 2 marks · Distance Vector and Link-State RoutingConsider a computer network using the distance vector routing algorithm in its network layer. The partial topology of the network is as shown below. The objective is to…
46. Q46 · MSQ · 2 marks · Graph TraversalsConsider the following directed graph: Which of the following is/are correct about the graph?
47. Q47 · MSQ · 2 marks · Regular Expressions and Finite AutomataWhich of the following regular expressions represent(s) the set of all binary numbers that are divisible by three? Assume that the string is divisible by three.
48. Q48 · NAT · 2 marks · Memory Management and Virtual MemoryConsider a three-level page table to translate a 39-bit virtual address to a physical address as shown below. The page size is 4KB (1KB = 210 bytes) and page table entry…
49. Q49 · NAT · 2 marks · RecursionConsider the following ANSI C program. #include int foo(int x, int y, int q) { if ((x The output of the program upon execution is …
50. Q50 · NAT · 2 marks · Discrete MathematicsLet S be a set consisting of 10 elements. The number of tuples of the form (A, B) such that A and B are subsets of S, and A ⊆ B is …
51. Q51 · NAT · 2 marks · ParsingConsider the following augmented grammar with {\#, @, , , a, b, c} as the set of terminals. S' → S S → S\#cS S → SS S → S@ S → S S → a S → b S → c Let I0 = CLOSURE({S' →…
52. Q52 · NAT · 2 marks · Boolean Algebra and MinimizationConsider a Boolean function f(w, x, y, z) such that f(w, 0, 0, z) = 1 f(1, x, 1, z) = x + z f(w, 1, y, z) = wz + y The number of literals in the minimal sum-of-products…
53. Q53 · NAT · 2 marks · Instruction PipeliningConsider a pipelined processor with 5 stages, Instruction Fetch (IF), Instruction Decode (ID), Execute (EX), Memory Access (MEM), and Write Back (WB). Each stage of the…
54. Q54 · NAT · 2 marks · Data Link LayerConsider a network using the pure ALOHA medium access control protocol, where each frame is of length 1,000 bits. The channel transmission rate is 1 Mbps (= 106 bits per…
55. Q55 · NAT · 2 marks · Graph TheoryIn a directed acyclic graph with a source vertex s, the *quality-score* of a directed path is defined to be the product of the weights of the edges on the path. Further,…

How many questions were in GATE CSE 2021 Set 2?

GATE CSE 2021 Set 2 had 55 questions for 85 marks: 24 MCQ, 13 MSQ and 18 NAT.

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

Engineering Mathematics carried the most marks (15 of 85). The top three were Engineering Mathematics (15), Theory of Computation (9), Algorithms (8).

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

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

Is the GATE CSE 2021 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 2021 Set 1 question paper
• GATE CSE 2020 question paper
• GATE CSE 2022 question paper
• All GATE CSE papers →
• GATE CSE Engineering Mathematics PYQs
• GATE CSE Theory of Computation PYQs
• GATE CSE Algorithms PYQs