1
GATE CSE 2021 Set 1
MCQ (Single Correct Answer)
+1
-0.33
A binary search tree T contains n distinct elements. What is the time complexity of picking an element in T that is smaller than the maximum element in T?
A
Θ(1)
B
Θ(n log n)
C
Θ(log n)
D
Θ(n)
2
GATE CSE 2021 Set 1
MCQ (Single Correct Answer)
+2
-0.67

Consider the following recurrence relation.

$$T(n) = \left\{ {\begin{array}{*{20}{c}} {T(n/2) + T(2n/5) + 7n \ \ \ if\ n > 0}\\ {1\ \ \ \ \ \ \ if\ n = 0} \end{array}} \right.$$

Which one of the following option is correct?

A
T(n) = Θ(n log n)
B
T(n) = Θ(n5/2)
C
T(n) = Θ((log n)5/2)
D
T(n) = Θ(n)
3
GATE CSE 2021 Set 1
MCQ (More than One Correct Answer)
+2
-0

Define Rn to be the maximum amount earned by cutting a rod of length n meters into one or more pieces of integer length and selling them. For i > 0, let p[i] denotes the selling price of a rod whose length is i meters. Consider the array of prices:

p[1] = 1, p[2] = 5, p[3] = 8, p[4] = 9, p[5] = 10, p[6] = 17, p[7] = 18

Which of the following statements is/are correct about R7?

A
R7 cannot be achieved by a solution consisting of three pieces.
B
R7 = 19
C
R7 = 18
D
R7 is achieved by three different solutions.
4
GATE CSE 2021 Set 1
MCQ (Single Correct Answer)
+1
-0.33

Consider the following statements.

S1 : Every SLR(1) grammar is unambiguous but there are certain unambiguous grammars that are not SLR(1).

S2 : For any context-free grammar, there is a parser that takes at most O(n3) time to parse a string of length n.

Which one of the following option is correct?

A
S1 is true and S2 is false
B
S1 is false and S2 is true
C
S1 is true and S2 is true
D
S1 is false and S2 is false
EXAM MAP