FUNDAMENTAL INFORMATION TECHNOLOGY ENGINEER
基本情報技術者の問題解説：次の木構造を再帰的に評価したとき、戻り値はどれか。配列の要素…
問題
次の木構造を再帰的に評価したとき、戻り値はどれか。配列の要素番号は1から始まる。
整数型の配列: value ← {5, 2, 4, 1, 3}
整数型の配列: left ← {2, 4, 0, 0, 0}
整数型の配列: right ← {3, 0, 5, 0, 0}
○整数型: calc(整数型: v)
if (v = 0)
return 0
endif
整数型: s ← calc(left[v]) ＋ value[v]
if (value[v] mod 2 = 0)
s ← s ＋ calc(right[v])
else
s ← s － calc(right[v])
endif
return s
calc(1) を呼び出す。- ア 1（正解）
- イ 3
- ウ 5
- エ 7
出典：オリジナル問題｜参考範囲：試験要綱Ver.5.5 / FEシラバスVer.9.2 科目B範囲
正解と解説
正解：1
calcは左部分木の値に自分のvalueを足した後、自分のvalueが偶数なら右部分木を足し、奇数なら右部分木を引きます。葉から順に戻り値を積み上げます。
| v | 左部分 | 右部分 | calc(v) |
|---|---|---|---|
| 4 | 0 | 0 | 1 |
| 2 | 1 | 0 | 3 |
| 5 | 0 | 0 | 3 |
| 3 | 0 | 3 | 7 |
| 1 | 3 | 7 | 1 |
根1はvalueが5で奇数なので、右部分木7を引き、3+5-7=1となります。
選択肢の見分け方：3や7は部分木だけの値、5は根のvalueだけを見た値です。左右の再帰結果を求めてから、根のvalueの偶奇で右部分木を足すか引くかを決めましょう。
評価の順序に注目：calcは「左部分木→自分のvalue→右部分木」の順で値を確定する深さ優先の再帰です。calc(1)では左の枝2を先に最後までたどって3を得てからvalue[1]=5を足し、最後に右の枝3を評価して7を引きます。先に右や根だけを見て計算すると符号や順序を取り違えるため、葉から戻り値を積み上げる流れを守ることが大切です。
この問題について
公開問題・サンプル問題の形式、擬似言語記法、アルゴリズム読解・トレース・空欄補充・セキュリティ事例判断の傾向を参考にした独自問題です。本文・数値・選択肢は新規作成しています。
公式試験問題、公開問題、市販教材、外部問題サイトの問題文を転載・改題したものではありません。