FE SUBJECT B
基本情報技術者 科目Bの問題解説
問題
次の有向非循環グラフを，入次数0の頂点を小さい番号から取り出す方法でトポロジカルソートする。4番目に出力される頂点はどれか。
辺: 1→3, 2→3, 2→4, 3→5, 4→5 入次数0の頂点を候補に入れる。複数ある場合は小さい番号を先に取り出す。
- ア 2
- イ 3
- ウ 4
- エ 5
出典：オリジナル問題｜参考範囲：試験要綱Ver.5.5 / FEシラバスVer.9.2 科目B範囲
正解と解説
正解：4
正解：4
初期の入次数0は1と2なので，1，2の順に出力する。2を出すと3と4の入次数が0になる。
候補が複数あるときは小さい番号を先に取り出すため，3を先に出力し，次に4を出力する。出力順は1,2,3,4,5なので，4番目は4。
Hardでの確認点：トポロジカルソートは，頂点を出すたびに隣接先の入次数を減らす。候補が複数ある場合の取り出し規則が答えに影響するので，「小さい番号から」などの条件を必ず使う。
追加の確認：Hard問題では、正解値だけでなく、途中の更新規則を一つずつ確認する。どの条件で変数・添字・候補集合が変わるのかを見落とすと、もっともらしい選択肢に引っかかりやすい。
この問題について
公開問題・サンプル問題の形式、擬似言語記法、アルゴリズム読解・トレース・空欄補充・セキュリティ事例判断の傾向を参考にした独自問題です。本文・数値・選択肢は新規作成しています。
公式試験問題、公開問題、市販教材、外部問題サイトの問題文を転載・改題したものではありません。