GATE CS 2025 Set 1 - W3Colleges

Question 21

MSQ · 1 mark

Consider the following \(B^{+}\) tree with 5 nodes, in which a node can store at most 3 key values. The value 23 is now inserted in the \(B^{+}\) tree. Which of the following option(s) is/are CORRECT?

B+ tree: root node with keys 6, 12, 19 and four full leaf nodes holding 1 4 3, 7 9 10, 13 15 17 and 20 21 22

None of the nodes will split. At least one node will split and redistribute. The total number of nodes will remain same. The height of the tree will increase.

Explanation

Answer: (B), (D)

23 is larger than every key, so it belongs in the rightmost leaf (20, 21, 22). That leaf is full, and so are all the other leaves, so no key can be moved to a neighbour: the leaf must split, for example into (20, 21) and (22, 23), sending the separator 22 up to the root.

The root (6, 12, 19) is also full, so it splits too and a new root is created above the two halves. The tree grows from 2 levels to 3 and from 5 nodes to 8.

(A) False: the leaf and the root both split.
(B) True: each full node splits and its keys are shared between the two halves.
(C) False: three nodes are added (a new leaf, the second half of the old root, and the new root).
(D) True: the new root adds a level.

Answer: B, D

Question 22

MSQ · 1 mark

Consider the 3-way handshaking protocol for TCP connection establishment. Let the three packets exchanged during the connection establishment be denoted as P1, P2, and P3, in order. Which of the following option(s) is/are TRUE with respect to TCP header flags that are set in the packets?

P3: SYN = 1, ACK = 1 P2: SYN = 1, ACK = 1 P2: SYN = 0, ACK = 1 P1: SYN = 1

Explanation

Answer: (B), (D)

In the 3-way handshake the client opens with a SYN segment (P1: SYN = 1, ACK = 0). The server replies with SYN + ACK (P2: SYN = 1, ACK = 1), and the client finishes with a pure acknowledgement (P3: SYN = 0, ACK = 1).

(A) False: P3 has SYN = 0.
(B) True: P2 acknowledges the client’s SYN and carries the server’s own SYN.
(C) False: P2 must have SYN = 1.
(D) True: P1 is the connection request, so SYN = 1.

Answer: B, D

Question 23

MSQ · 1 mark

Consider the given system of linear equations for variables \(x\) and \(y\), where \(k\) is a real-valued constant. Which of the following option(s) is/are CORRECT?

\(x + ky = 1\)
\(kx + y = -1\)

There is exactly one value of \(k\) for which the above system of equations has no solution. There exist an infinite number of values of \(k\) for which the system of equations has no solution. There exists exactly one value of \(k\) for which the system of equations has exactly one solution. There exists exactly one value of \(k\) for which the system of equations has an infinite number of solutions.

Explanation

Answer: (A), (D)

The determinant of the coefficient matrix is \(1 \cdot 1 - k \cdot k = 1 - k^{2}\). For every \(k \ne \pm 1\) it is non-zero, so the system has exactly one solution.

For \(k = 1\): \(x + y = 1\) and \(x + y = -1\) contradict each other, so there is no solution. For \(k = -1\): \(x - y = 1\) and \(-x + y = -1\) are the same equation, so there are infinitely many solutions.

(A) True: only \(k = 1\) gives no solution.
(B) False: no solution happens for \(k = 1\) alone.
(C) False: infinitely many values (every \(k \ne \pm 1\)) give exactly one solution.
(D) True: only \(k = -1\) gives infinitely many solutions.

Answer: A, D

Question 24

MSQ · 1 mark

Let \(X\) be a 3-variable Boolean function that produces output as ‘1’ when at least two of the input variables are ‘1’. Which of the following statement(s) is/are CORRECT, where \(a, b, c, d, e\) are Boolean variables?

\(X(a, b, X(c, d, e)) = X(X(a, b, c), d, e)\) \(X(a, b, X(a, b, c)) = X(a, b, c)\) \(X(a, b, X(a, c, d)) = (X(a, b, a) \text{ AND } X(c, d, c))\) \(X(a, b, c) = X(a, X(a, b, c), X(a, c, c))\)

Explanation

Answer: (B), (D)

\(X\) is the majority function. Two quick rules: \(X(p, p, r) = p\), and if two arguments differ, \(X\) equals the remaining one.

(A) False: with \(a = b = 1\), \(c = d = e = 0\), the left side is \(X(1, 1, 0) = 1\) but the right side is \(X(1, 0, 0) = 0\).
(B) True: if \(a = b\), both sides equal \(a\); if \(a \ne b\), the left side equals its third argument, \(X(a, b, c)\).
(C) False: the right side is \(a \cdot c\); with \(a = b = 1\), \(c = d = 0\), the left side is \(X(1, 1, 0) = 1\) but the right side is 0.
(D) True: \(X(a, c, c) = c\), so the right side is \(X(a, X(a, b, c), c)\); if \(a = c\) it equals \(a = X(a, b, c)\), and if \(a \ne c\) it equals the middle argument \(X(a, b, c)\).

Answer: B, D

Question 25

MSQ · 1 mark

The number −6 can be represented as 1010 in 4-bit 2’s complement representation. Which of the following is/are CORRECT 2’s complement representation(s) of −6?

1000 1010 in 8-bits 1111 1010 in 8-bits 1000 0000 0000 1010 in 16-bits 1111 1111 1111 1010 in 16-bits

Explanation

Answer: (B), (D)

To widen a 2’s complement number, copy its sign bit into every new position (sign extension). The sign bit of 1010 is 1, so \(-6\) is 1111 1010 in 8 bits and 1111 1111 1111 1010 in 16 bits.

(A) False: 1000 1010 is \(-128 + 10 = -118\).
(B) True: 1111 1010 is \(-128 + 122 = -6\).
(C) False: 1000 0000 0000 1010 is \(-32768 + 10 = -32758\).
(D) True: it is 1010 sign-extended to 16 bits, value \(-6\).

Answer: B, D

Question 26

MSQ · 1 mark

Which of the following statement(s) is/are TRUE for any binary search tree (BST) having \(n\) distinct integers?

The maximum length of a path from the root node to any other node is \((n - 1)\). An inorder traversal will always produce a sorted sequence of elements. Finding an element takes \(O(\log_{2} n)\) time in the worst case. Every BST is also a Min-Heap.

Explanation

Answer: (A), (B)

(A) True: a path from the root visits distinct nodes, so it has at most \(n - 1\) edges, and a skewed BST (keys inserted in sorted order) reaches exactly \(n - 1\).
(B) True: every left subtree holds smaller keys and every right subtree larger ones, so left–root–right order lists the keys in increasing order.
(C) False: a skewed BST has height \(n - 1\), so a search can take \(O(n)\) time; \(O(\log_{2} n)\) is guaranteed only for balanced trees.
(D) False: in a min-heap a parent is smaller than its children, but in a BST any left child is smaller than its parent.

Answer: A, B

Question 27

MSQ · 1 mark

A partial data path of a processor is given in the figure, where RA, RB, and RZ are 32-bit registers. Which option(s) is/are CORRECT related to arithmetic operations using the data path as shown?

Data path: Mux_A selects RA or a 32-bit immediate value, Mux_B selects RB or a 32-bit immediate value; both mux outputs feed the ALU, whose result goes to RZ

The data path can implement arithmetic operations involving two registers. The data path can implement arithmetic operations involving one register and one immediate value. The data path can implement arithmetic operations involving two immediate values. The data path can only implement arithmetic operations involving one register and one immediate value.

Explanation

Answer: (A), (B), (C)

Each ALU input comes from its own multiplexer: Mux_A passes either RA or a 32-bit immediate value, and Mux_B passes either RB or a 32-bit immediate value. So every combination of the two operand sources is possible.

(A) True: select RA on Mux_A and RB on Mux_B.
(B) True: select RA and the immediate on Mux_B (or the immediate on Mux_A and RB).
(C) True: select the immediate input on both multiplexers.
(D) False: the word “only” is wrong, because (A) and (C) are also possible.

Answer: A, B, C

Question 28

MSQ · 1 mark

A regular language \(L\) is accepted by a non-deterministic finite automaton (NFA) with \(n\) states. Which of the following statement(s) is/are FALSE?

\(L\) may have an accepting NFA with \(\lt n\) states. \(L\) may have an accepting DFA with \(\lt n\) states. There exists a DFA with \(\le 2^{n}\) states that accepts \(L\). Every DFA that accepts \(L\) has \(\gt 2^{n}\) states.

Explanation

Answer: (D)

The question asks for the FALSE statements.

(A) True statement: a smaller NFA can exist. For example, if the given NFA (with \(n \ge 2\)) accepts every string, a 1-state NFA also accepts \(L\).
(B) True statement: in the same example a 1-state DFA accepts \(L\), so a DFA with fewer than \(n\) states is possible.
(C) True statement: the subset construction turns any \(n\)-state NFA into an equivalent DFA with at most \(2^{n}\) states.
(D) False: by (C), some DFA for \(L\) has at most \(2^{n}\) states, so not every DFA can have more than \(2^{n}\).

Answer: D

Question 29

NAT · 1 mark

Suppose in a multiprogramming environment, the following C program segment is executed. A process goes into I/O queue whenever an I/O related operation is performed. Assume that there will always be a context switch whenever a process requests for an I/O, and also whenever the process returns from an I/O. The number of times the process will enter the ready queue during its lifetime (not counting the time the process enters the ready queue when it is run initially) is _______. (Answer in integer)

int main()
{
    int x=0,i=0;
    scanf("%d",&x);
    for(i=0; i<20; i++)
    {
        x = x+20;
        printf("%d\n",x);
    }
    return 0;
}

Your answer

Explanation

Answer: 21

Every I/O call moves the process from the CPU to the I/O queue, and when that I/O completes the process re-enters the ready queue. So we only need to count the I/O operations.

The program performs one scanf and 20 printf calls (one in each iteration, \(i = 0\) to \(19\)); the addition and return 0 need no I/O.

Entries into the ready queue \(= 1 + 20 = 21\).

Answer: 21

Question 30

NAT · 1 mark

Let \(S\) be the set of all ternary strings defined over the alphabet \(\{a, b, c\}\). Consider all strings in \(S\) that contain at least one occurrence of two consecutive symbols, that is, “aa”, “bb” or “cc”. The number of such strings of length 5 that are possible is _______. (Answer in integer)

Your answer

Explanation

Answer: 195

Count the complement first: length-5 strings in which no two neighbouring symbols are the same. The first symbol has 3 choices and each of the next four has 2 (anything except the symbol just before it), so there are \(3 \times 2^{4} = 48\) such strings.

There are \(3^{5} = 243\) strings in all, so the number with at least one “aa”, “bb” or “cc” is \(243 - 48 = 195\).

Answer: 195

Computer Science and Information Technology