FUNDAMENTAL INFORMATION TECHNOLOGY ENGINEER
基本情報技術者の問題解説
問題
次のトポロジカルソートを実行したとき，戻り値はどれか。
整数型の配列の配列: edge ← {{3}, {3,4}, {5}, {5}, {6}, {}}
整数型の配列: indeg ← {0, 0, 2, 1, 2, 1}
整数型の配列: q, order
enqueue(q, 1)
enqueue(q, 2)
while (qが空でない)
v ← dequeue(q)
append(order, v)
for (edge[v]の各要素 u を先頭から順に取り出す)
indeg[u] ← indeg[u] - 1
if (indeg[u] = 0)
enqueue(q, u)
endif
endfor
endwhile
return order[4]- ア 3
- イ 4
- ウ 5
- エ 6
出典：オリジナル問題｜参考範囲：試験要綱Ver.5.5 / FEシラバスVer.9.2 科目B範囲
正解と解説
正解：4
正解：4
入次数が0の頂点1,2からキューに入る。1を処理しても3の入次数はまだ1残る。2を処理すると3と4の入次数が0になり，この順にキューへ入る。
| 取り出し | 新たに追加 | order |
|---|---|---|
| 1 | なし | {1} |
| 2 | 3,4 | {1,2} |
| 3 | なし | {1,2,3} |
| 4 | 5 | {1,2,3,4} |
したがってorder[4]は4。辺を消した後の入次数更新を順に追う必要がある。
選択肢の見分け方：3は3番目，5は4の処理後に入る頂点，6はさらに後の頂点である。入次数が0になった瞬間にキューへ入る順番を追う。
この問題について
公開問題・サンプル問題の形式、擬似言語記法、アルゴリズム読解・トレース・空欄補充・セキュリティ事例判断の傾向を参考にした独自問題です。本文・数値・選択肢は新規作成しています。
公式試験問題、公開問題、市販教材、外部問題サイトの問題文を転載・改題したものではありません。