サンプル問題セット(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 手)。「真・偽」は、その行の条件の判定です。
| 手 | 実行した行 | 変わった値 |
|---|---|---|
| 1 | 1行目○prioSched() | |
| 2 | 2行目PrioQueue: prioQueue ← PrioQueue() | prioQueue = "<PrioQueue>" |
| 3 | 3行目prioQueue.enqueue("A", 1) | |
| 4 | 4行目prioQueue.enqueue("B", 2) | |
| 5 | 5行目prioQueue.enqueue("C", 2) | |
| 6 | 6行目prioQueue.enqueue("D", 3) | |
| 7 | 7行目prioQueue.dequeue() /* 戻り値は使用しない */ | |
| 8 | 8行目prioQueue.dequeue() /* 戻り値は使用しない */ | |
| 9 | 9行目prioQueue.enqueue("D", 3) | |
| 10 | 10行目prioQueue.enqueue("B", 2) | |
| 11 | 11行目prioQueue.dequeue() /* 戻り値は使用しない */ | |
| 12 | 12行目prioQueue.dequeue() /* 戻り値は使用しない */ | |
| 13 | 13行目prioQueue.enqueue("C", 2) | |
| 14 | 14行目prioQueue.enqueue("A", 1) | |
| 15 | 15行目while (prioQueue.size() が 0 と等しくない) | 真 |
| 16 | 16行目prioQueue.dequeue() の戻り値を出力 | |
| 17 | 15行目while (prioQueue.size() が 0 と等しくない) | 真 |
| 18 | 16行目prioQueue.dequeue() の戻り値を出力 | |
| 19 | 15行目while (prioQueue.size() が 0 と等しくない) | 真 |
| 20 | 16行目prioQueue.dequeue() の戻り値を出力 | |
| 21 | 15行目while (prioQueue.size() が 0 と等しくない) | 真 |
| 22 | 16行目prioQueue.dequeue() の戻り値を出力 | |
| 23 | 15行目while (prioQueue.size() が 0 と等しくない) | 偽 |
出力:A, C, D, D