基本情報技術者試験 過去問解説
再帰とは？基本情報技術者試験 平成31年度 春期 午前 問6を解説
基本情報技術者試験 平成31年度 春期 午前 問6は、再帰に関する理解を問う問題です。検索から入っても、問題文、選択肢、正解、解説、各選択肢がなぜ違うかをこのページだけで確認できます。
問題文
三つのスタック A, B, C のいずれの初期状態も [1, 2, 3] であるとき，再帰的に定義された関数 f() を呼び出して終了した後の B の状態はどれか。ここで，スタックが [a1, a2, …, an-1] の状態のときに an を push した後のスタックの状態は [a1, a2, …, an-1, an] で表す。 f(){ A が空ならば{ 何もしない。 } そうでない場合{ A から pop した値を C に push する。 f() を呼び出す。 C から pop した値を B に push する。 } }
この問題の出題ポイント
- 再帰の定義だけでなく、問題文中の条件がどの選択肢に当てはまるかを確認する。
- データ構造分野では、用語の目的・主体・責任範囲の違いが選択肢で問われやすい。
- 関連タグ: 再帰、数学。
選択肢
- ア[1, 2, 3, 1, 2, 3]正解
- イ[1, 2, 3, 3, 2, 1]
- ウ[3, 2, 1, 1, 2, 3]
- エ[3, 2, 1, 3, 2, 1]
正解
ア: [1, 2, 3, 1, 2, 3]
解説
f() は再帰呼び出しで A→C→B のデータ転送を行う。初期 A=[1,2,3] から: pop 3→push C、再帰、pop 2→push C、再帰、pop 1→push C、再帰でA空でreturn、C[1,2,3,3,2,1] から pop 1→B、戻って pop 2→B、戻って pop 3→B。B は元の [1,2,3] に 1,2,3 を順に追加して [1,2,3,1,2,3]。アが正解。
なぜ他の選択肢が違うのか
ア（正解）
B の初期 [1,2,3] に、A から経由されて取り出された 1,2,3 が順に追加される。正解。
イ
[1,2,3,3,2,1] は C から逆順に取り出されるイメージだが、実際の手順とは異なる。
ウ
[3,2,1,1,2,3] は B の初期状態を逆順にした想定だが、B は変更されない部分が先頭に残る。
エ
[3,2,1,3,2,1] は両端を逆順にした誤った想定。
解き方の整理
再帰の問題では、選択肢のキーワードだけで判断せず、問題文が示す条件と正解選択肢の説明が一致しているかを見ます。誤答選択肢は、似た用語を混ぜる、主体を入れ替える、目的や範囲を広げすぎる、という形で作られることが多いため、選択肢別解説まで確認しておくと復習効率が上がります。
関連問題
前後の問題
平成31年度 春期 午前 の関連する問題
復習を続ける
間違えた問題、苦手タグ、模試履歴を保存して復習する導線を用意しています。広告なしPro、弱点分析、復習リマインダーは段階的に提供予定です。