CS and IT GATE 2025 SET-1 Questions with Answer

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.