HOME»サンプル問題»[科目B]問8

サンプル問題 [科目B]問8

問8

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

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

 手続 prioSched を呼び出したとき,出力は の順となる。
b08_1.png/image-size:514×402
〔プログラム〕
b08_2.png/image-size:337×334
  • "A","B","C","D"
  • "A","B","D","D"
  • "A","C","C","D"
  • "A","C","D","D"

分類

アルゴリズムとプログラミング » データ構造及びアルゴリズム

正解

解説

enqueue(エンキュー)はキューの最後尾に要素を追加する操作、dequeue(デキュー)はキューから要素を取り出す操作です。dequeueでは、キューの中で最も優先度の高い(優先度 prio が小さい)要素を取り出し、同じ優先度の要素が複数ある場合には、より先に追加された要素が取り出すとあります。

この操作を踏まえて、プログラムの処理をトレースしていきます。以下の解説中の[ ]はキューの中身だと考えてください(左がキューの先頭)。
enqueue("A", 1)
[("A", 1)]
enqueue("B", 2)
[("A", 1), ("B", 2)]
enqueue("C", 2)
[("A", 1), ("B", 2), ("C", 2)]
enqueue("D", 3)
[("A", 1), ("B", 2), ("C", 2), ("D", 3)]
dequeue()
最も優先度の高い"A"を取り出す
[("B", 2), ("C", 2), ("D", 3)]
dequeue()
"B"と"C"で優先度が同じなので、先に追加された"B"を取り出す
[("C", 2), ("D", 3)]
enqueue("D", 3)
[("C", 2), ("D", 3), ("D", 3)]
enqueue("B", 2)
[("C", 2), ("D", 3), ("D", 3), ("B", 2)]
dequeue()
"C"と"B"で優先度が同じなので、先に追加された"Cを取り出す
[("D", 3), ("D", 3), ("B", 2)]
dequeue()
最も優先度の高い"B"を取り出す
[("D", 3), ("D", 3)]
enqueue("C", 2)
[("D", 3), ("D", 3), ("C", 2)]
enqueue("A", 1)
[("D", 3), ("D", 3), ("C", 2), ("A", 1)]
出力する前のキューの中身は上記のとおりです。この状態からdequeueを4回繰り返すと、優先度の高い順に"A"⇒"C"⇒"D"⇒"D"と出力されます。したがって「エ」が正解です。
© 2010-2024 基本情報技術者試験ドットコム All Rights Reserved.

Pagetop