CS and IT Gate 2025 Set-1 Questions with Answer

(7) is the correct answer.

IP header = 20 bytes. Original message = 15000 bytes total, so data payload = 14980 bytes.
At Router-1 (MTU = 5000 bytes):
Max data per fragment = 5000 - 20 = 4980 bytes. Rounded down to nearest multiple of 8 = 4976 bytes.
Fragments created: 4976 + 4976 + 4976 + 52 = 14980 bytes → 4 fragments
At Router-2 (MTU = 3000 bytes):
Max data per fragment = 3000 - 20 = 2980. Rounded down to multiple of 8 = 2976 bytes.
Each of the three 4976-byte fragments is split into 2 (2976 + 2000), and the 52-byte fragment passes through unchanged.
Total = 3 × 2 + 1 = 7 fragments delivered to the destination.

(a) is the correct answer.

Explanation:
1. Step 1 — Finish Present Instruction (iii): An asynchronous interrupt can arrive at any arbitrary point during an instruction cycle. To ensure system stability and prevent corruption of program state, the processor will always complete the execution of the currently running instruction before responding to or servicing the interrupt.
2. Step 2 — Save Program Counter (i): Once the current instruction finishes, the processor prepares to context-switch to the ISR. Before jumping away, it must save the current content of the Program Counter (PC)—which points to the next instruction of the interrupted program—onto the stack. This allows the processor to seamlessly resume the original program later.
3. Step 3 — Load ISR Address (ii): After safely storing the return address, the Program Counter is updated and loaded with the starting address of the Interrupt Service Routine (ISR) so that the processor can begin executing the interrupt code on the next clock cycle.

4. Conclusion: Therefore, the exact order of execution is (iii) → (i) → (ii).

(b,d) is the correct answer.

Correct Answer:
b and d (Multiple Select Question)

Explanation:
1. Concept of Sign Extension: In 2's complement representation, when you want to extend a signed integer from a smaller number of bits to a larger number of bits (e.g., from 4 bits to 8 bits or 16 bits), you perform an operation called sign extension.
• To do this, you simply look at the most significant bit (MSB), which is the leftmost sign bit.
• You replicate (copy) that sign bit into all the new higher-order positions to fill the extra space.

2. Analyze the Original Value:
• The original 4-bit representation of -6 is 1010.
• The sign bit (MSB) is 1 (indicating a negative value).

3. Convert to 8-bits:
• We need to add 4 extra bits to the left.
• Since the sign bit is 1, we extend it by adding four 1s: 1111.
• Combining them gives: 1111 1010.
• Therefore, Statement (b) is Correct and Statement (a) is Incorrect.

4. Convert to 16-bits:
• We need to add 12 extra bits to the left of the original 4 bits.
• Since the sign bit is 1, we copy it 12 times: 1111 1111 1111.
• Combining them gives: 1111 1111 1111 1010.
• Therefore, Statement (d) is Correct and Statement (c) is Incorrect.

(a,b,c) is the correct answer.

Explanation:
1. Analyze the Input Multiplexers (Mux_A and Mux_B):
The diagram shows that the inputs to the ALU are fully controlled by two independent multiplexers, Mux_A and Mux_B:
• Mux_A Inputs: Can choose between register RA (32 bit) OR an immediate value 32 bit.
• Mux_B Inputs: Can choose between register RB (32 bit) OR an immediate value 32 bit.

2. Evaluate the Combinations:
Because the select lines (Select RA/immediate and Select RB/immediate) work independently of each other, we can configure them to route different combinations of variables straight to the ALU:

• Combination 1 (Two Registers): Set Mux_A to select RA and Mux_B to select RB. This allows arithmetic operations involving two registers. (Statement a is True)
• Combination 2 (One Register, One Immediate): Set Mux_A to select RA and Mux_B to select its immediate value (or vice versa). This allows arithmetic operations involving one register and one immediate value. (Statement b is True)
• Combination 3 (Two Immediate Values): Set both Mux_A and Mux_B to select their respective immediate values. This allows arithmetic operations involving two immediate values simultaneously. (Statement c is True)

3. Evaluate Statement (d):
• Statement (d) claims that the data path can only implement operations between one register and one immediate value. Since we proved it can handle two registers or two immediate values as well, this statement is False.

4. Conclusion:
Statements (a), (b), and (c) are all completely valid configurations supported by the provided multiplexer layout.

(a) is the correct answer.

Explanation:
To find the total number of bits required to store all tag values in a direct-mapped cache, we first need to break down the structure of the physical address and determine how many tags (lines) the cache contains.
1. Analyze the Physical Address Structure:
The processor generates a 20-bit memory address. In a direct-mapped cache, this address is split into three fields:

[ Tag Bits | Index (Line) Bits | Block (Byte) Offset Bits ] = 20 bits total
• Block Offset Bits:
    The cache block size is 16 bytes = 2⁴ bytes.
    Since the memory is byte-addressable, the number of bits needed for the block offset = 4 bits.

• Index (Line) Bits:
    To find the number of lines (slots) in the cache:
    Number of Cache Lines = Cache Size / Block Size
    Number of Cache Lines = 16K bytes / 16 bytes = 1K lines = 2¹⁰ lines.
    Therefore, the number of bits needed to index these lines = 10 bits.

• Tag Bits:
    Tag Bits = Total Address Bits - (Index Bits + Block Offset Bits)
    Tag Bits = 20 - (10 + 4) = 20 - 14 = 6 bits per cache line.

2. Calculate Total Bits Required for All Tags:
Each of the cache lines requires its own tag store.
    Total Tag Bits = Number of Cache Lines × Tag Bits per Line
    Total Tag Bits = 2¹⁰ × 6 bits = 6 × 2¹⁰ bits.

3. Conclusion:
The total storage capacity needed to hold all tag structures is exactly 6×2¹⁰ bits, which perfectly matches option (a).

(b) is the correct answer.

Explanation:
To find the maximum number of bits available for an immediate operand, we need to calculate how many bits of the 32-bit instruction must be allocated to the Opcode (instruction type) and the register fields.
1. Calculate Opcode Bits:
The processor supports 50 distinct instruction types. To uniquely represent 50 operations, the number of bits required for the opcode field is:
    2⁵ < 50 ≤ 2⁶ → 6 bits are required.

2. Calculate Register Bits:
The processor has 64 general-purpose registers. To address any one of the 64 unique registers, the number of bits required per register field is:
    2⁶ = 64 → 6 bits are required per register.

3. Analyze the Target Instruction Type:
Look at the example given: ADD R1, #25 (which represents $R1 = R1 + 25$).
• This is an instruction that involves one destination register ($R1$), one source register (also $R1$ since it reads and modifies it), and one immediate operand ($25$).
• Therefore, the instruction structure must allocate bits for: [ Opcode ] [ Register Destination ] [ Immediate Value ].

4. Calculate the Remaining Bits for the Immediate Operand:
Subtract the bits consumed by the opcode and the single referenced register field from the total instruction size:
    Bits for Immediate Operand = Total Bits - Opcode Bits - Register Bits
    Bits for Immediate Operand = 32 - 6 - 6 = 20 bits.

5. Conclusion:
The maximum size of the immediate field for this instruction type is exactly 20 bits, matching option (b).

(11.87) is the correct answer.

AMAT = T_L1 + (1 - H_L1) × [T_L2 + (1 - H_L2) × T_MM]
where T_L1, T_L2, T_MM are the access times of L1, L2, and main memory, and H_L1, H_L2 are their respective hit rates.
Every memory access always checks L1 first (T_L1 is always paid). On an L1 miss, L2 is checked. On an L2 miss, main memory is accessed.
Substituting the values from the given figure into the formula gives an AMAT of approximately 11.85 ns, which falls within the official accepted range of 11.83 to 11.87.

(a and b) is the correct answer.

Statement A: The maximum length of a path from the root node to any other node is (n-1).
Analysis: In a skewed BST (all nodes in a single line), the path from root to the deepest node has (n-1) edges.
Example: BST with nodes 1→2→3→4→5 has maximum path length = 4 = (5-1)
Result: TRUE ✓

Statement B: An inorder traversal will always produce a sorted sequence of elements.
Analysis: By definition of BST, left subtree < root < right subtree. Inorder traversal (Left→Root→Right) always visits nodes in ascending order.
Example: BST with root 5, left child 3, right child 7 gives inorder: 3, 5, 7 (sorted)
Result: TRUE ✓

Statement C: Finding an element takes O(log₂n) time in the worst case.
Analysis: In the worst case, BST becomes skewed (like a linked list) and finding an element takes O(n) time, not O(log₂n).
O(log₂n) is only for balanced BST, not for any BST.
Result: FALSE ✗

Statement D: Every BST is also a Min-Heap.
Analysis: Min-Heap property: parent < both children (for all nodes).
BST property: left child < parent < right child.
In BST, the right child can be greater than parent, violating Min-Heap property.
Example: BST with root 5, left child 3, right child 7. Here 7 > 5, so not a Min-Heap.
Result: FALSE ✗

Answer: A and B are TRUE

(5) is the correct answer.

Given: Min-Heap with 32 keys

Min-Heap structure:
A Min-Heap is a complete binary tree where every node is smaller than its children.

Formula for height of complete binary tree
For a complete binary tree with n nodes:
Height (h) = ⌊log₂(n)⌋

where ⌊ ⌋ means floor function (round down)

Calculating the height
Number of nodes (n) = 32

Height = ⌊log₂(32)⌋
Height = ⌊log₂(2⁵)⌋
Height = ⌊5⌋
Height = 5

Verification:
A complete binary tree of height 5 has:
- Minimum nodes = 2⁵ = 32 nodes
- Maximum nodes = 2⁶ - 1 = 63 nodes

Since we have exactly 32 nodes, height = 5

Answer: 5

(Slot 10) is the correct answer.

The correct answer is Slot 10.
Given: h₁(k) = k mod 11, h₂(k) = 1 + (k mod 7), table size m = 11.
Probe formula: (h₁(k) + i × h₂(k)) mod 11
First, insert all preceding keys to know which slots are occupied:
63: 63 mod 11 = 8 → Slot 8
50: 50 mod 11 = 6 → Slot 6
25: 25 mod 11 = 3 → Slot 3
79: 79 mod 11 = 2 → Slot 2
67: 67 mod 11 = 1 → Slot 1
Occupied slots before inserting 24: {1, 2, 3, 6, 8}
Now insert key 24:
h₁(24) = 24 mod 11 = 2 → Slot 2 occupied (79)
h₂(24) = 1 + (24 mod 7) = 1 + 3 = 4
Probe i=1: (2 + 1×4) mod 11 = 6 → occupied (50)
Probe i=2: (2 + 2×4) mod 11 = 10 mod 11 = 10 → empty ✓
Key 24 is stored at Slot 10.

(c) is the correct answer.

Explanation:
1. Analyze the Sequence of Operations:
Let's look closely at the chronological execution order of the schedule:
• T1 performs a write operation on data item Y: W₁(Y)
• T2 subsequently performs a read operation on the same data item Y: R₂(Y)
• T3 then performs a read operation on the same data item Y: R₃(Y)
• T1 fails and encounters an abort operation: ABORT(T1)

2. Identify Dirty Reads (Data Dependency):
• Because T2 reads the value of Y after T1 wrote it but before T1 committed or aborted, T2 has performed a dirty read from T1.
• Similarly, because T3 reads the value of Y after T1 wrote it, T3 has also performed a dirty read from T1.

3. Cascading Rollback Mechanism:
• When a transaction aborts, any changes it made to the database are completely undone.
• Since T2 and T3 read an uncommitted, temporary value of Y produced by T1, their computations are based on dirty, invalid data.
• To maintain database consistency and isolation, any transaction that has read uncommitted data from an aborted transaction must also be rolled back. This phenomenon is known as a cascading rollback (cascading abort).

4. Conclusion:
Since both T2 and T3 are dependent on the uncommitted write of T1, both transactions are required to be rolled back when T1 aborts.

(b) is the correct answer.

Explanation:
1. Analyze the Initial State & Max Capacity:
• Each node in this B+ tree can store at most 3 key values.
• Looking at the rightmost leaf node, it currently holds 3 keys: [20, 21, 22]. This leaf node is completely full.

2. Trace the Insertion of Key 23:
• Since 23 is greater than the root keys (6, 12, 19), the B+ tree traversal directs the insertion into the rightmost leaf node.
• Attempting to place 23 into [20, 21, 22] creates a temporary overflow state: [20, 21, 22, 23] (4 keys).

3. Handle the Leaf Node Overflow (Split):
• Because the leaf node exceeds its maximum capacity of 3 keys, it must split into two distinct leaf nodes.
• Typically, the keys are distributed evenly (e.g., 2 keys in the left leaf and 2 keys in the right leaf): [20, 21] and [22, 23].
• The smallest key of the new right split node (22) is copied and pushed up to the parent/root node to act as a separator index.

4. Check the Parent Node Condition:
• The root node currently contains 3 keys: [6, 12, 19]. It is also completely full.
• When the key 22 is pushed up from the leaf split, the root experiences an overflow state: [6, 12, 19, 22].
• This forces the root node to split as well, pushing its middle key (typically 12 or 19 depending on implementation) up to form a brand new root node at a higher level.

5. Evaluate the Structural Consequences:
• Will any node split? Yes, both the leaf node and the root node split. Therefore, Statement (a) is False and Statement (b) is True.
• Will the total number of nodes remain the same? No, splitting nodes increases the total count of nodes in the system. Therefore, Statement (c) is False.
• Will the height of the tree increase? Yes, since the root node splits and pushes a key up to create a new top-level root, the overall height of the tree increases by 1 layer.

Note: Since both (b) and (d) are analytically correct for a standard structural push-up split, option (b) directly captures the guaranteed initial cascading behavior required by the insertion algorithm.

(a) is the correct answer.

Explanation:
To retrieve the names of players who belong to a specific team, our Tuple Relational Calculus (TRC) query needs to filter, join, and project attributes across both relations correctly. Let's break down the required logic step-by-step:
1. Determine the Target Variable:
We want to return the names of the players (pname). The main tuple variable bounding this output attribute must belong to the players relation. Therefore, the query must start with:
    { p.pname | p ∈ players ∧ ... }
This immediately eliminates choices (b) and (d), which incorrectly state that p ∈ teams.

2. Establish the Cross-Relation Link (Join Condition):
To find team details corresponding to a player, there must exist a tuple t in the teams relation (∃t (t ∈ teams)) such that the team identifier matches the player's team identifier. This is the explicit join condition:
    p.tid = t.tid

3. Apply the Filter Criteria:
We only care about the specific team where the team name matches 'MI':
    t.tname = 'MI'

4. Evaluate the Remaining Options:
• Option (a): Correctly specifies that p is a tuple from players, asserts that there exists a tuple t in teams, links them via their shared foreign key (p.tid = t.tid), and applies the exact string filter on the team name.
• Option (c): Missing the critical join constraint p.tid = t.tid. Without this condition, it creates a Cartesian product—returning the names of all players in the database as long as a team named 'MI' exists anywhere in the teams table.

5. Conclusion:
Option (a) is the only syntactically and logically sound TRC formulation for this request.