GATE CS 2021 Set 2 question paper: all 65 questions with answers and solutions

General Aptitude

10 questions, 15 marks

General AptitudeMCQ1 markEasy (estimate)
Q.1 (GA Q.1)
Gauri said that she can play the keyboard __________ her sister.
Verbal Ability and Grammar
General AptitudeMCQ1 markMedium (estimate)
Q.2 (GA Q.2)
A transparent square sheet with a vertical dashed centerline. An inverted V chevron spans the bottom half. The left diagonal has two short vertical segments below it, and the ri...
Spatial Aptitude
General AptitudeMCQ1 markEasy (estimate)
Q.3 (GA Q.3)
If $θ$ is the angle, in degrees, between the longest diagonal of the cube and any one of the edges of the cube, then, $cos θ =$
Quantitative Aptitude
General AptitudeMCQ1 markEasy (estimate)
Q.4 (GA Q.4)
If $(x - \frac{1}{2})^{2} - (x - \frac{3}{2})^{2} = x + 2$ , then the value of $x$ is:
Quantitative Aptitude
General AptitudeMCQ1 markEasy (estimate)
Q.5 (GA Q.5)
Pen : Write :: Knife : ______ Which one of the following options maintains a similar logical relation in the above?
Verbal Ability and Grammar
General AptitudeMCQ2 marksMedium (estimate)
Q.6 (GA Q.6)
Listening to music during exercise improves exercise performance and reduces discomfort. Scientists researched whether listening to music while studying can help students learn...
Reading Comprehension and Verbal Deduction
General AptitudeMCQ2 marksMedium (estimate)
Q.7 (GA Q.7)
A jigsaw puzzle piece with straight top and right boundary edges, and a stepped profile with tabs and indentations along its left and bottom boundaries. One of the two pieces of...
Spatial Aptitude
General AptitudeMCQ2 marksMedium (estimate)
Q.8 (GA Q.8)
The number of students 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 th...
Quantitative Aptitude
General AptitudeMCQ2 marksHard (estimate)
Q.9 (GA Q.9)
A grouped bar chart displaying Number of units sold and Net Profit in Rupees across three years: Year 1 has 100 units sold and 240 net profit, Year 2 has 200 units sold and 296...
Data Interpretation and Graphs
General AptitudeMCQ2 marksMedium (estimate)
Q.10 (GA Q.10)
Six 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 s...
Analytical and Logical Reasoning

Computer Science and Information Technology

55 questions, 85 marks

AlgorithmsMCQ1 markMedium (estimate)
Q.11 (CS Q.1)
Let $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 spann...
Minimum Spanning Trees
Data StructuresMCQ1 markEasy (estimate)
Q.12 (CS Q.2)
Let $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$ ?
Binary Heaps and Priority Queues
Compiler DesignMCQ1 markEasy (estimate)
Q.13 (CS Q.3)
Consider 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?
Parsing and Syntax Analysis (LL and LR) · Intermediate Code Generation, Data Flow Analysis and Code Optimization
Digital LogicMCQ1 markMedium (estimate)
Q.14 (CS Q.4)
The format of the single-precision floating-point representation of a real number as per the IEEE 754 standard is as follows: Sign bit: 1 bit, Exponent: 8 bits, Mantissa: 23 bit...
Number Representations and Computer Arithmetic
Digital LogicMCQ1 markMedium (estimate)
Q.15 (CS Q.5)
Which 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.
Combinational Circuits
DatabasesMCQ1 markEasy (estimate)
Q.16 (CS Q.6)
Consider 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...
ER Model and Relational Schema Design
Computer NetworksMCQ1 markEasy (estimate)
Q.17 (CS Q.7)
Consider 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...
Transport Layer: UDP, TCP Flow and Congestion Control, Sockets
AlgorithmsMCQ1 markEasy (estimate)
Q.18 (CS Q.8)
What is the worst-case number of arithmetic operations performed by recursive binary search on a sorted array of size $n$ ?
Divide and Conquer
Theory of ComputationMCQ1 markEasy (estimate)
Q.19 (CS Q.9)
Let $L \subseteq {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 mi...
Regular Expressions, Finite Automata and Regular Languages
Programming in CMCQ1 markMedium (estimate)
Q.20 (CS Q.10)
Consider the following ANSI C program. #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;...
Pointers, Arrays and Strings
Engineering MathematicsMSQ1 markEasy (estimate)
Q.21 (CS Q.11)
Consider the following sets, where $n \geq 2$ : $S_{1}$ : Set of all $n \times n$ matrices with entries from the set ${a, b, c}$ $S_{2}$ : Set of all functions from the set…
Sets, Relations, Functions, Partial Orders and Lattices
Theory of ComputationMSQ1 markMedium (estimate)
Q.22 (CS Q.12)
Let $L_{1}$ be a regular language and $L_{2}$ be a context-free language. Which of the following languages is/are context-free?
Context-Free Grammars, Pushdown Automata and CFLs
Compiler DesignMSQ1 markEasy (estimate)
Q.23 (CS Q.13)
In the context of compilers, which of the following is/are NOT an intermediate representation of the source program?
Intermediate Code Generation, Data Flow Analysis and Code Optimization
Operating SystemsMSQ1 markMedium (estimate)
Q.24 (CS Q.14)
Which of the following statement(s) is/are correct in the context of CPU scheduling?
CPU Scheduling
Engineering MathematicsMSQ1 markEasy (estimate)
Q.25 (CS Q.15)
Choose the correct choice(s) regarding the following propositional logic assertion $S$ : $S : ((P \land Q) \to R) \to ((P \land Q) \to (Q \to R))$
Propositional and First-Order Logic
Data StructuresNAT1 markEasy (estimate)
Q.26 (CS Q.16)
Consider 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...
Binary Trees, Binary Search Trees and Balanced Trees
Theory of ComputationNAT1 markEasy (estimate)
Q.27 (CS Q.17)
Consider the following deterministic finite automaton (DFA). A 6-state deterministic finite automaton where start state q0 transitions on 0 to q1 and on 1 to q2; q1 transitions...
Regular Expressions, Finite Automata and Regular Languages
Digital LogicNAT1 markEasy (estimate)
Q.28 (CS Q.18)
If $x$ and $y$ are two decimal digits and $(0.1101)_{2} = (0.8 x y 5)_{10}$ , the decimal value of $x + y$ is ______.
Number Representations and Computer Arithmetic
Computer Organization and ArchitectureNAT1 markEasy (estimate)
Q.29 (CS Q.19)
Consider a set-associative cache of size 2KB ( $1 KB = 2^{10} bytes$ ) with cache block size of 64 bytes. Assume that the cache is byte-addressable and a 32-bit addr...
Memory Hierarchy: Cache, Main Memory and Secondary Storage
Computer Organization and ArchitectureNAT1 markEasy (estimate)
Q.30 (CS Q.20)
Consider 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 interv...
I/O Interface, Interrupts and DMA
DatabasesNAT1 markMedium (estimate)
Q.31 (CS Q.21)
A 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 rec...
File Organization, B-Trees and B+ Trees Indexing
Engineering MathematicsNAT1 markEasy (estimate)
Q.32 (CS Q.22)
For 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 numb...
Probability and Statistics
Programming in CNAT1 markEasy (estimate)
Q.33 (CS Q.23)
Consider 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, y);...
Functions, Recursion, Scope and Storage Classes
Engineering MathematicsNAT1 markEasy (estimate)
Q.34 (CS Q.24)
Suppose that $P$ is a $4 \times 5$ matrix such that every solution of the equation $P x = 0$ is a scalar multiple of $[25431]^{T}$ . The rank of $P$ is ______.
Linear Algebra
Engineering MathematicsNAT1 markEasy (estimate)
Q.35 (CS Q.25)
Suppose that $f : R \to 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...
Calculus
AlgorithmsMCQ2 marksMedium (estimate)
Q.36 (CS Q.26)
Consider 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 to one...
Greedy Algorithms
Computer Organization and ArchitectureMCQ2 marksMedium (estimate)
Q.37 (CS Q.27)
Assume 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...
Memory Hierarchy: Cache, Main Memory and Secondary Storage
Digital LogicMCQ2 marksMedium (estimate)
Q.38 (CS Q.28)
Suppose 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...
Sequential Circuits, Counters and Registers
Engineering MathematicsMCQ2 marksEasy (estimate)
Q.39 (CS Q.29)
In 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 zer...
Probability and Statistics
Compiler DesignMCQ2 marksMedium (estimate)
Q.40 (CS Q.30)
Consider the following ANSI C code segment: 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;...
Intermediate Code Generation, Data Flow Analysis and Code Optimization
DatabasesMCQ2 marksEasy (estimate)
Q.41 (CS Q.31)
The 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 employ...
SQL Queries and Integrity Constraints
DatabasesMCQ2 marksMedium (estimate)
Q.42 (CS Q.32)
Let $S$ be the following schedule of operations of three transactions $T_{1}$ , $T_{2}$ and $T_{3}$ in a relational database system…
Transactions, Serializability and Concurrency Control
Engineering MathematicsMCQ2 marksMedium (estimate)
Q.43 (CS Q.33)
A 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 bal...
Probability and Statistics
Computer NetworksMCQ2 marksEasy (estimate)
Q.44 (CS Q.34)
Consider the cyclic redundancy check (CRC) based error detecting scheme having the generator polynomial $X^{3} + X + 1$ . Suppose the message $m_{4} m_{3} m_{2} m_{1} m_{0} = 11000$ is to be...
Data Link Layer: Framing, Error Detection and Sliding Window
Programming in CMCQ2 marksMedium (estimate)
Q.45 (CS Q.35)
Consider the following ANSI C program: #include <stdio.h> #include <stdlib.h> struct Node { int value; struct Node *next; }; int main() { struct Node *boxE, *head, *boxN; i...
Pointers, Arrays and Strings
Theory of ComputationMCQ2 marksMedium (estimate)
Q.46 (CS Q.36)
Consider 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...
Decidability, Reducibility and Undecidability
Engineering MathematicsMCQ2 marksEasy (estimate)
Q.47 (CS Q.37)
For two $n$ -dimensional real vectors $P$ and $Q$ , the operation $s (P, Q)$ is defined as follows: $s (P, Q) = \sum_{i = 1}^{n} (P_{i} \cdot Q_{i})$ Let $L$ be a set of 10-dime...
Linear Algebra
Compiler DesignMCQ2 marksEasy (estimate)
Q.48 (CS Q.38)
For 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$ …
Intermediate Code Generation, Data Flow Analysis and Code Optimization
AlgorithmsMCQ2 marksEasy (estimate)
Q.49 (CS Q.39)
For constants $a \geq 1$ and $b > 1$ , consider the following recurrence defined on the non-negative integers: $T (n) = a \cdot T (\frac{n}{b}) + f (n)$ Which one of the...
Asymptotic Analysis and Time/Space Complexity
DatabasesMSQ2 marksEasy (estimate)
Q.50 (CS Q.40)
Suppose the following functional dependencies hold on a relation $U$ with attributes $P, Q, R, S$ , and $T$ : $P \to QR$ $R S \to T$ Which of the following functional dependenc...
Functional Dependencies and Normalization
Theory of ComputationMSQ2 marksMedium (estimate)
Q.51 (CS Q.41)
For 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?
Context-Free Grammars, Pushdown Automata and CFLs
Operating SystemsMSQ2 marksMedium (estimate)
Q.52 (CS Q.42)
Consider 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 and T2…
Process Synchronization and Concurrency
Operating SystemsMSQ2 marksMedium (estimate)
Q.53 (CS Q.43)
Consider 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...
Deadlock Prevention, Avoidance and Detection
Computer Organization and ArchitectureMSQ2 marksMedium (estimate)
Q.54 (CS Q.44)
If 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 u...
Machine Instructions and Addressing Modes
Computer NetworksMSQ2 marksMedium (estimate)
Q.55 (CS Q.45)
Consider a computer network using the distance vector routing algorithm in its network layer. The partial topology of the network is as shown below. A distance vector routing ne...
Routing Algorithms (Distance Vector, Link State) and BGP/OSPF
AlgorithmsMSQ2 marksMedium (estimate)
Q.56 (CS Q.46)
Consider the following directed graph: A 4 by 4 directed grid graph with 16 solid black vertices and directed edges between adjacent vertices. The bottom-left vertex is labeled...
Graph Traversals, Topological Sort and Connectivity
Theory of ComputationMSQ2 marksMedium (estimate)
Q.57 (CS Q.47)
Which 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.
Regular Expressions, Finite Automata and Regular Languages
Operating SystemsNAT2 marksMedium (estimate)
Q.58 (CS Q.48)
Consider a three-level page table to translate a 39-bit virtual address to a physical address as shown below. A 39-bit virtual address bit layout divided into four fields: Level...
Memory Management and Virtual Memory
Programming in CNAT2 marksEasy (estimate)
Q.59 (CS Q.49)
Consider the following ANSI C program. #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...
Functions, Recursion, Scope and Storage Classes
Engineering MathematicsNAT2 marksEasy (estimate)
Q.60 (CS Q.50)
Let $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 \subseteq B$ is ______.
Combinatorics, Counting, Recurrence Relations and Generating Functions
Compiler DesignNAT2 marksMedium (estimate)
Q.61 (CS Q.51)
Consider the following augmented grammar with ${#, @, <, >, a, b, c}$ as the set of terminals.…
Parsing and Syntax Analysis (LL and LR)
Digital LogicNAT2 marksMedium (estimate)
Q.62 (CS Q.52)
Consider a Boolean function $f (w, x, y, z)$ such that $f (w, 0, 0, z) f (1, x, 1, z) f (w, 1, y, z) = 1 = x + z = w z + y$ The number of lit...
Combinational Circuits
Computer Organization and ArchitectureNAT2 marksHard (estimate)
Q.63 (CS Q.53)
Consider 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...
Instruction Pipelining and Hazards
Computer NetworksNAT2 marksMedium (estimate)
Q.64 (CS Q.54)
Consider 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 ( $= 1 0^{6}$ bits per seco...
Medium Access Control (ALOHA, CSMA/CD) and Ethernet/Switching
AlgorithmsNAT2 marksMedium (estimate)
Q.65 (CS Q.55)
In 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 v...
Dynamic Programming