FUNDAMENTAL INFORMATION TECHNOLOGY ENGINEER
基本情報技術者の問題解説：次の二分木を postorder（左、右、根）でたどる。4番…
問題
次の二分木を postorder（左、右、根）でたどる。4番目に訪問する頂点はどれか。
left[1]=2, right[1]=3 left[2]=4, right[2]=0 left[3]=0, right[3]=5 left[4]=0, right[4]=0 left[5]=0, right[5]=0 0は子がないことを表す。
- ア 1
- イ 2
- ウ 3（正解）
- エ 5
出典：オリジナル問題｜参考範囲：試験要綱Ver.5.5 / FEシラバスVer.9.2 科目B範囲
正解と解説
正解：3
postorderは左、右、根の順です。根1からすぐ訪問しません。
左部分木では4を訪問してから2，右部分木では5を訪問してから3，最後に根1を訪問します。訪問順は4,2,5,3,1なので、4番目は3です。
Hardでの確認点：木の走査では、preorder，inorder，postorderのどれかを必ず確認しましょう。postorderでは根を最後に訪問するため、配列上の根番号や見た目の先頭をすぐに答えにしないようにしましょう。
追加の確認：Hard問題では、正解値だけでなく、途中の更新規則を一つずつ確認しましょう。どの条件で変数・添字・候補集合が変わるのかを見落とすと、もっともらしい選択肢に引っかかりやすくなります。
この問題について
公開問題・サンプル問題の形式、擬似言語記法、アルゴリズム読解・トレース・空欄補充・セキュリティ事例判断の傾向を参考にした独自問題です。本文・数値・選択肢は新規作成しています。
公式試験問題、公開問題、市販教材、外部問題サイトの問題文を転載・改題したものではありません。