Data Structure Questions and Answers – Breadth First Search

This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Breadth First Search”.

1. Breadth First Search is equivalent to which of the traversal in the Binary Trees?
a) Pre-order Traversal
b) Post-order Traversal
c) Level-order Traversal
d) In-order Traversal
View Answer

Answer: c
Explanation: The Breadth First Search Algorithm searches the nodes on the basis of level. It takes a node (level 0), explores it’s neighbors (level 1) and so on.

2. Time Complexity of Breadth First Search is? (V – number of vertices, E – number of edges)
a) O(V + E)
b) O(V)
c) O(E)
d) O(V*E)
View Answer

Answer: a
Explanation: The Breadth First Search explores every node once and every edge once (in worst case), so it’s time complexity is O(V + E).

3. The Data structure used in standard implementation of Breadth First Search is?
a) Stack
b) Queue
c) Linked List
d) Tree
View Answer

Answer: b
Explanation: The Breadth First Search explores every node once and put that node in queue and then it takes out nodes from the queue and explores it’s neighbors.

4. The Breadth First Search traversal of a graph will result into?
a) Linked List
b) Tree
c) Graph with back edges
d) Arrays
View Answer

Answer: b
Explanation: The Breadth First Search will make a graph which don’t have back edges (a tree) which is known as Breadth First Tree.

5. A person wants to visit some places. He starts from a vertex and then wants to visit every place connected to this vertex and so on. What algorithm he should use?
a) Depth First Search
b) Breadth First Search
c) Trim’s algorithm
d) Kruskal’s algorithm
View Answer

Answer: b
Explanation: This is the definition of the Breadth First Search. Exploring a node, then it’s neighbors and so on.
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

6. Which of the following is not an application of Breadth First Search?
a) Finding shortest path between two nodes
b) Finding bipartiteness of a graph
c) GPS navigation system
d) Path Finding
View Answer

Answer: d
Explanation: Breadth First Search can be applied to Bipartite a graph, to find the shortest path between two nodes, in GPS Navigation. In Path finding, Depth First Search is used.

7. 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) When the graph is a Ternary Tree
View Answer

Answer: b
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.

8. 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
View Answer

Answer: c
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.

9. In BFS, how many times a node is visited?
a) Once
b) Twice
c) Equivalent to number of indegree of the node
d) Thrice
View Answer

Answer: c
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.

Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.

To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]

Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.