平成31年度 春期 午前 問6
データ構造
スタックに関する問題
三つのスタック A，B，C のいずれの初期状態も [1, 2, 3] であるとき，再帰的に定義された関数 f( ) を呼び出して終了した後の B の状態はどれか。ここで，スタックが [a₁, a₂, …, aₙ₋₁] の状態のときに aₙ を push した後のスタックの状態は [a₁, a₂, …, aₙ₋₁, aₙ] で表す。
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]
解説
取り出した順が二度ひっくり返り、元の並びが後ろに付きます。
再帰の追跡は、呼び出しの前と後で何をするかを分けて見ます。この関数は、呼ぶ前に一つ移し、呼んだ後にもう一つ移します。まず A から順に取り出して C へ積みます。A の上から三、二、一と取り出されるので、C にはその順で積まれます。A が空になると、そこで呼び出しが止まります。ここから戻りながら、C から取り出して B へ積みます。C の上には最後に積んだ一があるので、まず一が B へ移ります。次に二、最後に三と続きます。つまり B には一、二、三の順で足されます。B は最初から一、二、三が入っていたので、その後ろに付く形になります。取り出しで一度ひっくり返り、積み直しでもう一度戻るのが要点です。二度ひっくり返れば元の順に戻る、と押さえると迷いません。途中の C は、最後に元の中身へ戻ります。
ほかの選択肢はなぜ違うのか
- イ[1, 2, 3, 3, 2, 1]：後ろ半分が三、二、一の順になっています。ひっくり返りが一度だけ起きたときの並びです。呼び出しの後の積み直しを数えていません。C を経由する分を落とすと、この形になります。積み直しは戻りの途中で起きます。呼び出しの後の行を見ます。
- ウ[3, 2, 1, 1, 2, 3]：前半が三、二、一になっています。B の初めの中身は問題文で与えられており、変わりません。元から入っていた分に手は加わりません。足されるのは後ろだけです。初期状態は問題文が与えています。勝手に並べ替わりません。
- エ[3, 2, 1, 3, 2, 1]：前半も後半もひっくり返っています。初めの中身と、足される分の両方を取り違えた形です。二か所が違うので、正しい並びから最も離れています。どちらか一方でも確かめれば除けます。二か所とも取り違えています。初期状態と足す分の両方を見ます。
出典：平成31年度 春期 基本情報技術者試験 午前 問6
この解説に誤りを見つけたら教えてください。直して、直した記録を残します。誤りを報告する（メールが開きます）