The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+14 votes
1.8k views

Which of the following statements is false?

  1. Optimal binary search tree construction can be performed efficiently using dynamic programming

  2. Breadth-first search cannot be used to find connected components of a graph

  3. Given the prefix and postfix walks over a binary tree, the binary tree cannot be uniquely constructed.

  4. Depth-first search can be used to find connected components of a graph

asked in Algorithms by Veteran (59.6k points)
retagged by | 1.8k views
+3
I think B should be connected components in place of converted components.

5 Answers

+11 votes
Best answer

Answer is $B$.

  1. True.
  2. False.
  3. True.
  4. True.
answered by Boss (34k points)
edited by
+2
Elaborate (a) part..
0
anybody explain A part
0
explain this "Given the prefix and postfix walks over a binary tree, the binary tree cannot be uniquely constructed."
0
Without inorder we can't  construct binary tree.
0
Inorder of a bonarbtree can be obtain from sorted sequence right ? Then why option c is true.
+4 votes

https://gateoverflow.in/113167/ugcnet-dec2016-ii-25 

Refer this link for the explanation 

answered by (323 points)
+3 votes
A- An optimal binary search tree is a binary search tree for which the nodes are arranged on levels such that the tree cost is minimum.

B-B should be answer because we can find BFS only if Connected components

option B
answered by Loyal (6.9k points)
+3 votes
Answer B, We can randomly select a source vertex and run BFS algorithm, after that we need to check each vertex whether it's distance from source is still infinite or not(note: BFS algorithm first initializes each vertex's distance  from source as infinite and source's distance as 0) . If we find any vertex  having infinite distance then the graph is not connected(Assuming the graph is undirected)
answered by Active (1.8k points)
0
For directed graph Dfs is also applied in most cases ...
0
How?
+1 vote

Option B is false. We can use BFS to find connected components.  

https://www.geeksforgeeks.org/connected-components-in-an-undirected-graph/

answered by Active (3.7k points)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

41,063 questions
47,662 answers
147,324 comments
62,381 users