FUNDAMENTAL INFORMATION TECHNOLOGY ENGINEER
基本情報技術者の問題解説
問題
次の二分木を 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
正解：3
postorderは左，右，根の順である。根1からすぐ訪問しない。
左部分木では4を訪問してから2，右部分木では5を訪問してから3，最後に根1を訪問する。訪問順は4,2,5,3,1なので，4番目は3。
Hardでの確認点：木の走査では，preorder，inorder，postorderのどれかを必ず確認する。postorderでは根を最後に訪問するため，配列上の根番号や見た目の先頭をすぐに答えにしない。
追加の確認：Hard問題では、正解値だけでなく、途中の更新規則を一つずつ確認する。どの条件で変数・添字・候補集合が変わるのかを見落とすと、もっともらしい選択肢に引っかかりやすい。
この問題について
公開問題・サンプル問題の形式、擬似言語記法、アルゴリズム読解・トレース・空欄補充・セキュリティ事例判断の傾向を参考にした独自問題です。本文・数値・選択肢は新規作成しています。
公式試験問題、公開問題、市販教材、外部問題サイトの問題文を転載・改題したものではありません。