基本情報の午後試験はプログラム問題です.
科目B問題を解けるようになるにはプログラムを元に自分でコードを書いてみるのが1番良いでしょう.
今回は科目B問8「優先度付きキューを操作するプログラム」の解説とそのコードを紹介します.
プログラムを元にPythonで書き直しました.
Pythonで書いてみたので是非手元で実行してみてください
サンプル問題 科目B 問8「優先度付きキューを操作するプログラム」
問題文は以下のとおりです.
キューに関する問題ですね.


Pythonでプログラムを書く
プログラムをPythonで書き換えました.
import queue
class PrioQueue:
def __init__(self):
self.queue = queue.PriorityQueue()
# 優先度を指定して要素を追加する
def enqueue(self, item: str, priority: int):
self.queue.put((priority, item))
# 優先度付きキューからキュー内で最も優先度の高い要素を取り出して返す
# 最も優先度の高い要素が複数あるときは,そのうち最初に追加された要素を1つ取り出して返す
def dequeue(self):
if self != None:
return self.queue.get()[1]
# 優先度付きキューに格納されている要素の個数を返す
def size(self):
return self.queue.qsize()
# インスタンスを作成する
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):
print(prioQueue.dequeue())

プログラムを実行した結果「A, C, D, D」と表示されました.
この問題の答えは「エ」なので実行結果と一致していますね.
プログラムに誤りはなさそうです.
ポイントを確認します.
ポイント 優先度が高い順に取り出される
キューは先に入れたデータが先に取り出される(先入れ先出し)データ構造です.
問題ではまず「A(1)→B(2)→C(2)→D(3)」の順でデータを入れています.
優先度は小さいほど高いことを意味しているので,「A→B→C→D」の順で取り出されそうですね.

「A→B→C→D」の順で表示されました.
今回はたまたま優先度が影響しなかったため入れた順で取り出されましたね.
問題では「B」まで取り出した後に新しいデータ「D」と「B」を追加しました.
ここで2つ取り出してみましょう.

「B」と「C」が表示されました.
先に入れた「C」や「D」よりも「B」が先に取り出されたのは「B」の方が優先度が高いためです.

キューの中には「D(3)」「D(3)」「C(2)」「A(1)」が残りました.
ここでも優先度順に取り出されるので「A, C, D, D」となります.
まとめ
今回は科目B問8「優先度付きキューを操作するプログラム」について紹介しました.
キューは先入れ先出しのデータ構造です.
通常であれば先に入れたデータから取り出されるでしょう.
しかし,この問題では先入れ先出しに加えて優先度が関係していました.
優先度が高い(数値が低い)順にデータが取り出されます.
そのため入れた順番と取り出した順番が変わっていましたね.
処理過程に詰まったときは書き出してみましょう!