平成24年度 春期 午前 問6

✓ これが正解ウ5

解説

六通りのうち作れない形が一つで五通りです。

三個のデータを並べる順序は全部で六通りあります。スタックは後から入れたものが先に出るデータ構造ですから、この六通りのうち、その決まりに反する形だけが作れません。試し方は素直です。入力の順番は決まっていますので、各データについて入れる操作と出す操作をどの位置に置くかを、六通りの出力ごとに当てはめます。五つは操作の並べ方が見つかります。作れないのは、最後に入力されたデータを最初に出し、そのあとに最初に入力されたデータを出す形です。最後のデータを先に出すには、その前の二つが下に積まれている必要があり、下に積まれた二つは後から入れたほうが先に出るからです。よって六通りから一つを除いた五通りになります。数え上げるより、作れない形を探して引くほうが速く済みます。

ほかの選択肢はなぜ違うのか

• ア3：三通りしか作れないとすると、半分を除くことになります。実際に操作を当てはめると、入れてすぐ出す形や、二つ入れてから順に出す形など、五つまでは組み立てられます。
• イ4：四通りとするには、組み立てられない形が二つあることになります。実際に除かれるのは、最後に入力されたデータを先に出したあと最初のデータを出す一つだけです。
• エ6：六通りは、三個の並べ方の総数をそのまま答えた形です。後から入れたものが先に出るという制約を数えていませんので、組み立てられない順序が一つ混じっています。