[qsm quiz=1]
Q1 – Which one of the following sequences when stored in an array at locations A[1], . . . , A[10] forms a max-heap? (GATE 2023)
1. 23, 17, 10, 6, 13, 14, 1, 5, 7, 12
2. 23, 17, 14, 7, 13, 10, 1, 5, 6, 12
3. 23, 17, 14, 6, 13, 10, 1, 5, 7, 15
4. 23, 14, 17, 1, 10, 13, 16, 12, 7, 5
Ans – (2)
Explanation –
Q2 – The Lucas sequence Ln is defined by the recurrence relation:
Ln = Ln−1 + Ln−2, for n ≥ 3,
with L1 = 1 and L2 = 3.
Which one of the options given is TRUE? (GATE 2023)
Ans – (1)
Explanation –
Q3 – An algorithm has to store several keys generated by an adversary in a hash table. The adversary is malicious who tries to maximize the number of collisions.
Let k be the number of keys, m be the number of slots in the hash table, and k >m.
Which one of the following is the best hashing strategy to counteract the adversary? (GATE 2023)
1. Division method, i.e., use the hash function h(k) = k mod m.
2. Multiplication method, i.e., use the hash function h(k) = floor(m(kA – floor(kA))), where A is a carefully chosen constant.
3. Universal hashing method.
4. If k is a prime number, use Division method. Otherwise, use Multiplication method.
Ans – (3)
Explanation –
Q4 – Let f and g be functions of natural numbers given by f(n) = n and g(n) = n2.
Which of the following statements is/are TRUE? (GATE 2023)
1. f ∈ O(g)
2. f ∈ Ω(g)
3. f ∈ o(g)
4. f ∈ Θ(g)
Ans – (1, 3)
Explanation –
Q5 – Let A be a priority queue for maintaining a set of elements. Suppose A is implemented using a max-heap data structure. The operation Extract-Max(A) extracts and deletes the maximum element from A. The operation Insert(A, key) inserts a new element key in A. The properties of a max-heap are preserved at the end of each of these operations.
When A contains n elements, which one of the following statements about the worst case running time of these two operations is TRUE? (GATE 2023)
1. Both Extract-Max(A) and Insert(A, key) run in O(1).
2. Both Extract-Max(A) and Insert(A, key) run in O(log(n)).
3. Extract-Max(A) runs in O(1) whereas Insert(A, key) runs in O(n).
4. Extract-Max(A) runs in O(1) whereas Insert(A, key) runs in O(log(n)).
Ans – (2)
Explanation –
Q6 – Consider functions Function 1 and Function 2 expressed in pseudocode as follows:
Function 1
while n > 1 do
for i = 1 to n do
x = x + 1;
end for
n = floor(n/2);
end while
Function 2
for i = 1 to 100 ∗ n do
x = x + 1;
end for
Let f1(n) and f2(n) denote the number of times the statement “x = x + 1” is executed in Function 1 and Function 2, respectively.
Which of the following statements is/are TRUE? (GATE 2023)
1. f1(n) ∈ Θ(f2(n))
2. f1(n) ∈ o(f2(n))
3. f1(n) ∈ ω(f2(n))
4. f1(n) ∈ O(n)
Ans – (1, 4)
Explanation –
Q7 – Let G be a simple, finite, undirected graph with vertex set {v1, . . . , vn}. Let Δ(G) denote the maximum degree of G and let N = {1, 2, . . .} denote the set of all possible colors. Color the vertices of G using the following greedy strategy:
for i = 1, . . . , n
color(vi) ← min{j ∈ N : no neighbour of vi is colored j}
Which of the following statements is/are TRUE? (GATE 2023)
1. This procedure results in a proper vertex coloring of G.
2. The number of colors used is at most Δ(G) + 1.
3. The number of colors used is at most Δ(G).
4. The number of colors used is equal to the chromatic number of G.
Ans – (1, 2)
Explanation –
Q8 – Let U = {1, 2, 3}. Let 2U denote the powerset of U. Consider an undirected graph G whose vertex set is 2U. For any A, B ∈ 2U, (A,B) is an edge in G if and only if (i) A ≠ B, and (ii) either A ⊊ B or B ⊊ A. For any vertex A in G, the set of all possible orderings in which the vertices of G can be visited in a Breadth First Search (BFS) starting from A is denoted by ẞ(A).
If ∅ denotes the empty set, then the cardinality of ẞ(∅) is __________. (GATE 2023)
Ans – (5040)
Explanation –
Q9 – Which one of the following statements is TRUE for all positive functions f(n)? (GATE 2022)
1. f(n2) = Ɵ(f(n)2), when f (n) is a polynomial
2. f(n2) = o(f(n)2)
3. f(n2) = O(f(n)2), when f (n) is an exponential function
4. f(n2) = Ω(f(n)2)
Ans – (1)
Explanation –
Q10 – Consider a simple undirected weighted graph G, all of whose edge weights are distinct. Which of the following statements about the minimum spanning trees of G is/are TRUE? (GATE 2022)
1. The edge with the second smallest weight is always part of any minimum spanning tree of G.
2. One or both of the edges with the third smallest and the fourth smallest weights are part of any minimum spanning tree of G.
3. Suppose S ⊆ V be such that S ≠ Φ and S ≠ V. Consider the edge with the minimum weight such that one of its vertices is in S and the other in V \ S . Such an edge will always be part of any minimum spanning tree of G.
4. G can have multiple minimum spanning trees.
Ans – (1, 2, 3)
Explanation –