GATE CS 2020 question paper: all 65 questions with answers and solutions

General Aptitude

10 questions, 15 marks

General AptitudeMCQ1 markEasy (estimate)
Q.1 (GA Q.1)
Raman is confident of speaking English _______ six months as he has been practising regularly _______ the last three weeks.
Verbal Ability and Grammar
General AptitudeMCQ1 markEasy (estimate)
Q.2 (GA Q.2)
His knowledge of the subject was excellent but his classroom performance was _______.
Verbal Ability and Grammar
General AptitudeMCQ1 markEasy (estimate)
Q.3 (GA Q.3)
Select the word that fits the analogy: Cook : Cook :: Fly : _______
Verbal Ability and Grammar
General AptitudeMCQ1 markEasy (estimate)
Q.4 (GA Q.4)
The dawn of the 21st century witnessed the melting glaciers oscillating between giving too much and too little to billions of people who depend on them for fresh water. The UN c...
Reading Comprehension and Verbal Deduction
General AptitudeMCQ1 markMedium (estimate)
Q.5 (GA Q.5)
There are multiple routes to reach from node 1 to node 2, as shown in the network. Directed graph showing travel routes from node 1 to node 2 through toll booths a, b, c, d, e,...
Quantitative Aptitude
General AptitudeMCQ2 marksEasy (estimate)
Q.6 (GA Q.6)
Goods and Services Tax (GST) is an indirect tax introduced in India in 2017 that is imposed on the supply of goods and services, and it subsumes all indirect taxes except few. I...
Reading Comprehension and Verbal Deduction
General AptitudeMCQ2 marksEasy (estimate)
Q.7 (GA Q.7)
If $P = 3$ , $R = 27$ , $T = 243$ , then $Q + S =$
Quantitative Aptitude
General AptitudeMCQ2 marksMedium (estimate)
Q.8 (GA Q.8)
The figure below shows an annular ring with outer and inner radii as $b$ and $a$ , respectively. The annular space has been painted in the form of blue colour circles touching th...
Spatial Aptitude
General AptitudeMCQ2 marksEasy (estimate)
Q.9 (GA Q.9)
Two straight lines are drawn perpendicular to each other in X-Y plane. If $α$ and $β$ are the acute angles the straight lines make with the X-axis, then…
Quantitative Aptitude
General AptitudeMCQ2 marksMedium (estimate)
Q.10 (GA Q.10)
The total revenue of a company during 2014-2018 is shown in the bar graph. If the total expenditure of the company in each year is 500 million rupees, then the aggregate profit...
Data Interpretation and Graphs

Computer Science and Information Technology

55 questions, 85 marks

Engineering MathematicsMCQ1 markEasy (estimate)
Q.11 (CS Q.1)
Consider the functions I. $e^{- x}$ II. $x^{2} - sin x$ III. $x^{3} + 1$ Which of the above functions is/are increasing everywhere in $[0, 1]$ ?
Calculus
AlgorithmsMCQ1 markMedium (estimate)
Q.12 (CS Q.2)
For parameters $a$ and $b$ , both of which are $ω (1)$ , $T (n) = T (n^{1/ a}) + 1$ , and $T (b) = 1$ . Then $T (n)$ is
Asymptotic Analysis and Time/Space Complexity
Computer Organization and ArchitectureMCQ1 markEasy (estimate)
Q.13 (CS Q.3)
Consider the following statements. I. Daisy chaining is used to assign priorities in attending interrupts. II. When a device raises a vectored interrupt, the CPU does polling to...
I/O Interface, Interrupts and DMA
Computer Organization and ArchitectureMCQ1 markMedium (estimate)
Q.14 (CS Q.4)
Consider the following data path diagram. Single bus CPU data path architecture diagram showing MAR, MDR, IR, PC, general registers R0 through R7, temporary registers TEMP1 and...
ALU, Datapath and Control Unit
Data StructuresMCQ1 markEasy (estimate)
Q.15 (CS Q.5)
The preorder traversal of a binary search tree is 15, 10, 12, 11, 20, 18, 16, 19. Which one of the following is the postorder traversal of the tree?
Binary Trees, Binary Search Trees and Balanced Trees
Data StructuresMCQ1 markMedium (estimate)
Q.16 (CS Q.6)
What is the worst case time complexity of inserting $n^{2}$ elements into an AVL-tree with $n$ elements initially?
Binary Trees, Binary Search Trees and Balanced Trees · Asymptotic Analysis and Time/Space Complexity
Theory of ComputationMCQ1 markMedium (estimate)
Q.17 (CS Q.7)
Which one of the following regular expressions represents the set of all binary strings with an odd number of 1's?
Regular Expressions, Finite Automata and Regular Languages
Theory of ComputationMCQ1 markEasy (estimate)
Q.18 (CS Q.8)
Consider the following statements. I. If $L_{1} \cup L_{2}$ is regular, then both $L_{1}$ and $L_{2}$ must be regular. II. The class of regular languages is closed under infinite union....
Regular Expressions, Finite Automata and Regular Languages
Compiler DesignMCQ1 markEasy (estimate)
Q.19 (CS Q.9)
Consider the following statements. I. Symbol table is accessed only during lexical analysis and syntax analysis. II. Compilers for programming languages that support recursion n...
Runtime Environments and Parameter Passing · Parsing and Syntax Analysis (LL and LR) · Parsing and Syntax Analysis (LL and LR)
Theory of ComputationMCQ1 markMedium (estimate)
Q.20 (CS Q.10)
Consider the language $L = {a^{n} ∣ n \geq 0} \cup {a^{n} b^{n} ∣ n \geq 0}$ and the following statements. I. $L$ is deterministic context-free. II. $L$ is context-free but no...
Context-Free Grammars, Pushdown Automata and CFLs · Parsing and Syntax Analysis (LL and LR)
Operating SystemsMCQ1 markEasy (estimate)
Q.21 (CS Q.11)
Consider allocation of memory to a new process. Assume that none of the existing holes in the memory will exactly fit the process's memory requirement. Hence, a new hole of smal...
Memory Management and Virtual Memory
Operating SystemsMCQ1 markEasy (estimate)
Q.22 (CS Q.12)
Consider the following statements about process state transitions for a system using preemptive scheduling. I. A running process can move to ready state. II. A ready process can...
CPU Scheduling · Processes, Threads and System Calls
DatabasesMCQ1 markMedium (estimate)
Q.23 (CS Q.13)
Consider a relational database containing the following schemas. sno pno cost S1 P1 150 S1 P2 50 S1 P3 100 S2 P4 200 S2 P5 250 S3 P1 250 S3 P2 150 S3 P5 300 S3 P4 250 sno sname...
SQL Queries and Integrity Constraints
DatabasesMCQ1 markEasy (estimate)
Q.24 (CS Q.14)
Which one of the following is used to represent the supporting many-one relationships of a weak entity set in an entity-relationship diagram?
ER Model and Relational Schema Design
Computer NetworksMCQ1 markEasy (estimate)
Q.25 (CS Q.15)
Consider the following statements about the functionality of an IP based router. I. A router does not modify the IP packets during forwarding. II. It is not necessary for a rout...
Routing Algorithms (Distance Vector, Link State) and BGP/OSPF · IPv4/IPv6 Addressing, Subnetting, CIDR, ARP, ICMP and NAT
Data StructuresMCQ1 markEasy (estimate)
Q.26 (CS Q.16)
What is the worst case time complexity of inserting $n$ elements into an empty linked list, if the linked list needs to be maintained in sorted order?
Arrays and Linked Lists · Asymptotic Analysis and Time/Space Complexity
Engineering MathematicsNAT1 markEasy (estimate)
Q.27 (CS Q.17)
Let $R$ be the set of all binary relations on the set ${1, 2, 3}$ . Suppose a relation is chosen from $R$ at random. The probability that the chosen relation is reflexive (roun...
Sets, Relations, Functions, Partial Orders and Lattices · Probability and Statistics
Engineering MathematicsNAT1 markEasy (estimate)
Q.28 (CS Q.18)
Let $G$ be a group of 35 elements. Then the largest possible size of a subgroup of $G$ other than $G$ itself is _______.
Monoids and Groups
Digital LogicNAT1 markEasy (estimate)
Q.29 (CS Q.19)
A multiplexer is placed between a group of 32 registers and an accumulator to regulate data movement such that at any given point in time the content of only one register will m...
Combinational Circuits
Digital LogicNAT1 markEasy (estimate)
Q.30 (CS Q.20)
If there are $m$ input lines and $n$ output lines for a decoder that is used to uniquely address a byte addressable 1 KB RAM, then the minimum value of $m + n$ is _______.
Combinational Circuits · Memory Hierarchy: Cache, Main Memory and Secondary Storage
Computer Organization and ArchitectureNAT1 markMedium (estimate)
Q.31 (CS Q.21)
A direct mapped cache memory of 1 MB has a block size of 256 bytes. The cache has an access time of 3 ns and a hit rate of 94%. During a cache miss, it takes 20 ns to bring the...
Memory Hierarchy: Cache, Main Memory and Secondary Storage
Programming in CNAT1 markEasy (estimate)
Q.32 (CS Q.22)
Consider the following C program. #include <stdio.h> int main() { int a[4][5] = {{ {1, 2, 3, 4, 5}, {6, 7, 8, 9, 10}, {11, 12, 13, 14, 15}, {16, 17, 18, 19, 20} }}; printf(...
Pointers, Arrays and Strings · Pointers, Arrays and Strings
Data StructuresNAT1 markEasy (estimate)
Q.33 (CS Q.23)
Consider a double hashing scheme in which the primary hash function is $h_{1} (k) = k mod 23$ , and the secondary hash function is $h_{2} (k) = 1 + (k mod 19)$ . Assume that the tab...
Hash Tables and Collision Resolution
Compiler DesignNAT1 markEasy (estimate)
Q.34 (CS Q.24)
Consider the following grammar. $S B \to a S B ∣ d \to b$ The number of reduction steps taken by a bottom-up parser while accepting the s...
Parsing and Syntax Analysis (LL and LR)
Computer NetworksNAT1 markEasy (estimate)
Q.35 (CS Q.25)
Assume that you have made a request for a web page through your web browser to a web server. Initially the browser cache is empty. Further, the browser is configured to send HTT...
Application Layer: DNS, HTTP, SMTP, FTP
Theory of ComputationMCQ2 marksMedium (estimate)
Q.36 (CS Q.26)
Which of the following languages are undecidable? Note that $⟨ M ⟩$ indicates encoding of the Turing machine $M$ .…
Decidability, Reducibility and Undecidability
Engineering MathematicsMCQ2 marksEasy (estimate)
Q.37 (CS Q.27)
Let $A$ and $B$ be two $n \times n$ matrices over real numbers. Let $rank (M)$ and $det (M)$ denote the rank and determinant of a matrix $M$ , respectively. Consider the fo...
Linear Algebra
Digital LogicMCQ2 marksEasy (estimate)
Q.38 (CS Q.28)
Consider the Boolean function $z (a, b, c)$ represented by the logic circuit below. Logic circuit diagram with inputs a, b, c, an inverter on b, an AND gate combining not-b and c...
Boolean Algebra and Logic Minimization · Combinational Circuits
Digital LogicMCQ2 marksMedium (estimate)
Q.39 (CS Q.29)
Consider three registers R1, R2, and R3 that store numbers in IEEE-754 single precision floating point format. Assume that R1 and R2 contain the values (in hexadecimal notation)...
Number Representations and Computer Arithmetic
Computer Organization and ArchitectureMCQ2 marksMedium (estimate)
Q.40 (CS Q.30)
A computer system with a word length of 32 bits has a 16 MB byte-addressable main memory and a 64 KB, 4-way set associative cache memory with a block size of 256 bytes. Consider...
Memory Hierarchy: Cache, Main Memory and Secondary Storage
AlgorithmsMCQ2 marksMedium (estimate)
Q.41 (CS Q.31)
Let $G = (V, E)$ be a weighted undirected graph and let $T$ be a Minimum Spanning Tree (MST) of $G$ maintained using adjacency lists. Suppose a new weighted edge…
Greedy Algorithms · Graph Traversals, Topological Sort and Connectivity
Theory of ComputationMCQ2 marksHard (estimate)
Q.42 (CS Q.32)
Consider the following languages. $L_{1} L_{2} = {w x y x ∣ w, x, y \in (0 + 1)^{+}} = {x y ∣ x, y \in (a + b)^{*}, ∣ x ∣ = ∣ y ∣, x \neq = y}$ W...
Regular Expressions, Finite Automata and Regular Languages · Context-Free Grammars, Pushdown Automata and CFLs
Compiler DesignMCQ2 marksEasy (estimate)
Q.43 (CS Q.33)
Consider the productions $A \to P Q$ and $A \to X Y$ . Each of the five non-terminals $A, P, Q, X$ , and $Y$ has two attributes: $s$ is a synthesized attribute, and $i$ is an inhe...
Syntax-Directed Translation
Operating SystemsMCQ2 marksMedium (estimate)
Q.44 (CS Q.34)
Each of a set of $n$ processes executes the following code using two semaphores $a$ and $b$ initialized to 1 and 0, respectively. Assume that count is a shared variable initia...
Process Synchronization and Concurrency
Operating SystemsMCQ2 marksEasy (estimate)
Q.45 (CS Q.35)
Consider the following five disk access requests of the form (request id, cylinder number) that are present in the disk scheduler queue at a given time.…
File Systems, I/O and Disk Scheduling
DatabasesMCQ2 marksEasy (estimate)
Q.46 (CS Q.36)
Consider a relational table $R$ that is in 3NF, but not in BCNF. Which one of the following statements is TRUE?
Functional Dependencies and Normalization
DatabasesMCQ2 marksMedium (estimate)
Q.47 (CS Q.37)
Consider a schedule of transactions $T_{1}$ and $T_{2}$ given below.…
Transactions, Serializability and Concurrency Control
Computer NetworksMCQ2 marksMedium (estimate)
Q.48 (CS Q.38)
An organization requires a range of IP addresses to assign one to each of its 1500 computers. The organization has approached an Internet Service Provider (ISP) for this task. T...
IPv4/IPv6 Addressing, Subnetting, CIDR, ARP, ICMP and NAT
Engineering MathematicsMCQ2 marksMedium (estimate)
Q.49 (CS Q.39)
Which one of the following predicate formulae is NOT logically valid? Note that $W$ is a predicate formula without any free occurrence of $x$ .
Propositional and First-Order Logic
AlgorithmsMCQ2 marksMedium (estimate)
Q.50 (CS Q.40)
Let $G = (V, E)$ be a directed, weighted graph with weight function $w : E \to R$ . For some function $f : V \to R$ , for each edge $(u, v) \in E$ , define…
Graph Traversals, Topological Sort and Connectivity
Data StructuresMCQ2 marksEasy (estimate)
Q.51 (CS Q.41)
In a balanced binary search tree with $n$ elements, what is the worst case time complexity of reporting all elements in range $[a, b]$ ? Assume that the number of reported elemen...
Binary Trees, Binary Search Trees and Balanced Trees · Asymptotic Analysis and Time/Space Complexity
Engineering MathematicsNAT2 marksMedium (estimate)
Q.52 (CS Q.42)
The number of permutations of the characters in LILAC so that no character appears in its original position, if the two L's are indistinguishable, is _______.
Combinatorics, Counting, Recurrence Relations and Generating Functions
Computer Organization and ArchitectureNAT2 marksMedium (estimate)
Q.53 (CS Q.43)
Consider a non-pipelined processor operating at 2.5 GHz. It takes 5 clock cycles to complete an instruction. You are going to make a 5-stage pipeline out of this processor. Over...
Instruction Pipelining and Hazards
Computer Organization and ArchitectureNAT2 marksMedium (estimate)
Q.54 (CS Q.44)
A processor has 64 registers and uses 16-bit instruction format. It has two types of instructions: I-type and R-type. Each I-type instruction contains an opcode, a register name...
Instruction Pipelining and Hazards · Number Representations and Computer Arithmetic
Engineering MathematicsNAT2 marksEasy (estimate)
Q.55 (CS Q.45)
For $n \geq 2$ , let $a \in {0, 1}^{n}$ be a non-zero vector. Suppose that $x$ is chosen uniformly at random from ${0, 1}^{n}$ . Then, the probability that $\sum_{i = 1}^{n} a_{i} x_{i}$ ...
Probability and Statistics
Programming in CNAT2 marksMedium (estimate)
Q.56 (CS Q.46)
Consider the following C functions. int fun1(int n) { static int i = 0; if (n > 0) { ++i; fun1(n - 1); } return (i); } int fun2(int n) { static int i = 0; if (n > 0) { i =...
Functions, Recursion, Scope and Storage Classes · Functions, Recursion, Scope and Storage Classes
Data StructuresNAT2 marksMedium (estimate)
Q.57 (CS Q.47)
Consider the array representation of a binary min-heap containing 1023 elements. The minimum number of comparisons required to find the maximum in the heap is _______.
Binary Heaps and Priority Queues
Programming in CNAT2 marksEasy (estimate)
Q.58 (CS Q.48)
Consider the following C functions. int tob(int b, int* arr) { int i; for (i = 0; b > 0; i++) { if (b % 2) arr[i] = 1; else arr[i] = 0; b = b / 2; } return (i); } int pp(in...
Pointers, Arrays and Strings · Functions, Recursion, Scope and Storage Classes
AlgorithmsNAT2 marksEasy (estimate)
Q.59 (CS Q.49)
Consider a graph $G = (V, E)$ , where $V = {v_{1}, v_{2}, \dots, v_{100}}$ , $E = {(v_{i}, v_{j}) ∣ 1 \leq i < j \leq 100}$ , and weight of the edge $(v_{i}, v_{j})$ is $∣ i - j ∣$ . The wei...
Greedy Algorithms · Graph Traversals, Topological Sort and Connectivity
Operating SystemsNAT2 marksMedium (estimate)
Q.60 (CS Q.50)
Consider the following set of processes, assumed to have arrived at time 0. Consider the CPU scheduling algorithms Shortest Job First (SJF) and Round Robin (RR). For RR, assume...
CPU Scheduling
Theory of ComputationNAT2 marksMedium (estimate)
Q.61 (CS Q.51)
Consider the following language. $L = {x \in {a, b}^{*} ∣ number of a ’s in x is divisible by 2 but not divisible by 3}$ The minimum number of stat...
Regular Expressions, Finite Automata and Regular Languages
Engineering MathematicsNAT2 marksHard (estimate)
Q.62 (CS Q.52)
Graph $G$ is obtained by adding vertex $s$ to $K_{3, 4}$ and making $s$ adjacent to every vertex of $K_{3, 4}$ . The minimum number of colours required to edge-colour $G$ is _______.
Graph Theory
Operating SystemsNAT2 marksHard (estimate)
Q.63 (CS Q.53)
Consider a paging system that uses 1-level page table residing in main memory and a TLB for address translation. Each main memory access takes 100 ns and TLB lookup takes 20 ns....
Memory Management and Virtual Memory · Memory Management and Virtual Memory
DatabasesNAT2 marksMedium (estimate)
Q.64 (CS Q.54)
Consider a database implemented using B+ tree for file indexing and installed on a disk drive with block size of 4 KB. The size of search key is 12 bytes and the size of tree/di...
File Organization, B-Trees and B+ Trees Indexing
Computer NetworksNAT2 marksMedium (estimate)
Q.65 (CS Q.55)
Consider a TCP connection between a client and a server with the following specifications: the round trip time is 6 ms, the size of the receiver advertised window is 50 KB, slow...
Transport Layer: UDP, TCP Flow and Congestion Control, Sockets