GATE CSE 2020 | GATE CSE Year Wise Previous Years Questions

GATE CSE 2020

MCQ (Single Correct Answer)

-0.67

Let G = (V, E) be a directed, weighted graph with weight function w: E $$ \to $$ R. For some function f: V $$ \to $$ R, for each edge (u, v) $$ \in $$ E, define w'(u, v) as w(u, v) + f(u) - f(v).

Which one of the options completes the following sentence so that it is TRUE?
“The shortest paths in G under w are shortest paths under w’ too, _______”.

for every f : V $$ \to $$ R

if and only if $$\forall u \in V$$, f(u) is positive

if and only if $$\forall u \in V$$, f(u) is negative

f and only if f(u) is the distance from s to u in the graph obtained by adding a new vertex s to G and edges of zero weight from s to every vertex of G

GATE CSE 2020

Numerical

-0

Consider the array representation of a binary min-heap containing 1023 elements. The minimum number of comparisons required to find the maximum in the heap is _______.

Your input ____

GATE CSE 2020

MCQ (Single Correct Answer)

-0.33

What is the worst case time complexity of inserting n² elements into an AVL-tree with n elements initially?

$$\Theta \left( {{n^2}} \right)$$

$$\Theta \left( {{n^2}\log n} \right)$$

$$\Theta \left( {{n^4}} \right)$$

$$\Theta \left( {{n^3}} \right)$$

GATE CSE 2020

MCQ (Single Correct Answer)

-0.33

The preorder traversal of a binary search tree is 15, 10, 12, 11, 20, 18, 16, 19. Which one of the following is the postorder traversal of the tree?

20, 19, 18, 16, 15, 12, 11, 10

10, 11, 12, 15, 16, 18, 19, 20

11, 12, 10, 16, 19, 18, 20, 15

19, 16, 18, 20, 11, 12, 10, 15

PREVIOUS NEXT

GATE CSE Papers

2024