Algorithms (GATE Computer Science): Questions 46 - 51 of 98

Get 1 year subscription: Access detailed explanations (illustrated with images and videos) to 913 questions. Access all new questions we will add tracking exam-pattern and syllabus changes. View Sample Explanation or View Features.

Rs. 450.00 or

Question number: 46

» Algorithms » Basic Concepts of Complexity Classes P, NP, NP-Hard, NP-Complete

MCQ▾

Question

The problems 3-SAT and 2-SAT are

Choices

Choice (4) Response
a.

complete

b.

in P

c.

NP-complete and in P respectively

d. Question does not provide sufficient data or is vague

Question number: 47

» Algorithms » Dynamic Programming

MCQ▾

Question

Spanning tree is defines only for a ________

Choices

Choice (4) Response
a.

The optimal substructure property

b.

A divide-and-conquer approach

c.

Tables

d.

Hill climbing

Question number: 48

» Algorithms » Dynamic Programming

MCQ▾

Question

Which of the following algorithm is used finding all pairs of shortest distance in the graph?

Choices

Choice (4) Response
a.

algorithm

b.

Dijkstra algorithm

c.

Foly Warshall algorithm

d. Question does not provide sufficient data or is vague

Question number: 49

» Algorithms » Tree and Graph Traversals

MCQ▾

Question

The recurrence relation capturing the optimal execution time of the Towers of Hanoi problem with n discs is

Choices

Choice (4) Response
a.

T (n) =2T (n1) +1

b.

T (n) =2T (n1) / 1

c.

T (n) =2T (n1) - 2

d. All of the above

Question number: 50

» Algorithms » Tree and Graph Traversals

MCQ▾

Question

If any undirected graph, the sum of degrees of all the nodes

Choices

Choice (4) Response
a.

Need not be even

b.

Must be odd

c.

Is twice the number of edge?

d. Question does not provide sufficient data or is vague

Question number: 51

» Algorithms » Tree and Graph Traversals

MCQ▾

Question

When converting binary tree into extended binary tree, all the original nodes in binary tree are

Choices

Choice (4) Response
a.

internal nodes on extended tree

b.

external nodes on extended tree

c.

vanished on extended tree

d. None of the above

Sign In