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

Engineering Mathematics and Algorithms together made up 29 of 85 marks, up 7 from GATE CSE 2020. 18 of 55 questions were NAT, the most since 2020. Discrete Mathematics was the heaviest single topic with 6 marks across 3 questions. Computer Networks moved the most against GATE CSE 2020: up 5 marks.

1. Q1 · MCQ · 1 mark · Context-Free Grammars and PDAsSuppose that L1 is a regular language and L2 is a context-free language. Which one of the following languages is NOT necessarily context-free?
2. Q2 · MCQ · 1 mark · Searching, Sorting and HashingLet P be an array containing n integers. Let t be the lowest upper bound on the number of comparisons of the array elements, required to find the minimum and maximum val…
3. Q3 · MCQ · 1 mark · Asymptotic AnalysisConsider the following three functions. f1 = 10n f2 = nlog n f3 = n√(n) Which one of the following options arranges the functions in the increasing order of asymptotic g…
4. Q4 · MCQ · 1 mark · Runtime EnvironmentsConsider the following statements. S1: The sequence of procedure calls corresponds to a preorder traversal of the activation tree. S2: The sequence of procedure returns…
5. Q5 · MCQ · 1 mark · ParsingConsider the following statements. S1 : Every SLR(1) grammar is unambiguous but there are certain unambiguous grammars that are not SLR(1). S2 : For any context-free gra…
6. Q6 · MCQ · 1 mark · Number Representation and ArithmeticLet the representation of a number in base 3 be 210. What is the hexadecimal representation of the number?
7. Q7 · MCQ · 1 mark · Propositional and First-Order LogicLet p and q be two propositions. Consider the following two formulae in propositional logic. S1 : ( eg p ∧ (p ∨ q)) → q S2 : q → ( eg p ∧ (p ∨ q)) Which one of the follo…
8. Q8 · MCQ · 1 mark · Data Link LayerConsider the following two statements. S1 : Destination MAC address of an ARP reply is a broadcast address. S2 : Destination MAC address of an ARP request is a broadcast…
9. Q9 · MCQ · 1 mark · SortingConsider the following array. Which algorithm out of the following options uses the least number of comparisons (among the array elements) to sort the above array in asc…
10. Q10 · MCQ · 1 mark · Binary Search TreesA binary search tree T contains n distinct elements. What is the time complexity of picking an element in T that is smaller than the maximum element in T?
11. Q11 · MSQ · 1 mark · Memory Management and Virtual MemoryIn the context of operating systems, which of the following statements is/are correct with respect to paging?
12. Q12 · MSQ · 1 mark · Turing Machines and UndecidabilityLet M denote an encoding of an automaton M. Suppose that = {0, 1}. Which of the following languages is/are NOT recursive?
13. Q13 · MSQ · 1 mark · Transactions and Concurrency ControlSuppose a database system crashes again while recovering from a previous crash. Assume checkpointing is not done by the database either during the transactions or during…
14. Q14 · MSQ · 1 mark · System CallsWhich of the following standard C library functions will always invoke a system call when executed from a single-threaded process in a UNIX/Linux operating system?
15. Q15 · MSQ · 1 mark · File SystemsConsider a linear list based directory implementation in a file system. Each directory is a list of nodes, where each node contains the file name along with the file met…
16. Q16 · NAT · 1 mark · Graph TheoryIn an undirected connected planar graph G, there are eight vertices and five faces. The number of edges in G is …
17. Q17 · NAT · 1 mark · Minimum Spanning TreesConsider the following undirected graph with edge weights as shown: The number of minimum-weight spanning trees of the graph is …
18. Q18 · NAT · 1 mark · Probability and StatisticsThe lifetime of a component of a certain type is a random variable whose probability density function is exponentially distributed with parameter 2. For a randomly picke…
19. Q19 · NAT · 1 mark · CombinatoricsThere are 6 jobs with distinct difficulty levels, and 3 computers with distinct processing speeds. Each job is assigned to a computer such that: - The fastest computer g…
20. Q20 · NAT · 1 mark · CalculusConsider the following expression. limx → -3 √(2x+22)-4x+3 The value of the above expression (rounded to 2 decimal places) is …
21. Q21 · NAT · 1 mark · Programming and Data StructuresConsider the following sequence of operations on an empty stack. push(54); push(52); pop(); push(55); push(62); s = pop(); Consider the following sequence of operations…
22. Q22 · NAT · 1 mark · Cache Memory and HierarchyConsider a computer system with a byte-addressable primary memory of size 232 bytes. Assume the computer system has a direct-mapped cache of size 32 KB (1 KB = 210 bytes…
23. Q23 · NAT · 1 mark · Relational Model and SQLA relation r(A, B) in a relational database has 1200 tuples. The attribute A has integer values ranging from 6 to 20, and the attribute B has integer values ranging from…
24. Q24 · NAT · 1 mark · Number Representation and ArithmeticConsider the following representation of a number in IEEE 754 single-precision floating point format with a bias of 127. S : 1 E : 10000001 F : 11110000000000000000000 H…
25. Q25 · NAT · 1 mark · CPU and I/O SchedulingThree processes arrive at time zero with CPU bursts of 16, 20 and 10 milliseconds. If the scheduler has prior knowledge about the length of the CPU bursts, the minimum a…
26. Q26 · MCQ · 2 marks · Syntax-Directed TranslationConsider the following grammar (that admits a series of declarations, followed by expressions) and the associated syntax directed translation (SDT) actions, given as pse…
27. Q27 · MCQ · 2 marks · Relational AlgebraThe following relation records the age of 500 employees of a company, where empNo (indicating the employee number) is the key: empAge( empNo, age) Consider the following…
28. Q28 · MCQ · 2 marks · Combinational and Sequential CircuitsConsider a 3-bit counter, designed using T flip-flops, as shown below: Assuming the initial state of the counter given by PQR as 000, what are the next three states?
29. Q29 · MCQ · 2 marks · Data Link LayerAssume that a 12-bit Hamming codeword consisting of 8-bit data and 4 check bits is d8d7d6d5c8d4d3d2c4d1c2c1, where the data bits and the check bits are given in the foll…
30. Q30 · MCQ · 2 marks · Asymptotic AnalysisConsider the following recurrence relation. T(n) = T(n/2) + T(2n/5) + 7n & if n > 0 1 & if n = 0 Which one of the following options is correct?
31. Q31 · MCQ · 2 marks · Lexical Analysis, Parsing and SDTConsider the following context-free grammar where the set of terminals is {a, b, c, d, f}. S &→ d a T R f T &→ a S b a T R &→ c a T R The following is a partially-filled…
32. Q32 · MCQ · 2 marks · Transactions and Concurrency ControlLet ri(z) and wi(z) denote read and write operations respectively on a data item z by a transaction Ti. Consider the following two schedules. S1 : r1(x) r1(y) r2(x) r2(y…
33. Q33 · MCQ · 2 marks · Integrity Constraints and Normal FormsConsider the relation R(P, Q, S, T, X, Y, Z, W) with the following functional dependencies. PQ → X; P → YX; Q → Y; Y → ZW Consider the decomposition of the relation R in…
34. Q34 · MCQ · 2 marks · Discrete MathematicsLet G be a group of order 6, and H be a subgroup of G such that 1 < |H| < 6. Which one of the following options is correct?
35. Q35 · MCQ · 2 marks · Probability and StatisticsConsider the two statements. S1 :& There exist random variables X and Y such that & ( E [(X - E(X)) (Y - E(Y)) ] )2 > Var[X] Var[Y] S2 :& For all random variables X and…
36. Q36 · MCQ · 2 marks · Discrete MathematicsLet G = (V, E) be an undirected unweighted connected graph. The diameter of G is defined as: diam(G) = maxu,v ∈ V {the length of shortest path between u and v} Let M be…
37. Q37 · MCQ · 2 marks · Programming in CConsider the following ANSI C program. #include int main() { int i, j, count; count = 0; i = 0; for (j = -3; j = 0) && (i++)) count = count + j; } count = count + i; pri…
38. Q38 · MCQ · 2 marks · Regular Expressions and Finite AutomataConsider the following language. L = {w ∈ {0, 1}* w ends with the substring 011} Which one of the following deterministic finite automata accepts L?
39. Q39 · MCQ · 2 marks · Turing Machines and UndecidabilityFor a Turing machine M, M denotes an encoding of M. Consider the following two languages. L1 = { M M takes more than 2021 steps on all inputs} L2 = { M M takes more than…
40. Q40 · MSQ · 2 marks · Dynamic ProgrammingDefine Rn to be the maximum amount earned by cutting a rod of length n meters into one or more pieces of integer length and selling them. For i > 0, let p[i] denote the…
41. Q41 · MSQ · 2 marks · Graph TraversalsAn articulation point in a connected graph is a vertex such that removing the vertex and its incident edges disconnects the graph into two or more connected components.…
42. Q42 · MSQ · 2 marks · Boolean Algebra and MinimizationConsider the following Boolean expression. F = (X + Y + Z)( X + Y)( Y + Z) Which of the following Boolean expressions is/are equivalent to F (complement of F)?
43. Q43 · MSQ · 2 marks · Discrete MathematicsA relation R is said to be circular if aRb and bRc together imply cRa. Which of the following options is/are correct?
44. Q44 · MSQ · 2 marks · TCP Flow and Congestion ControlA TCP server application is programmed to listen on port number P on host S. A TCP client is connected to the TCP server over the network. Consider that while the TCP co…
45. Q45 · MSQ · 2 marks · IPv4 FragmentationConsider two hosts P and Q connected through a router R. The maximum transfer unit (MTU) value of the link between P and R is 1500 bytes, and between R and Q is 820 byte…
46. Q46 · MSQ · 2 marks · Concurrency and SynchronizationConsider the following pseudocode, where S is a semaphore initialized to 5 in line#2 and counter is a shared variable initialized to 0 in line#1. Assume that the increme…
47. Q47 · MSQ · 2 marks · Searching, Sorting and HashingConsider a *dynamic* hashing approach for 4-bit integer keys: 1. There is a main hash table of size 4. 2. The 2 least significant bits of a key is used to index into the…
48. Q48 · NAT · 2 marks · Programming in CConsider the following ANSI C function: int SimpleFunction(int Y[], int n, int x) { int total = Y[0], loopIndex; for (loopIndex = 1; loopIndex Let Z be an array of 10 el…
49. Q49 · NAT · 2 marks · Data Link LayerConsider the sliding window flow-control protocol operating between a sender and a receiver over a full-duplex error-free link. Assume the following: • The time taken fo…
50. Q50 · NAT · 2 marks · Data Flow AnalysesConsider the following C code segment: a = b + c; e = a + 1; d = b + c; f = d + 1; g = e + f; In a compiler, this code segment is represented internally as a directed ac…
51. Q51 · NAT · 2 marks · Context-Free Grammars and PDAsIn a pushdown automaton P = (Q, , , , q0, F), a transition of the form, where p, q ∈ Q, a ∈ ∪ { }, and X, Y ∈ ∪ { }, represents (q, Y) ∈ (p, a, X). Consider the followin…
52. Q52 · NAT · 2 marks · Linear AlgebraConsider the following matrix. 0 & 1 & 1 & 1 1 & 0 & 1 & 1 1 & 1 & 0 & 1 1 & 1 & 1 & 0 The largest eigenvalue of the above matrix is …
53. Q53 · NAT · 2 marks · Instruction PipeliningA five-stage pipeline has stage delays of 150, 120, 150, 160 and 140 nanoseconds. The registers that are used between the pipeline stages have a delay of 5 nanoseconds e…
54. Q54 · NAT · 2 marks · Probability and StatisticsA sender (S) transmits a signal, which can be one of the two kinds: H and L with probabilities 0.1 and 0.9 respectively, to a receiver (R). In the graph below, the weigh…
55. Q55 · NAT · 2 marks · Instruction Set and Addressing ModesConsider the following instruction sequence where registers R1, R2 and R3 are general purpose and MEMORY[X] denotes the content at the memory location X. Assume that the…

How many questions were in GATE CSE 2021 Set 1?

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

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

Engineering Mathematics carried the most marks (17 of 85). The top three were Engineering Mathematics (17), Algorithms (12), Computer Networks (9).

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

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

Is the GATE CSE 2021 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 2021 Set 2 question paper
• GATE CSE 2020 question paper
• GATE CSE 2022 question paper
• All GATE CSE papers →
• GATE CSE Engineering Mathematics PYQs
• GATE CSE Algorithms PYQs
• GATE CSE Computer Networks PYQs