recategorized by
9,866 views
36 votes
36 votes

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

recategorized by

5 Answers

Best answer
22 votes
22 votes

The answer is B.

  1. True.
  2. False.
  3. True.
  4. True.
edited by
26 votes
26 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 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

edited by
9 votes
9 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)
Answer:

Related questions