# Algorithms (GATE (Graduate Aptitude Test in Engineering) 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

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

f Page