edited by
3,936 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 reconstructed uniquely.
  4. Depth-first-search can be used to find the connected components of a graph.                                                                         
edited by

4 Answers

12 votes
12 votes

Answer: B

(a) True. ref:http://www.geeksforgeeks.org/dynamic-programming-set-24-optimal-binary-search-tree/
(b) False. ref: https://www.quora.com/Why-is-DFS-preferred-for-finding-connected-components-in-directed-graphs

BFS and DFS both algorithm are used to find connected component. For example: In BFS, a search that begins at some particular vertex 'v' will find the entire connected component containing v (and no more) before returning. To find all the connected components of a graph, loop through its vertices, starting a new breadth first  search whenever the loop reaches a vertex that has not already been included in a previously found connected component. For example:If we do the breadth first traversal of the above graph and print the visited node as the output, it will print the following output. “A B C D E F”. The BFS visits the nodes level by level, so it will start with level 0 which is the root node, and then it moves to the next levels which are B, C and D, then the last levels which are E and F.       

               In BFS, a search that begins at some particular vertex v will find the entire connected component containing v (and no more) before returning. To find all the connected components of a graph, loop through its vertices, starting a new breadth first  search whenever the loop reaches a vertex that has not already been included in a previously found connected component.  

Tree


(c) True. because: inorder is needed
(d) True. ref: https://www.quora.com/Why-is-DFS-preferred-for-finding-connected-components-in-directed-graphs

1 votes
1 votes

For connected components we are using Depth first search but not breadth first search.
A connected component (or just component) of an undirected graph is a sub graph in which any two vertices are connected to each other by
paths, and which is connected to no additional vertices in the super graph.
1. Kosaraju's algorithm for strongly connected components.
2. Tarjan's Algorithm to find strongly Connected Components Time complexity for both algorithms are O(V+E).

1 votes
1 votes
1) Optimal binary tree can be efficiently constructed using dynamic programming.

2) Breadth-first search and Depth-first search both can be used to find the connected components in a graph.

3) To construct a tree uniquely one of the following combinations should be present:

     i) infix and prefix   or,

     ii) infix and postfix.

with prefix and postfix tree can be constructed but not uniquely.

so, option b is false.
reshown by
0 votes
0 votes
Answer:

Related questions

0 votes
0 votes
4 answers
3
go_editor asked Mar 24, 2020
989 views
Match the following :$\begin{array}{llll} & \textbf{List – I} & {} & \textbf{List – II} \\ \text{a.} & \text{Absurd} & \text{i.} & \text{Clearly impossible being con...