GATE CSE 2020 Paper 1 — page 17

Questions 49–51 of 65. Imported answers require review unless explicitly marked reviewed.

Which one of the following predicate formulae is NOT logically valid? Note that

is a predicate formula without any free occurrence of

Your answerChoose one option.

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Let

be a directed, weighted graph with weight function

. For some function

, for each edge

, define

. Which one of the options completes the following sentence so that it is TRUE? “The shortest paths in

under

are shortest paths under

too, ________.”

Your answerChoose one option.

for every

if and only if

is positive

if and only if

is negative

if and only if

is the distance from

in the graph obtained by adding a new vertex

and edges of zero weight from

to every vertex of $G

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

In a balanced binary search tree with

elements, what is the worst case time complexity of reporting all elements in range

? Assume that the number of reported elements is

Your answerChoose one option.

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

2020 · Paper 1