The travelling salesman problem can be solved using _________(a) A spanning tree(b) A minimum spanning tree(c) Bellman – Ford algorithm(d) DFS traversalI have been asked this question in class test.The query is from Minimum Spanning Tree topic in division Minimum Spanning Tree of Data Structures & Algorithms II

The travelling salesman problem can be solved using _________(a) A spa

1.	The travelling salesman problem can be solved using _________(a) A spanning tree(b) A minimum spanning tree(c) Bellman – Ford algorithm(d) DFS traversalI have been asked this question in class test.The query is from Minimum Spanning Tree topic in division Minimum Spanning Tree of Data Structures & Algorithms II
Answer» The correct choice is (b) A minimum spanning TREE To explain: In the travelling salesman problem we have to find the shortest possible ROUTE that visits every CITY exactly once and returns to the starting point for the given a set of cities. So, travelling salesman problem can be solved by CONTRACTING the minimum spanning tree.

Discussion

No Comment Found

Related InterviewSolutions

Which of the following is false about Prim’s algorithm?(a) It is a greedy algorithm(b) It constructs MST by selecting edges in increasing order of their weights(c) It never accepts cycles in the MST(d) It can be implemented using the Fibonacci heapThe question was posed to me in an interview for internship.I want to ask this question from Minimum Spanning Tree in chapter Minimum Spanning Tree of Data Structures & Algorithms II
Prim’s algorithm can be efficiently implemented using _____ for graphs with greater density.(a) d-ary heap(b) linear search(c) fibonacci heap(d) binary searchThis question was posed to me during an online exam.Query is from Minimum Spanning Tree topic in chapter Minimum Spanning Tree of Data Structures & Algorithms II
Prim’s algorithm is also known as __________(a) Dijkstra–Scholten algorithm(b) Borůvka’s algorithm(c) Floyd–Warshall algorithm(d) DJP AlgorithmThe question was posed to me during an interview for a job.My doubt stems from Minimum Spanning Tree in division Minimum Spanning Tree of Data Structures & Algorithms II
Kruskal’s algorithm is best suited for the sparse graphs than the prim’s algorithm.(a) True(b) FalseThe question was posed to me at a job interview.Asked question is from Minimum Spanning Tree topic in portion Minimum Spanning Tree of Data Structures & Algorithms II
Prim’s algorithm resemblesDijkstra’s algorithm.(a) True(b) FalseI had been asked this question in quiz.Question is from Minimum Spanning Tree in division Minimum Spanning Tree of Data Structures & Algorithms II
Prim’s algorithm is a ______(a) Divide and conquer algorithm(b) Greedy algorithm(c) Dynamic Programming(d) Approximation algorithmI got this question in class test.My question is taken from Minimum Spanning Tree in chapter Minimum Spanning Tree of Data Structures & Algorithms II
Worst case is the worst case time complexity of Prim’s algorithm if adjacency matrix is used?(a) O(log V)(b) O(V^2)(c) O(E^2)(d) O(V log E)I had been asked this question during an interview.Query is from Minimum Spanning Tree topic in portion Minimum Spanning Tree of Data Structures & Algorithms II
Which of the following is true?(a) Prim’s algorithm initialises with a vertex(b) Prim’s algorithm initialises with a edge(c) Prim’s algorithm initialises with a vertex which has smallest edge(d) Prim’s algorithm initialises with a forestThis question was addressed to me in examination.Origin of the question is Minimum Spanning Tree in division Minimum Spanning Tree of Data Structures & Algorithms II
Kruskal’s algorithm is best suited for the dense graphs than the prim’s algorithm.(a) True(b) FalseI have been asked this question by my college professor while I was bunking the class.Question is from Minimum Spanning Tree in section Minimum Spanning Tree of Data Structures & Algorithms II
Which of the following is false about the Kruskal’s algorithm?(a) It is a greedy algorithm(b) It constructs MST by selecting edges in increasing order of their weights(c) It can accept cycles in the MST(d) It uses union-find data structureThe question was posed to me in unit test.Question is from Minimum Spanning Tree topic in division Minimum Spanning Tree of Data Structures & Algorithms II

Discussion

No Comment Found

Related InterviewSolutions

Reply to Comment