優先度付きキューの操作【基本情報技術者試験 科目B サンプル問題】

← 科目Bの公開問題一覧へ戻る

　基本情報技術者試験の科目Bのサンプル問題を題材に，優先度付きキューの操作について学習します。この問題では，優先度に応じて要素を取り出す処理と，同じ優先度の要素を追加した順に取り出す処理を確認します。

（令和4年度12月公開） 基本情報技術者試験 サンプル問題 科目B 問8

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

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

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

〔プログラム〕

○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”

【参考】	「データ構造の基礎まとめ（キューとは）」

この問題のポイント

　この問題から学べることは，

• 優先度付きキューの基本的なしくみ
• enqueue によって要素を優先度付きキューに追加する方法
• dequeue によって優先度の高い要素から取り出す方法
• 同じ優先度の要素を追加した順に取り出す方法
• キューの状態を追跡して，取り出される要素を求める方法

です。特に，優先度は数値が小さいほど高く，同じ優先度の要素は追加した順に取り出されることを理解しておきましょう。

基本情報技術者試験の学習におすすめの参考書

基本情報技術者試験の合格を目指す方におすすめの参考書です。