The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+14 votes
2k 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 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

asked in Algorithms by Veteran (59.7k points)
retagged by | 2k views
+3
I think B should be connected components in place of converted components.

5 Answers

+11 votes
Best answer

Answer is $B$.

  1. True.
  2. False.
  3. True.
  4. True.
answered by Boss (34.1k points)
edited by
+4
Elaborate (a) part..
0
anybody explain A part
0
explain this "Given the prefix and postfix walks over a binary tree, the binary tree cannot be uniquely constructed."
+1
Without inorder we can't  construct binary tree.
0
Inorder of a bonarbtree can be obtain from sorted sequence right ? Then why option c is true.
0
@Chintan Patel  That will be in case of binary search tree not in binary tree
0
got it bro tq !!
+5 votes

https://gateoverflow.in/113167/ugcnet-dec2016-ii-25 

Refer this link for the explanation 

answered by (447 points)
+4 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)
answered by Active (2.2k points)
0
For directed graph Dfs is also applied in most cases ...
0
How?
+3 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.

B-B should be answer because we can find BFS only if Connected components

option B
answered by Loyal (7.5k points)
+1 vote

Option B is false. We can use BFS to find connected components.  

https://www.geeksforgeeks.org/connected-components-in-an-undirected-graph/

answered by Active (3.9k points)
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,458 questions
49,916 answers
165,411 comments
65,897 users