GATE CSE 2025 Set 2 | GATE CSE Year Wise Previous Years Questions

GATE CSE 2025 Set 2

MCQ (Single Correct Answer)

-0.67

Let $G$ be an edge-weighted undirected graph with positive edge weights. Suppose a positive constant $\alpha$ is added to the weight of every edge. Which ONE of the following statements is TRUE about the minimum spanning trees (MSTs) and shortest paths (SPs) in G before and after the edge weight update?

Every MST remains an MST, and every SP remains an SP.

MSTs need not remain MSTs, and every SP remains an SP.

Every MST remains an MST, and SPs need not remain SPs.

MSTs need not remain MSTs, and SPs need not remain SPs.

GATE CSE 2025 Set 2

MCQ (Single Correct Answer)

-0.67

An array $A$ of length $n$ with distinct elements is said to be bitonic if there is an index $1=i=n$ such that $A[1 . . i]$ is sorted in the non-decreasing order and $A[i+1 . . n]$ is sorted in the non-increasing order.

Which ONE of the following represents the best possible asymptotic bound for the worstcase number of comparisons by an algorithm that searches for an element in a bitonic array $A$?

$\Theta(n)$

$\Theta(1)$

$\Theta\left(\log ^2 n\right)$

$\Theta(\log n)$

GATE CSE 2025 Set 2

MCQ (Single Correct Answer)

-0.33

Consider the following statements about the use of backpatching in a compiler for

(I) Backpatching can be used to generate code for Boolean expression in one pass.

(II) Backpatching can be used to generate code for flow-of-control statements in one pass.

Which ONE of the following options is CORRECT?

Only (I) is correct.

Only (II) is correct.

Both (I) and (II) are correct.

Neither (I) nor (II) is correct.

GATE CSE 2025 Set 2

MCQ (Single Correct Answer)

-0.33

Given the following syntax directed translation rules :

Rule 1 : $R \rightarrow A B\{B . i=R . i-1 ; A . i=B . i R . i=A . i+1 ;\}$

Rule 2 : $P \rightarrow C D\{P . i=C . i+D . i ; D . i=C . i+2\}$

Rule 3 : $Q \rightarrow E F\{Q . i=E . i+F . i ;\}$

Which ONE is the CORRECT option among the following?

Rule 1 is S -attributed and L-attributed; Rule 2 is S -attributed and not L-attributed; Rule 3 is neither S -attributed nor L-attributed

Rule 1 is neither S-attributed nor L-attributed: Rule 2 is S-attributed and L-attributed: Rule 3 is S-attributed and L-attributed

Rule 1 is neither S-attributed nor L-attributed; Rule 2 is not S -attributed and is Lattributed; Rule 3 is S -attributed and L-attributed

Rule 1 is S-attributed and not L-attributed; Rule 2 is not S-attributed and is Lattributed: Rule 3 is S -attributed and L-attributed

PREVIOUS NEXT

GATE CSE Papers

2025