データ構造 (全29問中5問目)

No.5

A,B,Cの順序で入力されるデータがある。各データについてスタックへの挿入と取出しを1回ずつ行うことができる場合,データの出力順序は何通りあるか。
05.gif/image-size:163×109
  • [この問題の出題歴]
  • 応用情報技術者 H24春期 問6
  • ソフトウェア開発技術者 H15春期 問10
  • ソフトウェア開発技術者 H19秋期 問9

分類

テクノロジ系 » アルゴリズムとプログラミング » データ構造

正解

解説

A,B,Cの考えられる出力順序としては6種類があるので、それぞれが出力可能であるかを検証します。

[A→B→C]
push(A)→pop→push(B)→pop→push(C)→pop の順序で出力可能です。
[A→C→B]
push(A)→pop→push(B)→push(C)→pop→pop の順序で出力可能です。
[B→A→C]
push(A)→push(B)→pop→pop→push(C)→pop の順序で出力可能です。
[B→C→A]
push(A)→push(B)→pop→push(C)→pop→pop の順序で出力可能です。
[C→A→B]
push(A)→push(B)→push(C)→pop→pop×
Bより先にAを出力できません。
[C→B→A]
push(A)→push(B)→push(C)→pop→pop→pop の順序で出力可能です。

したがってデータの出力順序は5通りになります。
© 2010-2018 応用情報技術者試験ドットコム All Rights Reserved.

Pagetop