CS and IT Gate 2025 Set-1 Questions with Answer

Answer: B — d₁(u,v) ≤ d₂(u,v)

Explanation:
The tree T is a subgraph of G. Any path that exists in T also exists in G. Let P be the shortest path between u and v inside T; its length is d₂(u,v).
Since P is also a valid path in G, the shortest distance in G cannot be longer than this path. Therefore:
d₁(u,v) ≤ d₂(u,v)

Example:
Graph G is a triangle with vertices A, B, C and edge weights:
AB = 1, BC = 1, AC = 3.
A minimum spanning tree T includes edges AB and BC.
In G: shortest A–C path = A–B–C = 1 + 1 = 2 → d₁(A,C) = 2
In T: only path A–B–C = 2 → d₂(A,C) = 2
Hence, d₁ = d₂.

Example
Graph G is a triangle with all edges weight 1: AB = BC = AC = 1.
A minimum spanning tree T includes edges AB and BC.
In G: shortest A–C path = AC = 1 → d₁(A,C) = 1
In T: only path A–B–C = 1 + 1 = 2 → d₂(A,C) = 2
So d₁ < d₂.

Conclusion:
Removing edges (as when taking a Minimum Spanning Tree) can never make the distance shorter.
Therefore, the correct option is: B — d₁(u,v) ≤ d₂(u,v).

Given: T(n) = 2T(n − 1) + n2ⁿ,   T(0) = 1

We need to find the asymptotic bound Θ.

Expand the recurrence
T(n) = 2T(n−1) + n2ⁿ
= 2(2T(n−2) + (n−1)2ⁿ⁻¹) + n2ⁿ
= 4T(n−2) + 2(n−1)2ⁿ⁻¹ + n2ⁿ
= 4T(n−2) + (n−1)2ⁿ + n2ⁿ
= 4T(n−2) + (2n − 1)2ⁿ

T(n) = 2^kT(n−k) + Σ_i=0^k−1 2ⁱ(n−i)2ⁿ⁻ⁱ

When k = n:
T(n) = 2ⁿT(0) + Σ_i=0ⁿ⁻¹ 2ⁱ(n−i)2ⁿ⁻ⁱ

Simplify the terms
Since 2ⁱ × 2ⁿ⁻ⁱ = 2ⁿ,
T(n) = 2ⁿ + 2ⁿ Σ_i=0ⁿ⁻¹ (n−i)

Σ_i=0ⁿ⁻¹ (n−i) = n + (n−1) + (n−2) + … + 1 = n(n + 1)/2
T(n) = 2ⁿ + 2ⁿ × (n(n + 1)/2)

T(n) = 2ⁿ (1 + n(n + 1)/2)

As n grows large, dominant term ≈ (n² × 2ⁿ).

Therefore: T(n) = Θ(n² × 2ⁿ)

Final Answer:
Option A: T(n) = Θ(n² × 2ⁿ)

Explanation:
The code is bubble sort using adjacent swaps whenever A[j] > A[j+1]. For an array of length n = 30 in strict descending order every pair (i,j) with i < j is an inversion. The number of inversions is n(n−1)/2, so total swaps = 30×29/2 = 435.

Explaination:

• Diameter of G = max_{u,v} d(u,v) = 30.
• Define the radius of G as rad(G) = min_{x} max_{y} d(x,y). It is always true that rad(G) ≤ diam(G) ≤ 2 · rad(G).
• From diam(G) = 30 we get rad(G) ≥ ⌈30/2⌉ = 15.
• For any root r, a BFS tree T rooted at r has height equal to the eccentricity of r, i.e. height(T) = max_{v} d(r,v) which is ≥ rad(G).
• Therefore for every BFS tree T we have height(T) ≥ rad(G) ≥ 15. Hence the height is at least 15.

Why other options are wrong (quick examples):

• A (exactly 15): Not guaranteed — if you root at an endpoint of a diameter pair, the BFS tree height can be 30.
• B (exactly 30): Not guaranteed — if you pick a center vertex (when rad(G)=15), a BFS tree can have height 15.
• D (at least 30): False — some BFS trees can have height 15, so "at least 30" is not true for every BFS tree.

Concrete illustrations:

• Take a simple path of 31 vertices (a path graph of length 30). Its diameter is 30. A BFS tree rooted at an endpoint has height 30; a BFS tree rooted at the middle vertex has height 15.

Explanation:
To force the edge BC to appear in every minimum spanning tree (MST), there must be no alternative path from B to C whose largest edge weight is <= x.
If such a path exists, Kruskal's algorithm could connect B and C using that path's edges and skip the direct edge BC.
Examine all simple B–C paths and record the largest edge weight on each path:

• Path B – A – C: edge weights 7 and 1 → largest = 7
• Path B – D – C: edge weights 3 and 8 → largest = 8
• Path B – D – A – C: edge weights 3, 6, 1 → largest = 6

The minimum, over these paths, of the largest-edge value is 6. That means there exists a B–C path whose maximum edge is 6. For BC to be in every MST we need x < 6 (strictly less than 6), otherwise that path could be used instead of BC.
Since the answer asks for an integer value, the largest integer x satisfying x < 6 is: 5

Statement A: Symbol table is responsible for keeping track of the scope of variables — This is TRUE. The symbol table manages scope information to determine where variables can be accessed.

Statement B: Symbol table can be implemented using a binary search tree — This is TRUE. Symbol tables can be implemented using various data structures including binary search trees, hash tables, arrays, or linked lists.

Statement C: Symbol table is not required after the parsing phase — This is FALSE. The symbol table is used throughout multiple phases including semantic analysis, intermediate code generation, code optimization, and target code generation, not just during parsing.

Statement D: Symbol table is created during the lexical analysis phase — This is TRUE. The lexical analyzer creates entries for tokens and identifiers when it encounters them during scanning.

✅ Final Answer: Option (C) — Symbol table is not required after the parsing phase.

Reason: The symbol table is used by multiple compilation phases beyond parsing, including semantic analysis, code generation, and optimization phases.

A) Run-time function call management — This involves managing function calls at runtime and does not use live variable analysis.

B) Register assignment to variables — This uses live variable analysis to determine which variables are live at different program points, helping the compiler decide which variables should be allocated to registers and for how long. This is the primary application of live variable analysis.

C) Strength reduction — This optimization replaces expensive operations with cheaper ones (like replacing multiplication by 2 with left shift) and does not require live variable analysis.

D) Constant folding — This optimization evaluates constant expressions at compile time and does not use live variable analysis.

✅ Final Answer: Option (B) — Register assignment to variables.

Reason: Live variable analysis determines which variables are "live" at each program point, which is essential for efficient register allocation and assignment to minimize memory access and optimize performance.

Statement A: For a production A→ε, ε will be added to First(A) — This is TRUE. The First set of a non-terminal A includes ε if A can derive the empty string directly.

Statement B: If there is any input right end marker, it will be added to First(S), where S is the start symbol — This is FALSE. The end marker ($) is never added to the First set of any symbol. First sets contain only terminals that can begin strings derived from that symbol.

Statement C: For a production A→ε, ε will be added to Follow(A) — This is FALSE. The fact that A can produce ε does not mean ε is added to Follow(A). Follow sets contain terminals that can appear immediately after a non-terminal, not ε itself.

Statement D: If there is any input right end marker, it will be added to Follow(S), where S is the start symbol — This is TRUE. The end marker ($) is always added to Follow(S) for the start symbol S, indicating the end of input.

✅ Final Answer: Statements A and D are TRUE.

Reason: First sets include ε for productions that derive empty strings, and Follow sets for the start symbol always include the end marker ($). However, end markers are never in First sets, and ε is never in Follow sets.

To identify basic blocks, we find leaders (starting points) and group consecutive statements until a jump or branch. Leaders include the first statement, targets of jumps, and statements immediately following conditional jumps.

The leaders in this code are at lines 1001, 1002, 1003, 1010, 1012, and 1013. This creates six basic blocks: Block 1 (line 1001), Block 2 (line 1002), Block 3 (lines 1003-1009), Block 4 (lines 1010-1011), Block 5 (line 1012), and Block 6 (lines 1013-1017).

✅ Final Answer: 6

Reason: Each leader starts a new basic block, and consecutive statements without control flow changes belong to the same block.

Network layer (a): Responsible for packet routing between networks, determining the best path for data transmission from source to destination. This matches functionality (I) - Packet routing.

Transport layer (b): Provides host-to-host communication, ensuring end-to-end delivery of data between processes on different hosts. This matches functionality (III) - Host to host communication.

Data link layer (c): Handles framing of data into frames and provides error detection and correction mechanisms for reliable transmission over the physical medium. This matches functionality (II) - Framing and error handling.

Therefore, the correct matching is: Network layer with Packet routing, Transport layer with Host to host communication, and Data link layer with Framing and error handling.

✅ Final Answer: Option (B) — (a)-(I), (b)-(III), (c)-(II).

Reason: Each OSI layer has specific functions: Network layer routes packets, Transport layer provides host-to-host communication, and Data link layer handles framing and error control.

For a message to be delivered error-free, all bits must be transmitted correctly. Since each bit has a probability of 0.99 of being transmitted correctly and bit transmissions are independent, we multiply the probabilities for all 5 bits.

Probability of error-free transmission = (0.99)^5 = 0.9509900499

Rounded to three decimal places, this gives 0.951.

✅ Final Answer: 0.951

Reason: Independent events require multiplication of individual probabilities, and all bits must be correct for error-free delivery.