IPA FE Subject B sample Question 9
A question IPA Japan published in 基本情報技術者試験 科目B サンプル問題 問9, translated into English. ITPEC is based on the same exams.
From the answer group below, select the correct answer to be inserted into blank in the description. Here, the array index starts at 1.
The procedure order outputs all the node numbers while traversing the subtree of the binary tree in the figure whose root is the node specified by the argument. The global array tree represents the binary tree in the figure. Each element of the array tree is an array that stores the node numbers of the children of the corresponding node, in the order of the left child and then the right child. For example, the element at index 1 of the array tree is an array consisting of the node numbers of the children of node number 1, and it stores node number 2 of the left child and node number 3 of the right child as the array {2, 3}.
When the procedure order is called as order(, the node numbers are output in the order blank.
Figure Binary tree handled by the program
Answer group
Explanation
8, 4, 9, 2, 10, 5, 11, 1, 12, 6, 13, 3, 14, 7 — order outputs a node after its left subtree and before its right subtree: an in-order traversal.
- •Two children: visit the left subtree, output
n, visit the right subtree. - •One child (always the left one, Note 2): visit it, then output
n. - •No children: output
n.
order( first goes down the left edge to leaf 8 and outputs 8, then its parent 4, then 9; then 2, and the subtree of 5 gives 10, 5, 11. After the root 1, the right side follows the same pattern: 12, 6, 13, then 3, then 7's only child 14 before 7 itself.
Answer (c)
Why not others:
- •(a) — lists the nodes level by level (breadth-first), which needs a queue, not this recursion
- •(b) — outputs each node before its children (preorder), as if
output ncame before the first recursive call - •(d) — outputs each node after all its children (postorder), so the root 1 comes last
Key rule: Where the output sits relative to the recursive calls decides the traversal: before both is preorder, between them in-order, after both postorder.
Binary Search Tree · AI-written, may contain errors
This question comes from the past questions IPA Japan publishes, translated into English by ITPEC Practice. ITPEC Practice is an independent study tool and is not affiliated with IPA or ITPEC. See the original paper (PDF) or Report an issue.