GATE CS 2024 Set 1 - W3Colleges

Question 41

MCQ · 2 marks · −0.66

An array [82, 101, 90, 11, 111, 75, 33, 131, 44, 93] is heapified. Which one of the following options represents the first three elements in the heapified array?

82, 90, 101 82, 11, 93 131, 11, 93 131, 111, 90

Explanation

Answer: (D)

No option starts with the smallest key, 11, so the heap meant is a max-heap. Build it bottom-up, sifting down from the last internal node (position 5) back to the root:

111 is already larger than its child 93; 11 swaps with its larger child 131; 90 stays above 75 and 33.
101 swaps with its larger child, now 131.
At the root, 82 swaps with 131, then with 111, then with 93.

The heap is [131, 111, 90, 101, 93, 75, 33, 11, 44, 82], and inserting the keys one at a time gives the same first three. Option C is impossible because 11, the smallest key, cannot have children in a max-heap; A and B do not start with the maximum, 131.

Answer: D

Question 42

MCQ · 2 marks · −0.66

Consider the following recurrence relation:

\[T(n) = \begin{cases} \sqrt{n}\,T\left(\sqrt{n}\right) + n & \text{for } n \ge 1, \\ 1 & \text{for } n = 1. \end{cases}\]

Which one of the following options is CORRECT?

\(T(n) = \Theta(n \log \log n)\) \(T(n) = \Theta(n \log n)\) \(T(n) = \Theta(n^{2} \log n)\) \(T(n) = \Theta(n^{2} \log \log n)\)

Explanation

Answer: (A)

Divide both sides by \(n\): \(\frac{T(n)}{n} = \frac{T(\sqrt{n})}{\sqrt{n}} + 1\). Writing \(S(n) = T(n)/n\), this is \(S(n) = S(\sqrt{n}) + 1\): each step takes a square root and adds 1.

For \(n = 2^{2^{k}}\), taking the square root \(k\) times brings \(n\) down to a constant, so \(S(n) = \Theta(k) = \Theta(\log \log n)\) and \(T(n) = n\,S(n) = \Theta(n \log \log n)\).

In the recursion tree, every level does exactly \(n\) work in total (for example \(\sqrt{n}\) subproblems of size \(\sqrt{n}\) cost \(\sqrt{n} \cdot \sqrt{n}\)), and there are \(\log \log n\) levels.

Answer: A

Question 43

MCQ · 2 marks · −0.66

Consider a binary min-heap containing 105 distinct elements. Let \(k\) be the index (in the underlying array) of the maximum element stored in the heap. The number of possible values of \(k\) is

53 52 27 1

Explanation

Answer: (A)

In a min-heap every parent is smaller than its children, so the maximum element cannot have a child: it must be a leaf. With the 105 elements at indices 1 to 105, the nodes with children are indices 1 to \(\lfloor 105/2 \rfloor = 52\), and the leaves are indices 53 to 105, which is \(105 - 52 = 53\) positions.

Every leaf is possible: put the maximum at any chosen leaf and fill the other positions with the remaining elements in increasing order of index; each parent is still smaller than its children. So \(k\) has 53 possible values (indices 52 to 104 with 0-based indexing, still 53).

Answer: A

Question 44

MSQ · 2 marks

The symbol \(\to\) indicates functional dependency in the context of a relational database. Which of the following options is/are TRUE?

\((X, Y) \to (Z, W)\) implies \(X \to (Z, W)\) \((X, Y) \to (Z, W)\) implies \((X, Y) \to Z\) \(\big((X, Y) \to Z \text{ and } W \to Y\big)\) implies \((X, W) \to Z\) \((X \to Y \text{ and } Y \to Z)\) implies \(X \to Z\)

Explanation

Answer: (B), (C), (D)

A is false. The left side of a dependency cannot just be shrunk. In a relation with the tuples \((X, Y, Z, W) = (0, 0, 0, 0)\) and \((0, 1, 1, 1)\), \((X, Y) \to (Z, W)\) holds because the tuples differ on \((X, Y)\), but \(X \to (Z, W)\) fails.
B is true by decomposition: whatever determines \((Z, W)\) also determines \(Z\).
C is true (pseudo-transitivity). Augmenting \(W \to Y\) with \(X\) gives \((X, W) \to (X, Y)\), and with \((X, Y) \to Z\) this yields \((X, W) \to Z\).
D is true by transitivity, one of Armstrong’s axioms.

Answer: B, C, D

Question 45

MSQ · 2 marks

Let \(G\) be a directed graph and \(T\) a depth first search (DFS) spanning tree in \(G\) that is rooted at a vertex \(v\). Suppose \(T\) is also a breadth first search (BFS) tree in \(G\), rooted at \(v\). Which of the following statements is/are TRUE for every such graph \(G\) and tree \(T\) ?

There are no back-edges in \(G\) with respect to the tree \(T\) There are no cross-edges in \(G\) with respect to the tree \(T\) There are no forward-edges in \(G\) with respect to the tree \(T\) The only edges in \(G\) are the edges in \(T\)

Explanation

Answer: (C)

In a BFS tree the depth of every vertex equals its shortest distance from \(v\), and any edge \((u, w)\) forces \(\text{dist}(w) \le \text{dist}(u) + 1\).

C is true. A forward edge \((u, w)\) leads to a descendant \(w\) of \(u\) that is not its child, so \(w\) is at least two levels below \(u\) in \(T\). The edge itself gives \(\text{dist}(w) \le \text{dist}(u) + 1\), a contradiction.
A and D are false: with the edges \(v \to u\) and \(u \to v\), both searches give the tree \(v \to u\), and \(u \to v\) is a back edge.
B is false: with the edges \(v \to a\), \(v \to b\) and \(b \to a\), a DFS that visits \(a\) first builds the tree \(v \to a\), \(v \to b\), which is also the BFS tree, and \(b \to a\) is a cross edge.

Answer: C

Question 46

MSQ · 2 marks

Consider the following read-write schedule \(S\) over three transactions \(T_{1}\), \(T_{2}\), and \(T_{3}\), where the subscripts in the schedule indicate transaction IDs:

\(S\colon r_{1}(z);\) \(w_{1}(z);\) \(r_{2}(x);\) \(r_{3}(y);\) \(w_{3}(y);\) \(r_{2}(y);\) \(w_{2}(x);\) \(w_{2}(y);\)

Which of the following transaction schedules is/are conflict equivalent to \(S\) ?

\(T_{1}T_{2}T_{3}\) \(T_{1}T_{3}T_{2}\) \(T_{3}T_{2}T_{1}\) \(T_{3}T_{1}T_{2}\)

Explanation

Answer: (B), (C), (D)

Two operations conflict when they come from different transactions, use the same item and at least one of them is a write.

\(z\) is used only by \(T_{1}\) and \(x\) only by \(T_{2}\), so they cause no conflicts.
On \(y\), both \(r_{3}(y)\) and \(w_{3}(y)\) come before \(r_{2}(y)\) and \(w_{2}(y)\). The conflicting pairs \(r_{3}(y)\)–\(w_{2}(y)\), \(w_{3}(y)\)–\(r_{2}(y)\) and \(w_{3}(y)\)–\(w_{2}(y)\) all order \(T_{3}\) before \(T_{2}\).

The precedence graph has the single edge \(T_{3} \to T_{2}\), and \(T_{1}\) is free. A serial schedule is conflict equivalent to \(S\) exactly when \(T_{3}\) comes before \(T_{2}\): \(T_{1}T_{3}T_{2}\), \(T_{3}T_{2}T_{1}\) and \(T_{3}T_{1}T_{2}\). Option A puts \(T_{2}\) first.

Answer: B, C, D

Question 47

MSQ · 2 marks

Consider a Boolean expression given by \(F(X, Y, Z) = \sum(3,5,6,7)\).

Which of the following statements is/are CORRECT?

\(F(X, Y, Z) = \Pi(0,1,2,4)\) \(F(X, Y, Z) = XY + YZ + XZ\) \(F(X, Y, Z)\) is independent of input \(Y\) \(F(X, Y, Z)\) is independent of input \(X\)

Explanation

Answer: (A), (B)

A is true. The maxterms of a function are exactly the minterms it does not contain; out of 0 to 7 these are 0, 1, 2 and 4.
B is true. \(XY + YZ + XZ\) is 1 exactly when at least two inputs are 1, that is for \(XYZ\) = 011, 101, 110 and 111, which are minterms 3, 5, 6 and 7. \(F\) is the 3-input majority function.
C and D are false. \(F(X, 0, Z) = XZ\) while \(F(X, 1, Z) = X + Z\), so \(F\) depends on \(Y\). Likewise \(F(0, Y, Z) = YZ\) and \(F(1, Y, Z) = Y + Z\) differ, so \(F\) depends on \(X\).

Answer: A, B

Question 48

MSQ · 2 marks

Consider the following C function definition.

int f(int x, int y) {
  for (int i=0; i<y; i++) {
    x=x+x+y;
  }
  return x;
}

Which of the following statements is/are TRUE about the above function?

If the inputs are x=20, y=10, then the return value is greater than \(2^{20}\) If the inputs are x=20, y=20, then the return value is greater than \(2^{20}\) If the inputs are x=20, y=10, then the return value is less than \(2^{10}\) If the inputs are x=10, y=20, then the return value is greater than \(2^{20}\)

Explanation

Answer: (B), (D)

Each iteration sets \(x \leftarrow 2x + y\), and the loop runs \(y\) times. Adding \(y\) to both sides shows that \(x + y\) doubles on every iteration, so the function returns \(2^{y}(x + y) - y\).

x=20, y=10: \(2^{10} \cdot 30 - 10 = 30710\). That is below \(2^{20} = 1048576\) but above \(2^{10} = 1024\), so A and C are false.
x=20, y=20: \(2^{20} \cdot 40 - 20 = 41943020 \gt 2^{20}\), so B is true.
x=10, y=20: \(2^{20} \cdot 30 - 20 = 31457260 \gt 2^{20}\), so D is true.

Both large results are below \(2^{31} - 1\), so int does not overflow.

Answer: B, D

Question 49

MSQ · 2 marks

Let \(A\) be any \(n \times m\) matrix, where \(m > n\). Which of the following statements is/are TRUE about the system of linear equations \(Ax = \mathbf{0}\) ?

There exist at least \(m - n\) linearly independent solutions to this system There exist \(m - n\) linearly independent vectors such that every solution is a linear combination of these vectors There exists a non-zero solution in which at least \(m - n\) variables are 0 There exists a solution in which at least \(n\) variables are non-zero

Explanation

Answer: (A)

Since \(A\) has only \(n\) rows, \(\operatorname{rank}(A) \le n\). By rank–nullity, the solutions of \(Ax = \mathbf{0}\) form a subspace of dimension \(m - \operatorname{rank}(A) \ge m - n \ge 1\).

(A) True: a basis of this subspace contains at least \(m - n\) linearly independent solutions.
(B) False: it needs the dimension to be exactly \(m - n\). For the \(1 \times 3\) zero matrix every vector in \(\mathbb{R}^{3}\) is a solution, and \(m - n = 2\) vectors cannot span a 3-dimensional space.
(C) False: for \(A = \begin{pmatrix} 1 & 1 \end{pmatrix}\) the solutions are \((t, -t)\), so no non-zero solution has a zero entry.
(D) False: for \(A = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix}\) every solution is \((0, 0, t)\), with at most one non-zero entry rather than \(n = 2\).

Answer: A

Question 50

MSQ · 2 marks

Consider the 5-state DFA \(M\) accepting the language \(L(M) \subset (0 + 1)^{*}\) shown below. For any string \(w \in (0 + 1)^{*}\) let \(n_{0}(w)\) be the number of \(0's\) in \(w\) and \(n_{1}(w)\) be the number of \(1's\) in \(w\).

A five-state DFA with states 1 to 5, where state 1 is both the start state and the only accepting state. On inputs 0 and 1 respectively, state 1 goes to 2 and 4, state 2 to 3 and 1, state 3 to 1 and 2, state 4 to 1 and 5, and state 5 to 4 and 1.

Which of the following statements is/are FALSE?

States 2 and 4 are distinguishable in \(M\) States 3 and 4 are distinguishable in \(M\) States 2 and 5 are distinguishable in \(M\) Any string \(w\) with \(n_{0}(w) = n_{1}(w)\) is in \(L(M)\)

Explanation

Answer: (B), (C)

Each state records \(n_{0} - n_{1} \bmod 3\) for the input read so far: a 0 adds 1 and a 1 subtracts 1. State 1 is residue 0, states 2 and 5 are residue 1, and states 3 and 4 are residue 2; every arrow fits (for example, 3 goes to 2 on a 1, and 5 goes to 4 on a 0). So \(L(M)\) is the set of strings with \(n_{0}(w) - n_{1}(w) \equiv 0 \pmod{3}\).

(A) is true: the input 1 takes state 2 to the accepting state 1 but takes state 4 to state 5.
(B) and (C) are false: 3 and 4 have the same residue, as do 2 and 5, so every suffix leads both states of a pair to the same verdict. They are equivalent, not distinguishable.
(D) is true: equal counts give a difference of 0.

Answer: B, C

Computer Science and Information Technology