Data Structure Questions and Answers-Non-recursive Depth First Search

Click on any option to know the CORRECT ANSWERS

 Question 1
Which of the following data structure is used to implement DFS?
 A linked list B tree C stack D queue

Question 1 Explanation:
Stack is used in the standard implementation of depth first search. It is used to store the elements which are to be explored.

 Question 2
Which of the following traversal in a binary tree is similar to depth first traversal?
 A level order B post order C pre order D in order

Question 2 Explanation:
In DFS we keep on exploring as far as possible along each branch before backtracking. It terminates when all nodes are visited. So it is similar to pre order traversal in binary tree.

 Question 3
What will be the result of depth first traversal in the following tree?
 A 4 2 5 1 3 B 1 2 4 5 3 C 4 5 2 3 1 D 1 2 3 4 5

Question 3 Explanation:
Depth first search is similar to pre order traversal in a tree. So here we will get the same result as for the pre order traversal (root, left right).

 Question 4
Which of the following is a possible result of depth first traversal of the given graph(consider 1 to be source element)?
 A 1 2 3 4 5 B 1 2 3 1 4 5 C 1 4 5 3 2 D 1 4 5 1 2 3

Question 4 Explanation:
As 1 is the source element so it will be considered first. Then we start exploring the vertices which are connected to 1. So there will be two possible results-1 2 3 4 5 and 1 4 5 2 3.

 Question 5
Which of the following represent the correct pseudo code for non recursive DFS algorithm?
 A procedure DFS-non....recursive(G, v): //let St be a stack St.push(v) while St is not empty v = St.pop() if v is not discovered: label v as discovered for all adjacent vertices of v do St.push(a)  B procedure DFS-non....recursive(G, v): //let St be a stack St.pop() while St is not empty v = St.push(v) if v is not discovered: label v as discovered for all adjacent vertices of v do St.push(a) / C procedure DFS-non....recursive(G, v): //let St be a stack St.push(v) while St is not empty v = St.pop() if v is not discovered: label v as discovered for all adjacent vertices of v do St.push(v) D procedure DFS-non....recursive(G, v): //let St be a stack St.pop(v) while St is not empty v = St.pop() if v is not discovered: label v as discovered for all adjacent vertices of v do St.push(a) //