Which of the following statements is false? (A) Optimal binary search tree construction can be performed efficiently using dynamic programming.
Which of the following statements is false?
(A) Optimal binary search tree construction can be performed efficiently using dynamic programming.
(B) Breadth-first search cannot be used to find connected components of a graph.
(C) Given the prefix and postfix walks of a binary tree, the tree cannot be re-constructed uniquely.
(D) Depth-first-search can be used to find the connected components of a graph.
Show answerHide answer
Correct answer: (B) B
Explanation
Statement B is false: breadth-first search can be used to find the connected components of a graph, just like depth-first search. Optimal binary search tree construction is a well-known dynamic programming application, and given only the prefix and postfix walks of a binary tree, the tree cannot be reconstructed uniquely.