1
GATE CSE 1994
MCQ (Single Correct Answer)
+2
-0.6
Conside the following two functions:
$${g_1}(n) = \left\{ {\matrix{ {{n^3}\,for\,0 \le n < 10,000} \cr {{n^2}\,for\,n \ge 10,000} \cr } } \right.$$
$${g_2}(n) = \left\{ {\matrix{ {n\,for\,0 \le n \le 100} \cr {{n^3}\,for\,n > 100} \cr } } \right.$$ Which of the following is true:
A
$${g_1}(n)\,is\,0\,({g_2}(n))$$
B
$${g_1}(n)\,is\,0\,({n^3})$$
C
$${g_2}(n)\,is\,0\,({g_1}(n))$$
D
$${g_2}(n)\,is\,0\,(n)$$
2
GATE CSE 1994
MCQ (Single Correct Answer)
+2
-0.6
Which one of the following statements is false?
A
Optimal binary search tree construction can be performed efficiently using dynamic programming.
B
Breadth-first search cannot be used to find connected components of a graph
C
Given the prefix and postfix walks over a binary tree, the binary tree cannot be uniquely constructed.
D
Depth-first search can be used to find connected components of a graph.
3
GATE CSE 1994
MCQ (Single Correct Answer)
+2
-0.6
The recurrence relation that arises in relation with the complexity of binary search is:
A
$$T(n) = 2T\left(\frac{n}{2}\right)+k, \text{ k is a constant }$$
B
$$T(n) = T\left(\frac{n}{2}\right)+k, \text{ k is a constant }$$
C
$$T(n) = T\left(\frac{n}{2}\right)+\log n$$
D
$$T(n) = T\left(\frac{n}{2}\right)+n$$
4
GATE CSE 1994
MCQ (Single Correct Answer)
+1
-0.3
Generation of intermediate code based on an abstract machine model is useful in compilers because
A
it makes implementation of lexical analysis and syntax analysis easier
B
syntax-directed translations can be written for intermediate code generation
C
it enhances the portability of the front end of the compiler
D
it is not possible to generate code for real machines directly from high level language programs
EXAM MAP
Medical
NEET
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
CBSE
Class 12