サンプル問題[科目B]問8 優先度付きキューを操作するプログラム

サンプル問題 [科目B]問8

問8

　次の記述中の　に入れる正しい答えを，解答群の中から選べ。

　優先度付きキューを操作するプログラムである。優先度付きキューとは扱う要素に優先度を付けたキューであり，要素を取り出す際には優先度の高いものから順番に取り出される。クラス PrioQueue は優先度付きキューを表すクラスである。クラス PrioQueue の説明を図に示す。ここで，優先度は整数型の値1，2，3のいずれかであり，小さい値ほど優先度が高いものとする。

　手続 prioSched を呼び出したとき，出力は　の順となる。

〔プログラム〕

"A"，"B"，"C"，"D"
"A"，"B"，"D"，"D"
"A"，"C"，"C"，"D"
"A"，"C"，"D"，"D"

分類

アルゴリズムとプログラミング » データ構造及びアルゴリズム

正解

エ

解説

enqueue(エンキュー)はキューの最後尾に要素を追加する操作、dequeue(デキュー)はキューから要素を取り出す操作です。dequeueでは、キューの中で最も優先度の高い（優先度 prio が小さい）要素を取り出し、同じ優先度の要素が複数ある場合には、より先に追加された要素が取り出すとあります。

この操作を踏まえて、プログラムの処理をトレースしていきます。以下の解説中の[ ]はキューの中身だと考えてください（左がキューの先頭）。

enqueue("A", 1): [("A", 1)]
enqueue("B", 2): [("A", 1), ("B", 2)]
enqueue("C", 2): [("A", 1), ("B", 2), ("C", 2)]
enqueue("D", 3): [("A", 1), ("B", 2), ("C", 2), ("D", 3)]
dequeue(): 最も優先度の高い"A"を取り出す
[("B", 2), ("C", 2), ("D", 3)]
dequeue(): "B"と"C"で優先度が同じなので、先に追加された"B"を取り出す
[("C", 2), ("D", 3)]
enqueue("D", 3): [("C", 2), ("D", 3), ("D", 3)]
enqueue("B", 2): [("C", 2), ("D", 3), ("D", 3), ("B", 2)]
dequeue(): "C"と"B"で優先度が同じなので、先に追加された"Cを取り出す
[("D", 3), ("D", 3), ("B", 2)]
dequeue(): 最も優先度の高い"B"を取り出す
[("D", 3), ("D", 3)]
enqueue("C", 2): [("D", 3), ("D", 3), ("C", 2)]
enqueue("A", 1): [("D", 3), ("D", 3), ("C", 2), ("A", 1)]

出力する前のキューの中身は上記のとおりです。この状態からdequeueを4回繰り返すと、優先度の高い順に"A"⇒"C"⇒"D"⇒"D"と出力されます。したがって「エ」が正解です。