GATE CS 2025 Set 2

Square the matrix first. The diagonal entries are \(1 \cdot 1 + 2 \cdot 2 = 5\) and \(2 \cdot 2 + (-1)(-1) = 5\), and both off-diagonal entries are \(1 \cdot 2 + 2 \cdot (-1) = 0\), so

\[A^{2} = \begin{pmatrix} 5 & 0 \\ 0 & 5 \end{pmatrix} = 5I.\]

Then \(A^{8} = (A^{2})^{4} = 5^{4}I = 625I\). The other options are \(5^{2}I\), \(5^{3}I\) and \(5^{5}I\), which are \(A^{4}\), \(A^{6}\) and \(A^{10}\).

Answer: C

Integrate by parts with \(u = \ln t\) and \(dv = t \, dt\):

\[\int t \ln t \, dt = \frac{t^{2}}{2}\ln t - \frac{t^{2}}{4}.\]

So \(\int_{1}^{x} t \ln t \, dt = \frac{x^{2}}{2}\ln x - \frac{x^{2}}{4} + \frac{1}{4}\). Setting this equal to \(\frac{1}{4}\) gives \(\frac{x^{2}}{2}\ln x = \frac{x^{2}}{4}\). Since \(x \neq 0\), \(\ln x = \frac{1}{2}\), so \(x = \sqrt{e}\).

The other options fail this last check: \(e\), \(e^{2}\) and \(e - 1\) give \(\ln x = 1\), \(2\) and about \(0.54\), not \(\frac{1}{2}\).

Answer: A

Let \(k\) be the number of nodes with two children; all other nodes are leaves. Count the edges in two ways:

• each of the \(k\) internal nodes has 2 child edges, giving \(2k\) edges;
• every node except the root has exactly one edge to its parent, giving \(n - 1\) edges.

So \(2k = n - 1\), that is, \(k = \frac{n-1}{2}\). For example, a root with two leaf children has \(n = 3\) and \(k = 1\). Such a tree always has an odd number of nodes, so \(\frac{n}{2}\) and \(\frac{n-2}{2}\) are not even whole numbers, while \(\frac{n+1}{2}\) counts the leaves.

Answer: B

Multiply \(L^{2} = L^{-1}\) on the right by \(L\) to get \(L^{3} = I\). Powers of \(L\) therefore repeat every three steps:

\[M = L^{8} = (L^{3})^{2}L^{2} = L^{2} = N.\]

So \(M - N\) is the zero matrix, and its determinant is 0. Non-singularity only guarantees that \(L^{-1}\) exists; it says nothing about the difference \(M - N\), so the non-zero options cannot occur.

Answer: A

Option A is the principle of mathematical induction: \(P(0)\) holds, and truth passes from each \(x\) to \(x + 1\), so it reaches 1, 2, 3, … and hence every natural number. It is true for every predicate \(P\).

Each other option fails for some predicate:

• B: take \(P(x)\) to be “\(x \le 5\)”. Both premises hold, but \(P(6)\) is false.
• C: take “\(x \le 1000\)”. Both premises hold, but \(P(1001)\) is false.
• D: take “\(x \ge 1000\)”. Both premises hold, but \(P(0)\) is false.

Answer: A

(i) is TRUE. A host that knows the IP address of a machine on its local network still needs that machine’s link-layer (MAC) address to build a frame. ARP broadcasts a request for that IP address and gets back the matching hardware address.

(ii) is FALSE. TCP is full duplex, and every segment header has an acknowledgement number field, so a segment carrying data from S to R can also acknowledge data received from R. This is called piggybacking, and it is the normal case when both sides are sending.

Answer: B

In distance vector routing (used by RIP), a router learns only the distance vectors of its neighbours. It keeps improving its own estimates with the Bellman-Ford relation \(D_x(y) = \min_v \{c(x, v) + D_v(y)\}\): the cost to a neighbour \(v\) plus that neighbour's distance to \(y\). So (i) matches (a).

In link state routing (used by OSPF), every router floods the costs of its own links, so each router learns the whole topology and runs Dijkstra's shortest path algorithm from itself. So (ii) matches (b).

The other options pair at least one protocol family with the wrong algorithm.

Answer: A

The protocol field names the protocol whose message sits directly in the payload of the IP datagram, so X must be a protocol that runs immediately on top of IP.

• ICMP (protocol number 1) and IGMP (2) are carried directly in IP datagrams.
• OSPF also runs directly over IP, with protocol number 89.
• RIP does not. Its messages travel inside UDP datagrams on port 520, so a datagram carrying RIP has 17 (UDP) in its protocol field, and RIP is identified only by the UDP port.

So RIP cannot be X.

Answer: D

The array holds the 14 characters @#Hello World! at indices 0 to 13, followed by '\0' at index 14.

stringcopy(a, a + 2) copies one character at a time from t to s, with t always two places ahead of s. Every character is therefore read before it can be overwritten, and the 12 characters Hello World! land in indices 0 to 11.

The loop stops as soon as *t is '\0', so the terminator is never copied. Indices 12 and 13 keep their old characters d!, and the string still ends at index 14, so printf prints Hello World!d!.

Answer: D

Pick any two elements and compare them once. Because the integers are distinct, one of them is strictly smaller, and that smaller element cannot be the largest in the list: the other element beats it. So one comparison always suffices.

Zero comparisons cannot work, since without any comparison every element we might pick could still be the maximum. Hence the minimum is 1.

\(N - 1\) comparisons are what it takes to find the largest element itself, which is a different task; the question only asks for some element that is not the largest.

Answer: A