GATE CS 2021 (Afternoon)
65 questions · 100 marks · 180 minutes
GENERAL APTITUDE (GA)
- Q1Gauri said that she can play keyboard her sister.Verbal Aptitude · Grammar Rules (Prepositions, Conjunctions, Verb-Noun Agreement, Other Parts of Speech) · MCQ · 1 mark
- Q2A transparent square sheet shown above is folded along the dotted line. The folded sheet will look like .Spatial Aptitude · Paper Folding and Cutting Diagnostics · MCQ · 1 mark
- Q3If is the angle, in degrees, between the longest diagonal of the cube and any one of the edges of the cube, then = .Quantitative Aptitude · Mensuration and Geometry · MCQ · 1 mark
- Q4If (x - 1 2 ) 2 - (x - 3 2 ) 2 = x + 2 , then the value of x is :Analytical Aptitude · Numerical Relations & Arithmetic Logic · MCQ · 1 mark
- Q5Pen : Write : : Knife : Which one of the following options maintains a similar logical relation in the above?Analytical Aptitude · Analogy and Relationship Matching · MCQ · 1 mark
- Q6Listening to music during exercise improves exercise performance and reduces discomfort. Scientists researched whether listening to music while studying can help students learn be…Verbal Aptitude · Reading Comprehension · MCQ · 2 marks
- Q7What will be the remaining part to make it a rectangle?Spatial Aptitude · Structural Morphing (Mirroring, Assembling, Grouping) · MCQ · 2 marks
- Q8The number of student in three classes is in the ratio 3 : 13 : 6. If 18 students are added to each class, the ratio changes to 15 : 35 : 21. The total number of students in all t…Quantitative Aptitude · Numerical Computation (Percentages, Ratios) · MCQ · 2 marks
- Q9The number of units of a product sold in three different years and the respective net profits are presented in the figure above. The cost/unit in Year 3 was Rs. 1, which was half…Quantitative Aptitude · Data Interpretation (Bar Graphs, Pie Charts, Histograms) · MCQ · 2 marks
- Q10Six students P, Q, R, S, T and U, with distinct heights, compare their heights and make the following observations : Observation I : S is taller than R. Observation II : Q is the…Analytical Aptitude · Operational Puzzles and Systemic Reasoning · MCQ · 2 marks
CORE CS
- Q11Let G be a connected undirected weighted graph. Consider the following two statements. S 1 : There exists a minimum weight edge in G which is present in every minimum spanning tre…Algorithms · Minimum Spanning Trees (Prim/Kruskal Algorithms) · MCQ · 1 mark
- Q12Let 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 in H?Data Structures · Binary Search Trees (BSTs) & Binary Heaps · MCQ · 1 mark
- Q13Consider the following ANSI C program: c int main( ) Integer x; return 0; Which one of the following phases in a seven-phase C compiler will throw an error?Compiler Design · Lexical Analysis & Parsing Architectures (LL(1), LR(1), LALR) · MCQ · 1 mark
- Q14The 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 correct with re…Digital Logic · Number Representations & Fixed/Floating Point Math · MCQ · 1 mark
- Q15Which one of the following circuits implements the Boolean function given below? f(x, y, z) = m 0 + m 1 + m 3 + m 4 + m 5 + m 6, where m i is the i th minterm.Digital Logic · Combinational Logic (Multiplexers, Decoders, Adders) · MCQ · 1 mark
- Q16Consider the following statements S 1 and S 2 about the relational data model : S 1 : A relation scheme can have at most one foreign key. S 2 : A foreign key in a relation scheme…Database Management Systems (DBMS) · Integrity Constraints & Functional Dependencies · MCQ · 1 mark
- Q17Consider 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 chosen by…Computer Networks (CN) · Transport Layer (Flow Control and Congestion Control, TCP, UDP, Sockets) · MCQ · 1 mark
- Q18What is the worst-case number of arithmetic operations performed by recursive binary search on a sorted array of size n?Algorithms · Searching, Sorting, Hashing Mechanisms · MCQ · 1 mark
- Q19Let 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 DFA with k s…Theory of Computation (TOC) · Regular Expressions & Finite Automata (DFA/NFA Min) · MCQ · 1 mark
- Q20Consider the following ANSI C program: c include <stdio.h> int main( ) int arr[4] [5] ; int i, j; for (i = 0; i < 4; i++) for (j = 0; j < 5; j++) arr[i] [j] = 10 i + j; printf("%d…Programming in C · Pointers, Multi-Dimensional Arrays, Structures · MCQ · 1 mark
- Q22Let L 1 be a regular language and L 2 be a context-free language. Which of the following languages is/are context-free?Theory of Computation (TOC) · Regular and Context-Free Languages & Pumping Lemma · MSQ · 1 mark
- Q23In the context of compilers, which of the following is/are NOT an intermediate representation of the source program?Compiler Design · Intermediate Code Generation & Local Code Optimization · MSQ · 1 mark
- Q24Which of the following statement(s) is/are correct in the context of CPU scheduling?Operating Systems (OS) · CPU and I/O Scheduling · MSQ · 1 mark
- Q26Consider 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 denote the s…Algorithms · Graph Traversals (BFS, DFS) & Single-Source Shortest Paths · NAT · 1 mark
- Q27Consider the following deterministic finite automation (DFA). The number of strings of length 8 accepted by the above automation is .Theory of Computation (TOC) · Regular Expressions & Finite Automata (DFA/NFA Min) · NAT · 1 mark
- Q28If x and y are two decimal digits and (0.1101) 2 = (0.8xy5) 10 , the decimal value of x + y is .Digital Logic · Number Representations & Fixed/Floating Point Math · NAT · 1 mark
- Q29Consider a set-associative cache of size 2 KB (1 KB = 2 10 bytes) with cache block size of 64 bytes. Assume that the cache is byte-addressable and a 32-bit address is used for acc…Computer Organization and Architecture (COA) · Memory Hierarchy (Direct/Associative Cache Mapping) · NAT · 1 mark
- Q30Consider 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 regular interval…Computer Organization and Architecture (COA) · I/O Interfaces (Interrupts & DMA Control Modes) · NAT · 1 mark
- Q31A 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 a record…Database Management Systems (DBMS) · File Organization & Indexing (e.g., B and B+ Trees) · NAT · 1 mark
- Q33Consider the following ANSI C function: c 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, y); if (y > x…Programming in C · Functions, Parameter Passing, Scope Rules, Recursion · NAT · 1 mark
- Q36Consider the string abbccdddee. Each letter in the string must be assigned a binary code satisfying the following properties: 1. For any two letters, the code assigned to one lett…Algorithms · Greedy Approach & Divide-and-Conquer Designs · MCQ · 2 marks
- Q37Assume a two-level inclusive cache hierarchy, L1 and L2, where L2 is the larger of the two. Consider the following statements. S 1 : Read misses in a write through L1 cache do not…Computer Organization and Architecture (COA) · Memory Hierarchy (Direct/Associative Cache Mapping) · MCQ · 2 marks
- Q38Suppose 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 subsequence of c…Digital Logic · Sequential Circuits (Flip-Flops, Registers, Counters) · MCQ · 2 marks
- Q40Consider the following ANSI C code segment: c z = x + 3 + y -> f1 + y -> f2; for (i = 0; i < 200; i = i + 2) if (z > i) p = p + x + 3; q = q + y -> f1; else p = p + y -> f2; q = q…Compiler Design · Intermediate Code Generation & Local Code Optimization · MCQ · 2 marks
- Q41The 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 employee is…Database Management Systems (DBMS) · SQL Queries (DDL/DML, Joins, Aggregations) · MCQ · 2 marks
- Q42Let S be the following schedule of operations of three transactions T 1, T 2 and T 3 in a relational database system: R 2(Y), R 1(X), R 3(Z), R 1(Y), W 1(X), R 2(Z), W 2(Y), R 3(X…Database Management Systems (DBMS) · Transactions, Concurrency Control, Conflict Serializability · MCQ · 2 marks
- Q44Consider the cyclic redundancy check (CRC) based error detecting scheme having the generator polynomial X 3 + X + 1. Suppose the message m 4m 3m 2m 1m 0 = 11000 is to be transmitt…Computer Networks (CN) · Data Link Layer (Framing, Error Detection, MAC, Ethernet Bridging) · MCQ · 2 marks
- Q45Consider the following ANSI C program: c include <stdio.h> include <stdlib.h> struct Node int value; struct Node next; ; int main( ) struct Node boxE, head, boxN; int index = 0; b…Programming in C · Pointers, Multi-Dimensional Arrays, Structures · MCQ · 2 marks
- Q46Consider the following two statements about regular languages: S 1 : Every infinite regular language contains an undecidable language as a subset. S 2 : Every finite language is r…Theory of Computation (TOC) · Regular and Context-Free Languages & Pumping Lemma · MCQ · 2 marks
- Q48For 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 that are…Compiler Design · Data Flow Analysis: Constant Propagation, Liveliness Analysis, Common Subexpression Elimination · MCQ · 2 marks
- Q49For 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 is correct about…Algorithms · Asymptotic Analysis (O, Omega, Theta Complexities) · MCQ · 2 marks
- Q50Suppose 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 be inferred from…Database Management Systems (DBMS) · Integrity Constraints & Functional Dependencies · MSQ · 2 marks
- Q51For a string w, we define w R to be the reverse of w. For example, if w = 01101 then w R = 10110. Which of the following languages is/are context-free?Theory of Computation (TOC) · Regular and Context-Free Languages & Pumping Lemma · MSQ · 2 marks
- Q52Consider the following multi-threaded code segment (in a mix of C and pseudo-code), invoked by two processes P 1 and P 2, and each of the processes spawns two threads T 1 and T 2:…Operating Systems (OS) · Concurrency & Synchronization (Semaphores, Mutex, Monitors, Locks) · MSQ · 2 marks
- Q53Consider 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 freeing o…Operating Systems (OS) · Deadlock Prevention, Avoidance, Detection, Recovery · MSQ · 2 marks
- Q54If 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(s) the uns…Computer Organization and Architecture (COA) · Machine Instructions & Addressing Modes · MSQ · 2 marks
- Q55Consider 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 find the s…Computer Networks (CN) · Routing Protocols (Shortest Path, Flooding, Distance Vector, Link State Routing) · MSQ · 2 marks
- Q56Consider the following directed graph: Which of the following is/are correct about the graph?Algorithms · Graph Traversals (BFS, DFS) & Single-Source Shortest Paths · MSQ · 2 marks
- Q57Which 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.Theory of Computation (TOC) · Regular Expressions & Finite Automata (DFA/NFA Min) · MSQ · 2 marks
- Q58Consider a three-level page table to translate a 39-bit virtual address to a physical address as shown below: The page size is 4 KB (1 KB = 2 10 bytes) and page table entry size a…Operating Systems (OS) · Memory Management and Virtual Memory · NAT · 2 marks
- Q59Consider the following ANSI C program: c include <stdio.h> int foo(int x, int y, int q) if ((x <= 0) (y <= 0)) return q; if (x <= 0) return foo(x, y - q, q) if (y <= 0) return foo…Programming in C · Functions, Parameter Passing, Scope Rules, Recursion · NAT · 2 marks
- Q61Consider 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 I 0 = CLOSURE (\ S' S\ ). The number of i…Compiler Design · Lexical Analysis & Parsing Architectures (LL(1), LR(1), LALR) · NAT · 2 marks
- Q62Consider 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 expression…Digital Logic · Boolean Algebra, Minimization, K-Maps · NAT · 2 marks
- Q63Consider 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 pipeline,…Computer Organization and Architecture (COA) · Instruction Pipelining, Performance, Hazard Management · NAT · 2 marks
- Q64Consider 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 (= 10 6 bits per second).…Computer Networks (CN) · Data Link Layer (Framing, Error Detection, MAC, Ethernet Bridging) · NAT · 2 marks
- Q65In 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, for a verte…Algorithms · Graph Traversals (BFS, DFS) & Single-Source Shortest Paths · NAT · 2 marks
MATHEMATICAL FOUNDATIONS
- Q21Consider the following sets, where n 2: S 1 : Set of all n n matrices with entries from the set \ a, b, c\ S 2 : Set of all functions from the set \ 0, 1, 2, ....., n 2 - 1\ to th…Discrete Mathematics · Sets, Relations, Functions, Partial Orders, Lattices · MSQ · 1 mark
- Q25Choose the correct choice(s) regarding the following propositional logic assertion S: S : ((P Q) R) ((P Q) (Q R))Discrete Mathematics · Propositional and First-Order Quantifier Logic · MSQ · 1 mark
- Q32For 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 the number o…Probability & Statistics · Standard Distributions (Poisson, Binomial) · NAT · 1 mark
- Q34Suppose 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 .Linear Algebra · Matrices, Determinants, & Linear Equation Systems · NAT · 1 mark
- Q35Suppose 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) 2. If f(-3…Calculus · Mean Value Theorems & Definite Integration · NAT · 1 mark
- Q39In 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 zero mark…Probability & Statistics · Random Variables & Sampling Rules · MCQ · 2 marks
- Q43A 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 ball is p…Probability & Statistics · Conditional Probability & Bayes Theorem · MCQ · 2 marks
- Q47For two n-dimensional real vectors P and Q, the operation s(P, Q) is defined as follows: s(P, Q) = i=1 n (P[i] . Q[i]) Let L be a set of 10-dimensional non-zero real vectors such…Linear Algebra · Eigenvalues and Eigenvectors · MCQ · 2 marks
- Q60Let 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 .Discrete Mathematics · Combinatorics (Counting Rules, Summation Formulas) · NAT · 2 marks

