CS and IT GATE 2025 SET-2 Questions with Answer

Ques 1 Algorithms

Consider an unordered list of N distinct integers.
What is the minimum number of element comparisons required to find an integer in the list that is NOT the largest in the list?

N-1

2N-1

Ques 2 Algorithms

Which of the following statements regarding Breadth First Search (BFS) and Depth First Search (DFS) on an undirected simple graph G is/are TRUE?

A DFS tree of G is a Shortest Path tree of G.

Every non-tree edge of G with respect to a DFS tree is a forward/back edge.

If (u,v) is a non-tree edge of G with respect to a BFS tree, then the distances from the source vertex s to u and v in the BFS tree are within ±1 of each other.

Both BFS and DFS can be used to find the connected components of G.

Ques 3 Algorithms

Let G be an edge-weighted undirected graph with positive edge weights. Suppose a positive constant a 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.

Ques 4 Algorithms

A meld operation on two instances of a data structure combines them into one single instance of the same data structure. Consider the following data structures:
P: Unsorted doubly linked list with pointers to the head node and tail node of the list.
Q: Min-heap implemented using an array.
R: Binary Search Tree.
Which ONE of the following options gives the worst-case time complexities for meld operation on instances of size n of these data structures?

P: Θ(1), Q: Θ(n), R: Θ(n)

P:Θ(1), Q: Θ(n log n) R: Θ(n)

P: Θ(n), Q: Θ(n log n), R: Θ(n²)

P: Θ(1), Q: Θ(n), R: Θ(n log n)

Ques 5 Algorithms

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 worst-case number of comparisons by an algorithm that searches for an element in a bitonic array A?

Θ(n)

Θ(1)

Θ(log²n)

Θ(log n)

Ques 6 Algorithms

Consider the following algorithm someAlgo that takes an undirected graph G as input.

The output of someAlgo (T) for the tree shown in the given figure is ______ (Answer in integer)

Ques 7 Compilers

Consider the following statements about the use of backpatching in a compiler for intermediate code generation:
(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.

Ques 8 Compilers

Given the following syntax directed translation rules:
Rule 1: R→AB {B.i = R.i1; A.i=B.i; R.i=A.i+1;}
Rule 2: P→CD {P.i = C.i+D.i; D.i=C.i+2;}
Rule 3: Q→EF {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 L-attributed; 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 L-attributed; Rule 3 is S-attributed and L-attributed

Ques 9 Compilers

Given a Context-Free Grammar G as follows:
S→Aa|bAc|dc|bda
A→d
Which ONE of the following statements

G is neither LALR(1) nor SLR(1)

G is CLR(1), not LALR(1)

G is LALR(1), not SLR(1)

G is LALR(1), also SLR(1)

Ques 10 Compilers

Consider two grammars G₁ and G₂ with the production rules given below:
G₁: S→if E then S|if E then S else S | a
E→b
G₂: S→if E then S|M
M→if E then M else S | c
E→b
where if, then, else, a, b, c are the terminals.
Which of the following option(s) is/are CORRECT?

G₁ is not LL(1) and G₂ is LL(1)

G₁ is LL(1) and G₂ is not LL(1).

G₁ and G₂ are not LL(1).

G₁ and G₂ are ambiguous.

Ques 11 Computer Networks

Consider the following statements:
(i) Address Resolution Protocol (ARP) provides a mapping from an IP address to the corresponding hardware (link-layer) address.
(ii) A single TCP segment from a sender S to a receiver R cannot carry both data from S to R and acknowledgement for a segment from R to S.
Which ONE of the following is CORRECT?

Both (i) and (ii) are TRUE

(i) is TRUE and (ii) is FALSE

(i) is FALSE and (ii) is TRUE

Both (i) and (ii) are FALSE

Ques 12 Computer Networks

Consider the routing protocols given in List I and the names given in List II:
List I
(i) Distance vector routing
(ii) Link state routing
List II
(a) Bellman-Ford
(b) Dijkstra
For matching of items in List I with those in List II, which ONE of the following options is CORRECT?

(i)-(a) and (ii)-(b)

(i)-(a) and (ii)-(a)

(i)-(b) and (ii)-(a)

(i)-(b) and (ii)-(b)

Ques 13 Computer Networks

A machine receives an IPv4 datagram. The protocol field of the IPv4 header has the protocol number of a protocol X.
Which ONE of the following is NOT a possible candidate for X?

Internet Control Message Protocol (ICMP)

Internet Group Management Protocol (IGMP)

Open Shortest Path First (OSPF)

Routing Information Protocol (RIP)

1 2 3 4 5

Total Unique Visitors

Loading......

CS/IT Gate Yearwise

CS and IT GATE 2025 SET-2 Questions with Answer