GATE CSE 1994 | GATE CSE Year Wise Previous Years Questions

PREVIOUS NEXT

GATE CSE 1994

MCQ (Single Correct Answer)

-0.6

Which one of the following statements is false?

Optimal binary search tree construction can be performed efficiently using dynamic programming.

Breadth-first search cannot be used to find connected components of a graph

Given the prefix and postfix walks over a binary tree, the binary tree cannot be uniquely constructed.

Depth-first search can be used to find connected components of a graph.

GATE CSE 1994

MCQ (Single Correct Answer)

-0.6

The recurrence relation that arises in relation with the complexity of binary search is:

$$T(n) = 2T\left(\frac{n}{2}\right)+k, \text{ k is a constant }$$

$$T(n) = T\left(\frac{n}{2}\right)+k, \text{ k is a constant }$$

$$T(n) = T\left(\frac{n}{2}\right)+\log n$$

$$T(n) = T\left(\frac{n}{2}\right)+n$$

GATE CSE 1994

MCQ (Single Correct Answer)

-0.3

Generation of intermediate code based on an abstract machine model is useful in compilers because

it makes implementation of lexical analysis and syntax analysis easier

syntax-directed translations can be written for intermediate code generation

it enhances the portability of the front end of the compiler

it is not possible to generate code for real machines directly from high level language programs

GATE CSE 1994

MCQ (Single Correct Answer)

-0.6

In a compact single dimensional array representation for lower triangular matrices (i.e all the elements above the diagonal are zero) of size n $$\times$$ n, non-zero elements (i.e., elements of the lower triangle) of each row are stored one after another, starting from the first row, the index of the (i, j)^th element of the lower triangular matrix in this new representation is

i + j

i + j - 1

$$(j - 1) + i{{(i - 1)} \over 2}$$

$$i + {{j(j - 1)} \over 2}$$

PREVIOUS NEXT

GATE CSE Papers

2023