Consider the following statements: (a) Depth-first search is used to traverse…
2015
Consider the following statements:
(a) Depth-first search is used to traverse a rooted tree
(b) Pre-order, Post-order and Inorder are used to list the vertices of an ordered rooted tree.
(c) Huffman's algorithm is used to find an optimal binary tree with given weights
(d) Topological sorting provides a labelling such that the parents have larger labels than their children
Which one of the above statements is true?
- A.
(a) and (b)
- B.
(c) and (d)
- C.
(a), (b) and (c)
- D.
(a), (b), (c) and (d)
Attempted by 336 students.
Show answer & explanation
Correct answer: D
Answer: All four statements are true.
Statement (a): Depth-first search is used to traverse a rooted tree. Reason: DFS explores as far as possible along each branch before backtracking, and is a standard method for traversing trees.
Statement (b): Pre-order, post-order and inorder are used to list the vertices of an ordered rooted tree. Reason: Pre-order and post-order are general depth-first listings for ordered rooted trees. Inorder is the standard depth-first listing when the tree is an ordered binary tree (left, root, right).
Statement (c): Huffman's algorithm is used to find an optimal binary tree with given weights. Reason: Huffman builds a binary prefix tree that minimizes the total weighted path length for given symbol weights, producing an optimal binary code tree.
Statement (d): Topological sorting provides a labelling such that the parents have larger labels than their children. Reason: A topological order lists each parent before its children. If you assign numeric labels in reverse topological order (for example, assign the largest number to the first vertex in a topological sequence), then every parent receives a larger label than its children.
Therefore the correct choice is the one that includes all four statements.