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

GATE CS 2022 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: 14 · Programming and Data Structures: 7 · Computer Organization and Architecture: 7 · Computer Networks: 6 · Theory of Computation: 5 · Operating System: 5 · Databases: 5 · Quantitative Aptitude: 3 · Compiler Design: 3 · Analytical Aptitude: 3 · Spatial Aptitude: 2 · Digital Logic: 2 · Algorithms: 2 · Verbal Aptitude: 1

Free sample questions from GATE CS 2022 Question Paper

Question 1 · Engineering Mathematics · 2022 MCQ

A box contains five balls of same size and shape. Three of them are green coloured balls and two of them are orange coloured balls. Balls are drawn from the box one at a time. If a green ball is drawn, it is not replaced. If an orange ball is drawn, it is replaced with another orange ball.

First ball is drawn. What is the probability of getting an orange ball in the next draw?

A.
$\frac{1}{2}$
B.
$\frac{8}{25}$
C.
$\frac{19}{50}$
D.
$\frac{23}{50}$

Correct Answer:

Step-by-Step Solution

Insight: This is an asymmetric replacement problem requiring the Law of Total Probability over the unknown first draw.

Exam route: Branch into two paths: 1st is Green (prob 3/5, new state 2G, 2O) and 1st is Orange (prob 2/5, new state 3G, 2O). Multiply and sum the path probabilities.

Learning route:

Step 1: Identify initial state: 3 Green (G), 2 Orange (O). Total = 5.

Step 2: Define the two mutually exclusive paths for the first draw.

Path A: First ball is Green.

Probability of Path A: P(1st G) = 3/5.
Rule: Green is not replaced. New state: 2 G, 2 O. Total = 4.
Probability of 2nd Orange given Path A: P(2nd O | 1st G) = 2/4 = 1/2.
Joint probability of Path A: (3/5) * (1/2) = 3/10 = 15/50.

Path B: First ball is Orange.

Probability of Path B: P(1st O) = 2/5.
Rule: Orange is replaced with another Orange. The drawn orange is removed, but another is added, so the count of Orange remains 2, and total remains 5. New state: 3 G, 2 O. Total = 5.
Probability of 2nd Orange given Path B: P(2nd O | 1st O) = 2/5.
Joint probability of Path B: (2/5) * (2/5) = 4/25 = 8/50.

Step 3: Apply the Law of Total Probability.

P(2nd O) = P(Path A) + P(Path B) = 15/50 + 8/50 = 23/50.

Verification: The sum of all path probabilities for the second draw must equal 1. P(2nd G) = (3/5 2/4) + (2/5 3/5) = 15/50 + 12/50 = 27/50. Total = 23/50 + 27/50 = 1. The math is perfectly consistent.

Question 2 · Engineering Mathematics · 2022 MCQ

Consider the following two statements with respect to the matrices

A_{m \times n}

B_{n \times m}

C_{n \times n}

and

D_{n \times n}

.

Statement 1:

tr (A B) = tr (B A)

Statement 2:

tr (C D) = tr (D C)

where

tr ()

represents the trace of a matrix. Which one of the following holds?

A.
Statement 1 is correct and Statement 2 is wrong.
B.
Statement 1 is wrong and Statement 2 is correct.
C.
Both Statement 1 and Statement 2 are correct.
D.
Both Statement 1 and Statement 2 are wrong.

Correct Answer:

Step-by-Step Solution

Key idea: This is a trace identity question, recognizable because it tests the cyclic property of the trace operator for matrix products. The trigger is the presence of $tr (A B)$ and $tr (B A)$ for matrices of compatible dimensions.

Step 1: Analyze Statement 1. Let $A$ be an $m \times n$ matrix and $B$ be an $n \times m$ matrix. The product $A B$ is an $m \times m$ matrix, and $B A$ is an $n \times n$ matrix. Both traces are well-defined.

Step 2: By definition, $tr (A B) = \sum_{i = 1}^{m} (A B)_{ii} = \sum_{i = 1}^{m} \sum_{j = 1}^{n} A_{ij} B_{j i}$ .

Step 3: Similarly, $tr (B A) = \sum_{j = 1}^{n} (B A)_{j j} = \sum_{j = 1}^{n} \sum_{i = 1}^{m} B_{j i} A_{ij}$ .

Step 4: Since scalar multiplication is commutative ( $A_{ij} B_{j i} = B_{j i} A_{ij}$ ) and finite sums can be swapped, $tr (A B) = tr (B A)$ . Statement 1 is correct.

Step 5: Analyze Statement 2. $C$ and $D$ are both $n \times n$ matrices. This is a special case of Statement 1 where $m = n$ . Thus, $tr (C D) = tr (D C)$ is also correct.

Step 6: Both statements are universally true for matrices of compatible dimensions.

Answer: Both Statement 1 and Statement 2 are correct. (Option C)

Question 3 · Engineering Mathematics · 2022 MSQ

Which of the following statements is/are TRUE for a group $G$ ?

A.
If for all $x, y \in G$ , $(x y)^{2} = x^{2} y^{2}$ , then $G$ is commutative.
B.
If for all $x \in G$ , $x^{2} = 1$ , then $G$ is commutative. Here, $1$ is the identity element of $G$ .
C.
If the order of $G$ is $2$ , then $G$ is commutative.
D.
If $G$ is commutative, then a subgroup of $G$ need not be commutative.

Correct Answer:

["A","B","C"]

Step-by-Step Solution

Insight: Test each algebraic identity by expanding and cancelling. For small orders, use group classification.

Exam route:

Option A: $(x y)^{2} = x^{2} y^{2} ⟹ x y x y = xx y y$ . Left-multiply by $x^{- 1}$ and right-multiply by $y^{- 1}$ to get $y x = x y$ . True.

Option B: $x^{2} = 1 ⟹ x = x^{- 1}$ . Then $(x y)^{- 1} = y^{- 1} x^{- 1} = y x$ . But since $x y \in G$ , $(x y)^{2} = 1 ⟹ (x y)^{- 1} = x y$ . Thus $x y = y x$ . True.

Option C: $∣ G ∣ = 2 ⟹ G = {e, a}$ . The only products are $ee, e a, a e, aa$ , all of which commute. True.

Option D: Subgroups of Abelian groups are always Abelian. The statement "need not be" is False.

Learning route:

For A, expand $(x y) (x y) = xx y y$ . Cancel $x$ on the left: $y x y = x y y$ . Cancel $y$ on the right: $y x = x y$ .
For B, the condition means every element is its own inverse. The inverse of $x y$ is $y^{- 1} x^{- 1} = y x$ . But $x y$ is also its own inverse, so $x y = y x$ .
For C, a group of order 2 is isomorphic to $Z_{2}$ , which is Abelian.
For D, if $ab = ba$ for all $a, b \in G$ , then for any $a, b \in H \subseteq G$ , $ab = ba$ still holds.

Question 4 · Programming and Data Structures · 2022 MCQ

Consider the problem of reversing a singly linked list. To take an example, given the linked list below,

the reversed linked list should look like

Which one of the following statements is TRUE about the time complexity of algorithms that solve the above problem in

O (1)

space?

A.
The best algorithm for the problem takes $θ (n)$ time in the worst case.
B.
The best algorithm for the problem takes $θ (n lo g n)$ time in the worst case.
C.
The best algorithm for the problem takes $θ (n^{2})$ time in the worst case.
D.
It is not possible to reverse a singly linked list in $O (1)$ space.

Correct Answer:

Step-by-Step Solution

Insight: This is a linked list reversal complexity question, recognizable because it asks for the time complexity of reversing a singly linked list under a strict $O (1)$ space constraint.

Exam route: Iterative reversal uses 3 pointers and visits each node exactly once, yielding $θ (n)$ time and $O (1)$ space.

Learning route:

Step 1: Understand the constraints. We must reverse a singly linked list of $n$ nodes using only $O (1)$ extra space (i.e., a constant number of pointers, no recursion stack, no auxiliary arrays).

Step 2: Recall the standard iterative reversal algorithm. We maintain three pointers: prev (initially NULL), curr (initially head), and next_temp (initially NULL).

Step 3: Traverse the list. In each iteration, we store curr->next in next_temp, reverse the link by setting curr->next = prev, and then advance prev and curr by one step.

Step 4: Analyze the complexity. The algorithm visits each of the $n$ nodes exactly once, performing a constant number of pointer assignments per node. Therefore, the time complexity is strictly $θ (n)$ . The space complexity is $O (1)$ because only three pointers are used.

Question 5 · Programming and Data Structures · 2022 MCQ

Suppose we are given $n$ keys, $m$ hash table slots, and two simple uniform hash functions $h_{1}$ and $h_{2}$ . Further suppose our hashing scheme uses $h_{1}$ for the odd keys and $h_{2}$ for the even keys. What is the expected number of keys in a slot?

A.
$\frac{m}{n}$
B.
$\frac{n}{m}$
C.
$\frac{2 n}{m}$
D.
$\frac{n}{2 m}$

Correct Answer:

Step-by-Step Solution

Insight: Simple uniform hashing guarantees that every key independently has a $1/ m$ probability of landing in any specific slot, regardless of the deterministic rule used to pick the hash function.

Exam route: Recognize that any simple uniform hash function distributes keys evenly in expectation. The expected load is simply total keys divided by total slots.

Learning route:

Let $X_{i, j}$ be an indicator random variable that is 1 if key $i$ hashes to slot $j$ , and 0 otherwise.

Because both $h_{1}$ and $h_{2}$ are simple uniform hash functions, for any key $k$ , the probability that it maps to slot $j$ is exactly $1/ m$ , whether it uses $h_{1}$ or $h_{2}$ .

Thus, $E [X_{i, j}] = 1/ m$ for all $i \in {1 \dots n}$ .

The total number of keys in slot $j$ is $Y_{j} = \sum_{i = 1}^{n} X_{i, j}$ .

By linearity of expectation:

$E [Y_{j}] = \sum_{i = 1}^{n} E [X_{i, j}] = \sum_{i = 1}^{n} \frac{1}{m} = \frac{n}{m}$ .

Tempting wrong path: Assuming the parity split halves the keys per slot, leading to $n /2 m$ . While half the keys use $h_{1}$ and half use $h_{2}$ , both functions map to the same $m$ slots with probability $1/ m$ , so the total expectation remains $n / m$ .

Generalization: Linearity of expectation holds regardless of dependencies or deterministic routing rules, as long as the marginal probability for each item remains uniform.

Verification: If $n = m$ , expected keys per slot is 1. Formula gives $m / m = 1$ . Matches intuition.

Question 6 · Programming and Data Structures · 2022 MCQ

What is printed by the following ANSI C program?

#include<stdio.h>

int main(int argc, char *argv[])

{

       int x = 1, z[2] = {10, 11};

       int *p = NULL;

       p = &x;

       *p = 10;

       p = &z[1];

       *(&z[0] + 1) += 3;

       printf("%d, %d, %d\n", x, z[0], z[1]);

       return 0;

}

A.
1, 10, 11
B.
1, 10, 14
C.
10, 14, 11
D.
10, 10, 14

Correct Answer:

Step-by-Step Solution

Insight: This is a pointer tracing question with array indexing, recognizable by mixed pointer assignments and arithmetic on array base addresses.

Exam route: Track x, z[0], and z[1]. p = 10 changes x to 10. (&z[0] + 1) is equivalent to z[1], so z[1] becomes 11 + 3 = 14. z[0] remains 10.

Learning route:

Initial state: x = 1, z[0] = 10, z[1] = 11.
p = &x: p points to x.
*p = 10: The value at p (which is x) is updated to 10.
p = &z[1]: p is redirected to point to z[1]. (This line does not change z[1]'s value, only p's target).
*(&z[0] + 1) += 3:

&z[0] is the address of the first element.
Adding 1 scales by the size of int, yielding the address of the next element, &z[1].
Dereferencing this gives z[1].
z[1] += 3 updates z[1] from 11 to 14.

Final values: x = 10, z[0] = 10, z[1] = 14.
Output matches option D.

Question 7 · Computer Organization and Architecture · 2022 MCQ

Which one of the following facilitates transfer of bulk data from hard disk to main memory with the highest throughput?

A.
DMA based I/O transfer
B.
Interrupt driven I/O transfer
C.
Polling based I/O transfer
D.
Programmed I/O transfer

Correct Answer:

Step-by-Step Solution

Key idea: This is a conceptual comparison question about I/O transfer mechanisms, recognisable because it asks for the "highest throughput" for "bulk data" among standard I/O techniques.

Step 1: Evaluate Programmed I/O. The CPU must execute a sequence of instructions for every single byte or word transferred. This keeps the CPU 100% occupied with the transfer, resulting in the lowest throughput.

Step 2: Evaluate Polling. Similar to programmed I/O, the CPU continuously checks the device status in a loop, wasting even more cycles when the device is not ready. Throughput remains very low.

Step 3: Evaluate Interrupt-driven I/O. The CPU can do other work while waiting for the device. However, when the device is ready, the CPU still must execute instructions to move each byte from the device interface to memory.

Step 4: Evaluate DMA (Direct Memory Access). The DMA controller takes over the system bus and transfers entire blocks of data directly between the device and main memory without CPU intervention. The CPU is only involved at the start and end. This minimizes overhead and maximizes data transfer rate.

Answer: A

Question 8 · Computer Organization and Architecture · 2022 MSQ

Let WB and WT be two set associative cache organizations that use LRU algorithm for cache block replacement. WB is a write back cache and WT is a write through cache. Which of the following statements is/are FALSE?

A.
Each cache block in WB and WT has a dirty bit.
B.
Every write hit in WB leads to a data transfer from cache to main memory.
C.
Eviction of a block from WT will not lead to data transfer from cache to main memory.
D.
A read miss in WB will never lead to eviction of a dirty block from WB.

Correct Answer:

["A","B","D"]

Step-by-Step Solution

Insight: This is a multi-statement write-policy comparison. Evaluate each statement against the fundamental rules of WB and WT.

Exam route:

A: WT does not use dirty bits → FALSE.
B: WB write hit updates cache only, not memory → FALSE.
C: WT eviction needs no writeback (memory already current) → TRUE.
D: A read miss in WB can evict a dirty block if the set is full → FALSE.

Answer: A, B, D

Learning route:

This is a multi-statement true/false question about write policies, recognisable by the WB vs WT comparison and the "which is/are FALSE" phrasing.

Recall the fundamental rules:

Write-Through (WT): Write hit → update cache AND memory. No dirty bit needed. Eviction → discard (memory is already current).
Write-Back (WB): Write hit → update cache only, set dirty bit. Eviction → writeback to memory if dirty bit = 1.

Now evaluate each statement:

A. "Each cache block in WB and WT has a dirty bit." — WB needs dirty bits, but WT does not (cache and memory are always in sync). FALSE.

B. "Every write hit in WB leads to a data transfer from cache to main memory." — In WB, a write hit updates only the cache and sets the dirty bit. Memory is updated only on eviction. FALSE.

C. "Eviction of a block from WT will not lead to data transfer from cache to main memory." — In WT, memory is always current, so eviction simply discards the line. No writeback. TRUE.

D. "A read miss in WB will never lead to eviction of a dirty block from WB." — A read miss loads a new block. If the target set is full, a replacement occurs. The evicted block may be dirty (if it was previously written). FALSE.

The question asks for FALSE statements: A, B, D.

Question 9 · Computer Organization and Architecture · 2022 NAT

A cache memory that has a hit rate of 0.8 has an access latency 10 ns and miss penalty 100 ns. An optimization is done on the cache to reduce the miss rate. However, the optimization results in an increase of cache access latency to 15 ns, whereas the miss penalty is not affected. The minimum hit rate (rounded off to two decimal places) needed after the optimization such that it should not increase the average memory access time is _____________.

Correct Answer:

0.85

Step-by-Step Solution

Key idea: This is a cache optimization AMAT comparison problem. We must calculate the original AMAT, set up an inequality for the new AMAT, and solve for the minimum required hit rate.

Step 1: Calculate the original AMAT.

Original hit rate ( $H_{o l d}$ ) = 0.8 $⟹$ miss rate ( $M_{o l d}$ ) = 0.2
Original access latency ( $T_{o l d}$ ) = 10 ns
Miss penalty ( $P$ ) = 100 ns
$A M A T_{o l d} = T_{o l d} + M_{o l d} \times P$
$A M A T_{o l d} = 10 + 0.2 \times 100 = 10 + 20 = 30$ ns.

Step 2: Set up the equation for the optimized cache.

New access latency ( $T_{n e w}$ ) = 15 ns
Miss penalty ( $P$ ) = 100 ns (unaffected)
Let the new hit rate be $H_{n e w}$ . Then the new miss rate is $(1 - H_{n e w})$ .
$A M A T_{n e w} = T_{n e w} + (1 - H_{n e w}) \times P$
$A M A T_{n e w} = 15 + (1 - H_{n e w}) \times 100$

Step 3: Apply the optimization constraint.

The optimization should not increase the AMAT, so $A M A T_{n e w} \leq A M A T_{o l d}$ .

$15 + 100 \times (1 - H_{n e w}) \leq 30$

$15 + 100 - 100 \times H_{n e w} \leq 30$

$115 - 100 \times H_{n e w} \leq 30$

$115 - 30 \leq 100 \times H_{n e w}$

$85 \leq 100 \times H_{n e w}$

$H_{n e w} \geq 0.85$

Step 4: Format the answer.

The minimum hit rate needed is 0.85. Rounded to two decimal places, this is 0.85.

Answer: 0.85

Question 10 · Computer Networks · 2022 MCQ

Consider an enterprise network with two Ethernet segments, a web server and a firewall, connected via three routers as shown below.

What is the number of subnets inside the enterprise network?

A.
3
B.
12
C.
6
D.
8

Question 11 · Computer Networks · 2022 NAT

Consider the resolution of the domain name <code>www.gate.org.in</code> by a DNS resolver. Assume that no resource records are cached anywhere across the DNS servers and that iterative query mechanism is used in the resolution. The number of DNS query-response pairs involved in completely resolving the domain name is_____________.

Question 12 · Computer Networks · 2022 MSQ

Consider routing table of an organization’s router shown below:

Subnet Number	Subnet Mask	Next Hop
12.20.164.0	255.255.252.0	R1
12.20.170.0	255.255.254.0	R2
12.20.168.0	255.255.254.0	Interface 0
12.20.166.0	255.255.254.0	Interface 1
default		R3

Which of the following prefixes in CIDR notation can be collectively used to correctly aggregate all of the subnets in the routing table?

A.
12.20.164.0/20
B.
12.20.164.0/22
C.
12.20.164.0/21
D.
12.20.168.0/22

Question 13 · Theory of Computation · 2022 MCQ

Which one of the following regular expressions correctly represents the language of the finite automaton given below?

A.
$a b^{*} ba b^{*} + b a^{*} ab a^{*}$
B.
$(a b^{*} b)^{*} a b^{*} + (b a^{*} a)^{*} b a^{*}$
C.
$(a b^{*} b + b a^{*} a)^{*} (a^{*} + b^{*})$
D.
$(b a^{*} a + a b^{*} b)^{*} (a b^{*} + b a^{*})$

Correct Answer:

Step-by-Step Solution

Key idea: This is a DFA-to-Regex conversion problem. We can use Arden's Theorem or State Elimination.

Step 1: Write state equations.

Let $q_{0}$ be start, $q_{1}, q_{2}$ be finals.

$q_{0} = ϵ + q_{1} b + q_{2} a$

$q_{1} = q_{0} a + q_{1} b$ (Wait, diagram: $q_{0} a q_{1}$ . $q_{1} b q_{1}$ ? No, $q_{1} b q_{0}$ ?

Let's trace P3 diagram carefully.

Start -> Left Circle ( $q_{0}$ ).

$q_{0} a q_{1}$ (Top Right, Final).

$q_{0} b q_{2}$ (Bottom Right, Final).

$q_{1} b q_{0}$ .

$q_{1} a q_{1}$ ? No, loop on $q_{1}$ is labeled 'b'?

Diagram:

Left ( $q_{0}$ ) to Top ( $q_{1}$ ): 'a'.
Left ( $q_{0}$ ) to Bottom ( $q_{2}$ ): 'b'.
Top ( $q_{1}$ ) to Left ( $q_{0}$ ): 'b'.
Top ( $q_{1}$ ) loop: 'a'? No, arrow from $q_{1}$ to $q_{1}$ ?

The SVG shows:

Path from $q_{1}$ (300,55) curving back to itself? No.
Path from $q_{1}$ to $q_{2}$ ? No.
Path from $q_{1}$ to $q_{0}$ : 'b'.
Path from $q_{2}$ to $q_{0}$ : 'a'.
Loop on $q_{1}$ : 'b'? The text 'b' is at (363, 48). The path is a loop on $q_{1}$ .
Loop on $q_{2}$ : 'a'? The text 'a' is at (363, 170). The path is a loop on $q_{2}$ .

So:

$q_{0} = ϵ + q_{1} b + q_{2} a$

$q_{1} = q_{0} a + q_{1} b$

$q_{2} = q_{0} b + q_{2} a$

Step 2: Solve for $q_{1}$ and $q_{2}$ using Arden's.

$q_{1} = q_{0} a + q_{1} b ⟹ q_{1} = q_{0} a b^{*}$

$q_{2} = q_{0} b + q_{2} a ⟹ q_{2} = q_{0} b a^{*}$

Step 3: Substitute into $q_{0}$ .

$q_{0} = ϵ + (q_{0} a b^{*}) b + (q_{0} b a^{*}) a$

$q_{0} = ϵ + q_{0} (a b^{*} b + b a^{*} a)$

Let $R = a b^{*} b + b a^{*} a$ .

$q_{0} = ϵ + q_{0} R ⟹ q_{0} = R^{*} = (a b^{*} b + b a^{*} a)^{*}$

Step 4: Find Language ( $q_{1} + q_{2}$ ).

$L = q_{1} + q_{2} = q_{0} a b^{*} + q_{0} b a^{*} = q_{0} (a b^{*} + b a^{*})$

$L = (a b^{*} b + b a^{*} a)^{*} (a b^{*} + b a^{*})$

Compare with Option B: $((a b^{*} b)^{*} a b^{*} + (b a^{*} a)^{*} b a^{*})$ ? No.

Option B: $(a b^{*} b)^{*} a b^{*} + (b a^{*} a)^{*} b a^{*}$ . This looks like two separate parts.

Let's check Option D: $(b a^{*} a + a b^{*} b)^{*} (a b^{*} + b a^{*})$ .

My result: $(a b^{*} b + b a^{*} a)^{*} (a b^{*} + b a^{*})$ .

This matches Option D exactly (order of union doesn't matter).

Answer: D

Question 14 · Theory of Computation · 2022 MSQ

Which of the following statements is/are TRUE?

A.
Every subset of a recursively enumerable language is recursive.
B.
If a language $L$ and its complement $\overline{L}$ are both recursively enumerable, then $L$ must be recursive.
C.
Complement of a context-free language must be recursive.
D.
If $L_{1}$ and $L_{2}$ are regular, then $L_{1} \cap L_{2}$ must be deterministic context-free.

Question 15 · Theory of Computation · 2022 MSQ

Which of the following is/are undecidable?

A.
Given two Turing machines $M_{1}$ and $M_{2}$ , decide if $L (M_{1}) = L (M_{2})$ .
B.
Given a Turing machine $M$ , decide if $L (M)$ is regular.
C.
Given a Turing machine $M$ , decide if $M$ accepts all strings.
D.
Given a Turing machine $M$ , decide if $M$ takes more than 1073 steps on every string.

Question 16 · Operating System · 2022 MCQ

Consider the following threads, T1, T2, and T3 executing on a single processor, synchronized using three binary semaphore variables, S1, S2, and S3, operated upon using standard wait() and signal(). The threads can be context switched in any order and at any time.

T1	T2	T3
`while(true){ wait(S3); print(“C”); signal(S2); }`	`while(true){ wait(S1); print(“B”); signal(S3); }`	`while(true){ wait(S2); print(“A”); signal(S1); }`

Which initialization of the semaphores would print the sequence BCABCABCA….?

A.
S1 = 1; S2 = 1; S3 = 1
B.
S1 = 1; S2 = 1; S3 = 0
C.
S1 = 1; S2 = 0; S3 = 0
D.
S1 = 0; S2 = 1; S3 = 1

Question 17 · Operating System · 2022 MSQ

Which of the following statements is/are TRUE with respect to deadlocks?

A.
Circular wait is a necessary condition for the formation of deadlock.
B.
In a system where each resource has more than one instance, a cycle in its wait-for graph indicates the presence of a deadlock.
C.
If the current allocation of resources to processes leads the system to unsafe state, then deadlock will necessarily occur.
D.
In the resource-allocation graph of a system, if every edge is an assignment edge, then the system is not in deadlock state.

Question 18 · Operating System · 2022 MCQ

Consider four processes P, Q, R, and S scheduled on a CPU as per round robin algorithm with a time quantum of 4 units. The processes arrive in the order P, Q, R, S, all at time $t = 0$ . There is exactly one context switch from S to Q, exactly one context switch from R to Q, and exactly two context switches from Q to R. There is no context switch from S to P. Switching to a ready process after the termination of another process is also considered a context switch. Which one of the following is NOT possible as CPU burst time (in time units) of these processes?

A.
P = 4, Q = 10, R = 6, S = 2
B.
P = 2, Q = 9, R = 5, S = 1
C.
P = 4, Q = 12, R = 5, S = 4
D.
P = 3, Q = 7, R = 7, S = 3

Question 19 · Databases · 2022 MCQ

In a relational data model, which one of the following statements is TRUE?

A.
A relation with only two attributes is always in BCNF.
B.
If all attributes of a relation are prime attributes, then the relation is in BCNF.
C.
Every relation has at least one non-prime attribute.
D.
BCNF decompositions preserve functional dependencies.

Question 20 · Databases · 2022 MSQ

Consider the following three relations in a relational database.

Employee (\underline{eId}, Name), Brand (\underline{bId}, bName), Own (\underline{eId}, \underline{bId})

Which of the following relational algebra expressions return the set of

e I d s

who own all the brands?

A.
$Π_{e I d} (Π_{e I d, b I d} (O w n) / Π_{b I d} (B r an d))$
B.
$Π_{e I d} (O w n) - Π_{e I d} ((Π_{e I d} (O w n) \times Π_{b I d} (B r an d)) - Π_{e I d, b I d} (O w n))$
C.
$Π_{e I d} (Π_{e I d, b I d} (O w n) / Π_{b I d} (O w n))$
D.
$Π_{e I d} ((Π_{e I d} (O w n) \times Π_{b I d} (O w n)) / Π_{b I d} (B r an d))$

Question 21 · Databases · 2022 NAT

Consider a relation $R (A, B, C, D, E)$ with the following three functional dependencies.

$A B \to C; B C \to D; C \to E;$

The number of superkeys in the relation $R$ is ____________.

Question 22 · Quantitative Aptitude · 2022 MCQ

A function $y (x)$ is defined in the interval $[0, 1]$ on the $x$ -axis as

$y (x) = ⎩ ⎨ ⎧ 231 if 0 \leq x < \frac{1}{3} if \frac{1}{3} \leq x < \frac{3}{4} if \frac{3}{4} \leq x \leq 1$

Which one of the following is the area under the curve for the interval $[0, 1]$ on the $x$ -axis?

A.
$\frac{5}{6}$
B.
$\frac{6}{5}$
C.
$\frac{13}{6}$
D.
$\frac{6}{13}$

Correct Answer:

Step-by-Step Solution

Insight: The area under a piecewise constant (step) function is simply the sum of the areas of the rectangular blocks it forms.

Exam route: Area = $2 (1/3) + 3 (3/4 - 1/3) + 1 (1 - 3/4) = 2/3 + 5/4 + 1/4 = 2/3 + 6/4 = 13/6$ .

Learning route:

The function is constant on three sub-intervals. The area under the curve is the sum of the areas of three rectangles.
Rectangle 1: Interval $[0, 1/3]$ . Width = $1/3 - 0 = 1/3$ . Height = 2. Area = $2 \times 1/3 = 2/3$ .
Rectangle 2: Interval $[1/3, 3/4]$ . Width = $3/4 - 1/3 = 9/12 - 4/12 = 5/12$ . Height = 3. Area = $3 \times 5/12 = 15/12 = 5/4$ .
Rectangle 3: Interval $[3/4, 1]$ . Width = $1 - 3/4 = 1/4$ . Height = 1. Area = $1 \times 1/4 = 1/4$ .
Total Area = $2/3 + 5/4 + 1/4$ .
Combine the fractions with denominator 4: $5/4 + 1/4 = 6/4 = 3/2$ .
Add to the first term: $2/3 + 3/2$ . The common denominator is 6.
Total Area = $4/6 + 9/6 = 13/6$ .

Wrong path: Miscalculating the width of the second interval (e.g., $3/4 - 1/3 = 2/1$ due to bad fraction subtraction), or adding the heights instead of multiplying by width, or confusing the interval bounds. Option A (5/6) might come from missing the middle term entirely.

Question 23 · Quantitative Aptitude · 2022 MCQ

Let

r

be a root of the equation

x^{2} + 2 x + 6 = 0

.

Then the value of the expression

(r + 2) (r + 3) (r + 4) (r + 5)

A.
$51$
B.
$- 51$
C.
$126$
D.
$- 126$

Correct Answer:

Step-by-Step Solution

Insight: If $r$ is a root of $x^{2} + 2 x + 6 = 0$ , then $r^{2} + 2 r = - 6$ . We can group the factors of the target expression to form this known polynomial.

Exam route: Group $(r + 2) (r + 3) = r^{2} + 5 r + 6 = (r^{2} + 2 r + 6) + 3 r = 3 r$ . Group $(r + 4) (r + 5) = r^{2} + 9 r + 20 = (r^{2} + 2 r + 6) + 7 r + 14 = 7 (r + 2)$ . Multiply them: $3 r \cdot 7 (r + 2) = 21 (r^{2} + 2 r) = 21 (- 6) = - 126$ .

Learning route:

Step 1: Write the given equation as $r^{2} + 2 r = - 6$ .

Step 2: Expand pairs of the target expression to reveal the polynomial $r^{2} + 2 r + 6$ .

Step 3: $(r + 2) (r + 3) = r^{2} + 5 r + 6 = (r^{2} + 2 r + 6) + 3 r$ . Since $r^{2} + 2 r + 6 = 0$ , this simplifies to $3 r$ .

Step 4: $(r + 4) (r + 5) = r^{2} + 9 r + 20 = (r^{2} + 2 r + 6) + 7 r + 14$ . Since $r^{2} + 2 r + 6 = 0$ , this simplifies to $7 r + 14 = 7 (r + 2)$ .

Step 5: Multiply the simplified parts: $3 r \times 7 (r + 2) = 21 r (r + 2) = 21 (r^{2} + 2 r)$ .

Step 6: Substitute $r^{2} + 2 r = - 6$ to get $21 (- 6) = - 126$ .

Question 24 · Quantitative Aptitude · 2022 MCQ

In a recently conducted national entrance test, boys constituted 65% of those who appeared for the test. Girls constituted the remaining candidates and they accounted for 60% of the qualified candidates.

Which one of the following is the correct logical inference based on the information provided in the above passage?

A.
Equal number of boys and girls qualified
B.
Equal number of boys and girls appeared for the test
C.
The number of boys who appeared for the test is less than the number of girls who appeared
D.
The number of boys who qualified the test is less than the number of girls who qualified

Correct Answer:

Step-by-Step Solution

Insight: Percentages of the qualified pool tell us the boys-vs-girls split among qualifiers directly — no need to know the pass rates.

Exam route: Girls are $60%$ of qualified $⟹$ boys are $40%$ of qualified. So fewer boys qualified than girls. Option D.

Learning route:

Step 1: Let total appeared $= 100$ . Boys appeared $= 65$ , girls appeared $= 35$ .

Step 2: Girls account for $60%$ of qualified candidates. Therefore boys account for the remaining $40%$ of qualified candidates.

Step 3: Compare the options:

A: "Equal number of boys and girls qualified" — false, since $60% \neq = 40%$ .
B: "Equal number of boys and girls appeared" — false, $65 \neq = 35$ .
C: "Boys who appeared $<$ girls who appeared" — false, $65 > 35$ .
D: "Boys who qualified $<$ girls who qualified" — true, since $40% < 60%$ of the same qualified pool.

Trap warning: Students often try to compute actual numbers of qualifiers, but the pass rates are not given. The inference must come purely from the qualified-pool split.

Verification: Whatever the total qualified count $Q$ is, boys qualified $= 0.4 Q$ and girls qualified $= 0.6 Q$ , so boys $<$ girls always holds.

Question 25 · Compiler Design · 2022 MCQ

Which one of the following statements is TRUE?

A.
The $L A L R (1)$ parser for a grammar $G$ cannot have reduce-reduce conflict if the $L R (1)$ parser for $G$ does not have reduce-reduce conflict.
B.
Symbol table is accessed only during the lexical analysis phase.
C.
Data flow analysis is necessary for run-time memory management.
D.
$L R (1)$ parsing is sufficient for deterministic context-free languages.

Correct Answer:

Step-by-Step Solution

Key idea: Evaluate each statement based on formal language theory and compiler design principles.

Step 1: Analyze Option A. LALR(1) parsers are formed by merging states of LR(1) parsers. This merging can introduce reduce-reduce conflicts that were not present in the original LR(1) parser. Thus, Option A is FALSE.

Step 2: Analyze Option B. The symbol table is a central data structure accessed by almost all compiler phases (lexical, syntax, semantic, intermediate code generation, optimization, and code generation), not just lexical analysis. Thus, Option B is FALSE.

Step 3: Analyze Option C. Data flow analysis is a technique used for code optimization (e.g., constant propagation, dead code elimination), not for run-time memory management. Run-time memory management is handled by the run-time system. Thus, Option C is FALSE.

Step 4: Analyze Option D. Deterministic Context-Free Languages (DCFLs) are exactly the class of languages that can be recognized by a Deterministic Pushdown Automaton (DPDA). LR(1) parsing is a deterministic parsing technique that can parse all DCFLs. Thus, Option D is TRUE.

Answer: D

Question 26 · Compiler Design · 2022 NAT

Consider the augmented grammar with ${+, *, (,), i d}$ as the set of terminals.

$S^{'} S R P \to S \to S + R ∣ R \to R * P ∣ P \to (S) ∣ i d$

If $I_{0}$ is the set of two $L R (0)$ items ${[S^{'} \to S \cdot], [S \to S \cdot + R]}$ , then $g o t o (c l os u r e (I_{0}), +)$ contains exactly __________ items.

Question 27 · Compiler Design · 2022 NAT

Consider the following grammar along with translation rules.

S S T T R \to S_{1} # T \to T \to T_{1} % R \to R \to i d {S_{. v a l} = S_{1. v a l} * T_{. v a l}} {S_{. v a l} = T_{. v a l}} {T_{. v a l} = T_{1. v a l} \div R_{. v a l}} {T_{. v a l} = R_{. v a l}} {R_{. v a l} = i d_{. v a l}}

Here # and % are operators and

i d

is a token that represents an integer and

i d_{. v a l}

represents the corresponding integer value. The set of non-terminals is

{S, T, R, P}

and a subscripted non-terminal indicates an instance of the non-terminal.

Using this translation scheme, the computed value of

S_{. v a l}

for root of the parse tree for the expression

20#10%5#8%2%2

is_____________.

Question 28 · Analytical Aptitude · 2022 MCQ

Given below are four statements.

Statement 1: All students are inquisitive.

Statement 2: Some students are inquisitive.

Statement 3: No student is inquisitive.

Statement 4: Some students are not inquisitive.

From the given four statements, find the two statements that CANNOT BE TRUE simultaneously, assuming that there is at least one student in the class.

A.
Statement 1 and Statement 3
B.
Statement 1 and Statement 2
C.
Statement 2 and Statement 4
D.
Statement 3 and Statement 4

Correct Answer:

Step-by-Step Solution

Insight: "All S are P" and "No S is P" are mutually exclusive; they cannot both be true for a non-empty set.

Exam route: Statement 1 is Type A (All), Statement 3 is Type E (No). A and E are contraries. Select Option A.

Learning route: In categorical logic, assuming the subject class is not empty, the universal affirmative (All students are inquisitive) and the universal negative (No student is inquisitive) cannot both be true. If all are inquisitive, it is false that none are. Statement 2 (Some are) and Statement 4 (Some are not) can both be true simultaneously if only a portion are inquisitive. Therefore, Statements 1 and 3 are the pair that cannot be true simultaneously.

Wrong path: A student might think "Some" means "Some but not all" (everyday language trap), leading them to believe Statements 2 and 4 cannot both be true (Option C). This breaks because in formal logic, "Some" means "at least one" and does not exclude "All". If all are inquisitive, both "Some are" and "Some are not" (wait, if all are, "Some are not" is false. But if some are, then some are not can also be true. The pair 2 and 4 can both be true if the set is partially inquisitive). Generalization: Never assume "Some S are P" implies "Some S are not P" in formal logic. Verification: Statements 1 and 3 directly contradict each other for any non-empty set.

Question 29 · Analytical Aptitude · 2022 MCQ

Some people believe that “what gets measured, improves”. Some others believe that “what gets measured, gets gamed”. One possible reason for the difference in the beliefs is the work culture in organizations. In organizations with good work culture, metrics help improve outcomes. However, the same metrics are counterproductive in organizations with poor work culture.

Which one of the following is the CORRECT logical inference based on the information in the above passage?

A.
Metrics are useful in organizations with poor work culture
B.
Metrics are useful in organizations with good work culture
C.
Metrics are always counterproductive in organizations with good work culture
D.
Metrics are never useful in organizations with good work culture

Correct Answer:

Step-by-Step Solution

Insight: The passage explicitly states the effect of metrics in good work cultures. Deductive inference requires selecting what must be true based strictly on the text.

Exam route: Scan for "good work culture". The text says "metrics help improve outcomes". This directly means metrics are useful. Match with Option B.

Learning route:

Analyze the passage: The text states, "In organizations with good work culture, metrics help improve outcomes."
Apply the Golden Rule of Deductive Inference: Accept the passage as absolute truth and look for what must be true without adding outside assumptions.
Evaluate options:

Option A claims metrics are useful in poor work culture, but the text says they are "counterproductive".
Option B claims metrics are useful in good work culture, which perfectly matches "help improve outcomes".
Options C and D claim metrics are counterproductive or never useful in good work culture, directly contradicting the text.

Answer is B.

Question 30 · Analytical Aptitude · 2022 MCQ

The corners and mid-points of the sides of a triangle are named using the distinct letters P, Q, R, S, T and U, but not necessarily in the same order. Consider the following statements:

• The line joining P and R is parallel to the line joining Q and S.
• P is placed on the side opposite to the corner T.
• S and U cannot be placed on the same side.

Which one of the following statements is correct based on the above information?

A.
P cannot be placed at a corner
B.
S cannot be placed at a corner
C.
U cannot be placed at a mid-point
D.
R cannot be placed at a corner

Correct Answer:

Step-by-Step Solution

Insight: In a triangle, the only way two lines formed by {corners, midpoints} are parallel is if one is a mid-segment (connecting two midpoints) and the other is the side parallel to it (connecting two corners).

Exam route:

Step 1: PR || QS. This means either {P, R} are midpoints and {Q, S} are corners, OR {P, R} are corners and {Q, S} are midpoints.

Step 2: "P is placed on the side opposite to the corner T." This implies T is a corner, and the side containing P is opposite to T.

Step 3: Test Case A: {P, R} are midpoints. Then PR is a mid-segment. It is parallel to the side connecting the two corners not on the sides of P and R. For QS to be parallel to PR, Q and S must be those two corners. Thus, corners = {Q, S, T}. This leaves {P, R, U} as midpoints. But S is a corner, so it belongs to two sides. U is a midpoint, so it must lie on one of those two sides, violating "S and U cannot be placed on the same side". Contradiction.

Step 4: Test Case B: {P, R} are corners. Then PR is a side. For QS to be parallel to PR, QS must be the mid-segment. Thus, {Q, S} are midpoints. This perfectly satisfies all clues: T is the third corner, and S (a midpoint) and U (the remaining midpoint) are on different sides.

Step 5: Conclusion: S must be a midpoint. Therefore, "S cannot be placed at a corner" is definitively true.

Learning route:

Step 1: Recall the geometric constraint: Parallel lines in this context require one mid-segment and one side.

Step 2: Set up the two mutually exclusive cases for {P, R} and {Q, S}.

Step 3: Use the "opposite to corner T" clue to anchor T as a corner and link P to a specific side.

Step 4: Apply the negative constraint "S and U not on same side" to eliminate the case where S is a corner (as it would force U onto a side touching S).

Step 5: Deduce that S must be a midpoint, making the statement "S cannot be placed at a corner" the correct answer.

Question 31 · Spatial Aptitude · 2022 MCQ

A palindrome is a word that reads the same forwards and backwards. In a game of words, a player has the following two plates painted with letters.

From the additional plates given in the options, which one of the combinations of additional plates would allow the player to construct a five-letter palindrome. The player should use all the five plates exactly once. The plates can be rotated in their plane.

Question 32 · Spatial Aptitude · 2022 MCQ

A plot of land must be divided between four families. They want their individual plots to be similar in shape, not necessarily equal in area. The land has equally spaced poles, marked as dots in the below figure. Two ropes, R1 and R2, are already present and cannot be moved.

What is the least number of additional straight ropes needed to create the desired plots? A single rope can pass through three poles that are aligned in a straight line.

A.
2
B.
4
C.
5
D.
3

Correct Answer:

Step-by-Step Solution

Key idea: This is a geometric partitioning problem where we must divide an irregular polygon into 4 similar shapes using the minimum number of additional straight lines (ropes).

Step 1: Analyze the given shape and existing ropes.

The land is a hexagon with equally spaced poles. R1 is a horizontal rope of length 2 units. R2 is a vertical rope of length 2 units.

Step 2: Understand the goal.

We need 4 similar plots. Similarity means they must have the same shape and angles, though their areas can differ.

Step 3: Visualize the partition.

To create 4 similar shapes from this specific hexagon, we need to extend the existing boundaries and create proportional divisions. By adding 3 strategic ropes (e.g., extending R1, extending R2, and adding one diagonal or connecting rope), we can divide the land into 4 regions that are scaled versions of each other.

Step 4: Verify the minimum number.

With 2 additional ropes, we can at most create 3 or 4 regions, but they will not maintain the required similarity in shape. With exactly 3 additional ropes, we can achieve the required 4 similar plots by completing the internal grid that mirrors the outer boundary's proportions.

Answer: D

Question 33 · Digital Logic · 2022 MCQ

Let R1 and R2 be two 4-bit registers that store numbers in 2’s complement form. For the operation R1+R2, which one of the following values of R1 and R2 gives an arithmetic overflow?

A.
R1 = 1011 and R2 = 1110
B.
R1 = 1100 and R2 = 1010
C.
R1 = 0011 and R2 = 0100
D.
R1 = 1001 and R2 = 1111

Correct Answer:

Step-by-Step Solution

Insight: Overflow in 2's complement only occurs when adding two numbers of the same sign yields a result with a different sign.

Exam route:

Check the sign bits (MSB) of R1 and R2.

A) 1011 (-), 1110 (-). Same sign. Sum = 11001 $\to$ 1001 (-). No overflow.

B) 1100 (-), 1010 (-). Same sign. Sum = 10110 $\to$ 0110 (+). OVERFLOW.

C) 0011 (+), 0100 (+). Same sign. Sum = 0111 (+). No overflow.

D) 1001 (-), 1111 (-). Same sign. Sum = 11000 $\to$ 1000 (-). No overflow.

Learning route:

In a 4-bit 2's complement system, the range is -8 to +7. Overflow happens if the true mathematical sum exceeds this range.

The golden rule for detection: Overflow can ONLY happen when adding two numbers of the same sign. If the operands have the same sign, but the result's sign bit is different, overflow has occurred.

Let's evaluate the options:

A) R1 = 1011 (-5), R2 = 1110 (-2). Both negative. Sum = -7. Binary: 1011 + 1110 = 11001. Discard carry $\to$ 1001 (-7). Sign matches. Valid.

B) R1 = 1100 (-4), R2 = 1010 (-6). Both negative. True sum = -10 (out of range). Binary: 1100 + 1010 = 10110. Discard carry $\to$ 0110 (+6). Two negatives gave a positive. OVERFLOW.

C) R1 = 0011 (+3), R2 = 0100 (+4). Both positive. Sum = +7. Binary: 0011 + 0100 = 0111 (+7). Sign matches. Valid.

D) R1 = 1001 (-7), R2 = 1111 (-1). Both negative. Sum = -8. Binary: 1001 + 1111 = 11000. Discard carry $\to$ 1000 (-8). Sign matches. Valid.

Question 34 · Digital Logic · 2022 MCQ

Consider a digital display system (DDS) shown in the figure that displays the contents of register X. A 16-bit code word is used to load a word in X, either from S or from R. S is a 1024-word memory segment and R is a 32-word register file. Based on the value of mode bit M, T selects an input word to load in X. P and Q interface with the corresponding bits in the code word to choose the addressed word. Which one of the following represents the functionality of P, Q, and T?

A.
P is 10:1 multiplexer; Q is 5:1 multiplexer; T is 2:1 multiplexer
B.
P is 10: $2^{10}$ decoder; Q is 5: $2^{5}$ decoder; T is 2:1 encoder
C.
P is 10: $2^{10}$ decoder; Q is 5: $2^{5}$ decoder; T is 2:1 multiplexer
D.
P is 1:10 de-multiplexer; Q is 1:5 de-multiplexer; T is 2:1 multiplexer

Correct Answer:

Step-by-Step Solution

Insight: The system routes a 16-bit word from either a 1024-word memory (S) or a 32-word register file (R) based on a mode bit M, requiring specific address decoding and data selection hardware.

Exam route:

S requires 10 address bits ( $2^{10} = 1024$ ), so P must be a 10-to- $2^{10}$ decoder.
R requires 5 address bits ( $2^{5} = 32$ ), so Q must be a 5-to- $2^{5}$ decoder.
T selects between the two 16-bit outputs based on M, making it a 2:1 multiplexer.
Option C matches this hardware configuration perfectly.

Learning route:

Identify address requirements: 1024 words need 10 bits, 32 words need 5 bits.
Decoders convert $n$ -bit addresses to $2^{n}$ selection lines. Thus, P is 10: $2^{10}$ and Q is 5: $2^{5}$ .
A multiplexer selects one of multiple data inputs. T chooses between S and R, so it is a 2:1 MUX.
Option C perfectly matches this hardware configuration.

Question 35 · Algorithms · 2022 MCQ

Which one of the following statements is TRUE for all positive functions $f (n)$ ?

A.
$f (n^{2}) = θ (f (n)^{2})$ , when $f (n)$ is a polynomial
B.
$f (n^{2}) = o (f (n)^{2})$
C.
$f (n^{2}) = O (f (n)^{2})$ , when $f (n)$ is an exponential function
D.
$f (n^{2}) = Ω (f (n)^{2})$

Question 36 · Algorithms · 2022 MSQ

Consider a simple undirected weighted graph $G$ , all of whose edge weights are distinct. Which of the following statements about the minimum spanning trees of $G$ is/are TRUE?

A.
The edge with the second smallest weight is always part of any minimum spanning tree of $G$ .
B.
One or both of the edges with the third smallest and the fourth smallest weights are part of any minimum spanning tree of $G$ .
C.
Suppose $S \subseteq V$ be such that $S \neq = ϕ$ and $S \neq = V$ . Consider the edge with the minimum weight such that one of its vertices is in $S$ and the other in $V ∖ S$ . Such an edge will always be part of any minimum spanning tree of $G$ .
D.
$G$ can have multiple minimum spanning trees.

Correct Answer:

["A","B","C"]

Step-by-Step Solution

Key idea: Apply the Cut Property and Kruskal's algorithm logic to a graph with strictly distinct edge weights.

Step 1: Analyze the distinct weights condition. Since all edge weights are distinct, the Minimum Spanning Tree (MST) of the graph is strictly unique. This immediately makes the statement "G can have multiple minimum spanning trees" FALSE.

Step 2: Evaluate the smallest edges. Let the edges sorted by weight be $e_{1} < e_{2} < e_{3} < e_{4} \dots$

By Kruskal's algorithm, $e_{1}$ is always included.

Step 3: Evaluate $e_{2}$ . Can $e_{2}$ form a cycle with $e_{1}$ ? No, because a cycle requires at least 3 edges in a simple graph. Thus, $e_{2}$ will never be rejected by Kruskal's and is always in the MST. Statement A is TRUE.

Step 4: Evaluate $e_{3}$ and $e_{4}$ . For an edge to be rejected by Kruskal's, it must form a cycle with edges already in the MST. The only edges smaller than $e_{3}$ are $e_{1}$ and $e_{2}$ . These two edges can form at most one path of length 2 (if they share a vertex). Therefore, they can form a cycle with at most ONE additional edge (which would be $e_{3}$ ).

Step 5: Since $e_{1}$ and $e_{2}$ can only cause the rejection of at most one edge (the one closing their cycle), they cannot cause the rejection of BOTH $e_{3}$ and $e_{4}$ . Thus, at least one of $e_{3}$ or $e_{4}$ must be accepted into the MST. Statement B is TRUE.

Step 6: Evaluate the cut property. The statement describes exactly the Cut Property: the minimum weight edge crossing any cut $(S, V ∖ S)$ is always part of the MST. Since weights are distinct, this minimum is unique. Statement C is TRUE.

Answer: A, B, C

Question 37 · Verbal Aptitude · 2022 MCQ

The _________ is too high for it to be considered _________.

A.
fair / fare
B.
faer / fair
C.
fare / fare
D.
fare / fair

Correct Answer:

Step-by-Step Solution

Insight: This is a classic homophone and commonly confused words question, testing the distinction between "fare" (price) and "fair" (just/reasonable).

Exam route: The sentence needs a noun for the first blank (something that can be "too high") and an adjective for the second blank (a judgment of that thing). "Fare" is the price charged for a journey. "Fair" means just or reasonable. "The fare is too high for it to be considered fair."

Learning route:

Step 1: Analyze the grammatical and logical requirements of the blanks. The first blank is the subject, requiring a noun representing a cost or value. The second blank follows "considered", requiring an adjective describing a judgment of that cost.

Step 2: Define the candidate words. "Fare" (noun): The money a passenger on public transportation has to pay. "Fair" (adjective): Treating people equally without favouritism; just or reasonable.

Step 3: Test the combinations. "fair / fare" places an adjective in the noun slot. "faer" is not a standard English word. "fare / fare" makes no logical sense. "fare / fair" creates a logically sound sentence: "The fare (price) is too high for it to be considered fair (reasonable)."

Section-wise Paper Structure

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 2022 Question Paper with Solutions: 65 Questions, Answer Key & Section-wise Analysis

Paper breakdown

Free sample questions from GATE CS 2022 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

Other GATE CS papers