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 exampattern and syllabus changes. View Sample Explanation or View Features.
Rs. 450.00 or
Question number: 46
» Algorithms » Basic Concepts of Complexity Classes P, NP, NPHard, NPComplete
Question
The problems 3SAT and 2SAT are
Choices
Choice (4)  Response  

a.  complete 

b.  in P 

c.  NPcomplete 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 divideandconquer 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 
