The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+8 votes
1.6k 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 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
  1. 1
  2. 2
  3. 3
  4. 4
asked in Others by Veteran (369k points) | 1.6k views
+1

This should be merged with:

https://gateoverflow.in/2465/gate1994-1-22

1 Answer

+11 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

answered by Active (3.9k points)
0
But for binary tree in order is always sorted sequence then why we can't create from pre and post order ??
0

@chintain Patel . Only binary search tree inorder is always a sorted sequence.

0

adeebafatima1  thank you actually its kind of tricky way to ask.. tq...next time i willbe careful!!

Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

44,264 questions
49,758 answers
164,194 comments
65,849 users