ITパスポート|アルゴリズムとプログラミング 問15
下から上へデータを積み上げ、上にあるデータから順に取り出すデータ構造(以下、スタックという)がある。これを用いて、右側から入力されたデータの順番を変化させて、左側に出力する装置を考える。この装置に対する操作は次の3通りである。
- ①
- 右側から入力されたデータをそのまま左側に出力する。
- ②
- 右側から入力されたデータをスタックに積み上げる。
- ③
- スタックの1番上にあるデータを取り出して左側に出力する。
この装置の右側から順番に X、Y、Z を入力した場合に、この①~③の操作を組み合わせても、左側に出力できない順番はどれか。
正解:ウ
解説
Z を最初に出すには、X と Y をスタックに積む必要があり、上から Y、X の順になります。そのあと X を Y より先に取り出すことはできません。
- ア X を出し、Y を積み、Z を出し、Y を取り出せます。
- イ X を積み、Y、Z を出し、X を取り出せます。
- ウ 正解。出力できません。
- エ X、Y を積み、Z を出し、Y、X の順に取り出せます。
もう一歩深く
ウの Z、X、Y を作るには、まず X と Y をスタックに積み、Z をそのまま出します。次に X を出したいのですが、スタックの一番上は Y なので、X を先に取り出すことはできません。アは X をそのまま出し、Y を積み、Z を出してから Y を取り出せば作れます。イとエも作れるので、作れないのはウだけです。
出典:平成22年度春期 ITパスポート試験 公開問題 問85(読点「,」を「、」に改変)