GATE CS 2021 (Forenoon)
65 questions · 100 marks · 180 minutes
GENERAL APTITUDE (GA)
- Q1The ratio of boys to girls in a class is 7 to 3. Among the options below, an acceptable value for the total number of students in the class is:Quantitative Aptitude · Numerical Computation (Percentages, Ratios) · MCQ · 1 mark
- Q2A polygon is convex if, for every pair of points P and Q belonging to the polygon, the line segment PQ lies completely inside or on the polygon. Which one of the following is NOT…Quantitative Aptitude · Mensuration and Geometry · MCQ · 1 mark
- Q3Consider the following sentences: (i) Everybody in the class is prepared for the exam. (ii) Babu invited Danish to his home because he enjoys playing chess. Which of the following…Verbal Aptitude · Grammar Rules (Prepositions, Conjunctions, Verb-Noun Agreement, Other Parts of Speech) · MCQ · 1 mark
- Q4A circular sheet of paper is folded along the lines in the directions shown. The paper, after being punched in the final folded state as shown and unfolded in the reverse order of…Spatial Aptitude · Paper Folding and Cutting Diagnostics · MCQ · 1 mark
- Q5is to surgery as writer is to Which one of the following options maintains a similar logical relation in the above sentence?Analytical Aptitude · Analogy and Relationship Matching · MCQ · 1 mark
- Q6We have 2 rectangular sheets of paper, M and N, of dimensions 6 cm × 1 cm each. Sheet M is rolled to form an open cylinder by bringing the short edges of the sheet together. Sheet…Quantitative Aptitude · Mensuration and Geometry · MCQ · 2 marks
- Q7Details of prices of two items P and Q are presented in the above table. The ratio of cost of item P to cost of item Q is 3 : 4. Discount is calculated as the difference between t…Quantitative Aptitude · Numerical Computation (Percentages, Ratios) · MCQ · 2 marks
- Q8There are five bags each containing identical sets of ten distinct chocolates. One chocolate is picked from each bag. The probability that at least two chocolates are identical is…Quantitative Aptitude · Elementary Statistics and Probability · MCQ · 2 marks
- Q9Given below are two statements 1 and 2, and two conclusions I and II. Statement 1: All bacteria are microorganisms. Statement 2: All pathogens are microorganisms. Conclusion I: So…Analytical Aptitude · Logic Deduction and Induction Frameworks · MCQ · 2 marks
- Q10Some people suggest anti-obesity measures (AOM) such as displaying calorie information in restaurant menus. Such measures sidestep addressing the core problems that cause obesity:…Verbal Aptitude · Reading Comprehension · MCQ · 2 marks
CORE CS
- Q11Suppose that L 1 is a regular language and L 2 is a context-free language. Which one of the following languages is NOT necessarily context-free?Theory of Computation (TOC) · Regular and Context-Free Languages & Pumping Lemma · MCQ · 1 mark
- Q12Let 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 values in an…Algorithms · Searching, Sorting, Hashing Mechanisms · MCQ · 1 mark
- Q13Consider the following three functions: f 1 = 10 n, f 2 = n n , f 3 = n n Which one of the following options arranges the functions in the increasing order of asymptotic growth ra…Algorithms · Asymptotic Analysis (O, Omega, Theta Complexities) · MCQ · 1 mark
- Q14Consider the following statements: S 1 : The sequence of procedure calls corresponds to a preorder traversal of the activation tree. S 2 : The sequence of procedure returns corres…Programming in C · Functions, Parameter Passing, Scope Rules, Recursion · MCQ · 1 mark
- Q15Consider the following statements: S 1 : Every SLR(1) grammar is unambiguous but there are certain unambiguous grammars that are not SLR(1). S 2 : For any context-free grammar, th…Compiler Design · Lexical Analysis & Parsing Architectures (LL(1), LR(1), LALR) · MCQ · 1 mark
- Q16Let the representation of a number in base 3 be 210. What is the hexadecimal representation of the number?Digital Logic · Number Representations & Fixed/Floating Point Math · MCQ · 1 mark
- Q18Consider the following two statements: S 1 : Destination MAC address of an ARP reply is a broadcast address. S 2 : Destination MAC address of an ARP request is a broadcast address…Computer Networks (CN) · Fragmentation and IP Addressing (IPv4, IPv6, CIDR, Basics of IP support Protocols (ARP, DHCP, ICMP), NAT) · MCQ · 1 mark
- Q19Consider 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 ascending ord…Algorithms · Searching, Sorting, Hashing Mechanisms · MCQ · 1 mark
- Q20A 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?Data Structures · Binary Search Trees (BSTs) & Binary Heaps · MCQ · 1 mark
- Q21In the context of operating systems, which of the following statements is/are correct with respect to paging?Operating Systems (OS) · Memory Management and Virtual Memory · MSQ · 1 mark
- Q22Let M denote an encoding of an automaton M. Suppose that = \ 0, 1\ . Which of the following languages is/are NOT recursive?Theory of Computation (TOC) · Turing Machines & Undecidability · MSQ · 1 mark
- Q23Suppose 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 recovery.…Database Management Systems (DBMS) · Transactions, Concurrency Control, Conflict Serializability · MSQ · 1 mark
- Q24Which 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?Operating Systems (OS) · System Calls, Processes, Threads, InterProcess Communication · MSQ · 1 mark
- Q25Consider 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 metadata, suc…Operating Systems (OS) · File Systems Operations & Disk Scheduling Optimization · MSQ · 1 mark
- Q27Consider the following undirected graph with edge weights as shown: The number of minimum-weight spanning trees of the graph is .Algorithms · Minimum Spanning Trees (Prim/Kruskal Algorithms) · NAT · 1 mark
- Q31Consider 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 on…Data Structures · Abstract Data Types (ADTs), Stacks, Queues · NAT · 1 mark
- Q32Consider a computer system with a byte-addressable primary memory of size 2 32 bytes. Assume the computer system has a direct-mapped cache of size 32 KB (1 KB = 2 10 bytes), and e…Computer Organization and Architecture (COA) · Memory Hierarchy (Direct/Associative Cache Mapping) · NAT · 1 mark
- Q33A 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 1 to 20.…Database Management Systems (DBMS) · Relational Models, Relational Algebra, Tuple Calculus · NAT · 1 mark
- Q34Consider 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 Here S, E a…Digital Logic · Number Representations & Fixed/Floating Point Math · NAT · 1 mark
- Q35Three 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 achievable…Operating Systems (OS) · CPU and I/O Scheduling · NAT · 1 mark
- Q36Consider the following grammar (that admits a series of declarations, followed by expressions) and the associated syntax directed translation (SDT) actions, given as pseudo-code:…Compiler Design · Syntax-Directed Translation & Runtime Environments · MCQ · 2 marks
- Q37The 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 relation…Database Management Systems (DBMS) · Relational Models, Relational Algebra, Tuple Calculus · MCQ · 2 marks
- Q38Consider 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?Digital Logic · Sequential Circuits (Flip-Flops, Registers, Counters) · MCQ · 2 marks
- Q39Assume that a 12-bit Hamming codeword consisting of 8-bit data and 4 check bits is d 8\ d 7\ d 6\ d 5\ c 8\ d 4\ d 3\ d 2\ c 4\ d 1\ c 2\ c 1, where the data bits and the check bi…Computer Networks (CN) · Data Link Layer (Framing, Error Detection, MAC, Ethernet Bridging) · MCQ · 2 marks
- Q40Consider the following recurrence relation: T(n) = cases T ( n 2 ) + T ( 2n 5 ) + 7n & if n > 0 \\ 1 & if n = 0 cases Which one of the following options is correct?Algorithms · Asymptotic Analysis (O, Omega, Theta Complexities) · MCQ · 2 marks
- Q41Consider the following context-free grammar where the set of terminals is \ a, b, c, d, f\ S daT Rf T aS baT R caTR The following is a partially-filled LL(1) parsing table. Which…Compiler Design · Lexical Analysis & Parsing Architectures (LL(1), LR(1), LALR) · MCQ · 2 marks
- Q42Let r i(z) and w i(z) denote read and write operations respectively on a data item z by a transaction T i. Consider the following two schedules: S 1 : r 1(x), r 1(y), r 2(x), r 2(…Database Management Systems (DBMS) · Transactions, Concurrency Control, Conflict Serializability · MCQ · 2 marks
- Q43Consider 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 into the constituent…Database Management Systems (DBMS) · Normalization Schemes (1NF, 2NF, 3NF, BCNF Boundaries) · MCQ · 2 marks
- Q47Consider the following ANSI C program: c include <stdio.h> int main( ) int i, j, count; count = 0; i = 0; for (j = -3; j <= 3; j++) if ((j >= 0) && (i++)) count = count + j; count…Programming in C · Data Types, Syntax, Control Structures, Loops · MCQ · 2 marks
- Q48Consider the following language: L = \ w \ 0,1\ w ends with the substring 011 \ Which one of the following deterministic finite automata accepts L?Theory of Computation (TOC) · Regular Expressions & Finite Automata (DFA/NFA Min) · MCQ · 2 marks
- Q49For a Turing machine M, M denotes an encoding of M. Consider the following two languages: L 1 = \ M M takes more than 2021 steps on all inputs \ L 2 = \ M M takes more than 2021 s…Theory of Computation (TOC) · Turing Machines & Undecidability · MCQ · 2 marks
- Q50Define R n 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 selling p…Algorithms · Dynamic Programming Infrastructure · MSQ · 2 marks
- Q51An 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. Let T be a…Algorithms · Graph Traversals (BFS, DFS) & Single-Source Shortest Paths · MSQ · 2 marks
- Q52Consider the following Boolean expression: F = (X + Y + Z)( X + Y)( Y + Z) Which of the following Boolean expressions is/are equivalent to F ?Digital Logic · Boolean Algebra, Minimization, K-Maps · MSQ · 2 marks
- Q54A 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 connection w…Computer Networks (CN) · Transport Layer (Flow Control and Congestion Control, TCP, UDP, Sockets) · MSQ · 2 marks
- Q55Consider 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 bytes. A TCP s…Computer Networks (CN) · Fragmentation and IP Addressing (IPv4, IPv6, CIDR, Basics of IP support Protocols (ARP, DHCP, ICMP), NAT) · MSQ · 2 marks
- Q56Consider 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 increment operati…Operating Systems (OS) · Concurrency & Synchronization (Semaphores, Mutex, Monitors, Locks) · MSQ · 2 marks
- Q57Consider 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 main hash t…Algorithms · Searching, Sorting, Hashing Mechanisms · MSQ · 2 marks
- Q58Consider the following ANSI C function: c int SimpleFunction (int Y[ ], int n, int x) int total = Y[0], loopIndex; for (loopIndex = 1; loopIndex <= n - 1; loopIndex++) total = x t…Programming in C · Functions, Parameter Passing, Scope Rules, Recursion · NAT · 2 marks
- Q59Consider 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 for processi…Computer Networks (CN) · Data Link Layer (Framing, Error Detection, MAC, Ethernet Bridging) · NAT · 2 marks
- Q60Consider the following C code segment: c 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 acyclic gr…Compiler Design · Intermediate Code Generation & Local Code Optimization · NAT · 2 marks
- Q61In a pushdown automaton P = (Q, , , , q 0, F), a transition of the form, where p, q Q, a \ \ , and X, Y \ \ , represents (q, Y) (p, a, X) Consider the following pushdown automaton…Theory of Computation (TOC) · Context-Free Grammars & Push-Down Automata · NAT · 2 marks
- Q63A 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 each. The t…Computer Organization and Architecture (COA) · Instruction Pipelining, Performance, Hazard Management · NAT · 2 marks
- Q65Consider 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 content o…Computer Organization and Architecture (COA) · Machine Instructions & Addressing Modes · NAT · 2 marks
MATHEMATICAL FOUNDATIONS
- Q17Let p and q be two propositions. Consider the following two formulae in propositional logic. S 1 : ( p (p q)) p S 2 : q ( p (p q)) Which one of the following choices is correct?Discrete Mathematics · Propositional and First-Order Quantifier Logic · MCQ · 1 mark
- Q26In an undirected connected planar graph G, there are eight vertices and five faces. The number of edges in G is .Discrete Mathematics · Graph Theory (Connectivity, Paths, Cycles, Trees) · NAT · 1 mark
- Q28The 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 picked componen…Probability & Statistics · Continuous/Discrete Distributions (Uniform, Normal, Exponential) · NAT · 1 mark
- Q29There 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 gets the to…Discrete Mathematics · Combinatorics (Counting Rules, Summation Formulas) · NAT · 1 mark
- Q30Consider the following expression: x -3 2x + 22 - 4 x + 3 The value of the above expression (rounded to 2 decimal places) is .Calculus · Limits, Continuity, and Differentiability · NAT · 1 mark
- Q44Let 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?Discrete Mathematics · Algebraic Structures (Monoids, Groups) · MCQ · 2 marks
- Q45Consider the two statements: S 1 : There exist random variables X and Y such that (E[(X - E(X))(Y - E(Y))]) 2 > Var [X]\, Var [Y] S 2 : For all random variables X and Y Cov [X, Y]…Probability & Statistics · Random Variables & Sampling Rules · MCQ · 2 marks
- Q46Let G = (V, E) be an undirected unweighted connected graph. The diameter of G is defined as diam (G) = u,v V \ the length of shortest path between u and v\ Let M be the adjacency…Discrete Mathematics · Graph Theory (Connectivity, Paths, Cycles, Trees) · MCQ · 2 marks
- Q53A relation R is said to be circular if aRb and bRc together imply cRa. Which of the following options is/are correct?Discrete Mathematics · Sets, Relations, Functions, Partial Orders, Lattices · MSQ · 2 marks
- Q62Consider the following matrix: pmatrix 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 pmatrix The largest eigenvalue of the above matrix is .Linear Algebra · Eigenvalues and Eigenvectors · NAT · 2 marks
- Q64A 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 weight of edge…Probability & Statistics · Conditional Probability & Bayes Theorem · NAT · 2 marks

