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

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

Free sample questions from GATE CS 2023 Question Paper

Question 1 · Engineering Mathematics · 2023 MCQ

The Lucas sequence

L_{n}

is defined by the recurrence relation:

L_{n} = L_{n - 1} + L_{n - 2}, for n \geq 3,

with

L_{1} = 1

and

L_{2} = 3

.

Which one of the options given is TRUE?

A.
$L_{n} = (\frac{1 + 5}{2})^{n} + (\frac{1 - 5}{2})^{n}$
B.
$L_{n} = (\frac{1 + 5}{2})^{n} - (\frac{1 - 5}{3})^{n}$
C.
$L_{n} = (\frac{1 + 5}{2})^{n} + (\frac{1 - 5}{3})^{n}$
D.
$L_{n} = (\frac{1 + 5}{2})^{n} - (\frac{1 - 5}{2})^{n}$

Correct Answer:

Step-by-Step Solution

Insight: This is a second-order linear homogeneous recurrence. The characteristic roots are the golden ratio and its conjugate, and the initial conditions perfectly match the sum of their powers.

Exam route: Write the characteristic equation $r^{2} - r - 1 = 0$ . The roots are $α = \frac{1 + 5}{2}$ and $β = \frac{1 - 5}{2}$ . Notice that $α + β = 1$ and $α^{2} + β^{2} = (α + β)^{2} - 2 α β = 1^{2} - 2 (- 1) = 3$ . These exactly match $L_{1} = 1$ and $L_{2} = 3$ . Thus, the coefficients are both 1.

Learning route:

Step 1: Identify the recurrence type. The relation $L_{n} = L_{n - 1} + L_{n - 2}$ is a linear homogeneous recurrence with constant coefficients.

Step 2: Form the characteristic equation. Rewrite as $L_{n} - L_{n - 1} - L_{n - 2} = 0$ . The characteristic equation is $r^{2} - r - 1 = 0$ .

Step 3: Find the roots. Using the quadratic formula, $r = \frac{1 \pm 1 - 4 ( 1 ) ( - 1 )}{2} = \frac{1 \pm 5}{2}$ . Let $α = \frac{1 + 5}{2}$ and $β = \frac{1 - 5}{2}$ .

Step 4: Write the general solution. Since the roots are distinct, $L_{n} = c_{1} α^{n} + c_{2} β^{n}$ .

Step 5: Apply initial conditions.

For $n = 1$ : $c_{1} α + c_{2} β = 1$ .

For $n = 2$ : $c_{1} α^{2} + c_{2} β^{2} = 3$ .

We know $α + β = 1$ (sum of roots) and $α β = - 1$ (product of roots).

Calculate $α^{2} + β^{2} = (α + β)^{2} - 2 α β = 1^{2} - 2 (- 1) = 3$ .

Comparing this with the $n = 2$ condition, we see that $c_{1} = 1$ and $c_{2} = 1$ is a valid solution.

Step 6: Verify with $n = 1$ . $1 \cdot α + 1 \cdot β = α + β = 1$ , which matches $L_{1} = 1$ .

Therefore, the closed form is $L_{n} = α^{n} + β^{n} = (\frac{1 + 5}{2})^{n} + (\frac{1 - 5}{2})^{n}$ .

Answer: A

Question 2 · Engineering Mathematics · 2023 MCQ

Let

A = 1432214332144321

and

B = 3412412312342341 .

Let

det (A)

and

det (B)

denote the determinants of the matrices

A

and

B

, respectively.

Which one of the options given below is TRUE?

A.
$det (A) = det (B)$
B.
$det (B) = - det (A)$
C.
$det (A) = 0$
D.
$det (A B) = det (A) + det (B)$

Correct Answer:

Step-by-Step Solution

Key idea: This is a determinant permutation question, recognizable because it compares the determinants of two matrices that are row-permutations of each other. The trigger is the cyclic shifting of rows between $A$ and $B$ .

Step 1: Write down the rows of $A$ and $B$ .

$A$ : R1=(1,2,3,4), R2=(4,1,2,3), R3=(3,4,1,2), R4=(2,3,4,1).

$B$ : R1=(3,4,1,2), R2=(4,1,2,3), R3=(1,2,3,4), R4=(2,3,4,1).

Step 2: Compare the rows to find the permutation.

Notice that Row 1 of $B$ is exactly Row 3 of $A$ .

Row 2 of $B$ is exactly Row 2 of $A$ .

Row 3 of $B$ is exactly Row 1 of $A$ .

Row 4 of $B$ is exactly Row 4 of $A$ .

Step 3: Determine the effect on the determinant.

Matrix $B$ is obtained from $A$ by swapping Row 1 and Row 3. This is a single elementary row swap.

Step 4: A single row swap multiplies the determinant by $- 1$ .

Therefore, $det (B) = - det (A)$ .

Answer: Option B.

Question 3 · Engineering Mathematics · 2023 MSQ

Geetha has a conjecture about integers, which is of the form

\forall x (P (x) ⟹ \exists y Q (x, y)),

where

P

is a statement about integers, and

Q

is a statement about pairs of integers.
Which of the following (one or more) option(s) would imply Geetha’s conjecture?

A.
$\exists x (P (x) \land \forall y Q (x, y))$
B.
$\forall x \forall y Q (x, y)$
C.
$\exists y \forall x (P (x) ⟹ Q (x, y))$
D.
$\exists x (P (x) \land \exists y Q (x, y))$

Correct Answer:

["B","C"]

Step-by-Step Solution

Key idea: This is a quantified reasoning question about nested quantifiers and implications. The conjecture $\forall x (P (x) ⟹ \exists y Q (x, y))$ requires that for every $x$ , if $P (x)$ holds, then some $y$ exists making $Q (x, y)$ true. We must test which options logically force this to be true for all $x$ .

Step 1: Analyze the conjecture structure.

The conjecture is a universal statement: for ALL $x$ , the implication $P (x) ⟹ \exists y Q (x, y)$ must hold. To imply this, an option must guarantee the condition for every possible $x$ .

Step 2: Evaluate Option A: $\exists x (P (x) \land \forall y Q (x, y))$ .

This asserts there is at least one specific $x_{0}$ where $P (x_{0})$ is true and $Q (x_{0}, y)$ is true for all $y$ . However, this gives no information about any other $x$ . If there exists another $x_{1}$ where $P (x_{1})$ is true but no $y$ satisfies $Q (x_{1}, y)$ , the conjecture fails. Thus, A does not imply the conjecture.

Step 3: Evaluate Option B: $\forall x \forall y Q (x, y)$ .

This asserts $Q (x, y)$ is true for every pair $(x, y)$ . Now take any arbitrary $x$ . If $P (x)$ is true, we can pick any $y$ (the domain is non-empty) and $Q (x, y)$ will be true. Thus $\exists y Q (x, y)$ is guaranteed. This implies the conjecture.

Step 4: Evaluate Option C: $\exists y \forall x (P (x) ⟹ Q (x, y))$ .

This asserts there is a single, fixed $y_{0}$ such that for all $x$ , $P (x) ⟹ Q (x, y_{0})$ . Now take any arbitrary $x$ . If $P (x)$ is true, then by the given condition, $Q (x, y_{0})$ must be true. Since $y_{0}$ exists, we have found a $y$ (namely $y_{0}$ ) such that $Q (x, y)$ is true. Thus $\exists y Q (x, y)$ holds for all $x$ . This implies the conjecture.

Step 5: Evaluate Option D: $\exists x (P (x) \land \exists y Q (x, y))$ .

Similar to Option A, this only guarantees the condition for one specific $x$ . It does not cover all $x$ , so it cannot imply the universal conjecture.

Answer: B, C

Question 4 · Programming and Data Structures · 2023 MCQ

Which one of the following sequences when stored in an array at locations $A [1], \dots, A [10]$ forms a max-heap?

A.
23, 17, 10, 6, 13, 14, 1, 5, 7, 12
B.
23, 17, 14, 7, 13, 10, 1, 5, 6, 12
C.
23, 17, 14, 6, 13, 10, 1, 5, 7, 15
D.
23, 14, 17, 1, 10, 13, 16, 12, 7, 5

Correct Answer:

Step-by-Step Solution

Insight: This is a heap validation question. We need to check which of the given arrays satisfies the max-heap property: every parent must be greater than or equal to its children.

Exam route:

The max-heap property requires $A [i] \geq A [2 i]$ and $A [i] \geq A [2 i + 1]$ for all valid $i$ .
We can quickly eliminate options by checking small values of $i$ .
Check Option A: At $i = 3$ , $A [3] = 10$ . Its children are $A [6] = 14$ and $A [7] = 1$ . Since $10 < 14$ , this violates the max-heap property. Eliminate A.
Check Option C: At $i = 5$ , $A [5] = 13$ . Its child is $A [10] = 15$ . Since $13 < 15$ , this violates the property. Eliminate C.
Check Option D: At $i = 4$ , $A [4] = 1$ . Its children are $A [8] = 12$ and $A [9] = 7$ . Since $1 < 12$ , this violates the property. Eliminate D.
Check Option B: Every internal node is greater than or equal to its children. Specifically, 23>=17,14; 17>=7,13; 14>=10,1; 7>=5,6; and 13>=12. Option B satisfies all conditions.

Learning route:

Understand the max-heap property: For every node $i$ (from 1 to $⌊ n /2 ⌋$ ), its value must be greater than or equal to the values of its left child ( $2 i$ ) and right child ( $2 i + 1$ ), if they exist.
Systematically check each option. It is often faster to look for violations rather than verifying every single node.
A violation occurs if any parent is strictly less than any of its children.
By checking the internal nodes (indices 1 to 5 for a 10-element array), we can quickly identify which arrays are invalid max-heaps.

Question 5 · Programming and Data Structures · 2023 MCQ

Let SLLdel be a function that deletes a node in a singly-linked list given a pointer to the node and a pointer to the head of the list. Similarly, let DLLdel be another function that deletes a node in a doubly-linked list given a pointer to the node and a pointer to the head of the list.

Let

n

denote the number of nodes in each of the linked lists. Which one of the following choices is TRUE about the worst-case time complexity of SLLdel and DLLdel?

A.
$SLLdel$ is $O (1)$ and $DLLdel$ is $O (n)$
B.
Both $SLLdel$ and $DLLdel$ are $O (lo g (n))$
C.
Both $SLLdel$ and $DLLdel$ are $O (1)$
D.
$SLLdel$ is $O (n)$ and $DLLdel$ is $O (1)$

Correct Answer:

Step-by-Step Solution

Insight: This is a linked list deletion complexity question, recognizable because it asks for the worst-case time complexity of deleting a node given specific pointers.

Exam route: SLL requires $O (n)$ to find the predecessor from the head in the worst case (last node). DLL provides $O (1)$ access to the predecessor via the prev pointer.

Learning route:

Step 1: Analyze SLLdel. We are given a pointer to the node to be deleted and a pointer to the head. To delete a node in a singly linked list, we must update the next pointer of its predecessor. Since we only have the target node's pointer, we must traverse from the head to find the predecessor. In the worst case (deleting the last node, where the copy-data trick fails), this traversal takes $O (n)$ time.

Step 2: Analyze DLLdel. We are given a pointer to the node to be deleted. In a doubly linked list, every node has a prev pointer. We can directly access the predecessor in $O (1)$ time, update its next pointer, and update the successor's prev pointer. This entire process takes $O (1)$ time, regardless of the node's position.

Step 3: Compare the complexities. SLLdel is $O (n)$ and DLLdel is $O (1)$ .

Question 6 · Programming and Data Structures · 2023 NAT

The integer value printed by the ANSI-C program given below is __________.

#include<stdio.h>

int funcp(){
    static int x = 1;
    x++;
    return x;
}

int main(){
    int x,y;
    x = funcp();
    y = funcp()+x;
    printf("%d\n", (x+y));
    return 0;
}

Correct Answer:

7.00

Step-by-Step Solution

Insight: A static local variable retains its value across function calls, while local variables in main are independent. The question tests whether you can track two distinct variables named x in different scopes.

Exam route: Trace the static x inside funcp across two calls, then combine with the local x and y in main.

Learning route:

First call x = funcp();:

Inside funcp: static x is initialized to 1 (this happens only once, ever).
x++ increments static x to 2.
Returns 2.
In main: local variable x is assigned 2.

Second call y = funcp() + x;:

Inside funcp: static x retains its value of 2 from the previous call.
x++ increments static x to 3.
Returns 3.
In main: the expression evaluates to 3 + 2 (the local x in main is still 2).
Local y is assigned 5.

Print: printf("%d\n", (x+y)) prints 2 + 5 = 7.

Wrong path producing 5: A student who assumes static x resets to 1 on every call would get: first call returns 2, second call also returns 2, so y = 2 + 2 = 4, and x + y = 2 + 4 = 6. Or they might confuse the two x variables entirely.

Wrong path producing 9: A student who thinks the local x in main is the same variable as the static x in funcp might set x = 3 after the second call, then compute y = 3 + 3 = 6 and print 3 + 6 = 9.

Verification: Static x inside funcp: 1 $\to$ 2 $\to$ 3 (across two calls). Local x in main: 2 (set once, never modified again). Local y: 5. Sum: 7. Confirmed.

Generalization: Variables with the same name in different scopes are completely independent. Static variables persist across calls; automatic variables do not. Always maintain separate columns for each scope in your trace.

Question 7 · Operating System · 2023 MSQ

Which one or more of the following need to be saved on a context switch from one thread (T1) of a process to another thread (T2) of the same process?

A.
Page table base register
B.
Stack pointer
C.
Program counter
D.
General purpose registers

Question 8 · Operating System · 2023 MSQ

Which one or more of the following options guarantee that a computer system will transition from user mode to kernel mode?

A.
Function Call
B.
malloc Call
C.
Page Fault
D.
System Call

Question 9 · Operating System · 2023 MSQ

Which one or more of the following CPU scheduling algorithms can potentially cause starvation?

A.
First-in First-Out
B.
Round Robin
C.
Priority Scheduling
D.
Shortest Job First

Question 10 · Computer Organization and Architecture · 2023 NAT

Consider a 3-stage pipelined processor having a delay of 10 ns (nanoseconds), 20 ns, and 14 ns, for the first, second, and the third stages, respectively. Assume that there is no other delay and the processor does not suffer from any pipeline hazards. Also assume that one instruction is fetched every cycle.

The total execution time for executing 100 instructions on this processor is __________ ns.

Correct Answer:

2040

Step-by-Step Solution

Insight: In a synchronous pipeline, the clock cycle time is dictated by the slowest stage. Total time is (k + n - 1) multiplied by this cycle time.

Exam route: Max stage delay = 20 ns. Latch delay = 0. Cycle time = 20 ns. Total cycles = 3 + 100 - 1 = 102. Total time = 102 × 20 = 2040 ns.

Learning route:

Identify the delay of each stage: 10 ns, 20 ns, 14 ns.
Determine the pipeline cycle time, which is the maximum stage delay plus any latch delay. Here, max(10, 20, 14) + 0 = 20 ns.
Identify the number of stages (k = 3) and the number of instructions (n = 100).
Calculate the total number of cycles required to execute n instructions in a k-stage pipeline: k + n - 1 = 3 + 100 - 1 = 102 cycles.
Multiply the total cycles by the cycle time: 102 × 20 ns = 2040 ns.

Question 11 · Computer Organization and Architecture · 2023 NAT

A keyboard connected to a computer is used at a rate of 1 keystroke per second. The computer system polls the keyboard every 10 ms (milli seconds) to check for a keystroke and consumes

100 μ s

(micro seconds) for each poll. If it is determined after polling that a key has been pressed, the system consumes an additional

200 μ s

to process the keystroke. Let

T_{1}

denote the fraction of a second spent in polling and processing a keystroke.

In an alternative implementation, the system uses interrupts instead of polling. An interrupt is raised for every keystroke. It takes a total of 1 ms for servicing an interrupt and processing a keystroke. Let

T_{2}

denote the fraction of a second spent in servicing the interrupt and processing a keystroke.

The ratio

\frac{T _{1}}{T _{2}}

is __________. (Rounded off to one decimal place)

Correct Answer:

10.2

Step-by-Step Solution

Key idea: This is an I/O overhead comparison question, asking to calculate and compare the CPU time fraction consumed by polling versus interrupt-driven I/O.

Step 1: Calculate $T_{1}$ (Polling overhead per second).

Polling interval = 10 ms = 0.01 seconds.
Number of polls per second = $1/0.01 = 100$ polls.
Time spent polling per second = $100 \times 100 \mu s = 10, 000 \mu s = 0.01$ seconds.
The keyboard is used at 1 keystroke per second. Processing time for this keystroke = $200 \mu s = 0.0002$ seconds.
Total $T_{1} = 0.01 + 0.0002 = 0.0102$ seconds.

Step 2: Calculate $T_{2}$ (Interrupt overhead per second).

1 keystroke per second triggers 1 interrupt.
Time per interrupt service and processing = 1 ms = 0.001 seconds.
Total $T_{2} = 0.001$ seconds.

Step 3: Calculate the ratio $T_{1} / T_{2}$ .

Ratio = $0.0102/0.001 = 10.2$ .

Answer: 10.2

Question 12 · Computer Organization and Architecture · 2023 MCQ

Consider the given C-code and its corresponding assembly code, with a few operands U1–U4 being unknown. Some useful information as well as the semantics of each unique assembly instruction is annotated as inline comments in the code. The memory is byte-addressable.

//C-code

int a[10], b[10], i;
// int is 32-bit
for (i=0; i<10;i++)
   a[i] = b[i] * 8;

;assembly-code (; indicates comments)
;r1-r5 are 32-bit integer registers
;initialize r1=0, r2=10
;initialize r3, r4 with base address of a, b

L01: jeq r1, r2, end    ;if(r1==r2) goto end
L02: lw r5, 0(r4)        ;r5 <- Memory[r4+0]
L03: shl r5, r5, U1      ;r5 <- r5 << U1
L04: sw r5, 0(r3)        ;Memory[r3+0] <- r5
L05: add r3, r3, U2      ;r3 <- r3+U2
L06: add r4, r4, U3
L07: add r1, r1, 1
L08: jmp U4            ;goto U4
L09: end

Which one of the following options is a CORRECT replacement for operands in the position (U1, U2, U3, U4) in the above assembly code?

A.
(8, 4, 1, L02)
B.
(3, 4, 4, L01)
C.
(8, 1, 1, L02)
D.
(3, 1, 1, L01)

Correct Answer:

Step-by-Step Solution

Key idea: This is an assembly translation and tracing question, recognisable by the side-by-side C code and assembly with missing operands (U1–U4).

Why this method applies: We must map the high-level array operation a[i] = b[i] * 8 to the low-level load-store assembly, paying close attention to data sizes (byte addressing) and loop control flow.

Step 1: Analyze the multiplication.

The C code multiplies b[i] by 8. In assembly, shl r5, r5, U1 performs a left shift. Shifting left by $k$ is equivalent to multiplying by $2^{k}$ .

Since $8 = 2^{3}$ , we must shift left by 3. Therefore, U1 = 3.

Step 2: Analyze the array pointer increments.

The arrays a and b are of type int, which is 32-bit (4 bytes).

The memory is byte-addressable. To move to the next element in the array, the base address pointer must be incremented by the size of one element in bytes.

Therefore, both r3 (base of a) and r4 (base of b) must be incremented by 4.

This means U2 = 4 and U3 = 4.

Step 3: Analyze the loop control flow.

The loop condition i < 10 is checked at label L01 (jeq r1, r2, end).

After incrementing the pointers and the loop counter i (add r1, r1, 1), the program must jump back to the beginning of the loop to re-evaluate the condition.

Therefore, the jump target U4 must be L01.

Step 4: Combine the findings.

(U1, U2, U3, U4) = (3, 4, 4, L01).

Answer: Option B.

Question 13 · Theory of Computation · 2023 MCQ

Consider the Deterministic Finite-state Automaton (DFA)

A

shown below. The DFA runs on the alphabet

{0, 1}

, and has the set of states

{s, p, q, r}

, with

s

being the start state and

p

being the only final state.

Which one of the following regular expressions correctly describes the language accepted by

A

A.
$1 (0^{*} 11)^{*}$
B.
$0 (0 + 1)^{*}$
C.
$1 (0 + 11)^{*}$
D.
$1 (11 0^{*})^{*}$

Correct Answer:

Step-by-Step Solution

Key idea: This is an FA to Regex conversion question. The visual method (State Elimination) or algebraic method (Arden's Theorem) applies. Here, identifying dead states simplifies the process massively.

Step 1: Analyze the given DFA for dead states. State $r$ has transitions to itself on both '0' and '1', and it is not a final state. Any path that enters $r$ is permanently trapped and will be rejected. Thus, $r$ is a dead state.

Step 2: Eliminate $r$ and all its incoming edges.

The transition $s \to r$ on '0' is deleted.

The transition $q \to r$ on '0' is deleted.

Step 3: Trace the valid paths through the remaining states ${s, p, q}$ .

To leave the start state $s$ without dying, we MUST read '1' to go to $p$ . (Reading '0' goes to dead state $r$ ).
Once in $p$ (the only final state), we can loop on '0' indefinitely. This gives the term $0^{*}$ .
From $p$ , we can read '1' to go to $q$ .
From $q$ , we MUST read '1' to return to $p$ (reading '0' goes to dead state $r$ ).

Thus, a round trip from $p \to q \to p$ consumes exactly "11".

Step 4: Combine the loops at state $p$ . At $p$ , we can either loop on '0' or take the round trip "11". This gives the union $(0 + 11)^{*}$ .

Step 5: Construct the final regex. We start at $s$ , read '1' to reach $p$ , and then loop at $p$ .

Regex = $1 (0 + 11)^{*}$ .

Answer: C

Question 14 · Theory of Computation · 2023 MSQ

Which of the following statements is/are CORRECT?

A.
The intersection of two regular languages is regular.
B.
The intersection of two context-free languages is context-free.
C.
The intersection of two recursive languages is recursive.
D.
The intersection of two recursively enumerable languages is recursively enumerable.

Question 15 · Theory of Computation · 2023 MCQ

Consider the context-free grammar

G

below

S \to a S b ∣ X

X \to a X ∣ X b ∣ a ∣ b,

where

S

and

X

are non-terminals, and

a

and

b

are terminal symbols. The starting non-terminal is

S

.

Which one of the following statements is CORRECT?

A.
The language generated by $G$ is $(a + b)^{*}$
B.
The language generated by $G$ is $a^{*} (a + b) b^{*}$
C.
The language generated by $G$ is $a^{*} b^{*} (a + b)$
D.
The language generated by $G$ is not a regular language

Correct Answer:

Step-by-Step Solution

Key idea: This is a CFG language identification question. We need to analyze what strings the grammar can generate by understanding the role of each non-terminal.

Step 1: Analyze the grammar structure.

Grammar:

S → aSb | X

X → aX | Xb | a | b

Step 2: Understand what X generates.

X can produce 'a' or 'b' directly.

Recursive rules X → aX and X → Xb allow adding 'a' to the left or 'b' to the right.

This means X can never generate a 'b' followed by an 'a'.

Thus, L(X) = { a^i b^j | i + j >= 1 } = ab - {ε}.

Step 3: Understand what S generates.

S → X allows S to produce anything X produces.

S → aSb wraps matching pairs of 'a' and 'b' around whatever S produces.

So S generates a^n w b^n, where w ∈ L(X) and n >= 0.

Let w = a^i b^j (with i + j >= 1).

Then the string is a^n a^i b^j b^n = a^{n+i} b^{j+n}.

Let N = n + i and M = j + n.

Since i + j >= 1, we have N + M = 2n + i + j >= 1.

Also, N >= 0 and M >= 0.

Thus, S generates exactly { a^N b^M | N + M >= 1 } = ab - {ε}.

Step 4: Match with options.

Option A: (a+b)* includes "ba" and ε, which are not in L(S).

Option B: a(a+b)b generates strings with zero or more 'a's, exactly one 'a' or 'b', and zero or more 'b's. This is exactly (a^+ b) ∪ (a b^+) = ab - {ε}. This matches L(S).

Option C: ab(a+b) can generate "ba" (e.g., a^0 b^1 a), which is not in L(S).

Option D: The language is regular, so this is false.

Answer: Option B is correct.

Question 16 · Computer Networks · 2023 MCQ

Suppose two hosts are connected by a point-to-point link and they are configured to use Stop-and-Wait protocol for reliable data transfer. Identify in which one of the following scenarios, the utilization of the link is the lowest.

A.
Longer link length and lower transmission rate
B.
Longer link length and higher transmission rate
C.
Shorter link length and lower transmission rate
D.
Shorter link length and higher transmission rate

Question 17 · Computer Networks · 2023 MSQ

Which of the following statements is/are INCORRECT about the OSPF (Open Shortest Path First) routing protocol used in the Internet?

A.
OSPF implements Bellman-Ford algorithm to find shortest paths.
B.
OSPF uses Dijkstra’s shortest path algorithm to implement least-cost path routing.
C.
OSPF is used as an inter-domain routing protocol.
D.
OSPF implements hierarchical routing.

Question 18 · Computer Networks · 2023 MSQ

Suppose you are asked to design a new reliable byte-stream transport protocol like TCP. This protocol, named myTCP, runs over a 100 Mbps network with Round Trip Time of 150 milliseconds and the maximum segment lifetime of 2 minutes.

Which of the following is/are valid lengths of the Sequence Number field in the myTCP header?

A.
30 bits
B.
32 bits
C.
34 bits
D.
36 bits

Question 19 · Compiler Design · 2023 MCQ

Consider the following statements regarding the front-end and back-end of a compiler.

S1: The front-end includes phases that are independent of the target hardware.
S2: The back-end includes phases that are specific to the target hardware.
S3: The back-end includes phases that are specific to the programming language used in the source code.

Identify the CORRECT option.

A.
Only S1 is TRUE.
B.
Only S1 and S2 are TRUE.
C.
S1, S2, and S3 are all TRUE.
D.
Only S1 and S3 are TRUE.

Correct Answer:

Step-by-Step Solution

Key idea: This question tests the conceptual division of a compiler into Front-End and Back-End.

Step 1: Analyze S1.

"The front-end includes phases that are independent of the target hardware."

The front-end handles lexical analysis, syntax analysis, semantic analysis, and intermediate code generation. These phases depend only on the source programming language, not on the machine where the code will run.

Statement S1 is TRUE.

Step 2: Analyze S2.

"The back-end includes phases that are specific to the target hardware."

The back-end handles code optimization (machine-dependent) and code generation. These phases must know the instruction set, registers, and memory architecture of the target CPU.

Statement S2 is TRUE.

Step 3: Analyze S3.

"The back-end includes phases that are specific to the programming language used in the source code."

This is FALSE. The programming language specifics are entirely handled by the front-end. The back-end only cares about the intermediate representation (IR) and the target hardware.

Statement S3 is FALSE.

Step 4: Conclusion.

Only S1 and S2 are TRUE.

Answer: B

Question 20 · Compiler Design · 2023 MCQ

Consider the following definition of a lexical token id for an identifier in a programming language, using extended regular expressions:

letter t e x t b f d i g i t t e x t b f i d \to [A-Za-z] \to [0-9] \to letter (letter ∣ digit)^{*}

Which one of the following Non-deterministic Finite-state Automata with

ϵ

-transitions accepts the set of valid identifiers? (A double-circle denotes a final state)

Correct Answer:

Step-by-Step Solution

Key idea: This is a Finite Automata construction question. We need to identify the NFA with $ϵ$ -transitions that correctly accepts the regular expression $letter (letter ∣ digit)^{*}$ .

Step 1: Analyze the Regular Expression.

The regex requires:

Exactly one letter to start.
Followed by zero or more occurrences of either letter or digit.

Step 2: Evaluate the structural requirements for the NFA.

The start state must transition to a final state on a letter.
To handle the Kleene star $(letter ∣ digit)^{*}$ , there must be a mechanism to loop back and accept any sequence of letters and digits.
In an NFA with $ϵ$ -transitions (like Thompson's construction), this is typically done by having $ϵ$ -transitions from the final state back to an intermediate state that branches into letter and digit transitions, which then loop back via $ϵ$ -transitions.

Step 3: Analyze the given options (based on standard GATE patterns).

Options that allow an $ϵ$ -transition directly from the start state to the final state incorrectly accept the empty string $ϵ$ .
Options that branch into separate non-communicating loops for letter and digit cannot accept mixed strings like a1b.
The correct NFA must have a central looping mechanism: after the first letter, an $ϵ$ -transition leads to a state that can read a letter OR a digit, and after reading either, it must be able to return to the start of the loop to read more characters.

Step 4: Identify the correct option.

Option D (the 4th option) correctly implements this structure:

Start $letter q_{1}$ (final).

$q_{1} ϵ q_{2}$ .

$q_{2} letter q_{3}$ (final) and $q_{2} digit q_{4}$ (final).

$q_{3} ϵ q_{2}$ and $q_{4} ϵ q_{2}$ .

This perfectly matches $letter (letter ∣ digit)^{*}$ .

Answer: D

Question 21 · Compiler Design · 2023 MCQ

Consider the following program:

int main()
{
   f1();
   f2(2);
   f3();
   return(0);
}

int f1()
{
   return(1);
}

int f2(int X)
{
   f3();
   if (X==1)
      return f1();
   else
      return (X*f2(X-1));
}

int f3()
{
   return(5);
}

Which one of the following options represents the activation tree corresponding to the main function?

Question 22 · Algorithms · 2023 MCQ

An algorithm has to store several keys generated by an adversary in a hash table. The adversary is malicious who tries to maximize the number of collisions. Let

k

be the number of keys,

m

be the number of slots in the hash table, and

k > m

.

Which one of the following is the best hashing strategy to counteract the adversary?

A.
Division method, i.e., use the hash function $h (k) = k mod m$ .
B.
Multiplication method, i.e., use the hash function $h (k) = ⌊ m (k A - ⌊ k A ⌋) ⌋$ , where $A$ is a carefully chosen constant.
C.
Universal hashing method.
D.
If $k$ is a prime number, use Division method. Otherwise, use Multiplication method.

Correct Answer:

Step-by-Step Solution

Key idea: Adversarial inputs defeat deterministic hashing. Universal hashing uses randomization to prevent the adversary from predicting collisions.

Step 1: Analyze the threat. The adversary knows the hash function and tries to maximize collisions. If the hash function is fixed (like Division or Multiplication method with fixed constants), the adversary can simply choose keys that all map to the same slot. For example, if $h (k) = k (mod m)$ , the adversary picks ${0, m, 2 m, \dots}$ . This results in $O (k)$ worst-case time for operations.

Step 2: Evaluate Division Method. It is deterministic. Once $m$ is known, the adversary can easily construct a worst-case input. Thus, it is not robust against a malicious adversary.

Step 3: Evaluate Multiplication Method. It depends on a constant $A$ . If $A$ is fixed and known, the adversary can still analyze the function and find collisions. While it distributes keys better for random data, it does not provide theoretical guarantees against an adversary who knows $A$ .

Step 4: Evaluate Universal Hashing. In universal hashing, we select a hash function $h$ randomly from a family $H$ at runtime. The adversary does not know which specific $h$ was chosen. By definition of a universal family, for any two distinct keys $x$ and $y$ , the probability of collision $P r [h (x) = h (y)] \leq 1/ m$ . This ensures that the expected number of collisions remains low, regardless of the adversary's strategy.

Step 5: Conclusion. Universal hashing is the only strategy among the options that provides probabilistic guarantees against an adversary by introducing randomness unknown to the attacker.

Answer: C

Question 23 · Algorithms · 2023 MSQ

Let

f

and

g

be functions of natural numbers given by

f (n) = n

and

g (n) = n^{2}

.
Which of the following statements is/are TRUE?

A.
$f \in O (g)$
B.
$f \in Ω (g)$
C.
$f \in o (g)$
D.
$f \in Θ (g)$

Question 24 · Algorithms · 2023 MSQ

Consider functions Function 1 and Function 2 expressed in pseudocode as follows:

Function 1
while

n&gt;1

do
for

i = 1

n

x = x + 1;

end for

n = ⌊ n /2 ⌋;

end while

Function 2
for

i = 1

100 * n

x = x + 1;

end for

Let

f_{1} (n)

and

f_{2} (n)

denote the number of times the statement “

x = x + 1

” is executed in Function 1 and Function 2, respectively.

Which of the following statements is/are TRUE?

A.
$f_{1} (n) \in Θ (f_{2} (n))$
B.
$f_{1} (n) \in o (f_{2} (n))$
C.
$f_{1} (n) \in ω (f_{2} (n))$
D.
$f_{1} (n) \in O (n)$

Correct Answer:

["A","D"]

Step-by-Step Solution

Key idea: This is a loop complexity analysis question, recognizable because it provides pseudocode and asks for the asymptotic relationship between the execution counts of two functions.

Why this method applies: We need to mathematically count the number of iterations for each loop structure and then compare their growth rates using asymptotic notation definitions.

Step 1: Analyze Function 1. The outer while loop halves $n$ each time. The inner for loop runs $n$ times, then $⌊ n /2 ⌋$ times, then $⌊ n /4 ⌋$ times, and so on.

Step 2: The total number of executions $f_{1} (n)$ is bounded by the geometric series: $n + \frac{n}{2} + \frac{n}{4} + \dots \leq n \sum_{i = 0}^{\infty} (\frac{1}{2})^{i} = 2 n$ .

Step 3: Thus, $f_{1} (n) = Θ (n)$ .

Step 4: Analyze Function 2. The for loop runs exactly $100 n$ times. Thus, $f_{2} (n) = 100 n$ , which is also $Θ (n)$ .

Step 5: Compare $f_{1} (n)$ and $f_{2} (n)$ . Since both are $Θ (n)$ , their ratio approaches a constant ( $2/100$ ). Therefore, $f_{1} (n) \in Θ (f_{2} (n))$ is TRUE.

Step 6: Check other options. $f_{1} (n) \in o (f_{2} (n))$ is FALSE because the limit of their ratio is not 0. $f_{1} (n) \in ω (f_{2} (n))$ is FALSE for the same reason. $f_{1} (n) \in O (n)$ is TRUE because $f_{1} (n) \leq 2 n$ .

Answer: Options A and D are true.

Question 25 · Digital Logic · 2023 MCQ

The output of a 2-input multiplexer is connected back to one of its inputs as shown in the figure.

Match the functional equivalence of this circuit to one of the following options.

A.
D Flip-flop
B.
D Latch
C.
Half-adder
D.
Demultiplexer

Correct Answer:

Step-by-Step Solution

Insight: A 2x1 multiplexer with its output fed back to the '0' input and a select line 'S' acts as a level-sensitive memory element, specifically a D Latch.

Exam route: The MUX equation is $Y = \overline{S} \cdot I_{0} + S \cdot I_{1}$ . Substitute $I_{0} = Y_{o l d}$ (feedback) and $I_{1} = D$ (new data). This yields $Y_{n e w} = \overline{S} \cdot Y_{o l d} + S \cdot D$ , which is the exact characteristic equation of a D Latch where S acts as the Enable signal.

Learning route:

Step 1: Write the standard Boolean equation for a 2x1 multiplexer: $Y = \overline{S} \cdot I_{0} + S \cdot I_{1}$ .

Step 2: Identify the connections from the diagram. The output $Y$ is connected to input $I_{0}$ . Let the other input (at '1') be the data input $D$ .

Step 3: Substitute $I_{0} = Y_{o l d}$ into the MUX equation: $Y_{n e w} = \overline{S} \cdot Y_{o l d} + S \cdot D$ .

Step 4: Analyze the behavior based on the select line $S$ :

If $S = 0$ : $Y_{n e w} = 1 \cdot Y_{o l d} + 0 \cdot D = Y_{o l d}$ . The circuit holds its previous state (Memory/Transparent-low state).
If $S = 1$ : $Y_{n e w} = 0 \cdot Y_{o l d} + 1 \cdot D = D$ . The output follows the input data (Transparent-high state).

Step 5: Match this behavior to standard sequential elements. This "hold when 0, follow when 1" behavior is the defining characteristic of a positive-level-sensitive D Latch.

Verification: A D Flip-flop requires edge-triggering (typically built with two latches and an inverter), which is not present here. A half-adder and demultiplexer are combinational or different sequential structures entirely.

Question 26 · Digital Logic · 2023 NAT

A particular number is written as 132 in radix-4 representation. The same number in radix-5 representation is __________.

Correct Answer:

110.00

Step-by-Step Solution

Insight: Route the conversion through Base 10 to avoid direct base-4 to base-5 arithmetic errors.

Exam route:

Convert $(132)_{4}$ to Base 10: $1 (16) + 3 (4) + 2 (1) = 30$ .
Convert $3 0_{10}$ to Base 5: $30 \div 5 = 6$ R $0$ ; $6 \div 5 = 1$ R $1$ ; $1 \div 5 = 0$ R $1$ . Read bottom-up: $110$ .

Learning route:

The question asks for a cross-base conversion. The golden rule for arbitrary bases is to always route through Base 10.

Step 1: Evaluate $(132)_{4}$ in Base 10 using positional weights. The weights are $4^{2} = 16$ , $4^{1} = 4$ , $4^{0} = 1$ .

$1 \times 16 + 3 \times 4 + 2 \times 1 = 16 + 12 + 2 = 3 0_{10}$ .

Step 2: Convert $3 0_{10}$ to Base 5 using repeated division.

Divide 30 by 5: quotient 6, remainder 0.

Divide 6 by 5: quotient 1, remainder 1.

Divide 1 by 5: quotient 0, remainder 1.

Reading the remainders from bottom to top gives $(110)_{5}$ .

Verification: $(110)_{5} = 1 (25) + 1 (5) + 0 (1) = 3 0_{10}$ . Matches.

Question 27 · Digital Logic · 2023 MCQ

Consider a sequential digital circuit consisting of T flip-flops and D flip-flops as shown in the figure. CLKIN is the clock input to the circuit. At the beginning, Q1, Q2 and Q3 have values 0, 1 and 1, respectively.

Which one of the given values of (Q1, Q2, Q3) can NEVER be obtained with this digital circuit?

A.
(0, 0, 1)
B.
(1, 0, 0)
C.
(1, 0, 1)
D.
(1, 1, 1)

Correct Answer:

Step-by-Step Solution

Insight: This is a sequential circuit analysis problem requiring us to derive next-state equations for mixed flip-flop types and trace the state transition graph to find unreachable states.

Exam route: From the diagram, $T_{1} = \overline{Q_{3}}$ , $D_{2} = Q_{1}$ , $T_{3} = Q_{2}$ . Using $Q^{+} = T \oplus Q$ for T-FF and $Q^{+} = D$ for D-FF, we get $Q_{1}^{+} = \overline{Q_{3}} \oplus Q_{1}$ , $Q_{2}^{+} = Q_{1}$ , $Q_{3}^{+} = Q_{2} \oplus Q_{3}$ . Starting from $011$ , the sequence is $011 \to 000 \to 100 \to 010 \to 101 \to 111 \to 110 \to 011$ . The state $(0, 0, 1)$ is never visited.

Learning route:

Step 1: Identify the flip-flop types and their characteristic equations.

$Q_{1}$ is a T-FF: $Q_{1}^{+} = T_{1} \oplus Q_{1}$
$Q_{2}$ is a D-FF: $Q_{2}^{+} = D_{2}$
$Q_{3}$ is a T-FF: $Q_{3}^{+} = T_{3} \oplus Q_{3}$

Step 2: Extract excitation equations from the circuit diagram.

$T_{1} = \overline{Q_{3}}$
$D_{2} = Q_{1}$
$T_{3} = Q_{2}$

Step 3: Formulate the next-state equations.

$Q_{1}^{+} = \overline{Q_{3}} \oplus Q_{1}$
$Q_{2}^{+} = Q_{1}$
$Q_{3}^{+} = Q_{2} \oplus Q_{3}$

Step 4: Trace the state sequence starting from the initial state $Q_{1} Q_{2} Q_{3} = 011$ .

Current: $011$ . $Q_{1}^{+} = \overline{1} \oplus 0 = 0$ , $Q_{2}^{+} = 0$ , $Q_{3}^{+} = 1 \oplus 1 = 0$ . Next: $000$ .
Current: $000$ . $Q_{1}^{+} = \overline{0} \oplus 0 = 1$ , $Q_{2}^{+} = 0$ , $Q_{3}^{+} = 0 \oplus 0 = 0$ . Next: $100$ .
Current: $100$ . $Q_{1}^{+} = \overline{0} \oplus 1 = 0$ , $Q_{2}^{+} = 1$ , $Q_{3}^{+} = 0 \oplus 0 = 0$ . Next: $010$ .
Current: $010$ . $Q_{1}^{+} = \overline{0} \oplus 0 = 1$ , $Q_{2}^{+} = 0$ , $Q_{3}^{+} = 1 \oplus 0 = 1$ . Next: $101$ .
Current: $101$ . $Q_{1}^{+} = \overline{1} \oplus 1 = 1$ , $Q_{2}^{+} = 1$ , $Q_{3}^{+} = 0 \oplus 1 = 1$ . Next: $111$ .
Current: $111$ . $Q_{1}^{+} = \overline{1} \oplus 1 = 1$ , $Q_{2}^{+} = 1$ , $Q_{3}^{+} = 1 \oplus 1 = 0$ . Next: $110$ .
Current: $110$ . $Q_{1}^{+} = \overline{0} \oplus 1 = 0$ , $Q_{2}^{+} = 1$ , $Q_{3}^{+} = 1 \oplus 0 = 1$ . Next: $011$ (Initial state reached).

Step 5: List all visited states: $011, 000, 100, 010, 101, 111, 110$ .

Step 6: Compare with the options. The state $(0, 0, 1)$ is not in the list, meaning it can never be obtained.

Verification: The cycle length is 7, and it perfectly loops back to $011$ . State $001$ is outside this cycle.

Question 28 · Verbal Aptitude · 2023 MCQ

We reached the station late, and _______ missed the train.

A.
near
B.
nearly
C.
utterly
D.
mostly

Correct Answer:

Step-by-Step Solution

Insight: Adverbs of degree like 'nearly' modify verbs to show that an action was very close to occurring but ultimately did not.

Exam route: The sentence describes a close call with missing a train. 'Nearly' is the correct adverb of degree meaning 'almost'. 'Near' is a preposition/adjective, 'utterly' means completely (which contradicts the binary nature of missing a train), and 'mostly' means for the most part.

Learning route:

Step 1: Analyze the context. "Reached late" implies a rush, and the consequence is related to "missed the train". The missing word must indicate the degree or proximity of the action.

Step 2: Evaluate the options.

'near' is typically a preposition (near the station) or adjective (the near future), not an adverb modifying 'missed'.
'nearly' is an adverb meaning 'almost' or 'very nearly'. "Nearly missed" is a standard collocation.
'utterly' means completely or absolutely (e.g., utterly destroyed). You cannot "completely miss" a train in this context; you either miss it or you don't.
'mostly' means mainly or usually, which doesn't fit a single specific past event.

Step 3: Select 'nearly' as the only grammatically and semantically correct adverb.

Common trap: Confusing the adjective/preposition 'near' with the adverb 'nearly', or choosing 'utterly' because it sounds emphatic.

Verification: "We reached the station late, and nearly missed the train." This perfectly conveys the intended meaning of a close call.

Question 29 · Verbal Aptitude · 2023 MCQ

Kind : _______ : : Often : Frequently

(By word meaning)

A.
Mean
B.
Type
C.
Cruel
D.
Kindly

Correct Answer:

Step-by-Step Solution

Key idea: This is a synonym analogy, recognizable because the second pair (Often : Frequently) consists of two words that mean the exact same thing and share the same part of speech.

Step 1: Analyze the known pair. "Often" and "Frequently" are exact synonyms, both acting as adverbs indicating high regularity.

Step 2: Apply the relationship to the first pair. We need a synonym for "Kind" that matches its part of speech and positive tone.

Step 3: Evaluate the options. "Mean" and "Cruel" are antonyms of "Kind". "Type" is a noun and represents a different definition (polysemy) of the word "kind", not a synonym.

Step 4: "Kindly" can function as an adjective meaning kind, gentle, or sympathetic (e.g., a kindly person). It is the only true synonym among the choices.

Answer: D

Question 30 · Verbal Aptitude · 2023 MCQ

Which one of the following sentence sequences creates a coherent narrative?

(i) Once on the terrace, on her way to her small room in the corner, she notices the man right away.
(ii) She begins to pant by the time she has climbed all the stairs.
(iii) Mina has bought vegetables and rice at the market, so her bags are heavy.
(iv) He was leaning against the parapet, watching the traffic below.

A.
(i), (ii), (iv), (iii)
B.
(ii), (iii), (i), (iv)
C.
(iv), (ii), (i), (iii)
D.
(iii), (ii), (i), (iv)

Correct Answer:

Step-by-Step Solution

Insight: The opening sentence must introduce the main subject without dependent pronouns, and subsequent sentences must follow a strict chronological and pronoun-antecedent chain.

Exam route: Eliminate (i), (ii), and (iv) as openers because they start with dependent pronouns ("she", "He"). Only (iii) introduces "Mina" independently. This leaves only the sequence starting with (iii). Verify the chain: Mina (iii) → She (ii) → terrace/man (i) → He (iv).

Learning route:

Step 1: Identify the opening sentence. Sentence (iii) introduces "Mina" and her heavy bags. Sentences (i), (ii), and (iv) start with pronouns ("she", "He") that lack a prior antecedent, making them invalid openers.

Step 2: Build mandatory pairs. Sentence (ii) mentions "She begins to pant... climbed all the stairs", which logically follows carrying heavy bags in (iii).

Step 3: Establish chronology. Sentence (i) states "Once on the terrace...", which naturally follows climbing the stairs in (ii).

Step 4: Resolve remaining references. Sentence (i) introduces "the man", which is the antecedent for "He" in sentence (iv).

Thus, the sequence (iii) → (ii) → (i) → (iv) is the only logically coherent narrative.

Question 31 · Quantitative Aptitude · 2023 MCQ

A series of natural numbers

F_{1}, F_{2}, F_{3}, F_{4}, F_{5}, F_{6}, F_{7}, \dots

obeys

F_{n + 1} = F_{n} + F_{n - 1}

for all integers

n \geq 2

.

If

F_{6} = 37

, and

F_{7} = 60

, then what is

F_{1}

A.
4
B.
5
C.
8
D.
9

Correct Answer:

Step-by-Step Solution

Insight: To find earlier terms in a recursive sequence when later terms are known, rearrange the recurrence relation to step backwards one index at a time.

Exam route: The rule is $F_{n + 1} = F_{n} + F_{n - 1}$ , which rearranges to $F_{n - 1} = F_{n + 1} - F_{n}$ . Given $F_{7} = 60$ and $F_{6} = 37$ : $F_{5} = 60 - 37 = 23$ . $F_{4} = 37 - 23 = 14$ . $F_{3} = 23 - 14 = 9$ . $F_{2} = 14 - 9 = 5$ . $F_{1} = 9 - 5 = 4$ .

Learning route:

Step 1: Identify the forward recurrence relation: $F_{n + 1} = F_{n} + F_{n - 1}$ .

Step 2: Rearrange the formula to solve for the oldest term: $F_{n - 1} = F_{n + 1} - F_{n}$ .

Step 3: Use the given values $F_{7} = 60$ and $F_{6} = 37$ to find $F_{5}$ . Set $n = 6$ : $F_{5} = F_{7} - F_{6} = 60 - 37 = 23$ .

Step 4: Find $F_{4}$ using $F_{6}$ and $F_{5}$ . Set $n = 5$ : $F_{4} = F_{6} - F_{5} = 37 - 23 = 14$ .

Step 5: Find $F_{3}$ using $F_{5}$ and $F_{4}$ . Set $n = 4$ : $F_{3} = F_{5} - F_{4} = 23 - 14 = 9$ .

Step 6: Find $F_{2}$ using $F_{4}$ and $F_{3}$ . Set $n = 3$ : $F_{2} = F_{4} - F_{3} = 14 - 9 = 5$ .

Step 7: Find $F_{1}$ using $F_{3}$ and $F_{2}$ . Set $n = 2$ : $F_{1} = F_{3} - F_{2} = 9 - 5 = 4$ .

Question 32 · Quantitative Aptitude · 2023 MCQ

Consider two functions of time

(t)

f (t) = 0.01 t^{2}

g (t) = 4 t

where

0&lt;t&lt;\infty

.

Now consider the following two statements:

(i) For some

t&gt;0

g(t)&gt;f(t)

.
(ii) There exists a

T

, such that

f(t)&gt;g(t)

for all

t&gt;T

.

Which one of the following options is TRUE?

A.
only (i) is correct
B.
only (ii) is correct
C.
both (i) and (ii) are correct
D.
neither (i) nor (ii) is correct

Correct Answer:

Step-by-Step Solution

Insight: Compare the growth rates of a quadratic and a linear function; the linear function wins initially, but the quadratic eventually dominates.

Exam route: Set $f (t) = g (t)$ to find the crossover point $t = 400$ . For $0 < t < 400$ , $g (t) > f (t)$ , proving (i). For $t > 400$ , $f (t) > g (t)$ , proving (ii) with $T = 400$ .

Learning route:

Analyze the inequality for statement (i): $g (t) > f (t) ⟹ 4 t > 0.01 t^{2} ⟹ t (400 - t) > 0$ . Since $t > 0$ , this holds for $0 < t < 400$ . Thus, statement (i) is true.

Next, analyze the inequality for statement (ii): $f (t) > g (t) ⟹ 0.01 t^{2} > 4 t ⟹ t (t - 400) > 0$ . For $t > 400$ , this holds. Thus, choosing $T = 400$ satisfies statement (ii).

Both statements are correct.

Question 33 · Quantitative Aptitude · 2023 MCQ

$f (x)$ and $g (y)$ are functions of $x$ and $y$ , respectively, and $f (x) = g (y)$ for all real values of $x$ and $y$ . Which one of the following options is necessarily TRUE for all $x$ and $y$ ?

A.
$f (x) = 0$ and $g (y) = 0$
B.
$f (x) = g (y) = constant$
C.
$f (x) \neq = constant$ and $g (y) \neq = constant$
D.
$f (x) + g (y) = f (x) - g (y)$

Correct Answer:

Step-by-Step Solution

Insight: If a function of $x$ equals a function of $y$ for all independent real values of $x$ and $y$ , both functions must be equal to the same constant.

Exam route: Fix $y = y_{0}$ . Then $f (x) = g (y_{0})$ for all $x$ , meaning $f (x)$ is constant. Similarly, fix $x = x_{0}$ to show $g (y)$ is constant. Thus, $f (x) = g (y) = constant$ .

Learning route:

Step 1: We are given $f (x) = g (y)$ for all real $x$ and $y$ .

Step 2: Choose an arbitrary but fixed value for $y$ , say $y = c$ .

Step 3: The equation becomes $f (x) = g (c)$ for all $x$ . Since $g (c)$ is just a number, $f (x)$ must be a constant function.

Step 4: Similarly, choose a fixed value for $x$ , say $x = d$ . The equation becomes $g (y) = f (d)$ for all $y$ , meaning $g (y)$ is also a constant function.

Step 5: Since they are equal to each other, they must be the same constant. Therefore, $f (x) = g (y) = constant$ .

Question 34 · Databases · 2023 MCQ

Which one of the options given below refers to the degree (or arity) of a relation in relational database systems?

A.
Number of attributes of its relation schema.
B.
Number of tuples stored in the relation.
C.
Number of entries in the relation.
D.
Number of distinct domains of its relation schema.

Question 35 · Databases · 2023 NAT

Consider the following table named Student in a relational database. The primary key of this table is rollNum.

Student

The SQL query below is executed on this database.

SELECT *
FROM Student
WHERE gender = ‘F’ AND
marks > 65;

The number of rows returned by the query is __________.

Question 36 · Databases · 2023 NAT

Consider a database of fixed-length records, stored as an ordered file. The database has 25,000 records, with each record being 100 bytes, of which the primary key occupies 15 bytes. The data file is block-aligned in that each data record is fully contained within a block. The database is indexed by a primary index file, which is also stored as a block-aligned ordered file. The figure below depicts this indexing scheme.

Suppose the block size of the file system is 1024 bytes, and a pointer to a block occupies 5 bytes. The system uses binary search on the index file to search for a record with a given key. You may assume that a binary search on an index file of

b

blocks takes

⌈ lo g_{2} b ⌉

block accesses in the worst case.
Given a key, the number of block accesses required to identify the block in the data file that may contain a record with the key, in the worst case, is __________.

Question 37 · Spatial Aptitude · 2023 MCQ

Looking at the surface of a smooth 3-dimensional object from the outside, which one of the following options is TRUE?

A.
The surface of the object must be concave everywhere.
B.
The surface of the object must be convex everywhere.
C.
The surface of the object may be concave in some places and convex in other places.
D.
The object can have edges, but no corners.

Correct Answer:

Step-by-Step Solution

Key idea: This is a <conceptual> question testing understanding of surface curvature and the mathematical definition of smooth surfaces in 3D geometry.

Step 1: Understand what "smooth" means mathematically.

A smooth 3D surface has:

A unique tangent plane at every point
No sharp edges or corners
Continuous curvature (differentiable everywhere)

Step 2: Analyze each option.

Option A: "Must be concave everywhere"

FALSE: A sphere is smooth and convex everywhere
A smooth surface can be convex, concave, or mixed

Option B: "Must be convex everywhere"

FALSE: A smooth torus (donut shape) has both concave and convex regions
The inner part is concave, outer part is convex

Option C: "May be concave in some places and convex in other places"

TRUE: This is correct
Example: A torus, or a wavy surface, or an ellipsoid with varying curvature
Smoothness only requires continuous differentiability, not uniform curvature type

Option D: "Can have edges, but no corners"

FALSE: A smooth surface cannot have edges
Edges represent discontinuities in the tangent plane
By definition, smooth surfaces have no edges or corners

Step 3: Conclusion.

A smooth 3D object can have varying curvature - concave in some regions, convex in others - as long as the surface remains differentiable everywhere.

Answer: C

Question 38 · Spatial Aptitude · 2023 MCQ

Which one of the options best describes the transformation of the 2-dimensional figure P to Q, and then to R, as shown?

A. Operation 1: A clockwise rotation by $9 0^{\circ}$ about an axis perpendicular to the plane of the figure

Operation 2: A reflection along a horizontal line
B. Operation 1: A counter clockwise rotation by $9 0^{\circ}$ about an axis perpendicular to the plane of the figure

Operation 2: A reflection along a horizontal line
C. Operation 1: A clockwise rotation by $9 0^{\circ}$ about an axis perpendicular to the plane of the figure

Operation 2: A reflection along a vertical line
D. Operation 1: A counter clockwise rotation by $18 0^{\circ}$ about an axis perpendicular to the plane of the figure

Operation 2: A reflection along a vertical line

Correct Answer:

Step-by-Step Solution

Key idea: This is a sequential transformation identification problem. We need to determine the geometric operation that transforms P to Q, and then Q to R.

Step 1: Analyze Transformation P to Q.

Compare figure P and figure Q.

Figure P is an irregular polygon.
Figure Q appears to be rotated relative to P.
Let's track a specific vertex. The top-most vertex of P moves to the right-most position in Q?
Visually, P looks like it has been rotated 90 degrees Clockwise.
Check orientation: The sequence of vertices is preserved (no reflection).
Conclusion: Operation 1 is a 90-degree Clockwise Rotation.

Step 2: Analyze Transformation Q to R.

Compare figure Q and figure R.

Figure Q is the rotated P.
Figure R is a mirror image of Q?
Let's check for reflection.
If we reflect Q across a horizontal line, does it match R?
Top of Q becomes Bottom of R. Left of Q becomes Left of R?
Let's look at the options.
Option A says: Op 2 is Reflection along a horizontal line.
Option B says: Op 2 is Reflection along a horizontal line.
Option C says: Op 2 is Reflection along a vertical line.
Option D says: Op 2 is Reflection along a vertical line.

Let's verify the axis.

In Q, the "pointy" part is to the right. In R, the "pointy" part is to the right? No, R looks like Q flipped upside down.

If Q is flipped upside down (Horizontal Axis Reflection), the top becomes bottom.

Does R look like Q upside down? Yes.

Therefore:

Operation 1: 90-degree Clockwise Rotation.

Operation 2: Reflection along a horizontal line.

This matches Option A.

Answer: A

Question 39 · Analytical Aptitude · 2023 MCQ

A survey for a certain year found that 90% of pregnant women received medical care at least once before giving birth. Of these women, 60% received medical care from doctors, while 40% received medical care from other healthcare providers.

Given this information, which one of the following statements can be inferred with certainty?

A.
More than half of the pregnant women received medical care at least once from a doctor.
B.
Less than half of the pregnant women received medical care at least once from a doctor.
C.
More than half of the pregnant women received medical care at most once from a doctor.
D.
Less than half of the pregnant women received medical care at most once from a doctor.

Correct Answer:

Step-by-Step Solution

Insight: 60% of the 90% who received care is 54% of the total, which is strictly more than half.

Exam route: Calculate $0.60 \times 0.90 = 0.54$ . Since $54% > 50%$ , Option A is directly verified without needing to assume anything about overlap.

Learning route: Let the total number of pregnant women be 100. The passage states 90 received care. Of these 90, 60% received care from doctors. 60% of 90 is 54. Thus, 54 out of 100 women (54%) received care from a doctor. Since 54% is strictly greater than 50%, it is certain that more than half received care from a doctor. The trap is to assume the 60% and 40% must overlap or be disjoint in a way that changes the total, but the question only asks about the doctor subset, which is firmly 54%.

Wrong path: A student might add 60% and 40% to get 100% and assume they are disjoint, or try to find the overlap. This leads to confusion about the "at most once" options (C and D), which introduce frequency data not present in the passage. The exact line where it breaks is assuming the passage provides data on visit frequency. Generalization: Always calculate the true base for nested percentages and ignore unstated variables. Verification: 54% of total is indeed more than half, matching Option A.

Question 40 · Analytical Aptitude · 2023 MCQ

The country of Zombieland is in distress since more than 75% of its working population is suffering from serious health issues. Studies conducted by competent health experts concluded that a complete lack of physical exercise among its working population was one of the leading causes of their health issues. As one of the measures to address the problem, the Government of Zombieland has decided to provide monetary incentives to those who ride bicycles to work.

Based only on the information provided above, which one of the following statements can be logically inferred with certainty?

A.
All the working population of Zombieland will henceforth ride bicycles to work.
B.
Riding bicycles will ensure that all of the working population of Zombieland is free of health issues.
C.
The health experts suggested to the Government of Zombieland to declare riding bicycles as mandatory.
D.
The Government of Zombieland believes that riding bicycles is a form of physical exercise.

Correct Answer:

Step-by-Step Solution

Insight: The government's action (incentivizing cycling) to solve a specific problem (lack of exercise) reveals their underlying belief (cycling is exercise).

Exam route: Match the problem (lack of exercise) with the solution (incentivize cycling). The logical bridge is that the government believes cycling addresses the lack of exercise. Option D states exactly this.

Learning route: The passage establishes that lack of physical exercise is a leading cause of health issues. The government responds by providing monetary incentives for riding bicycles to work. For this action to make logical sense as a remedy for the stated problem, the government must believe that riding bicycles constitutes physical exercise. We cannot infer that everyone will ride bicycles (Option A), that it will cure all issues (Option B), or that experts suggested making it mandatory (Option C), as these introduce extreme claims or unstated information.

Wrong path: A student might see the government taking action and assume it will definitely solve the problem, leading to Option B. This breaks because the passage states lack of exercise is only "one of the leading causes", so cycling cannot guarantee a complete cure. Another wrong path is assuming experts suggested the specific policy (Option C), which is outside information. Generalization: An action taken to solve a problem implies a belief in the solution's efficacy, but does not guarantee the outcome or imply unstated suggestions. Verification: Option D perfectly bridges the problem and the action without overreaching.

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

Paper breakdown

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

Step-by-Step Solution

Step-by-Step Solution

Other GATE CS papers