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

General Aptitude

10 questions, 15 marks

General AptitudeMCQ1 markEasy (estimate)
Q.1 (GA Q.1)
The 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
General AptitudeMCQ1 markEasy (estimate)
Q.2 (GA Q.2)
A polygon is convex if, for every pair of points, $P$ and $Q$ belonging to the polygon, the line segment $P Q$ lies completely inside or on the polygon. Which one of the followin...
Spatial Aptitude
General AptitudeMCQ1 markEasy (estimate)
Q.3 (GA Q.3)
Consider 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 followi...
Verbal Ability and Grammar
General AptitudeMCQ1 markMedium (estimate)
Q.4 (GA Q.4)
A 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...
Spatial Aptitude
General AptitudeMCQ1 markEasy (estimate)
Q.5 (GA Q.5)
__________ is to surgery as writer is to __________ Which one of the following options maintains a similar logical relation in the above sentence?
Verbal Ability and Grammar
General AptitudeMCQ2 marksMedium (estimate)
Q.6 (GA Q.6)
We have 2 rectangular sheets of paper, $M$ and $N$ , of dimensions $6 cm \times 1 cm$ each. Sheet $M$ is rolled to form an open cylinder by bringing the short edges...
Quantitative Aptitude
General AptitudeMCQ2 marksMedium (estimate)
Q.7 (GA Q.7)
Items Cost (₹) Profit % Marked Price (₹) P 5,400 --- 5,860 Q --- 25 10,000 Details of prices of two items P and Q are presented in the above table. The ratio of cost of item P t...
Quantitative Aptitude
General AptitudeMCQ2 marksMedium (estimate)
Q.8 (GA Q.8)
There 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
General AptitudeMCQ2 marksMedium (estimate)
Q.9 (GA Q.9)
Given 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:...
Analytical and Logical Reasoning
General AptitudeMCQ2 marksEasy (estimate)
Q.10 (GA Q.10)
Some people suggest anti-obesity measures (AOM) such as displaying calorie information in restaurant menus. Such measures sidestep addressing the core problems that cause obesit...
Verbal Ability and Grammar

Computer Science and Information Technology

55 questions, 85 marks

Theory of ComputationMCQ1 markMedium (estimate)
Q.11 (CS Q.1)
Suppose 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?
Context-Free Grammars, Pushdown Automata and CFLs
AlgorithmsMCQ1 markMedium (estimate)
Q.12 (CS Q.2)
Let $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 value...
Searching and Sorting Algorithms
AlgorithmsMCQ1 markEasy (estimate)
Q.13 (CS Q.3)
Consider the following three functions. $f_{1} = 1 0^{n}, f_{2} = n^{l o g n}, f_{3} = n^{n}$ Which one of the following options arranges the functions in the increas...
Asymptotic Analysis and Time/Space Complexity
Compiler DesignMCQ1 markEasy (estimate)
Q.14 (CS Q.4)
Consider 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 co...
Runtime Environments and Parameter Passing
Compiler DesignMCQ1 markMedium (estimate)
Q.15 (CS Q.5)
Consider 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...
Parsing and Syntax Analysis (LL and LR)
Digital LogicMCQ1 markEasy (estimate)
Q.16 (CS Q.6)
Let the representation of a number in base 3 be 210. What is the hexadecimal representation of the number?
Number Representations and Computer Arithmetic
Engineering MathematicsMCQ1 markEasy (estimate)
Q.17 (CS Q.7)
Let $p$ and $q$ be two propositions. Consider the following two formulae in propositional logic. $S_{1} : (\neg p \land (p \lor q)) \to q$ …
Propositional and First-Order Logic
Computer NetworksMCQ1 markEasy (estimate)
Q.18 (CS Q.8)
Consider 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 add...
Data Link Layer: Framing, Error Detection and Sliding Window
AlgorithmsMCQ1 markEasy (estimate)
Q.19 (CS Q.9)
Consider the following array. 23 32 45 69 72 73 89 97 Which algorithm out of the following options uses the least number of comparisons (among the array elements) to sort the ab...
Searching and Sorting Algorithms
Data StructuresMCQ1 markMedium (estimate)
Q.20 (CS Q.10)
A 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$ ?
Binary Trees, Binary Search Trees and Balanced Trees
Operating SystemsMSQ1 markEasy (estimate)
Q.21 (CS Q.11)
In the context of operating systems, which of the following statements is/are correct with respect to paging?
Memory Management and Virtual Memory
Theory of ComputationMSQ1 markMedium (estimate)
Q.22 (CS Q.12)
Let $⟨ M ⟩$ denote an encoding of an automaton $M$ . Suppose that $Σ = {0, 1}$ . Which of the following languages is/are NOT recursive?
Decidability, Reducibility and Undecidability
DatabasesMSQ1 markMedium (estimate)
Q.23 (CS Q.13)
Suppose 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 recover...
Transactions, Serializability and Concurrency Control
Operating SystemsMSQ1 markMedium (estimate)
Q.24 (CS Q.14)
Which 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?
Processes, Threads and System Calls
Operating SystemsMSQ1 markMedium (estimate)
Q.25 (CS Q.15)
Consider 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, s...
File Systems, I/O and Disk Scheduling
Engineering MathematicsNAT1 markEasy (estimate)
Q.26 (CS Q.16)
In an undirected connected planar graph $G$ , there are eight vertices and five faces. The number of edges in $G$ is __________
Graph Theory
AlgorithmsNAT1 markMedium (estimate)
Q.27 (CS Q.17)
Consider the following undirected graph with edge weights as shown: A 3 by 3 grid graph with 9 vertices and labeled edge weights of 0.1 and 0.9. The number of minimum-weight spa...
Minimum Spanning Trees
Engineering MathematicsNAT1 markEasy (estimate)
Q.28 (CS Q.18)
The lifetime of a component of a certain type is a random variable whose probability density function is exponentially distributed with parameter $λ$ . For a randomly picke...
Probability and Statistics
Engineering MathematicsNAT1 markMedium (estimate)
Q.29 (CS Q.19)
There 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...
Combinatorics, Counting, Recurrence Relations and Generating Functions
Engineering MathematicsNAT1 markEasy (estimate)
Q.30 (CS Q.20)
Consider the following expression. $lim_{x \to - 3} \frac{2 x + 22 - 4}{x + 3}$ The value of the above expression (rounded to 2 decimal places) is __________
Calculus
Data StructuresNAT1 markEasy (estimate)
Q.31 (CS Q.21)
Consider 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 an...
Stacks and Queues
Computer Organization and ArchitectureNAT1 markEasy (estimate)
Q.32 (CS Q.22)
Consider 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$ …
Memory Hierarchy: Cache, Main Memory and Secondary Storage
DatabasesNAT1 markMedium (estimate)
Q.33 (CS Q.23)
A 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...
Relational Algebra and Tuple Relational Calculus
Digital LogicNAT1 markEasy (estimate)
Q.34 (CS Q.24)
Consider 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 an...
Number Representations and Computer Arithmetic
Operating SystemsNAT1 markEasy (estimate)
Q.35 (CS Q.25)
Three 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 achievabl...
CPU Scheduling
Compiler DesignMCQ2 marksMedium (estimate)
Q.36 (CS Q.26)
Consider the following grammar (that admits a series of declarations, followed by expressions) and the associated syntax directed translation (SDT) actions, given as pseudo-code...
Syntax-Directed Translation
DatabasesMCQ2 marksMedium (estimate)
Q.37 (CS Q.27)
The following relation records the age of 500 employees of a company, where empNo (indicating the employee number) is the key: $empAge (empNo, age)$ Consid...
Relational Algebra and Tuple Relational Calculus
Digital LogicMCQ2 marksMedium (estimate)
Q.38 (CS Q.28)
Consider a 3-bit counter, designed using T flip-flops, as shown below: Synchronous 3-bit counter circuit designed using three T flip-flops with inputs Tp=R, Tq=P', and Tr=Q'. As...
Sequential Circuits, Counters and Registers
Computer NetworksMCQ2 marksMedium (estimate)
Q.39 (CS Q.29)
Assume 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 bits are...
Data Link Layer: Framing, Error Detection and Sliding Window
AlgorithmsMCQ2 marksMedium (estimate)
Q.40 (CS Q.30)
Consider the following recurrence relation. $T (n) = {T (n /2) + T (2 n /5) + 7 n 1 if n > 0 if n = 0$ Which one of the following opti...
Asymptotic Analysis and Time/Space Complexity
Compiler DesignMCQ2 marksMedium (estimate)
Q.41 (CS Q.31)
Consider the following context-free grammar where the set of terminals is ${a, b, c, d, f}$ . $S \to d a T ∣ R f$ $T \to a S ∣ ba T ∣ ϵ$ …
Parsing and Syntax Analysis (LL and LR)
DatabasesMCQ2 marksEasy (estimate)
Q.42 (CS Q.32)
Let $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.…
Transactions, Serializability and Concurrency Control
DatabasesMCQ2 marksMedium (estimate)
Q.43 (CS Q.33)
Consider the relation $R (P, Q, S, T, X, Y, Z, W)$ with the following functional dependencies.…
Functional Dependencies and Normalization
Engineering MathematicsMCQ2 marksMedium (estimate)
Q.44 (CS Q.34)
Let $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?
Monoids and Groups
Engineering MathematicsMCQ2 marksMedium (estimate)
Q.45 (CS Q.35)
Consider 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]$ ...
Probability and Statistics
Engineering MathematicsMCQ2 marksMedium (estimate)
Q.46 (CS Q.36)
Let $G = (V, E)$ be an undirected unweighted connected graph. The diameter of $G$ is defined as…
Graph Theory
Programming in CMCQ2 marksMedium (estimate)
Q.47 (CS Q.37)
Consider the following ANSI C program. #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; }...
Data Types, Operators and Control Flow
Theory of ComputationMCQ2 marksEasy (estimate)
Q.48 (CS Q.38)
Consider the following language. $L = {w \in {0, 1}^{*} ∣ w ends with the substring 011}$ Which one of the following deterministic finite automata accepts $L$ ?
Regular Expressions, Finite Automata and Regular Languages
Theory of ComputationMCQ2 marksMedium (estimate)
Q.49 (CS Q.39)
For a Turing machine $M$ , $⟨ M ⟩$ denotes an encoding of $M$ . Consider the following two languages.…
Decidability, Reducibility and Undecidability
AlgorithmsMSQ2 marksMedium (estimate)
Q.50 (CS Q.40)
Define $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...
Dynamic Programming
AlgorithmsMSQ2 marksMedium (estimate)
Q.51 (CS Q.41)
An 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$ ...
Graph Traversals, Topological Sort and Connectivity
Digital LogicMSQ2 marksMedium (estimate)
Q.52 (CS Q.42)
Consider the following Boolean expression. $F = (X + Y + Z) (X + Y) (Y + Z)$ Which of the following Boolean expressions is/are equivalent to $F$ ...
Boolean Algebra and Logic Minimization
Engineering MathematicsMSQ2 marksMedium (estimate)
Q.53 (CS Q.43)
A relation $R$ is said to be circular if $a R b$ and $b R c$ together imply $c R a$ . Which of the following options is/are correct?
Sets, Relations, Functions, Partial Orders and Lattices
Computer NetworksMSQ2 marksMedium (estimate)
Q.54 (CS Q.44)
A 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 connec...
Transport Layer: UDP, TCP Flow and Congestion Control, Sockets
Computer NetworksMSQ2 marksMedium (estimate)
Q.55 (CS Q.45)
Consider 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 82...
IPv4/IPv6 Addressing, Subnetting, CIDR, ARP, ICMP and NAT
Operating SystemsMSQ2 marksMedium (estimate)
Q.56 (CS Q.46)
Consider 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 ope...
Process Synchronization and Concurrency
DatabasesMSQ2 marksHard (estimate)
Q.57 (CS Q.47)
Consider 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...
File Organization, B-Trees and B+ Trees Indexing
Programming in CNAT2 marksEasy (estimate)
Q.58 (CS Q.48)
Consider the following ANSI C function: int SimpleFunction(int Y[], int n, int x) { int total = Y[0], loopIndex; for (loopIndex = 1; loopIndex <= n - 1; loopIndex++) total = x *...
Data Types, Operators and Control Flow
Computer NetworksNAT2 marksMedium (estimate)
Q.59 (CS Q.49)
Consider 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 proces...
Data Link Layer: Framing, Error Detection and Sliding Window
Compiler DesignNAT2 marksEasy (estimate)
Q.60 (CS Q.50)
Consider 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 a...
Intermediate Code Generation, Data Flow Analysis and Code Optimization
Theory of ComputationNAT2 marksHard (estimate)
Q.61 (CS Q.51)
In a pushdown automaton $P = (Q, Σ, Γ, δ, q_{0}, F)$ , a transition of the form, $(q, Y) \in δ (p, a, X)$ where $p, q \in Q$ , $a \in Σ \cup {ϵ}$ ,...
Context-Free Grammars, Pushdown Automata and CFLs
Engineering MathematicsNAT2 marksEasy (estimate)
Q.62 (CS Q.52)
Consider the following matrix. $0111101111011110$ The largest eigenvalue of the above matrix is _...
Linear Algebra
Computer Organization and ArchitectureNAT2 marksEasy (estimate)
Q.63 (CS Q.53)
A 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...
Instruction Pipelining and Hazards
Engineering MathematicsNAT2 marksMedium (estimate)
Q.64 (CS Q.54)
A 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 edg...
Probability and Statistics
Computer Organization and ArchitectureNAT2 marksMedium (estimate)
Q.65 (CS Q.55)
Consider the following instruction sequence where registers R1, R2 and R3 are general purpose and $MEMORY [X]$ denotes the content at the memory location $X$ . Instruction...
Machine Instructions and Addressing Modes