GATE CS 2021_Set1 Question Paper with Solutions: 65 Questions, Answer Key & Section-wise Analysis

GATE CS 2021_Set1 previous year paper: 65 questions with answer key and detailed solutions, section-wise breakdown and free sample questions.

Paper breakdown

65 questions · 100 marks. Engineering Mathematics: 12 · Algorithms: 7 · Theory of Computation: 5 · Programming and Data Structures: 5 · Operating System: 5 · Databases: 5 · Computer Networks: 5 · Compiler Design: 5 · Computer Organization and Architecture: 4 · Quantitative Aptitude: 3 · Digital Logic: 3 · Verbal Aptitude: 2 · Spatial Aptitude: 2 · Analytical Aptitude: 2

Free sample questions from GATE CS 2021_Set1 Question Paper

Question 1 · Engineering Mathematics · 2021_Set1 MCQ

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

S_{2} : q \to (\neg p \land (p \lor q))

Which one of the following choices is correct?

A.
Both $S_{1}$ and $S_{2}$ are tautologies.
B.
$S_{1}$ is a tautology but $S_{2}$ is not a tautology.
C.
$S_{1}$ is not a tautology but $S_{2}$ is a tautology.
D.
Neither $S_{1}$ nor $S_{2}$ is a tautology.

Correct Answer:

Step-by-Step Solution

Key idea: This is a tautology checking question, recognizable because it asks to classify propositional formulae as tautologies. We can simplify the expressions algebraically using logical equivalences.

Step 1: Simplify the common subexpression.

Both $S_{1}$ and $S_{2}$ contain the term $(\neg p \land (p \lor q))$ .

Using the Distributive Law:

$\neg p \land (p \lor q) \equiv (\neg p \land p) \lor (\neg p \land q)$

Since $(\neg p \land p)$ is a contradiction (False):

$\equiv F \lor (\neg p \land q) \equiv \neg p \land q$ .

Step 2: Analyze $S_{1}$ .

$S_{1} : (\neg p \land q) \to q$

Using the Implication Law ( $A \to B \equiv \neg A \lor B$ ):

$\equiv \neg (\neg p \land q) \lor q$

Using De Morgan's Law:

$\equiv (p \lor \neg q) \lor q$

Using Associative Law:

$\equiv p \lor (\neg q \lor q)$

Since $(\neg q \lor q)$ is a tautology (True):

$\equiv p \lor T \equiv T$ .

Since $S_{1}$ simplifies to True for all values of $p$ and $q$ , $S_{1}$ is a tautology.

Step 3: Analyze $S_{2}$ .

$S_{2} : q \to (\neg p \land q)$

Using the Implication Law:

$\equiv \neg q \lor (\neg p \land q)$

Using the Distributive Law in reverse:

$\equiv (\neg q \lor \neg p) \land (\neg q \lor q)$

$\equiv (\neg q \lor \neg p) \land T \equiv \neg q \lor \neg p$ .

This expression is not always true (e.g., if $p = T$ and $q = T$ , it evaluates to $F \lor F = F$ ).

Therefore, $S_{2}$ is not a tautology (it is a contingency).

Step 4: Conclusion.

$S_{1}$ is a tautology, but $S_{2}$ is not.

Answer: B

Question 2 · Engineering Mathematics · 2021_Set1 MCQ

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 ___________

A.
0.3024
B.
0.4235
C.
0.6976
D.
0.8125

Correct Answer:

Step-by-Step Solution

Insight: "at least two identical" is the complement of "all distinct", so count the distinct case and subtract from 1.

Exam route:

Total ways to pick one chocolate from each of 5 bags = $1 0^{5} = 100, 000$ .

Ways to get all 5 chocolates distinct (slot-filling) = $10 \times 9 \times 8 \times 7 \times 6 = 30, 240$ .

$P (all distinct) = \frac{30 , 240}{100 , 000} = 0.3024$ .

$P (at least two identical) = 1 - 0.3024 = 0.6976$ .

Learning route:

This is a complementary-counting question, signalled by the phrase "at least two".

Step 1 — Build the sample space. Each bag is independent and has 10 distinct chocolates, so picking one from each of 5 bags gives $1 0^{5}$ equally likely outcomes.

Step 2 — Count the complementary event. "All distinct" means no two of the five picked chocolates share a label. The first pick has 10 choices, the second must avoid the first (9 choices), the third avoids the first two (8 choices), and so on: $10 \times 9 \times 8 \times 7 \times 6 = 30, 240$ .

Step 3 — Subtract from 1. $P (at least two identical) = 1 - \frac{30 , 240}{100 , 000} = 1 - 0.3024 = 0.6976$ .

Wrong path: If you forget to complement, you land on 0.3024 (option A), which is the probability that all are distinct — the exact opposite of what is asked.

Verification: $0.6976 + 0.3024 = 1.0000$ , so the two complementary events partition the sample space correctly.

Question 3 · Engineering Mathematics · 2021_Set1 NAT

In an undirected connected planar graph $G$ , there are eight vertices and five faces. The number of edges in $G$ is __________.

Correct Answer:

11.00

Step-by-Step Solution

Insight: Euler's formula for connected planar graphs directly relates vertices, edges, and faces.

Exam route: $V - E + F = 2 ⟹ 8 - E + 5 = 2 ⟹ E = 11$ .

Learning route:

Step 1: Identify the graph properties. The graph is undirected, connected, and planar.

Step 2: Recall Euler's formula for connected planar graphs: $V - E + F = 2$ .

Step 3: Substitute the given values. We have $V = 8$ vertices and $F = 5$ faces (including the outer face).

Step 4: Solve for $E$ :

$8 - E + 5 = 2$

$13 - E = 2$

$E = 11$ .

Question 4 · Algorithms · 2021_Set1 MCQ

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 values in an arbitrary array of $n$ elements. Which one of the following choices is correct?

A.
$t > 2 n - 2$
B.
$t > 3 ⌈ \frac{n}{2} ⌉$ and $t \leq 2 n - 2$
C.
$t > n$ and $t \leq 3 ⌈ \frac{n}{2} ⌉$
D.
$t > ⌈ lo g_{2} (n) ⌉$ and $t \leq n$

Correct Answer:

Step-by-Step Solution

Key idea: This is a comparison bounds question, recognisable because it asks for the lowest upper bound on the number of comparisons required to find both the minimum and maximum values simultaneously.

Step 1: The naive approach finds the minimum in $n - 1$ comparisons and the maximum in another $n - 1$ comparisons, totaling $2 n - 2$ comparisons.

Step 2: The optimal approach processes elements in pairs. Divide the $n$ elements into $⌈ n /2 ⌉$ pairs.

Step 3: Compare the two elements within each pair. This takes $⌈ n /2 ⌉$ comparisons and yields a local minimum and a local maximum for each pair.

Step 4: Find the global minimum by comparing the $⌈ n /2 ⌉$ local minimums. This takes $⌈ n /2 ⌉ - 1$ comparisons.

Step 5: Find the global maximum by comparing the $⌈ n /2 ⌉$ local maximums. This takes $⌈ n /2 ⌉ - 1$ comparisons.

Step 6: Total comparisons $t = ⌈ n /2 ⌉ + 2 (⌈ n /2 ⌉ - 1) = 3 ⌈ n /2 ⌉ - 2$ .

Step 7: This value is strictly less than or equal to $3 ⌈ n /2 ⌉$ . For $n \geq 3$ (with the minor exception of $n = 4$ where it equals $n$ ), it is greater than $n$ . Among the choices, Option C is the only one that correctly bounds the optimal count from above by $3 ⌈ n /2 ⌉$ and generally satisfies the lower bound for meaningful array sizes.

Answer: C

Question 5 · Algorithms · 2021_Set1 MCQ

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 increasing order of asymptotic growth rate?

A.
$f_{3}, f_{2}, f_{1}$
B.
$f_{2}, f_{1}, f_{3}$
C.
$f_{1}, f_{2}, f_{3}$
D.
$f_{2}, f_{3}, f_{1}$

Correct Answer:

Step-by-Step Solution

Key idea: This is a function growth comparison question, recognizable because it asks to order three functions by asymptotic growth rate.

Why this method applies: When comparing functions with variables in both the base and the exponent, taking the logarithm of all functions preserves their relative order and simplifies the expressions into comparable polynomial/logarithmic forms.

Step 1: Take the base-2 logarithm of each function.

$lo g f_{1} = lo g (1 0^{n}) = n lo g 10 = Θ (n)$ .

$lo g f_{2} = lo g (n^{l o g n}) = (lo g n) (lo g n) = (lo g n)^{2}$ .

$lo g f_{3} = lo g (n^{n}) = n lo g n$ .

Step 2: Compare the growth rates of the logarithms.

We need to order $(lo g n)^{2}$ , $n lo g n$ , and $n$ .

Divide all three by $lo g n$ (valid since $lo g n > 0$ for large $n$ ):

We get $lo g n$ , $n$ , and $\frac{n}{l o g n}$ .

Step 3: Apply the standard hierarchy of growth rates.

It is a well-known fact that $lo g n ≪ n ≪ \frac{n}{l o g n}$ .

Therefore, multiplying back by $lo g n$ , we have $(lo g n)^{2} ≪ n lo g n ≪ n$ .

Step 4: Since the logarithms are ordered as $lo g f_{2} ≪ lo g f_{3} ≪ lo g f_{1}$ , the original functions follow the exact same order: $f_{2} ≪ f_{3} ≪ f_{1}$ .

Answer: Option D is correct.

Question 6 · Algorithms · 2021_Set1 MCQ

Consider the following array.

Which algorithm out of the following options uses the least number of comparisons (among the array elements) to sort the above array in ascending order?

A.
Selection sort
B.
Mergesort
C.
Insertion sort
D.
Quicksort using the last element as pivot

Correct Answer:

Step-by-Step Solution

Key idea: This is a sorting algorithm operation counting question, recognisable because it provides a specific array and asks which algorithm uses the least number of comparisons. The added layer is recognizing the initial state of the array.

Step 1: Observe the given array: $[23, 32, 45, 69, 72, 73, 89, 97]$ .

Step 2: Notice that the array is already sorted in ascending order. Let $n = 8$ .

Step 3: Evaluate each option for an already sorted array:

Selection sort: Always performs $\frac{n ( n - 1 )}{2}$ comparisons regardless of input order. For $n = 8$ , this is $\frac{8 \times 7}{2} = 28$ comparisons.
Mergesort: Always performs $Θ (n lo g n)$ comparisons. For $n = 8$ , it is around $8 \times 3 = 24$ comparisons (specifically, 17 to 21 depending on implementation).
Insertion sort: For an already sorted array, the inner loop condition fails immediately on the first check for each element. It performs exactly $n - 1$ comparisons. For $n = 8$ , this is $7$ comparisons.
Quicksort (last element as pivot): For an already sorted array, this is the worst-case scenario. It performs $\frac{n ( n - 1 )}{2}$ comparisons. For $n = 8$ , this is 28 comparisons.

Step 4: Compare the counts: $7$ (Insertion) is the least.

Answer: C

Question 7 · Theory of Computation · 2021_Set1 MCQ

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?

A.
$L_{1} \cap L_{2}$
B.
$L_{1} \cdot L_{2}$
C.
$L_{1} - L_{2}$
D.
$L_{1} \cup L_{2}$

Correct Answer:

Step-by-Step Solution

Key idea: This is a closure properties question involving the interaction between Regular and Context-Free Languages (CFLs), recognizable because it asks which operation does NOT preserve the CFL property.

Step 1: Recall the closure properties of CFLs. CFLs are closed under union, concatenation, Kleene star, and intersection with Regular languages.

Step 2: Evaluate Option A: $L_{1} \cap L_{2}$ . Since $L_{1}$ is regular and $L_{2}$ is CFL, their intersection is guaranteed to be CFL.

Step 3: Evaluate Option B: $L_{1} \cdot L_{2}$ . Since Regular languages are a subset of CFLs, this is the concatenation of two CFLs, which is always CFL.

Step 4: Evaluate Option D: $L_{1} \cup L_{2}$ . The union of a regular language and a CFL is always CFL.

Step 5: Evaluate Option C: $L_{1} - L_{2}$ . By definition, $L_{1} - L_{2} = L_{1} \cap \overline{L_{2}}$ . If this were always CFL, then by choosing $L_{1} = Σ^{*}$ (which is regular), we would have $Σ^{*} \cap \overline{L_{2}} = \overline{L_{2}}$ is always CFL. This would mean CFLs are closed under complement, which is false. Thus, $L_{1} - L_{2}$ is NOT necessarily CFL.

Answer: C

Question 8 · Theory of Computation · 2021_Set1 MSQ

Let $⟨ M ⟩$ denote an encoding of an automaton $M$ . Suppose that $Σ = {0, 1}$ . Which of the following languages is/are NOT recursive?

A.
$L = {⟨ M ⟩ ∣ M is a DFA such that L (M) = \emptyset}$
B.
$L = {⟨ M ⟩ ∣ M is a DFA such that L (M) = Σ^{*}}$
C.
$L = {⟨ M ⟩ ∣ M is a PDA such that L (M) = \emptyset}$
D.
$L = {⟨ M ⟩ ∣ M is a PDA such that L (M) = Σ^{*}}$

Question 9 · Theory of Computation · 2021_Set1 MCQ

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

Correct Answer:

Step-by-Step Solution

Key idea: This is a DFA design question for a specific suffix pattern, recognizable by the "ends with" phrasing. The core method is tracking the longest suffix of the input that matches a prefix of the target pattern.

Step 1: Define the target pattern. We want strings ending in "011". The states must remember how much of "011" we have successfully matched at the end of the string read so far.

Step 2: Define the states based on the longest matched suffix:

$q_{0}$ : Start state. No part of "011" matched (or the string ends in '1' but not '01' or '011').
$q_{1}$ : The string ends in "0".
$q_{2}$ : The string ends in "01".
$q_{3}$ : The string ends in "011". This is the only final state.

Step 3: Determine transitions strictly using the longest suffix rule:

From $q_{0}$ : reading '0' gives suffix "0" $\to q_{1}$ . Reading '1' gives suffix "1" (no prefix match) $\to q_{0}$ .
From $q_{1}$ (ends in "0"): reading '0' gives "00", longest suffix matching prefix is "0" $\to q_{1}$ . Reading '1' gives "01" $\to q_{2}$ .
From $q_{2}$ (ends in "01"): reading '0' gives "010", longest matching prefix is "0" $\to q_{1}$ . Reading '1' gives "011" $\to q_{3}$ .
From $q_{3}$ (ends in "011"): reading '0' gives "0110", longest matching prefix is "0" $\to q_{1}$ . Reading '1' gives "0111", longest matching prefix is $ϵ$ $\to q_{0}$ .

Step 4: Match this logic to the given options. Option C is the only diagram that correctly routes $q_{3}$ on '1' back to $q_{0}$ and $q_{3}$ on '0' to $q_{1}$ , avoiding the trap of accepting "0111" or "011011".

Answer: C

Question 10 · Programming and Data Structures · 2021_Set1 MCQ

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$ ?

A.
$Θ (n lo g n)$
B.
$Θ (n)$
C.
$Θ (lo g n)$
D.
$Θ (1)$

Correct Answer:

Step-by-Step Solution

Insight: This is a BST complexity trick question, recognizable because it asks for the time complexity of finding "an element" smaller than the maximum, not a specific element like the second maximum.

Exam route: The maximum element in a BST is the rightmost node. We need ANY element smaller than it. If the root has a right child, the root itself is strictly smaller than the maximum (which is in the right subtree). If the root has no right child, the root IS the maximum, but since $n$ is distinct and presumably $n \geq 2$ , the root must have a left child, which is strictly smaller. In either case, we can pick a valid element by inspecting only the root and its immediate children. This takes $Θ (1)$ time.

Learning route:

Step 1: Understand the goal. We need to find ANY element in the BST that is strictly less than the maximum element. We do not need to find the second largest, just any valid candidate.

Step 2: Identify the maximum element. In a BST, the maximum is always the rightmost node.

Step 3: Consider the root node. There are two cases for the root:

Case A: The root has a right child. This means the maximum element is somewhere in the right subtree. Therefore, the root's value is strictly less than the maximum. We can simply pick the root.
Case B: The root has no right child. This means the root itself is the maximum element. However, since the tree has $n$ distinct elements (and for the question to be meaningful, $n \geq 2$ ), the root must have a left child. The left child's value is strictly less than the root (the maximum). We can simply pick the left child.

Step 4: Analyze the time complexity. In both cases, we only need to check the root and at most one of its immediate children (the right child, or if null, the left child). This requires a constant number of pointer dereferences.

Step 5: Conclude. The time complexity is $Θ (1)$ .

Wrong path: Assuming we must find the exact "second maximum" element (the inorder predecessor of the max), which would take $O (h)$ or $O (lo g n)$ time in a balanced tree, leading to Option C. Or assuming we must traverse the whole tree, leading to Option B.

Question 11 · Programming and Data Structures · 2021_Set1 NAT

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 empty queue.

enqueue(21); enqueue(24); dequeue(); enqueue(28); enqueue(32); q = dequeue();

The value of s + q is __________.

Correct Answer:

86.00

Step-by-Step Solution

Insight: This is a data structure simulation question, recognizable because it provides a sequence of standard stack (LIFO) and queue (FIFO) operations and asks for the final extracted values.

Exam route: Trace the stack to find s=62, trace the queue to find q=24, and sum them to get 86.

Learning route:

Step 1: Simulate the stack operations. The stack starts empty.

push(54): Stack is [54]
push(52): Stack is [54, 52]
pop(): Removes 52. Stack is [54]
push(55): Stack is [54, 55]
push(62): Stack is [54, 55, 62]
s = pop(): Removes and assigns 62 to s. Stack is [54, 55]. So, s = 62.

Step 2: Simulate the queue operations. The queue starts empty.

enqueue(21): Queue is [21]
enqueue(24): Queue is [21, 24]
dequeue(): Removes 21. Queue is [24]
enqueue(28): Queue is [24, 28]
enqueue(32): Queue is [24, 28, 32]
q = dequeue(): Removes and assigns 24 to q. Queue is [28, 32]. So, q = 24.

Step 3: Calculate the final value. s + q = 62 + 24 = 86.

Question 12 · Programming and Data Structures · 2021_Set1 MCQ

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;
    }
    count = count + i;
    printf("%d", count);
    return 0;
}

Which one of the following options is correct?

A.
The program will not compile successfully.
B.
The program will compile successfully and output 10 when executed.
C.
The program will compile successfully and output 8 when executed.
D.
The program will compile successfully and output 13 when executed.

Correct Answer:

Step-by-Step Solution

Insight: This is a short-circuit evaluation question with a post-increment side effect hidden inside the loop condition.

Exam route: Build a 7-row trace table. The key pivot is that && skips i++ entirely when j < 0, and at j=0 the post-increment returns 0 (false) so the body is skipped but i still increments.

Learning route:

Initialize: count = 0, i = 0.
For j = -3, -2, -1: (j >= 0) is false. Short-circuit skips (i++). Neither the body nor the increment runs. i stays 0, count stays 0.
For j = 0: (j >= 0) is true, so (i++) is evaluated. Post-increment returns the old value 0, which is falsy. The overall condition is false. Body is skipped. But the side effect fires: i becomes 1. count stays 0.
For j = 1: (i++) returns 1 (truthy). Body runs: count = 0 + 1 = 1. Side effect: i becomes 2.
For j = 2: (i++) returns 2 (truthy). Body runs: count = 1 + 2 = 3. Side effect: i becomes 3.
For j = 3: (i++) returns 3 (truthy). Body runs: count = 3 + 3 = 6. Side effect: i becomes 4.
After loop: count = count + i = 6 + 4 = 10.

Wrong path producing 13: A student who ignores short-circuit evaluation assumes i++ runs for all 7 values of j, making i = 7. They also incorrectly add negative j values. This is wrong because && guarantees the right operand is never evaluated when the left is false.

Wrong path producing 8: A student who forgets that post-increment still fires at j=0 (even though the body is skipped) would compute final i = 3 instead of 4, yielding 6 + 3 = 9 or possibly miscount the body executions.

Verification: Body executes for j = 1, 2, 3, accumulating $1 + 2 + 3 = 6$ . The increment i++ fires 4 times (at j = 0, 1, 2, 3), so final i = 4. Total $= 6 + 4 = 10$ . Confirmed.

Generalization: In any A && B condition, if A is false, B (including all its side effects) is completely skipped. Track the boolean test value and the post-side-effect value of any incremented variable as separate columns.

Question 13 · Operating System · 2021_Set1 MSQ

In the context of operating systems, which of the following statements is/are correct with respect to paging?

A.
Paging helps solve the issue of external fragmentation.
B.
Page size has no impact on internal fragmentation.
C.
Paging incurs memory overheads.
D.
Multi-level paging is necessary to support pages of different sizes.

Question 14 · Operating System · 2021_Set1 MSQ

Which of the following standard C library functions will <i>always</i> invoke a system call when executed from a single-threaded process in a UNIX/Linux operating system?

A.
exit
B.
malloc
C.
sleep
D.
strlen

Question 15 · Operating System · 2021_Set1 MSQ

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, such as the list of pointers to the data blocks. Consider a given directory foo.
Which of the following operations will necessarily require a full scan of foo for successful completion?

A.
Creation of a new file in foo
B.
Deletion of an existing file from foo
C.
Renaming of an existing file in foo
D.
Opening of an existing file in foo

Question 16 · Databases · 2021_Set1 MSQ

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 recovery.
Which of the following statements is/are correct?

A.
The same undo and redo list will be used while recovering again.
B.
The system cannot recover any further.
C.
All the transactions that are already undone and redone will not be recovered again.
D.
The database will become inconsistent.

Question 17 · Databases · 2021_Set1 NAT

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 to 20. Assume that the attributes

A

and

B

are independently distributed.

The estimated number of tuples in the output of

σ_{(A > 10) \lor (B = 18)} (r)

is __________.

Question 18 · Databases · 2021_Set1 MCQ

The following relation records the age of 500 employees of a company, where empNo (indicating the employee number) is the key:

empAge (\underline{empNo}, age)

Consider the following relational algebra expression:

Π_{empNo} (empAge ⋈_{(age > age1)} ρ_{empNo1, age1} (empAge))

What does the above expression generate?

A.
Employee numbers of only those employees whose age is the maximum.
B.
Employee numbers of only those employees whose age is more than the age of exactly one other employee.
C.
Employee numbers of all employees whose age is not the minimum.
D.
Employee numbers of all employees whose age is the minimum.

Question 19 · Computer Networks · 2021_Set1 MCQ

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 address.

Which one of the following choices is correct?

A.
Both $S_{1}$ and $S_{2}$ are true.
B.
$S_{1}$ is true and $S_{2}$ is false.
C.
$S_{1}$ is false and $S_{2}$ is true.
D.
Both $S_{1}$ and $S_{2}$ are false.

Question 20 · Computer Networks · 2021_Set1 MCQ

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 given in the following tables:

Data bits
$d_{8}$	$d_{7}$	$d_{6}$	$d_{5}$	$d_{4}$	$d_{3}$	$d_{2}$	$d_{1}$
1	1	0	$x$	0	1	0	1

Check bits
$c_{8}$	$c_{4}$	$c_{2}$	$c_{1}$
$y$	0	1	0

Which one of the following choices gives the correct values of

x

and

y

A.
$x$ is 0 and $y$ is 0.
B.
$x$ is 0 and $y$ is 1.
C.
$x$ is 1 and $y$ is 0.
D.
$x$ is 1 and $y$ is 1.

Question 21 · Computer Networks · 2021_Set1 MSQ

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 connection was active, the server machine

S

crashed and rebooted. Assume that the client does not use the TCP keepalive timer.
Which of the following behaviors is/are possible?

A.
If the client was waiting to receive a packet, it may wait indefinitely.
B.
The TCP server application on $S$ can listen on $P$ after reboot.
C.
If the client sends a packet after the server reboot, it will receive a RST segment.
D.
If the client sends a packet after the server reboot, it will receive a FIN segment.

Question 22 · Compiler Design · 2021_Set1 MCQ

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 corresponds to a postorder traversal of the activation tree.

Which one of the following options is correct?

A.
$S_{1}$ is true and $S_{2}$ is false
B.
$S_{1}$ is false and $S_{2}$ is true
C.
$S_{1}$ is true and $S_{2}$ is true
D.
$S_{1}$ is false and $S_{2}$ is false

Question 23 · Compiler Design · 2021_Set1 MCQ

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, there is a parser that takes at most

O (n^{3})

time to parse a string of length

n

.

Which one of the following options is correct?

A.
$S_{1}$ is true and $S_{2}$ is false
B.
$S_{1}$ is false and $S_{2}$ is true
C.
$S_{1}$ is true and $S_{2}$ is true
D.
$S_{1}$ is false and $S_{2}$ is false

Question 24 · Compiler Design · 2021_Set1 MCQ

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:

P D D E E E \to D^{*} E^{*} \to int ID {record that ID.lexeme is of type int} \to bool ID {record that ID.lexeme is of type bool} \to E_{1} + E_{2} {check that E_{1} . type = E_{2} . type = int; set E . type := int} \to! E_{1} {check that E_{1} . type = bool; set E . type := bool} \to ID {set E . type := int}

With respect to the above grammar, which one of the following choices is correct?

A.
The actions can be used to correctly type-check any syntactically correct program.
B.
The actions can be used to type-check syntactically correct integer variable declarations and integer expressions.
C.
The actions can be used to type-check syntactically correct boolean variable declarations and boolean expressions.
D.
The actions will lead to an infinite loop.

Correct Answer:

Step-by-Step Solution

Key idea: Trace the syntax-directed translation (SDT) actions to see what types are actually supported and checked.

Step 1: Look at the declaration rules. The grammar allows declaring variables as int or bool and records them in the symbol table.

Step 2: Look at the expression rules. The rule E -> ID has the action {set E.type := int}. It hardcodes the type to int and completely ignores the symbol table lookup.

Step 3: Because E -> ID always returns int, any boolean variable used in an expression will be incorrectly treated as an integer. Therefore, the SDT cannot correctly type-check any program (Option A is false) and cannot type-check boolean expressions (Option C is false).

Step 4: The SDT does not contain any recursive or cyclic dependencies that would cause an infinite loop (Option D is false).

Step 5: Since the expression rules only support int (e.g., E1 + E2 checks for int), the SDT can only successfully type-check integer variable declarations and integer expressions.

Answer: B

Question 25 · Computer Organization and Architecture · 2021_Set1 NAT

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 (1 KB =

2^{10}

bytes), and each cache block is of size 64 bytes.
The size of the tag field is __________ bits.

Correct Answer:

17.00

Step-by-Step Solution

Insight: This is a direct address-decomposition question — split the 32-bit address into Tag, Index, Offset using cache size and block size.

Exam route:

Cache = 32 KB = $2^{15}$ B, Block = 64 B = $2^{6}$ B.
Lines = $2^{15} / 2^{6} = 2^{9} = 512$ .
Index = $lo g_{2} (512) = 9$ bits.
Offset = $lo g_{2} (64) = 6$ bits.
Tag = $32 - 9 - 6 = 17$ bits.

Learning route:

This is a standard address-decomposition question, recognisable because the problem gives cache size, block size, and address width and asks for the tag field size.

In a direct-mapped cache every physical address is split into three contiguous fields: Tag | Index | Offset.

The Offset selects the byte within a block. Block = 64 B, so Offset = $lo g_{2} (64) = 6$ bits.
The Index selects the cache line. Number of lines = Cache / Block = $2^{15} / 2^{6} = 2^{9} = 512$ . So Index = $lo g_{2} (512) = 9$ bits.
The Tag is whatever remains: Tag = $32 - 9 - 6 = 17$ bits.

The main memory size ( $2^{32}$ B) is consistent with the 32-bit address but is not needed for the calculation — only cache size, block size, and address width matter.

Verification: Tag + Index + Offset = $17 + 9 + 6 = 32$ ✓.

Answer: 17

Question 26 · Computer Organization and Architecture · 2021_Set1 NAT

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

and

F

denote the sign, exponent and fraction components of the floating point representation.

The decimal value corresponding to the above representation (rounded to 2 decimal places) is __________.

Correct Answer:

-7.75

Step-by-Step Solution

Key idea: This is an IEEE 754 single-precision decoding question, recognisable because it gives $S$ , $E$ , $F$ fields and asks for the decimal value.

Step 1: Identify the fields. $S = 1$ (negative), $E = 1000000 1_{2}$ , $F = 1111000000000000000000 0_{2}$ .

Step 2: Compute the exponent. $E = 1000000 1_{2} = 129$ . True exponent $= 129 - 127 = 2$ .

Step 3: Compute the significand. Since $0 < E < 255$ , this is normalized. The implicit leading $1$ gives:

$1. F = 1.111 1_{2} = 1 + \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \frac{1}{16} = \frac{31}{16} = 1.9375$

Step 4: Apply the formula:

$V = (- 1)^{S} \times 1. F \times 2^{E - 127} = (- 1)^{1} \times 1.9375 \times 2^{2} = - 1.9375 \times 4 = - 7.75$

Step 5: Rounded to 2 decimal places: $- 7.75$ .

Answer: -7.75

Question 27 · Computer Organization and Architecture · 2021_Set1 NAT

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 total time to execute 100 independent instructions on this pipeline, assuming there are no pipeline stalls, is __________ nanoseconds.

Correct Answer:

17160

Step-by-Step Solution

Key idea: This is a pipeline execution time calculation, recognisable because it provides stage delays, register delays, and a number of instructions, asking for total execution time with no stalls.

Step 1: The pipeline clock cycle is determined by the slowest stage, because every stage must complete within one clock period. Find the maximum stage delay: $max (150, 120, 150, 160, 140) = 160$ ns.

Step 2: Add the pipeline register delay to get the cycle time. Each pipeline register sits between stages and adds overhead. Cycle time $= 160 + 5 = 165$ ns.

Step 3: Use the pipeline execution time formula for $n$ instructions on a $k$ -stage pipeline with no stalls: $T = (k + n - 1) \times cycle time$ .

Step 4: Substitute $k = 5$ , $n = 100$ : $T = (5 + 100 - 1) \times 165 = 104 \times 165$ .

Step 5: Compute $104 \times 165 = 104 \times 100 + 104 \times 65 = 10400 + 6760 = 17160$ ns.

Answer: 17160

Question 28 · Quantitative Aptitude · 2021_Set1 MCQ

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:

A.
21
B.
37
C.
50
D.
73

Correct Answer:

Step-by-Step Solution

Insight: The total quantity must be a multiple of the sum of the ratio parts.

Exam route: Ratio is 7:3. Sum of parts = 10. Total students must be a multiple of 10. Among the options, only 50 is a multiple of 10.

Learning route:

Step 1: Let the number of boys be $7 k$ and girls be $3 k$ .

Step 2: Total students $= 7 k + 3 k = 10 k$ .

Step 3: Since $k$ must be an integer (you cannot have a fraction of a student), the total number of students must be a multiple of 10.

Step 4: Check the options: 21, 37, 50, 73. Only 50 is divisible by 10.

Trap warning: Students might just look for a multiple of 7 or 3 individually. The sum of the parts is the key invariant.

Verification: If total is 50, $k = 5$ . Boys = 35, Girls = 15. Ratio = 35:15 = 7:3. Matches perfectly.

Question 29 · Quantitative Aptitude · 2021_Set1 MCQ

We have 2 rectangular sheets of paper, M and N, of dimensions 6 cm x 1 cm each. Sheet M is rolled to form an open cylinder by bringing the short edges of the sheet together. Sheet N is cut into equal square patches and assembled to form the largest possible closed cube. Assuming the ends of the cylinder are closed, the ratio of the volume of the cylinder to that of the cube is __________

A.
$\frac{π}{2}$
B.
$\frac{3}{π}$
C.
$\frac{9}{π}$
D.
$3 π$

Correct Answer:

Step-by-Step Solution

Insight: Rolling a sheet along its short edge makes the long edge the circumference. A closed cube requires exactly 6 square faces.

Exam route: Cylinder circumference = 6, height = 1 $⟹ r = 3/ π$ , Volume = $9/ π$ . Cube has 6 faces of 1x1 $⟹$ Volume = 1. Ratio = $9/ π$ .

Learning route:

Sheet M (6 cm x 1 cm) is rolled by bringing the short edges together. This means the seam is 1 cm long, so the cylinder height $h = 1$ cm.
The circumference of the cylinder is the long edge, $C = 6$ cm.
From $C = 2 π r = 6$ , we get the radius $r = \frac{6}{2 π} = \frac{3}{π}$ cm.
Volume of the cylinder $V_{cyl} = π r^{2} h = π (\frac{3}{π})^{2} (1) = π (\frac{9}{π ^{2}}) = \frac{9}{π}$ cm $^{3}$ .
Sheet N (6 cm x 1 cm) is cut into equal square patches to form the largest possible closed cube. A closed cube has exactly 6 faces.
The only way to cut a 6x1 sheet into 6 equal squares is to make six 1x1 cm squares.
These 6 squares assemble into a cube of edge length $a = 1$ cm.
Volume of the cube $V_{cube} = a^{3} = 1^{3} = 1$ cm $^{3}$ .
The ratio of the volume of the cylinder to that of the cube is $\frac{9}{π} : 1 = \frac{9}{π}$ .

Wrong path: Rolling along the long edge, making circumference = 1 and height = 6. This gives $r = 1/ (2 π)$ and Volume = $6/ (4 π) = 3/ (2 π)$ , which is not an option. Or assuming an open cube (5 faces), which doesn't divide 6 evenly into squares.

Question 30 · Quantitative Aptitude · 2021_Set1 MCQ

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 to cost of item Q is 3:4. Discount is calculated as the difference between the marked price and the selling price. The profit percentage is calculated as the ratio of the difference between selling price and cost, to the cost

(Profit % = \frac{Selling price - Cost}{Cost} \times 100)

.

The discount on item Q, as a percentage of its marked price, is ______

A.
25
B.
12.5
C.
10
D.
5

Correct Answer:

Step-by-Step Solution

Insight: The cost price of Q can be derived from the given ratio with P's cost price, then selling price follows from the profit percentage, and finally the discount percentage is calculated from the marked price.

Exam route: CP_Q = 5400 (4/3) = 7200. SP_Q = 7200 1.25 = 9000. Discount = 10000 - 9000 = 1000. Discount % = (1000 / 10000) * 100 = 10%.

Learning route:

Identify knowns: CP_P = 5400, and the ratio CP_P : CP_Q = 3 : 4.
Calculate CP_Q: Since 3 parts = 5400, 1 part = 1800. Thus, CP_Q = 4 * 1800 = 7200.
Use Profit % for Q (25%) to find SP_Q: SP_Q = CP_Q (1 + 25/100) = 7200 1.25 = 9000.
Use MP_Q (10000) to find the absolute Discount: Discount = MP_Q - SP_Q = 10000 - 9000 = 1000.
Calculate Discount %: The base for discount percentage is always the Marked Price. So, (1000 / 10000) * 100 = 10%.

Question 31 · Digital Logic · 2021_Set1 MCQ

Let the representation of a number in base 3 be 210. What is the hexadecimal representation of the number?

A.
15
B.
21
C.
D2
D.
528

Correct Answer:

Step-by-Step Solution

Insight: Route through Base 10 to convert from Base 3 to Hexadecimal (Base 16).

Exam route:

$(210)_{3} = 2 (9) + 1 (3) + 0 (1) = 2 1_{10}$ .
$21 \div 16 = 1$ R $5$ . Result is $1 5_{16}$ .

Learning route:

The question requires converting a Base 3 number to Hexadecimal. Since 3 and 16 are not powers of the same base, we must use Base 10 as an intermediate.

Step 1: Convert $(210)_{3}$ to Base 10. The positional weights for Base 3 are $3^{2} = 9$ , $3^{1} = 3$ , $3^{0} = 1$ .

$2 \times 9 + 1 \times 3 + 0 \times 1 = 18 + 3 + 0 = 2 1_{10}$ .

Step 2: Convert $2 1_{10}$ to Base 16. Divide 21 by 16. The quotient is 1 and the remainder is 5.

Reading the remainders gives $1 5_{16}$ .

Verification: $(15)_{16} = 1 (16) + 5 (1) = 2 1_{10}$ . Matches.

Question 32 · Digital Logic · 2021_Set1 MCQ

Consider a 3-bit counter, designed using T flip-flops, as shown below:

Assuming the initial state of the counter given by PQR as 000, what are the next three states?

A.
011, 101, 000
B.
001, 010, 111
C.
011, 101, 111
D.
001, 010, 000

Correct Answer:

Step-by-Step Solution

Insight: This is a synchronous counter where the T inputs are driven by combinational logic of the current state, requiring step-by-step state tracing using the T flip-flop characteristic equation.

Exam route: Extract excitation equations: $T_{P} = R$ , $T_{Q} = \overline{P}$ , $T_{R} = \overline{Q}$ . Use $Q^{+} = T \oplus Q$ . Starting from $P QR = 000$ , compute next states: $000 \to 011 \to 101 \to 000$ .

Learning route:

Step 1: Identify the flip-flop type and its characteristic equation. For T flip-flops, $Q_{n e x t} = T \oplus Q$ .

Step 2: Read the circuit diagram to find the excitation equations for each flip-flop input.

$T_{P}$ is connected to $R$ , so $T_{P} = R$ .
$T_{Q}$ is connected to $\overline{P}$ , so $T_{Q} = \overline{P}$ .
$T_{R}$ is connected to $\overline{Q}$ , so $T_{R} = \overline{Q}$ .

Step 3: Substitute the current state $P QR = 000$ into the excitation equations.

$T_{P} = 0$ , $T_{Q} = \overline{0} = 1$ , $T_{R} = \overline{0} = 1$ .

Step 4: Calculate the next state using $Q_{n e x t} = T \oplus Q$ .

$P^{+} = 0 \oplus 0 = 0$
$Q^{+} = 1 \oplus 0 = 1$
$R^{+} = 1 \oplus 0 = 1$

Next state is $011$ .

Step 5: Repeat for the next state $011$ .

$T_{P} = 1$ , $T_{Q} = \overline{0} = 1$ , $T_{R} = \overline{1} = 0$ .
$P^{+} = 1 \oplus 0 = 1$ , $Q^{+} = 1 \oplus 1 = 0$ , $R^{+} = 0 \oplus 1 = 1$ .

Next state is $101$ .

Step 6: Repeat for $101$ .

$T_{P} = 1$ , $T_{Q} = \overline{1} = 0$ , $T_{R} = \overline{0} = 1$ .
$P^{+} = 1 \oplus 1 = 0$ , $Q^{+} = 0 \oplus 0 = 0$ , $R^{+} = 1 \oplus 1 = 0$ .

Next state is $000$ .

Verification: The sequence $000 \to 011 \to 101 \to 000$ perfectly matches the first option.

Question 33 · Digital Logic · 2021_Set1 MSQ

Consider the following Boolean expression.

F = (X + Y + Z) (\overline{X} + Y) (\overline{Y} + Z)

Which of the following Boolean expressions is/are equivalent to

\overline{F}

(complement of

F

A.
$(\overline{X} + \overline{Y} + \overline{Z}) (X + \overline{Y}) (Y + \overline{Z})$
B.
$X \overline{Y} + \overline{Z}$
C.
$(X + \overline{Z}) (\overline{Y} + \overline{Z})$
D.
$X \overline{Y} + Y \overline{Z} + \overline{X} \overline{Y} \overline{Z}$

Correct Answer:

["B","C","D"]

Step-by-Step Solution

Insight: Simplify $F$ first using consensus and absorption, then apply De Morgan's laws to find $F^{'}$ .

Exam route: $(X + Y + Z) (X^{'} + Y) = Y + X^{'} Z$ . Then $(Y + X^{'} Z) (Y^{'} + Z) = Z (Y + X^{'})$ . Complementing gives $F^{'} = X Y^{'} + Z^{'}$ .

Learning route:

Step 1: Simplify $F = (X + Y + Z) (X^{'} + Y) (Y^{'} + Z)$ .

Apply the rule $(A + B) (A^{'} + C) = A C + A^{'} B + B C$ with $A = X, B = Y + Z, C = Y$ :

$(X + Y + Z) (X^{'} + Y) = X Y + X^{'} (Y + Z) + Y (Y + Z) = X Y + X^{'} Y + X^{'} Z + Y = Y (X + X^{'} + 1) + X^{'} Z = Y + X^{'} Z$ .

Step 2: Multiply by the third term:

$F = (Y + X^{'} Z) (Y^{'} + Z) = Y Y^{'} + Y Z + X^{'} Y^{'} Z + X^{'} Z Z = 0 + Y Z + X^{'} Y^{'} Z + X^{'} Z$ .

Factor $Z$ : $F = Z (Y + X^{'} Y^{'} + X^{'}) = Z (Y + X^{'} (Y^{'} + 1)) = Z (Y + X^{'}) = Y Z + X^{'} Z$ .

Step 3: Find $F^{'}$ using De Morgan's laws:

$F^{'} = (Z (Y + X^{'}))^{'} = Z^{'} + (Y + X^{'})^{'} = Z^{'} + Y^{'} X = X Y^{'} + Z^{'}$ .

Step 4: Verify options against $X Y^{'} + Z^{'}$ .

Option B is exactly $X Y^{'} + Z^{'}$ . (Correct)

Option C: $(X + Z^{'}) (Y^{'} + Z^{'}) = X Y^{'} + X Z^{'} + Y^{'} Z^{'} + Z^{'} = X Y^{'} + Z^{'} (X + Y^{'} + 1) = X Y^{'} + Z^{'}$ . (Correct)

Option D: $X Y^{'} + Y Z^{'} + X^{'} Y^{'} Z^{'} = X Y^{'} + Z^{'} (Y + X^{'} Y^{'}) = X Y^{'} + Z^{'} (Y + X^{'}) (Y + Y^{'}) = X Y^{'} + Z^{'} (Y + X^{'}) = X Y^{'} + Y Z^{'} + X^{'} Z^{'}$ .

By consensus on $X Y^{'}$ and $X^{'} Z^{'}$ , the term $Y^{'} Z^{'}$ is redundant, but wait, let's use a truth table or algebra:

$X Y^{'} + Z^{'} (Y + X^{'}) = X Y^{'} (1 + Z^{'}) + Z^{'} Y + Z^{'} X^{'} = X Y^{'} + X Y^{'} Z^{'} + Y Z^{'} + X^{'} Z^{'} = X Y^{'} + Z^{'} (X Y^{'} + Y + X^{'}) = X Y^{'} + Z^{'} (Y (1 + X^{'}) + X^{'}) = X Y^{'} + Z^{'} (Y + X^{'}) = X Y^{'} + Y Z^{'} + X^{'} Z^{'}$ .

This is algebraically identical to $X Y^{'} + Z^{'}$ . (Correct)

Option A simplifies to $X^{'} Z^{'} + Y^{'} Z^{'}$ , which fails for $X = 1, Y = 1, Z = 0$ (gives 0, but $F^{'} = 1$ ). (Incorrect)

Question 34 · Verbal Aptitude · 2021_Set1 MCQ

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 following is the CORRECT observation about the above two sentences?

A.
(i) is grammatically correct and (ii) is unambiguous
B.
(i) is grammatically incorrect and (ii) is unambiguous
C.
(i) is grammatically correct and (ii) is ambiguous
D.
(i) is grammatically incorrect and (ii) is ambiguous

Correct Answer:

Step-by-Step Solution

Insight: Indefinite pronouns like 'Everybody' are grammatically singular, while personal pronouns must have a single, unmistakable antecedent to avoid ambiguity.

Exam route: Sentence (i) uses 'Everybody', which is singular and correctly pairs with the singular verb 'is'. Sentence (ii) uses the pronoun 'he', which could logically refer to either 'Babu' or 'Danish', making the sentence ambiguous. Therefore, (i) is correct and (ii) is ambiguous.

Learning route:

Step 1: Analyze sentence (i). 'Everybody' belongs to the class of indefinite pronouns (along with someone, anyone, nobody), which always take singular verbs. 'Is' is singular, so the sentence is grammatically correct.

Step 2: Analyze sentence (ii). The pronoun 'he' is used in the dependent clause. The main clause contains two male nouns: 'Babu' and 'Danish'. Because both are valid antecedents for 'he', the reader cannot know who enjoys playing chess. This is a classic ambiguous reference error.

Step 3: Match these findings to the options. Option C correctly identifies (i) as correct and (ii) as ambiguous.

Common trap: Students might think 'Everybody' implies a plural group and incorrectly select 'are', or they might assume 'he' naturally refers to the subject 'Babu' and miss the ambiguity.

Verification: Rewriting (ii) to remove ambiguity (e.g., "Babu invited Danish because Babu enjoys chess") proves the original was structurally flawed in its clarity.

Question 35 · Verbal Aptitude · 2021_Set1 MCQ

Some people suggest anti-obesity measures (AOM) such as displaying calorie information in restaurant menus. Such measures sidestep addressing the core problems that cause obesity: poverty and income inequality.

Which one of the following statements summarizes the passage?

A.
The proposed AOM addresses the core problems that cause obesity.
B.
If obesity reduces, poverty will naturally reduce, since obesity causes poverty.
C.
AOM are addressing the core problems and are likely to succeed.
D.
AOM are addressing the problem superficially.

Correct Answer:

Step-by-Step Solution

Insight: The passage contrasts superficial measures (AOM) with core problems (poverty). The correct summary must capture this contrast without introducing outside facts.

Exam route: AOM "sidesteps addressing the core problems", meaning it only addresses the issue superficially. Option D captures this perfectly.

Learning route:

Identify the core argument: The author notes that AOM (like displaying calorie information) are suggested by some, but explicitly states that these measures "sidestep addressing the core problems" (which are poverty and income inequality).
Evaluate Option A: Claims AOM "addresses the core problems". This directly contradicts the word "sidestep". Incorrect.
Evaluate Option B: Claims "obesity causes poverty". This causal link is never mentioned in the passage. It relies on outside assumptions. Incorrect.
Evaluate Option C: Claims AOM are "likely to succeed". The passage is critical of AOM for missing the root cause; it does not predict success. Incorrect.
Evaluate Option D: Claims AOM are addressing the problem "superficially". This is a perfect paraphrase of "sidestep addressing the core problems". If you ignore the root cause, you are only treating the surface. Correct.
Conclusion: Option D is the only valid summary.

Question 36 · Spatial Aptitude · 2021_Set1 MCQ

A polygon is convex if, for every pair of points, P and Q belonging to the polygon, the line segment PQ lies completely inside or on the polygon.

Which one of the following is NOT a convex polygon?

Question 37 · Spatial Aptitude · 2021_Set1 MCQ

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 of folding, will look like _______.

Correct Answer:

Step-by-Step Solution

Key idea: This is a paper folding and punching problem. We must reverse the folding steps to determine the location and orientation of the punched holes on the unfolded sheet.

Step 1: Analyze the final folded state and the punch.

The final state is a quarter-circle sector (top-right quadrant of the original circle, if we assume standard folding).

The punch consists of:

A small circular hole near the center (the corner of the sector).
A rectangular notch on the curved edge.
A rectangular notch on the straight vertical edge.
A rectangular notch on the straight horizontal edge.

Actually, looking at the SVG for the final state:

It's a quarter circle.
Punches:

A small rectangle on the vertical radius.
A small rectangle on the horizontal radius.
A larger rectangle-like shape on the arc? No, it looks like a hole inside.

Let's look at the options to infer the punch pattern.

The options show:

A central circular hole.
Four rectangular holes arranged symmetrically.

Let's trace the folds backwards.

Fold 1: Vertical fold (Left over Right? Or Right over Left?). The arrow shows the left side folding to the right. So we have a semi-circle (Right half).

Fold 2: Horizontal fold (Bottom over Top? Or Top over Bottom?). The arrow shows the bottom folding up. So we have a quarter-circle (Top-Right quadrant).

The punch is made in this Top-Right quadrant.

Unfold Step 1 (Reverse Horizontal Fold):

Reflect the punch pattern across the horizontal axis (the bottom edge of the current quarter circle).

The Top-Right quadrant becomes the Right Half (Top-Right and Bottom-Right).
Any hole in the Top-Right will have a mirror image in the Bottom-Right.

Unfold Step 2 (Reverse Vertical Fold):

Reflect the entire Right Half pattern across the vertical axis (the left edge of the semi-circle).

The Right Half becomes the Full Circle.
Any hole in the Right Half will have a mirror image in the Left Half.

Analysis of Holes:

Central Hole: The punch near the corner (center of circle) reflects to itself or creates a cluster. In the options, there is a single central circular hole. This implies the punch was at the center or created a symmetric pattern that merges.
Rectangular Holes:

In the final quadrant, there appear to be punches on the edges.
Option A shows 4 rectangular holes: Top, Bottom, Left, Right.
This symmetry corresponds to a single punch in the quadrant that gets reflected 3 times.

Let's look at the specific shape in the final fold SVG:

There is a small rectangular cut on the vertical edge.
There is a small rectangular cut on the horizontal edge.
There is a cut on the arc?

Comparing with Option A:

Option A has rectangles at 12, 6, 3, 9 o'clock positions.
If we punch a rectangle at the midpoint of the vertical radius in the folded state, unfolding horizontally creates a pair at 3 o'clock (if it was on the edge) or similar.

Let's look at the "notch" shapes in the final fold.

One notch on the vertical straight edge.
One notch on the horizontal straight edge.
One notch on the curved edge?

If we unfold a notch on the vertical edge of the Top-Right quadrant:

Reflect across Horizontal: It stays in the Right Half (Top-Right and Bottom-Right? No, the vertical edge is the axis of the first fold? No, the vertical edge is the center of the original circle? No.

Let's re-evaluate the fold axes.

Circle folded vertically. Axis is vertical diameter. Result: Semi-circle.
Semi-circle folded horizontally. Axis is horizontal diameter. Result: Quarter-circle.

The straight edges of the final quarter-circle are the radii along the axes.

Vertical straight edge: Part of the vertical diameter.
Horizontal straight edge: Part of the horizontal diameter.

Punches in the final state:

A punch on the vertical straight edge. When unfolded horizontally (Step 1), this punch is on the axis of reflection? No, the horizontal fold axis is the horizontal edge. The vertical edge is perpendicular to it. So the punch on the vertical edge reflects to a punch on the vertical edge in the lower quadrant. So we have two punches on the vertical radius (one up, one down).

Then unfold vertically (Step 2). The vertical radius is the axis of reflection. Punches on the axis reflect to themselves? Or do they split? If it's a hole on the edge, it becomes a symmetric hole centered on the axis.

A punch on the horizontal straight edge. When unfolded horizontally, this is on the axis. It becomes a symmetric hole centered on the horizontal axis.

Option A shows:

Rectangles at Top and Bottom (on vertical axis).
Rectangles at Left and Right (on horizontal axis).

This matches perfectly if there were punches on the straight edges of the folded quadrant.

Answer: A

Question 38 · Analytical Aptitude · 2021_Set1 MCQ

_____ is to surgery as writer is to ________

Which one of the following options maintains a similar logical relation in the above sentence?

A.
Plan, outline
B.
Hospital, library
C.
Doctor, book
D.
Medicine, grammar

Correct Answer:

Step-by-Step Solution

Insight: This is a Worker-to-Product/Action analogy. The logical relationship is "A [Professional] performs/produces [Action/Product]".

Exam route: A Writer produces a Book. Following the same directional relationship, a Doctor performs Surgery. Therefore, the missing pair is Doctor, book.

Learning route:

Step 1: Isolate the known contiguous pair: "writer" and the blank. We know a writer's primary output is a "book".

Step 2: Formulate the Bridge Sentence: "A [Worker] produces/performs [Product/Action]".

Step 3: Apply to the first part: "A [Worker] performs surgery". The professional who performs surgery is a "Doctor".

Step 4: Verify directionality. Doctor $\to$ Surgery (Worker $\to$ Action). Writer $\to$ Book (Worker $\to$ Product). The logical relation is perfectly maintained.

Question 39 · Analytical Aptitude · 2021_Set1 MCQ

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: Some pathogens are bacteria.

Conclusion II: All pathogens are not bacteria.

Based on the above statements and conclusions, which one of the following options is logically CORRECT?

A.
Only conclusion I is correct
B.
Only conclusion II is correct
C.
Either conclusion I or II is correct.
D.
Neither conclusion I nor II is correct.

Correct Answer:

Step-by-Step Solution

Insight: Two subsets of a larger set may or may not overlap; without explicit information, neither overlap nor disjointness can be definitively concluded.

Exam route: Draw Venn diagram with Bacteria and Pathogens inside Microorganisms. They can be disjoint or overlapping. Since neither is a definite conclusion, select Option D.

Learning route: Let Microorganisms be the universal set. Bacteria and Pathogens are both subsets. The premises do not specify the relationship between Bacteria and Pathogens. If they overlap, Conclusion I (Some pathogens are bacteria) is true, and Conclusion II (All pathogens are not bacteria / No pathogens are bacteria) is false. If they are disjoint, Conclusion I is false, and Conclusion II is true. Because we cannot determine which scenario is the actual case from the premises alone, neither conclusion is logically correct as a definite deduction. Option C is a trap for those who recognize they are contradictory, but in strict syllogism, we only accept conclusions that are definitively true in all valid diagrams.

Wrong path: A student might see that I and II are contradictory and select Option C (Either I or II). This breaks because in strict syllogism, a conclusion must be definitely true based on the premises. Since we cannot deduce which one is true from the given statements, neither is a valid definite conclusion. Generalization: A conclusion must hold in every valid Venn diagram to be correct; do not fall for the "Either/Or" trap when neither is definitively provable. Verification: Both disjoint and overlapping diagrams satisfy the premises, proving neither conclusion is definite.

Free Solved Questions with Step-by-Step Solutions

Unlock All 65 Questions in Real Examination Mode

More GATE CS Previous Year Papers

Login to view the complete paper and solutions

Personalised first. High quality throughout.

Built around you, not around a syllabus PDF

Revision that hits your weak spots

Questions calibrated to the real exam

Notes written for recall, not for volume

One place for everything

Honest progress

Unlock the whole course

GATE CS 2021_Set1 Question Paper with Solutions: 65 Questions, Answer Key & Section-wise Analysis

Paper breakdown

Free sample questions from GATE CS 2021_Set1 Question Paper

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Other GATE CS papers