GATE CS 2019 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 expenditure on the project _____ as follows: equipment Rs. 20 lakhs, salaries Rs. 12 lakhs, and contingency Rs. 3 lakhs.
Verbal Ability and Grammar
General AptitudeMCQ1 markEasy (estimate)
Q.2 (GA Q.2)
The search engine's business model ___________ around the fulcrum of trust.
Verbal Ability and Grammar
General AptitudeMCQ1 markEasy (estimate)
Q.3 (GA Q.3)
Two cars start at the same time from the same location and go in the same direction. The speed of the first car is $50 km/h$ and the speed of the second car is…
Quantitative Aptitude
General AptitudeMCQ1 markEasy (estimate)
Q.4 (GA Q.4)
Ten friends planned to share equally the cost of buying a gift for their teacher. When two of them decided not to contribute, each of the other friends had to pay Rs 150 more. T...
Quantitative Aptitude
General AptitudeMCQ1 markEasy (estimate)
Q.5 (GA Q.5)
A court is to a judge as _____________ is to a teacher.
Verbal Ability and Grammar
General AptitudeMCQ2 marksMedium (estimate)
Q.6 (GA Q.6)
The police arrested four criminals - P, Q, R and S. The criminals knew each other. They made the following statements: P says "Q committed the crime." Q says "S committed the cr...
Verbal Ability and Grammar
General AptitudeMCQ2 marksEasy (estimate)
Q.7 (GA Q.7)
In the given diagram, teachers are represented in the triangle, researchers in the circle and administrators in the rectangle. Out of the total number of the people, the percent...
Quantitative Aptitude
General AptitudeMCQ2 marksEasy (estimate)
Q.8 (GA Q.8)
"A recent High Court judgement has sought to dispel the idea of begging as a disease - which leads to its stigmatization and criminalization - and to regard it as a symptom. The...
Verbal Ability and Grammar
General AptitudeMCQ2 marksMedium (estimate)
Q.9 (GA Q.9)
In a college, there are three student clubs. Sixty students are only in the Drama club, 80 students are only in the Dance club, 30 students are only in the Maths club, 40 studen...
Quantitative Aptitude
General AptitudeMCQ2 marksMedium (estimate)
Q.10 (GA Q.10)
Three of the five students allocated to a hostel put in special requests to the warden. Given the floor plan of the vacant rooms, select the allocation plan that will accommodat...
Spatial Aptitude

Computer Science and Information Technology

55 questions, 85 marks

Computer Organization and ArchitectureMCQ1 markEasy (estimate)
Q.11 (CS Q.1)
A certain processor uses a fully associative cache of size $16 kB$ . The cache block size is $16 bytes$ . Assume that the main memory is byte addressable and uses a...
Memory Hierarchy: Cache, Main Memory and Secondary Storage
Computer Organization and ArchitectureMCQ1 markEasy (estimate)
Q.12 (CS Q.2)
The chip select logic for a certain DRAM chip in a memory system design is shown below. Assume that the memory system has 16 address lines denoted by $A_{15}$ to $A_{0}$ . What is...
Memory Hierarchy: Cache, Main Memory and Secondary Storage
Compiler DesignMCQ1 markEasy (estimate)
Q.13 (CS Q.3)
Which one of the following kinds of derivation is used by LR parsers?
Parsing and Syntax Analysis (LL and LR)
Digital LogicMCQ1 markEasy (estimate)
Q.14 (CS Q.4)
In 16-bit 2's complement representation, the decimal number $- 28$ is:
Number Representations and Computer Arithmetic
Engineering MathematicsMCQ1 markMedium (estimate)
Q.15 (CS Q.5)
Let $U = {1, 2, \dots, n}$ . Let $A = {(x, X) ∣ x \in X, X \subseteq U}$ . Consider the following two statements on $∣ A ∣$ . I. $∣ A ∣ = n 2^{n - 1}$ II.…
Combinatorics, Counting, Recurrence Relations and Generating Functions
Digital LogicMCQ1 markEasy (estimate)
Q.16 (CS Q.6)
Which one of the following is NOT a valid identity?
Boolean Algebra and Logic Minimization
Theory of ComputationMCQ1 markEasy (estimate)
Q.17 (CS Q.7)
If $L$ is a regular language over $Σ = {a, b}$ , which one of the following languages is NOT regular?
Regular Expressions, Finite Automata and Regular Languages
Digital LogicMCQ1 markEasy (estimate)
Q.18 (CS Q.8)
Consider $Z = X - Y$ , where $X, Y$ and $Z$ are all in sign-magnitude form. $X$ and $Y$ are each represented in $n$ bits. To avoid overflow, the representation of $Z$ would requi...
Number Representations and Computer Arithmetic
Engineering MathematicsMCQ1 markEasy (estimate)
Q.19 (CS Q.9)
Let $X$ be a square matrix. Consider the following two statements on $X$ . I. $X$ is invertible. II. Determinant of $X$ is non-zero. Which one of the following is TRUE?
Linear Algebra
Engineering MathematicsMCQ1 markEasy (estimate)
Q.20 (CS Q.10)
Let $G$ be an arbitrary group. Consider the following relations on $G$ : $R_{1}$ : $\forall a, b \in G$ , $a R_{1} b$ if and only if $\exists g \in G$ such that $a = g^{- 1} b g$ $R_{2}$ …
Monoids and Groups
DatabasesMCQ1 markMedium (estimate)
Q.21 (CS Q.11)
Consider the following two statements about database transaction schedules: I. Strict two-phase locking protocol generates conflict serializable schedules that are also recovera...
Transactions, Serializability and Concurrency Control
Engineering MathematicsMCQ1 markEasy (estimate)
Q.22 (CS Q.12)
Let $G$ be an undirected complete graph on $n$ vertices, where $n > 2$ . Then, the number of different Hamiltonian cycles in $G$ is equal to
Graph Theory
Engineering MathematicsMCQ1 markEasy (estimate)
Q.23 (CS Q.13)
Compute $lim_{x \to 3} \frac{x ^{4} - 81}{2 x ^{2} - 5 x - 3}$
Calculus
DatabasesMCQ1 markEasy (estimate)
Q.24 (CS Q.14)
Which one of the following statements is NOT correct about the B+ tree data structure used for creating an index of a relational database table?
File Organization, B-Trees and B+ Trees Indexing
Theory of ComputationMCQ1 markMedium (estimate)
Q.25 (CS Q.15)
For $Σ = {a, b}$ , let us consider the regular language $L = {x ∣ x = a^{2 + 3 k} or x = b^{10 + 12 k}, k \geq 0}$ . Which one of the following can be a pumping len...
Regular Expressions, Finite Automata and Regular Languages
Computer NetworksMCQ1 markEasy (estimate)
Q.26 (CS Q.16)
Which of the following protocol pairs can be used to send and retrieve e-mails (in that order)?
Application Layer: DNS, HTTP, SMTP, FTP
Operating SystemsNAT1 markEasy (estimate)
Q.27 (CS Q.17)
The following C program is executed on a Unix/Linux system: #include <unistd.h> int main() { int i; for (i = 0; i < 10; i++) if (i % 2 == 0) fork(); return 0; } The tot...
Processes, Threads and System Calls
Programming in CNAT1 markEasy (estimate)
Q.28 (CS Q.18)
Consider the following C program: #include <stdio.h> int jumble(int x, int y){ x = 2 * x + y; return x; } int main(){ int x = 2, y = 5; y = jumble(y, x); x = jumble(y, x);...
Functions, Recursion, Scope and Storage Classes
Compiler DesignNAT1 markMedium (estimate)
Q.29 (CS Q.19)
Consider the grammar given below: $S A B D \to A a \to B D \to b ∣ ϵ \to d ∣ ϵ$ Let $a, b, d,$ and $$$ be indexed...
Parsing and Syntax Analysis (LL and LR)
AlgorithmsNAT1 markMedium (estimate)
Q.30 (CS Q.20)
An array of 25 distinct elements is to be sorted using quicksort. Assume that the pivot element is chosen uniformly at random. The probability that the pivot element gets placed...
Searching and Sorting Algorithms
Engineering MathematicsNAT1 markEasy (estimate)
Q.31 (CS Q.21)
The value of $3^{51} (mod 5)$ is ________.
Monoids and Groups
Engineering MathematicsNAT1 markMedium (estimate)
Q.32 (CS Q.22)
Two numbers are chosen independently and uniformly at random from the set ${1, 2, \dots, 13}$ . The probability (rounded off to 3 decimal places) that their 4-bit (unsigned) bi...
Probability and Statistics
Operating SystemsNAT1 markHard (estimate)
Q.33 (CS Q.23)
Consider three concurrent processes P1, P2 and P3 as shown below, which access a shared variable D that has been initialized to 100. P1 P2 P3 : : : : : : D = D + 20 D = D -...
Process Synchronization and Concurrency
Programming in CNAT1 markEasy (estimate)
Q.34 (CS Q.24)
Consider the following C program: #include <stdio.h> int main(){ int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 5}, *ip = arr + 4; printf("%d\n", ip[1]); return 0; } ...
Pointers, Arrays and Strings
AlgorithmsNAT1 markEasy (estimate)
Q.35 (CS Q.25)
Consider a sequence of 14 elements: $A = [- 5, - 10, 6, 3, - 1, - 2, 13, 4, - 9, - 1, 4, 12, - 3, 0]$ . The subsequence sum $S (i, j) = \sum_{k = i}^{j} A [k]$ . Determine the maximum of…
Divide and Conquer
Programming in CMCQ2 marksMedium (estimate)
Q.36 (CS Q.26)
Consider the following C function. void convert(int n){ if (n < 0) printf("%d", n); else { convert(n / 2); printf("%d", n % 2); } } Which one of the following will happ...
Functions, Recursion, Scope and Storage Classes
Programming in CMCQ2 marksMedium (estimate)
Q.37 (CS Q.27)
Consider the following C program: #include <stdio.h> int r(){ static int num = 7; return num--; } int main(){ for (r(); r(); r()) printf("%d", r()); return 0; } Which o...
Functions, Recursion, Scope and Storage Classes
Computer NetworksMCQ2 marksEasy (estimate)
Q.38 (CS Q.28)
Consider three machines M, N, and P with IP addresses 100.10.5.2, 100.10.5.5, and 100.10.5.6 respectively. The subnet mask is set to 255.255.255.252 for all the three machines....
IPv4/IPv6 Addressing, Subnetting, CIDR, ARP, ICMP and NAT
Computer NetworksMCQ2 marksEasy (estimate)
Q.39 (CS Q.29)
Suppose that in an IP-over-Ethernet network, a machine X wishes to find the MAC address of another machine Y in its subnet. Which one of the following techniques can be used for...
Routing Algorithms (Distance Vector, Link State) and BGP/OSPF
Digital LogicMCQ2 marksMedium (estimate)
Q.40 (CS Q.30)
Consider three 4-variable functions $f_{1}, f_{2},$ and $f_{3}$ , which are expressed in sum-of-minterms as…
Combinational Circuits
Theory of ComputationMCQ2 marksMedium (estimate)
Q.41 (CS Q.31)
Which one of the following languages over $Σ = {a, b}$ is NOT context-free?
Context-Free Grammars, Pushdown Automata and CFLs
DatabasesMCQ2 marksMedium (estimate)
Q.42 (CS Q.32)
Let the set of functional dependencies $F = {QR \to S, R \to P, S \to Q}$ hold on a relation schema $X = (P QR S)$ . $X$ is not in BCNF. Suppose $X$ is decomposed into two schema...
Functional Dependencies and Normalization
Operating SystemsMCQ2 marksMedium (estimate)
Q.43 (CS Q.33)
Assume that in a certain computer, the virtual addresses are 64 bits long and the physical addresses are 48 bits long. The memory is word addressable. The page size is 8 kB and...
Memory Management and Virtual Memory
Theory of ComputationMCQ2 marksMedium (estimate)
Q.44 (CS Q.34)
Consider the following sets: $S_{1}$ : Set of all recursively enumerable languages over the alphabet ${0, 1}$ $S_{2}$ : Set of all syntactically valid C programs $S_{3}$ : Set of all l...
Decidability, Reducibility and Undecidability
Engineering MathematicsMCQ2 marksMedium (estimate)
Q.45 (CS Q.35)
Consider the first order predicate formula $φ$ …
Propositional and First-Order Logic
Compiler DesignMCQ2 marksMedium (estimate)
Q.46 (CS Q.36)
Consider the following grammar and the semantic actions to support the inherited type declaration attributes. Let $X_{1}, X_{2}, X_{3}, X_{4}, X_{5},$ and $X_{6}$ be the placeholders for th...
Syntax-Directed Translation
AlgorithmsMCQ2 marksMedium (estimate)
Q.47 (CS Q.37)
There are $n$ unsorted arrays: $A_{1}, A_{2}, \dots, A_{n}$ . Assume that $n$ is odd. Each of $A_{1}, A_{2}, \dots, A_{n}$ contains $n$ distinct elements. There are no common elements betwee...
Divide and Conquer
AlgorithmsMCQ2 marksMedium (estimate)
Q.48 (CS Q.38)
Let $G$ be any connected, weighted, undirected graph. I. $G$ has a unique minimum spanning tree, if no two edges of $G$ have the same weight. II. $G$ has a unique minimum spanni...
Greedy Algorithms
Operating SystemsMCQ2 marksMedium (estimate)
Q.49 (CS Q.39)
Consider the following snapshot of a system running $n$ concurrent processes. Process $i$ is holding $X_{i}$ instances of a resource $R$ , $1 \leq i \leq n$ . Assume that all instance...
Process Synchronization and Concurrency
Data StructuresMCQ2 marksMedium (estimate)
Q.50 (CS Q.40)
Consider the following statements: I. The smallest element in a max-heap is always at a leaf node II. The second largest element in a max-heap is always a child of the root node...
Binary Heaps and Priority Queues
Operating SystemsNAT2 marksMedium (estimate)
Q.51 (CS Q.41)
Consider the following four processes with arrival times (in milliseconds) and their length of CPU bursts (in milliseconds) as shown below: | Process | Arrival time | CPU burst...
CPU Scheduling
Operating SystemsNAT2 marksMedium (estimate)
Q.52 (CS Q.42)
The index node (inode) of a Unix-like file system has 12 direct, one single-indirect and one double-indirect pointers. The disk block size is $4 kB$ , and the disk block a...
File Systems, I/O and Disk Scheduling
Compiler DesignNAT2 marksMedium (estimate)
Q.53 (CS Q.43)
Consider the augmented grammar given below: $S^{'} S L \to S \to ⟨ L ⟩ ∣ id \to L, S ∣ S$ Let…
Parsing and Syntax Analysis (LL and LR)
Engineering MathematicsNAT2 marksMedium (estimate)
Q.54 (CS Q.44)
Consider the following matrix: $R = 1111234549162582764125$ The absolute value of the product of...
Linear Algebra
Computer Organization and ArchitectureNAT2 marksMedium (estimate)
Q.55 (CS Q.45)
A certain processor deploys a single-level cache. The cache block size is 8 words and the word size is 4 bytes. The memory system uses a 60-MHz clock. To service a cache miss, t...
Memory Hierarchy: Cache, Main Memory and Secondary Storage
Data StructuresNAT2 marksMedium (estimate)
Q.56 (CS Q.46)
Let $T$ be a full binary tree with 8 leaves. (A full binary tree has every level full.) Suppose two leaves $a$ and $b$ of $T$ are chosen uniformly and independently at random. T...
Binary Trees, Binary Search Trees and Balanced Trees
Engineering MathematicsNAT2 marksMedium (estimate)
Q.57 (CS Q.47)
Suppose $Y$ is distributed uniformly in the open interval $(1, 6)$ . The probability that the polynomial $3 x^{2} + 6 x Y + 3 Y + 6$ has only real roots is (rounded off to 1 decimal pl...
Probability and Statistics
Theory of ComputationNAT2 marksHard (estimate)
Q.58 (CS Q.48)
Let $Σ$ be the set of all bijections from ${1, \dots, 5}$ to ${1, \dots, 5}$ , where $i d$ denotes the identity function, i.e. $i d (j) = j, \forall j$ . Let $\circ$ deno...
Regular Expressions, Finite Automata and Regular Languages
Computer NetworksNAT2 marksMedium (estimate)
Q.59 (CS Q.49)
Consider that 15 machines need to be connected in a LAN using 8-port Ethernet switches. Assume that these switches do not have any separate uplink ports. The minimum number of s...
Medium Access Control (ALOHA, CSMA/CD) and Ethernet/Switching · OSI/TCP-IP Layering, Physical Layer and Switching
Digital LogicNAT2 marksMedium (estimate)
Q.60 (CS Q.50)
What is the minimum number of 2-input NOR gates required to implement a 4-variable function expressed in sum-of-minterms form as $f = \sum (0, 2, 5, 7, 8, 10, 13, 15)$ ? Assume t...
Boolean Algebra and Logic Minimization
DatabasesNAT2 marksMedium (estimate)
Q.61 (CS Q.51)
A relational database contains two tables Student and Performance as shown below: Student | Roll_no. | Student_name | | :--- | :--- | | 1 | Amit | | 2 | Priya | | 3 | Vi...
SQL Queries and Integrity Constraints
Programming in CNAT2 marksEasy (estimate)
Q.62 (CS Q.52)
Consider the following C program: #include <stdio.h> int main() { float sum = 0.0, j = 1.0, i = 2.0; while (i/j > 0.0625) { j = j + j; sum = sum + i/j; printf("%f\n", sum);...
Data Types, Operators and Control Flow
Programming in CNAT2 marksEasy (estimate)
Q.63 (CS Q.53)
Consider the following C program: #include <stdio.h> int main() { int a[] = {2, 4, 6, 8, 10}; int i, sum = 0, *b = a + 4; for (i = 0; i < 5; i++) sum = sum + (*b - i) - *(b...
Pointers, Arrays and Strings
Computer NetworksNAT2 marksEasy (estimate)
Q.64 (CS Q.54)
In an RSA cryptosystem, the value of the public modulus parameter $n$ is 3007. If it is also known that $ϕ (n) = 2880$ , where $ϕ ()$ denotes Euler's Totient Function, then t...
Application Layer: DNS, HTTP, SMTP, FTP · Sets, Relations, Functions, Partial Orders and Lattices
DatabasesNAT2 marksMedium (estimate)
Q.65 (CS Q.55)
Consider the following relations $P (X, Y, Z)$ , $Q (X, Y, T)$ and $R (Y, V)$ : P | X | Y | Z | | :--- | :--- | :--- | | X1 | Y1 | Z1 | | X1 | Y1 | Z2 | | X2 | Y2 | Z2 | | X2 | Y...
Relational Algebra and Tuple Relational Calculus