Which of the following is false?(a) The spanning trees do not have any cycles(b) MST have n – 1 edges if the graph has n edges(c) Edge e belonging to a cut of the graph if has the weight smaller than any other edge in the same cut, then the edge e is present in all the MSTs of the graph(d) Removing one edge from the spanning tree will not make the graph disconnectedThe question was posed to me in exam.My question is based upon Minimum Spanning Tree topic in division Minimum Spanning Tree of Data Structures & Algorithms II

Which of the following is false?(a) The spanning trees do not have any

1.	Which of the following is false?(a) The spanning trees do not have any cycles(b) MST have n – 1 edges if the graph has n edges(c) Edge e belonging to a cut of the graph if has the weight smaller than any other edge in the same cut, then the edge e is present in all the MSTs of the graph(d) Removing one edge from the spanning tree will not make the graph disconnectedThe question was posed to me in exam.My question is based upon Minimum Spanning Tree topic in division Minimum Spanning Tree of Data Structures & Algorithms II
Answer» Correct answer is (d) Removing one edge from the spanning tree will not make the graph disconnected The best EXPLANATION: Every spanning tree has n – 1 EDGES if the graph has n edges and has no cycles. The MST follows the cut PROPERTY, Edge e BELONGING to a cut of the graph if has the weight smaller than any other edge in the same cut, then the edge e is present in all the MSTS of the graph.

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