GATE CS 2021 (Forenoon)

65 questions · 100 marks · 180 minutes

Take this paper as a timed test
From RENYXERAWhat rank do your marks get?GATE score, likely All-India Rank and qualifying marks for your category.

GENERAL APTITUDE (GA)

  1. 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
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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
  7. 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
  8. 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
  9. 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
  10. 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

  1. 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
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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
  7. 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
  8. 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
  9. 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
  10. 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
  11. 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
  12. 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
  13. 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
  14. 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
  15. 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
  16. 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
  17. 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
  18. 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
  19. 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
  20. 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
  21. 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
  22. 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
  23. 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
  24. 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
  25. 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
  26. 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
  27. 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
  28. 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
  29. 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
  30. 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
  31. 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
  32. 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
  33. 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
  34. 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
  35. 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
  36. 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
  37. 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
  38. 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
  39. 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
  40. 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
  41. 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
  42. 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
  43. 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
  44. 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

  1. 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
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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
  7. 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
  8. 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
  9. 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
  10. 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
  11. 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