# 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

### 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

### 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

### 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

### 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

### 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

### 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 |