問題プレビューID: 6390acbc基本情報技術者試験 2023年(令和5年度)サンプル問題 科目B

問 8
基本情報技術者試験 2023年(令和5年度)サンプル問題 科目B

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

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

〔クラス PrioQueue の説明〕

コンストラクタ説明
PrioQueue()空の優先度付きキューを生成する。
メソッド戻り値説明
enqueue(文字列型: s, 整数型: prio)なし優先度付きキューに,文字列 s を要素として,優先度 prio で追加する。
dequeue()文字列型優先度付きキューからキュー内で最も優先度の高い要素を取り出して返す。最も優先度の高い要素が複数あるときは,そのうちの最初に追加された要素を一つ取り出して返す。
size()整数型優先度付きキューに格納されている要素の個数を返す。

〔プログラム〕

○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

解答群

解説

正解は「エ」です。 「優先度」と「最初に追加された要素が優先される(同じ優先度の場合)」というルールに従ってキューの状態を追います。

  1. enqueue(A:1, B:2, C:2, D:3) → 状態: [A(1), B(2), C(2), D(3)]
  2. dequeue() → 最優先の A を取り出す。残: [B(2), C(2), D(3)]
  3. dequeue() → 優先度 2 のうち先に入った B を取り出す。残: [C(2), D(3)]
  4. enqueue(D:3, B:2) → 状態: [B(2), C(2), D(3), D(3)] ※B(2)はD(3)より優先される。
  5. dequeue() → 現時点の優先度 2 の先頭 B を取り出す。残: [C(2), D(3), D(3)]
  6. dequeue() → 残った優先度 2 の C を取り出す。残: [D(3), D(3)]
  7. enqueue(C:2, A:1) → 状態: [A(1), C(2), D(3), D(3)]
  8. 最後の while ループによる出力:
    • dequeue() → A (1)
    • dequeue() → C (2)
    • dequeue() → D (3)
    • dequeue() → D (3)

結果は A, C, D, D となります。

関連問題

本文が同じ・似ている問題を表示しています