2014 June UGC NET Paper 1
December 24, 2023Vectors
December 24, 2023Data-Structures
|
Question 10
|
Consider a complete binary tree with 7 nodes, Let A denote the set of first 3 elements obtained by performing Breadth-First Search (BFS) starting from the root. Let B denote the set of first 3 elements obtained by performing Depth-First Search (DFS) starting from the root.
The value of |A – B| is _______.
|
1
|
Question 10 Explanation:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible.
A={0,1,2} → BFS
The BFS traverse through level by level.
DFS:
B={0,1,3}
B={0,1,4}
B={0,2,6}
B={0,2,5}
The DFS starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking.
|A-B| = 1
Note: The cardinality of set A-B is 1.
Correct Answer: A
Question 10 Explanation:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible.
A={0,1,2} → BFS
The BFS traverse through level by level.
DFS:
B={0,1,3}
B={0,1,4}
B={0,2,6}
B={0,2,5}
The DFS starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking.
|A-B| = 1
Note: The cardinality of set A-B is 1.