うごく基本情報

サンプル問題セット(2022年12月公開) 科目B 問8

キュー ・ クラスの利用 ・ トレース

次の記述中の[ ]に入れる正しい答えを,解答群の中から選べ。
優先度付きキューを操作するプログラムである。優先度付きキューとは扱う要素に優先度を付けたキューであり,要素を取り出す際には優先度の高いものから順番に取り出される。クラス PrioQueue は優先度付きキューを表すクラスである。クラス PrioQueue の説明を図に示す。ここで,優先度は整数型の値 1,2,3 のいずれかであり,小さい値ほど優先度が高いものとする。
手続 prioSched を呼び出したとき,出力は[ ]の順となる。
コンストラクタ説明PrioQueue() 空の優先度付きキューを生成する。
メソッド戻り値説明enqueue(文字列型: s,整数型: prio)なし優先度付きキューに,文字列 s を要素として,優先度 prio で追加する。
dequeue() 文字列型優先度付きキューからキュー内で最も優先度の高い要素を取り出して返す。最も優先度の高い要素が複数あるときは,そのうちの最初に追加された要素を一つ取り出して返す。
size() 整数型優先度付きキューに格納されている要素の個数を返す。
図クラス PrioQueue の説明

○prioSched()
  PrioQueue: prioQueue ← PrioQueue()
  prioQueue.enqueue("A", 1)
  prioQueue.enqueue("B", 2)
  prioQueue.enqueue("C", 2)
  prioQueue.enqueue("D", 3)
  prioQueue.dequeue()  /* 戻り値は使用しない */
  prioQueue.dequeue()  /* 戻り値は使用しない */
  prioQueue.enqueue("D", 3)
  prioQueue.enqueue("B", 2)
  prioQueue.dequeue()  /* 戻り値は使用しない */
  prioQueue.dequeue()  /* 戻り値は使用しない */
  prioQueue.enqueue("C", 2)
  prioQueue.enqueue("A", 1)
  while (prioQueue.size() が 0 と等しくない)
    prioQueue.dequeue() の戻り値を出力
  endwhile
答え
アA,B,C,D
イA,B,D,D
ウA,C,C,D
エA,C,D,D

出典:基本情報技術者試験 科目B試験 サンプル問題セット(2022年12月公開) 問8

正解と解説を見る

正解:エ

ポイント:優先度付きキュー:優先度の高い(数が小さい)ものから取り出す。同じ優先度なら先に入れたもの(先入れ先出し)から。

PrioQueue は、優先度の値が小さいほど優先度が高く、同じ優先度なら先に入れたものから取り出します。キューの中身を順に追います。
1. A(1), B(2), C(2), D(3) を入れる
2. dequeue を2回 → A、次に B が取り出される。残り:C(2), D(3)
3. D(3), B(2) を入れる。中身:C(2), D(3), D(3), B(2)
4. dequeue を2回 → C(優先度2で先に入った)、次に B。残り:D(3), D(3)
5. C(2), A(1) を入れる。中身:D(3), D(3), C(2), A(1)
6. 空になるまで取り出して出力 → A, C, D, D
よって(エ)。
よくある間違い:手順4で、後から入れた B を C より先に取り出してしまう。同じ優先度 2 なら先に入っていた C が先です。

解説と下の表はこのサイトが作成したものです(表は、正解の選択肢を入れたプログラムを実際に実行した結果です)。

正解のプログラムを動かしてみる

prioSched() を呼び出したときに、1行ずつ何が起きるかの表です(全部で 23 手)。「真・偽」は、その行の条件の判定です。

手実行した行変わった値
11行目○prioSched()
22行目PrioQueue: prioQueue ← PrioQueue()prioQueue = "<PrioQueue>"
33行目prioQueue.enqueue("A", 1)
44行目prioQueue.enqueue("B", 2)
55行目prioQueue.enqueue("C", 2)
66行目prioQueue.enqueue("D", 3)
77行目prioQueue.dequeue() /* 戻り値は使用しない */
88行目prioQueue.dequeue() /* 戻り値は使用しない */
99行目prioQueue.enqueue("D", 3)
1010行目prioQueue.enqueue("B", 2)
1111行目prioQueue.dequeue() /* 戻り値は使用しない */
1212行目prioQueue.dequeue() /* 戻り値は使用しない */
1313行目prioQueue.enqueue("C", 2)
1414行目prioQueue.enqueue("A", 1)
1515行目while (prioQueue.size() が 0 と等しくない)真
1616行目prioQueue.dequeue() の戻り値を出力
1715行目while (prioQueue.size() が 0 と等しくない)真
1816行目prioQueue.dequeue() の戻り値を出力
1915行目while (prioQueue.size() が 0 と等しくない)真
2016行目prioQueue.dequeue() の戻り値を出力
2115行目while (prioQueue.size() が 0 と等しくない)真
2216行目prioQueue.dequeue() の戻り値を出力
2315行目while (prioQueue.size() が 0 と等しくない)偽

出力:A, C, D, D

サイトで、1行ずつ予想しながら動かす →