平成30年度 春期 午前 問5
データ構造
スタック操作を行った結果
次の二つのスタック操作を定義する。
PUSH n: スタックにデータ(整数値 n)をプッシュする。 POP: スタックからデータをポップする。
空のスタックに対して,次の順序でスタック操作を行った結果はどれか。
PUSH 1 → PUSH 5 → POP → PUSH 7 → PUSH 6 → PUSH 4 → POP → POP → PUSH 3
選択肢ア〜エは原典ではスタックの図(上から下へ3段の箱)。箱の中身を上から順に書き写した。
- ア上から 1,7,3
- イ上から 3,4,6
- ウ上から 3,7,1
- エ上から 6,4,3
答えと解説を見る
✓ これが正解ウ上から 3,7,1
解説
取り出しは後入れ先出しなので、上から3・7・1です。
スタックは、最後に積んだものから先に取り出す入れ物です。1を積み、5を積むと、上にあるのは5でした。ここで取り出すと5が消え、1だけが残ります。次に7、6、4と積むので、底から数えて1、7、6、4の並びになりました。続けて取り出しを2回行うと、上にあった4と6が順に消えます。残ったのは1と7で、上にあるのは7でした。最後に3を積むので、上から3、7、1となります。だから、その並びを挙げた肢が当たりました。上から1、7、3とする肢は、同じ中身を底のほうから書き並べています。上から3、4、6とする肢は、4を積んだ後の取り出し2回を反映していません。上から6、4、3とする肢は、その取り出しを行わないまま、さらに上下を逆に書いた形でした。積む順と取り出す順を、紙の上で一段ずつ並べ直すのが確実です。
ほかの選択肢はなぜ違うのか
- ア上から 1,7,3:上から1、7、3としています。残っている三つの値そのものは合っているのに、並べる向きが逆でした。いちばん最後に積んだ3が上に来ます。底に置かれるのは、最初に積んで一度も取り出されなかった1でした。書き出す向きだけが違っています。
- イ上から 3,4,6:上から3、4、6としています。4を積んだところまでは同じ形でした。そこから取り出しが2回あるのに、その操作が反映されていません。消えるはずの4と6が残ったままです。取り出しを飛ばすと、ちょうどこの並びが出てきます。
- エ上から 6,4,3:上から6、4、3としています。取り出しを飛ばしたうえに、書く向きまで逆になっていました。最後に積んだ3が底に置かれています。二つの取り違えが重なった形です。向きを直しても、まだ余分な二つが残ったままでした。
出典:平成30年度 春期 基本情報技術者試験 午前 問5
この解説に誤りを見つけたら教えてください。直して、直した記録を残します。誤りを報告する(メールが開きます)