3.2k 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

retagged | 3.2k views
+3
I think B should be connected components in place of converted components.
+1

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. for more information click here

Answer is $B$.

1. True.
2. False.
3. True.
4. True.
by Boss
edited
+4
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."
+1
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.
0
@Chintan Patel  That will be in case of binary search tree not in binary tree
0
got it bro tq !!
0

Or refer the same question here: https://gateoverflow.in/113167/ugcnet-dec2016-ii-25

$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 and it can be performed efficiently using Dynamic programming.click here

when $j\geq i$ $\bigg\{E = E[i,r-1] + E[r+1,j] + W(i,j)\bigg\}$

when $j\geq i$ $\Big\{W(i,j) = \Sigma^j_{l=i} p_l + \Sigma^l_{l=i-1} q_l \Big\}$

$B.$ To find Connected components we can start with either BFS or DFS but DFS is preffered over BFS because BFS takes exponential amount of memory whereas DFS takes linear amount of memory

$C.$ Using prefix and postfix the binary tree cannot be uniquely constructed check here

$D.$ It can be used and it consumes linear amount of memory

So $B$ is right answer

by Boss
edited
0

BFS takes exponential amount of memory whereas DFS takes linear amount of memory

How?

0
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)
by Active
–2
For directed graph Dfs is also applied in most cases ...
0
How?

Refer this link for the explanation

by Active
+1 vote

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

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

by Active