GATE CS 2025 Set 1

65 questions · Previous year paper

The GATE 2025 Computer Science and Information Technology paper, Set 1 (forenoon session): 65 questions for 100 marks in 180 minutes, with General Aptitude (15 marks) and the technical section (85 marks). Answers follow the official final answer key; every question has a short explanation.

Take it as a timed test: ₹99

Computer Science and Information Technology

Question 51

NAT · 2 marks

A disk of size 512M bytes is divided into blocks of 64K bytes. A file is stored in the disk using linked allocation. In linked allocation, each data block reserves 4 bytes to store the pointer to the next data block. The link part of the last data block contains a NULL pointer (also of 4 bytes). Suppose a file of 1M bytes needs to be stored in the disk. Assume, \(1\text{K} = 2^{10}\) and \(1\text{M} = 2^{20}\). The amount of space in bytes that will be wasted due to internal fragmentation is ______. (Answer in integer)

Explanation

Answer: 65468

Each block is \(64\text{K} = 65536\) bytes and 4 of them hold the link, so a block carries \(65536 - 4 = 65532\) bytes of file data.

The file has \(2^{20} = 1048576\) bytes. Sixteen blocks carry \(16 \times 65532 = 1048512\) bytes, which leaves \(1048576 - 1048512 = 64\) bytes for a 17th block.

The last block holds those 64 bytes and the 4-byte NULL link, so the unused space is \(65536 - 4 - 64 = 65468\) bytes.

Answer: 65468

Question 52

NAT · 2 marks

Refer to the given 3-address code sequence. This code sequence is split into basic blocks. The number of basic blocks is ________. (Answer in integer)

1001: i = 1
1002: j = 1
1003: t1 = 10*i
1004: t2 = t1+j
1005: t3 = 8*t2
1006: t4 = t3-88
1007: a[t4] = 0.0
1008: j = j+1
1009: if j <= 10 goto 1003
1010: i = i+1
1011: if i <= 10 goto 1002
1012: i = 1
1013: t5 = i-1
1014: t6 = 88*t5
1015: a[t6] = 1.0
1016: i = i+1
1017: if i <= 10 goto 1013

Explanation

Answer: 6

A new basic block starts at every leader: the first instruction, every jump target, and every instruction right after a jump.

  • First instruction: 1001.
  • Jump targets: 1003, 1002 and 1013.
  • Instructions after a jump: 1010 (after 1009) and 1012 (after 1011); 1017 is the last line.

The six leaders 1001, 1002, 1003, 1010, 1012 and 1013 give the blocks 1001 | 1002 | 1003–1009 | 1010–1011 | 1012 | 1013–1017.

Answer: 6

Question 53

NAT · 2 marks

A computer has a memory hierarchy consisting of two-level cache (L1 and L2) and a main memory. If the processor needs to access data from memory, it first looks into L1 cache. If the data is not found in L1 cache, it goes to L2 cache. If it fails to get the data from L2 cache, it goes to main memory, where the data is definitely available. Hit rates and access times of various memory units are shown in the figure. The average memory access time in nanoseconds (ns) is ________. (rounded off to two decimal places)

Processor, then L1 cache (hit rate 95%, access time 10 ns), then L2 cache (hit rate 85%, access time including L1 cache miss penalty 20 ns), then main memory (access time including L1 and L2 cache miss penalty 200 ns)

Explanation

Answer: 11.83 to 11.87

The L2 and main-memory times already include the time lost on the earlier misses, so each path is simply weighted by its probability.

  • L1 hit: probability \(0.95\), time 10 ns.
  • L1 miss, L2 hit: probability \(0.05 \times 0.85 = 0.0425\), time 20 ns.
  • Both miss: probability \(0.05 \times 0.15 = 0.0075\), time 200 ns.

\[T_{\text{avg}} = 0.95(10) + 0.0425(20) + 0.0075(200) = 9.5 + 0.85 + 1.5 = 11.85 \text{ ns}\]

Answer: 11.85

Question 54

NAT · 2 marks

In optimal page replacement algorithm, information about all future page references is available to the operating system (OS). A modification of the optimal page replacement algorithm is as follows:

The OS correctly predicts only up to next 4 page references (including the current page) at the time of allocating a frame to a page.

A process accesses the pages in the following order of page numbers:

1, 3, 2, 4, 2, 3, 1, 2, 4, 3, 1, 4.

If the system has three memory frames that are initially empty, the number of page faults that will occur during execution of the process is ________ . (Answer in integer)

Explanation

Answer: 6

On a fault with all frames full, look at the current reference and the next three. Replace a resident page that is not in this window; if all of them are in it, replace the one needed last.

  • 1, 3, 2: three faults fill the frames: {1, 3, 2}.
  • 4: fault. Window 4, 2, 3, 1, so page 1 is needed last; replace it: {4, 3, 2}. The next 2 and 3 are hits.
  • 1: fault. Window 1, 2, 4, 3, so page 3 is needed last; replace it: {4, 1, 2}. The next 2 and 4 are hits.
  • 3: fault. Window 3, 1, 4 does not contain page 2; replace it: {4, 1, 3}. The last 1 and 4 are hits.

Total page faults \(= 3 + 1 + 1 + 1 = 6\).

Answer: 6

Question 55

NAT · 2 marks

Consider the following database tables of a sports league.

player(pid,pname,age)          team(tid,tname,city,cid)
coach(cid,cname)               members(pid,tid)

An instance of the table and an SQL query are given.

player
pidpnameage
1Jasprit31
2Atharva24
3Ishan26
4Axar30
coach
cidcname
101Ricky
102Mark
103Trevor
team
tidtnamecitycid
10MIMumbai102
20DCDelhi101
30PKMohali103
members
pidtid
110
230
310
420
SELECT MIN(P.age)
FROM player P
WHERE P.pid IN (
    SELECT M.pid
    FROM team T, coach C, members M
    WHERE C.cname = 'Mark'
          AND T.cid = C.cid
          AND M.tid = T.tid
    )

The value returned by the given SQL query is ______ . (Answer in integer)

Explanation

Answer: 26

The subquery joins coach, team and members to find the players in teams coached by Mark.

  • coach: Mark has cid = 102.
  • team: the team with cid = 102 is MI, with tid = 10.
  • members: tid = 10 gives pid 1 and pid 3.

The outer query takes the smaller age of pid 1 (Jasprit, 31) and pid 3 (Ishan, 26), which is 26.

Answer: 26

Question 56

NAT · 2 marks

Suppose a 5-bit message is transmitted from a source to a destination through a noisy channel. The probability that a bit of the message gets flipped during transmission is 0.01. Flipping of each bit is independent of one another. The probability that the message is delivered error-free to the destination is ______ . (rounded off to three decimal places)

Explanation

Answer: 0.95

The message arrives error-free only if none of its 5 bits flips. Each bit survives with probability \(1 - 0.01 = 0.99\), and the bits are independent, so the probabilities multiply.

\[P = (0.99)^5 = 0.95099 \approx 0.951\]

Answer: 0.951

Question 57

NAT · 2 marks

Suppose a message of size 15000 bytes is transmitted from a source to a destination using IPv4 protocol via two routers as shown in the figure. Each router has a defined maximum transmission unit (MTU) as shown in the figure, including IP header. The number of fragments that will be delivered to the destination is ________ . (Answer in integer)

Source to Router-1 (MTU = 5000 bytes) to Router-2 (MTU = 3000 bytes) to Destination

Explanation

Answer: 7

Use the standard 20-byte IPv4 header. The data in every fragment except the last must be a multiple of 8 bytes, and routers never reassemble: each router only splits the packets it receives.

  • Router-1 (MTU 5000): at most \(5000 - 20 = 4980\) data bytes, i.e. 4976 as a multiple of 8. The 15000 bytes become \(4976 + 4976 + 4976 + 72\): 4 fragments.
  • Router-2 (MTU 3000): at most \(3000 - 20 = 2980\), i.e. 2976 data bytes. Each 4976-byte fragment splits into \(2976 + 2000\), but the last fragment (72 data bytes, 92 bytes with its header) already fits and passes through unchanged.

Fragments delivered \(= 3 \times 2 + 1 = 7\). The tempting \(4 \times 2 = 8\) wrongly splits the small fourth fragment again; even ignoring the multiple-of-8 rule (4980, 4980, 4980, 60) the count is 7.

Answer: 7

Question 58

NAT · 2 marks

Consider a probability distribution given by the density function \(P(x)\).

\[P(x) = \begin{cases} Cx^2, & \text{for } 1 \le x \le 4 \\ 0, & \text{for } x \lt 1 \text{ or } x \gt 4 \end{cases}\]

The probability that \(x\) lies between 2 and 3, i.e., \(P(2 \le x \le 3)\) is __________. (rounded off to three decimal places)

Explanation

Answer: 0.3

The total probability must be 1, which fixes \(C\):

\[\int_1^4 Cx^2\,dx = C \cdot \frac{4^3 - 1^3}{3} = 21C = 1 \;\Rightarrow\; C = \frac{1}{21}\]

\[P(2 \le x \le 3) = \frac{1}{21}\int_2^3 x^2\,dx = \frac{1}{21} \cdot \frac{3^3 - 2^3}{3} = \frac{19}{63} \approx 0.3016\]

Rounded to three decimal places, this is 0.302.

Answer: 0.302

Question 59

NAT · 2 marks

Consider a finite state machine (FSM) with one input \(X\) and one output \(f\), represented by the given state transition table. The minimum number of states required to realize this FSM is ________. (Answer in integer)

Present stateNext stateOutput \(f\)
\(X = 0\)\(X = 1\)\(X = 0\)\(X = 1\)
AFB00
BDC00
CFE00
DGA10
EDC00
FFB11
GGH01
HGA10

Explanation

Answer: 5

Minimise by partition refinement. The output depends on the input (a Mealy machine), so first group the states by their output pair for \(X = 0\) and \(X = 1\).

  • By outputs: {A, B, C, E} have (0, 0), {D, H} have (1, 0), {F} has (1, 1) and {G} has (0, 1).
  • On \(X = 0\), A and C go to F but B and E go to D, and F, D are in different groups. So {A, B, C, E} splits into {A, C} and {B, E}. D and H have identical rows (G, A), so they stay together.
  • Next pass: A goes to (F, B) and C to (F, E), with B and E now in one group; B, E and D, H still have identical rows. Nothing splits further.

The groups {A, C}, {B, E}, {D, H}, {F}, {G} give 5 states.

Answer: 5

Question 60

NAT · 2 marks

Consider the given sequential circuit designed using D-Flip-flops. The circuit is initialized with some value (initial state). The number of distinct states the circuit will go through before returning back to the initial state is _________ . (Answer in integer)

Four D flip-flops D0 to D3 on a common clock: Q0 drives D1, Q1 drives D2, Q2 drives D3, and the complemented output of D3 feeds back to D0

Explanation

Answer: 7 to 8

From the circuit, \(D_1 = Q_0\), \(D_2 = Q_1\), \(D_3 = Q_2\) and \(D_0 = \overline{Q_3}\). Each clock shifts the bits one place and feeds the complement of the last bit back to the first: a 4-bit Johnson (twisted-ring) counter.

With the state written as \(Q_0Q_1Q_2Q_3\): 0000 → 1000 → 1100 → 1110 → 1111 → 0111 → 0011 → 0001 → 0000. The other 8 states form a second cycle of the same length (0100 → 1010 → 1101 → 0110 → 1011 → 0101 → 0010 → 1001 → 0100), so from any initial state the circuit comes back after 8 clocks.

That is 8 distinct states counting the initial one, or 7 besides it, so the official key accepts 7 to 8.

Answer: 8 (7 is also accepted)

Questions 51 to 60 of 65