edited by
243 views
0 votes
0 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 of a binary tree, the tree cannot be re-constructed uniquely.
  4. Depth-first-search can be used to find the components of a graph.
edited by

2 Answers

0 votes
0 votes
here only B is wrong.. From direct property
0 votes
0 votes

Major applications of DFS:-

  • To check if the graph is connected. And to find number of connected and/or strongly connected components. Also, to find the number of nodes in a connected component.
  • To check if the graph is cyclic or acyclic.
  • To find cut vertices (articulation points) and cut edges (bridges) — both in $O(E)$ time.
  • Topological sorting.

Major applications of BFS:-

  • To check if the graph is connected. And to find number of connected and/or strongly connected components. Also, to find the number of nodes in a connected component.
  • To check if the graph is cyclic or acyclic.
  • Topological sorting
  • Finding single source shortest path for unweighted (or equally weighted, which we can consider unweighted) graphs. It's like a lightweight version of Dijkstra (which can handle weighted graphs).
  • To check if graph is bipartite. (Option B is FALSE)

Why is Option C true? We need infix and along with that either prefix or postfix will do. But if we don't have infix, we can't uniquely construct a Binary Tree.

edited by
Answer:

Related questions

0 votes
0 votes
1 answer
1
Bikram asked May 26, 2017
463 views
The cost of optimal binary search tree for the identifier set $(a1, a2, a3) =$ (do, if, while) with $p(1) = 0.3, \ p(2) = 0.2, $ $p(3) = 0.15, q (0) = 0.05, q(1) = 0.15...
2 votes
2 votes
2 answers
3
Bikram asked May 26, 2017
341 views
Assume Dijkstra's Algorithm is used to find the shortest paths from node G in the above graph. The total number of edges which are not included in any of the shortest pat...
1 votes
1 votes
2 answers
4
Bikram asked May 26, 2017
454 views
The total number of LCS (Longest Common Subsequences) of $P = abcd123$ and $Q= badc321$ that can be formed are ______.