GATE CS 2025 Set 1

Question 31

NAT · 1 mark

Consider the given function \(f(x)\).

\[ f(x) = \begin{cases} ax + b & \text{for } x \lt 1 \\ x^{3} + x^{2} + 1 & \text{for } x \ge 1 \end{cases} \]

If the function is differentiable everywhere, the value of \(b\) must be ________. (rounded off to one decimal place)

Your answer

Explanation

Answer: -2.1 to -1.9

A function that is differentiable at \(x = 1\) must be continuous there, and its left and right derivatives must be equal.

Continuity at \(x = 1\): \(a + b = 1 + 1 + 1 = 3\). Equal slopes: the left piece has slope \(a\), and the right piece has slope \(3x^{2} + 2x = 5\) at \(x = 1\), so \(a = 5\).

Hence \(b = 3 - 5 = -2\), that is, \(-2.0\).

Answer: −2.0

A box contains 5 coins: 4 regular coins and 1 fake coin. When a regular coin is tossed, the probability \(P(head) = 0.5\) and for a fake coin, \(P(head) = 1\). You pick a coin at random and toss it twice, and get two heads. The probability that the coin you have chosen is the fake coin is _______. (rounded off to two decimal places)

Your answer

Explanation

Answer: 0.49 to 0.51

Use Bayes’ theorem, with \(F\) = the fake coin is chosen and \(HH\) = two heads.

\(P(F) = \frac{1}{5}\) and \(P(HH \mid F) = 1\); a regular coin is chosen with probability \(\frac{4}{5}\) and gives two heads with probability \(0.5 \times 0.5 = \frac{1}{4}\).

\(P(HH) = \frac{1}{5} \cdot 1 + \frac{4}{5} \cdot \frac{1}{4} = \frac{2}{5}\), so \(P(F \mid HH) = \dfrac{1/5}{2/5} = \frac{1}{2} = 0.50\).

Answer: 0.50

Question 33

NAT · 1 mark

The pseudocode of a function fun() is given below:

fun(int A[0,…,n-1]){
    for i=0 to n-2
        for j=0 to n-i-2
            if (A[j]>A[j+1])
                then swap A[j] and A[j+1]

}

Let \(A[0, \ldots, 29]\) be an array storing 30 distinct integers in descending order. The number of swap operations that will be performed, if the function fun() is called with \(A[0, \ldots, 29]\) as argument, is __________. (Answer in integer)

Your answer

Explanation

Answer: 435

fun() is bubble sort. Each swap exchanges one adjacent out-of-order pair, so it removes exactly one inversion, and the total number of swaps equals the number of inversions in the input.

In a descending array of 30 distinct values every pair is an inversion, so the count is \(\binom{30}{2} = \frac{30 \times 29}{2} = 435\). Pass by pass gives the same total: pass \(i\) makes \(29 - i\) comparisons and every one of them swaps, so \(29 + 28 + \cdots + 1 = 435\).

Answer: 435

Question 34

NAT · 1 mark

#include <stdio.h>
void foo(int *p, int x){
    *p=x;
}
int main(){
    int *z;
    int a = 20, b = 25;
    z = &a;
    foo(z,b);
    printf("%d",a);
    return 0;
}

The output of the given C program is __________. (Answer in integer)

Your answer

Explanation

Answer: 25

In main, z = &a makes z hold the address of a. The call foo(z,b) copies that address into p and the value 25 into x.

Inside foo, *p=x stores 25 at the address held by p, which is the variable a itself. So a changes from 20 to 25, and printf prints 25.

Answer: 25

Question 35

NAT · 1 mark

The height of any rooted tree is defined as the maximum number of edges in the path from the root node to any leaf node.

Suppose a Min-Heap \(T\) stores 32 keys. The height of \(T\) is _____________. (Answer in integer)

Your answer

Explanation

Answer: 5

A binary heap is always a complete binary tree: every level is full except possibly the last, which fills from the left. So its shape, and hence its height, depends only on the number of keys.

Levels 0 to 4 hold \(1 + 2 + 4 + 8 + 16 = 31\) keys, so the 32nd key starts level 5. The deepest leaf is therefore 5 edges below the root, matching \(\lfloor \log_2 n \rfloor = \lfloor \log_2 32 \rfloor = 5\).

Answer: 5

Question 36

MCQ · 2 marks · −0.66

Consider a memory system with 1M bytes of main memory and 16K bytes of cache memory. Assume that the processor generates 20-bit memory address, and the cache block size is 16 bytes. If the cache uses direct mapping, how many bits will be required to store all the tag values? [Assume memory is byte addressable, 1K=\(2^{10}\), 1M=\(2^{20}\).]

\(6 \times 2^{10}\) \(8 \times 2^{10}\) \(2^{12}\) \(2^{14}\)

Explanation

Answer: (A)

Split the 20-bit address into tag, line index and block offset.

Offset: a block has \(16 = 2^4\) bytes, so 4 bits.
Index: the cache has \(2^{14} / 2^4 = 2^{10}\) lines, so 10 bits.
Tag: \(20 - 10 - 4 = 6\) bits.

Each of the \(2^{10}\) cache lines stores its own 6-bit tag, so the tag storage is \(6 \times 2^{10}\) bits.

Answer: A

Question 37

MCQ · 2 marks · −0.66

A processor has 64 general-purpose registers and 50 distinct instruction types. An instruction is encoded in 32-bits. What is the maximum number of bits that can be used to store the immediate operand for the given instruction?

ADD R1, #25     // R1 = R1 + 25

16 20 22 24

Explanation

Answer: (B)

The 32-bit instruction must hold the opcode, one register field (R1) and the immediate value; the immediate gets whatever bits are left.

Opcode: 50 instruction types need 6 bits, since \(2^5 = 32 \lt 50 \le 64 = 2^6\).
Register: 64 registers need \(\log_2 64 = 6\) bits.
Immediate: \(32 - 6 - 6 = 20\) bits.

Answer: B

Question 38

MCQ · 2 marks · −0.66

A computer has two processors, \(M_1\) and \(M_2\). Four processes \(P_1, P_2, P_3, P_4\) with CPU bursts of 20, 16, 25, and 10 milliseconds, respectively, arrive at the same time and these are the only processes in the system. The scheduler uses non-preemptive priority scheduling, with priorities decided as follows:

\(M_1\) uses priority of execution for the processes as, \(P_1 \gt P_3 \gt P_2 \gt P_4\), i.e., \(P_1\) and \(P_4\) have highest and lowest priorities, respectively.
\(M_2\) uses priority of execution for the processes as, \(P_2 \gt P_3 \gt P_4 \gt P_1\), i.e., \(P_2\) and \(P_1\) have highest and lowest priorities, respectively.

A process \(P_i\) is scheduled to a processor \(M_k\), if the processor is free and no other process \(P_j\) is waiting with higher priority. At any given point of time, a process can be allocated to any one of the free processors without violating the execution priority rules. Ignore the context switch time. What will be the average waiting time of the processes in milliseconds?

9.00 8.75 6.50 7.50

Explanation

Answer: (A)

Simulate both processors. Whenever a processor becomes free, it takes the waiting process that ranks highest in its own priority list.

\(t = 0\): \(M_1\) takes \(P_1\) (runs 0 to 20) and \(M_2\) takes \(P_2\) (runs 0 to 16).
\(t = 16\): \(M_2\) is free; \(P_3\) and \(P_4\) are waiting, and \(M_2\) prefers \(P_3\) (runs 16 to 41).
\(t = 20\): \(M_1\) is free and only \(P_4\) is left (runs 20 to 30).

All processes arrive at time 0, so each waiting time equals its start time: \(0 + 0 + 16 + 20 = 36\), and the average is \(36 / 4 = 9.00\) ms.

Answer: A

Question 39

MCQ · 2 marks · −0.66

Consider two relations describing \(teams\) and \(players\) in a sports league:

\(teams(tid, tname)\): \(tid\), \(tname\) are team-id and team-name, respectively
\(players(pid, pname, tid)\): \(pid\), \(pname\), and \(tid\) denote player-id, player-name and the team-id of the player, respectively

Which ONE of the following tuple relational calculus queries returns the name of the players who play for the team having \(tname\) as \(\text{‘MI’}\)?

\(\{\, p.pname \mid p \in players \land \exists t\, (t \in teams \land p.tid = t.tid \land t.tname = \text{‘MI’}) \,\}\) \(\{\, p.pname \mid p \in teams \land \exists t\, (t \in players \land p.tid = t.tid \land t.tname = \text{‘MI’}) \,\}\) \(\{\, p.pname \mid p \in players \land \exists t\, (t \in teams \land t.tname = \text{‘MI’}) \,\}\) \(\{\, p.pname \mid p \in teams \land \exists t\, (t \in players \land t.tname = \text{‘MI’}) \,\}\)

Explanation

Answer: (A)

The result must list players, so \(p\) has to range over \(players\) (the relation that has \(pname\)), and there must exist a team \(t\) with the same \(tid\) whose \(tname\) is ‘MI’.

(A) does exactly this: \(p \in players\), \(t \in teams\), joined by \(p.tid = t.tid\) and filtered by \(t.tname = \text{‘MI’}\). Correct.
(B) and (D) take \(p\) from \(teams\) and \(t\) from \(players\), but \(teams\) has no \(pname\) and \(players\) has no \(tname\), so they are wrong.
(C) has no join condition \(p.tid = t.tid\): as long as some team is called ‘MI’, it returns every player in the league.

Answer: A

Question 40

MCQ · 2 marks · −0.66

A packet with the destination IP address 145.36.109.70 arrives at a router whose routing table is shown. Which interface will the packet be forwarded to?

Subnet Address	Subnet Mask (in CIDR notation)	Interface
145.36.0.0	/16	E1
145.36.128.0	/17	E2
145.36.64.0	/18	E3
145.36.255.0	/24	E4
Default	--	E5

E3 E1 E2 E5

Explanation

Answer: (A)

A router uses longest prefix match: among the entries that match the destination, the one with the longest mask wins. The first two octets (145.36) agree with every listed subnet, so only the third octet matters: \(109 = 01101101_2\).

/16 (145.36.0.0): matches.
/17 (145.36.128.0): needs the third octet to begin with bit 1 (128 to 255); 109 begins with 0, so no match.
/18 (145.36.64.0): needs the third octet to begin with 01 (64 to 127); 109 does, so it matches.
/24 (145.36.255.0): needs the third octet to be 255, so no match.

Of the matches (/16, /18 and the default route), /18 is the longest, so the packet is sent on E3.

Answer: A

Computer Science and Information Technology

Question 31

Question 32

Question 33

Question 34

Question 35

Question 36

Question 37

Question 38

Question 39

Question 40