Data Structure Questions and Answers-Breadth First Search

YOU CAN DOWNLOAD 200+ SUBJECTS PDF BOOK FOR COMPETITIVE EXAMINATIONS

CLICK HERE TO DOWNLOAD

Data Structure Questions and Answers-Breadth First Search

Question 6 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
What can be the applications of Breadth First Search?
A
Finding shortest path between two nodes
B
Finding bipartiteness of a graph
C
GPS navigation system
D
All of the mentioned
Question 6 Explanation: 
Breadth First Search can be applied to all of the mentioned problems. Bipartiteness of a graph means that a graph can be divided into two disjoint sets such that every edge connects a vertex in to one in.

Question 7 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
When the Breadth First Search of a graph is unique?
A
When the graph is a Binary Tree
B
When the graph is a Linked List
C
When the graph is a n-ary Tree
D
None of the mentioned
Question 7 Explanation: 
When Every node will have one successor then the Breadth First Search is unique. In all other cases, when it will have more than one successor, it can choose any of them in arbitrary order.

Question 8 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
Regarding implementation of Breadth First Search using queues, what is the maximum distance between two nodes present in the queue? (considering each edge length 1)
A
Can be anything
B
0
C
At most 1
D
Insufficient Information
Question 8 Explanation: 
In the queue, at a time, only those nodes will be there whose difference among levels is 1. Same as level order traversal of the tree.

Question 9 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
In BFS, how many times a node is visited?
A
Once
B
Twice
C
equivalent to number of indegree of the node
D
None of the mentioned
Question 9 Explanation: 
In Breadth First Search, we have to see whether the node is visited or not by it's ancestor. If it is visited, we won't let it enter it in the queue.

There are 9 questions to complete.