基本情報技術者試験「グラフ」の問題
6 個のノード（番号 1〜6）からなる有向グラフを次の辺リストで与える（u → v は u から v への辺）。
1→2, 1→3, 2→4, 3→4, 2→5, 4→6
出次数（そのノードから出ていく辺の本数）が 0 のノード、すなわち他のどのノードへも辺を持たない終端ノードの個数を求める。次の擬似言語を実行したとき返り値 sinks はどれか。
○関数: countSinks(): 整数型
整数型の配列: outdeg ← {0, 0, 0, 0, 0, 0}
各辺 u→v について
outdeg[u] ← outdeg[u] + 1
整数型: i, sinks ← 0
for (i を 1 から 6 まで 1 ずつ増やす)
if (outdeg[i] = 0)
sinks ← sinks + 1
endif
endfor
return sinksア4 個
イ1 個
ウ2 個
エ3 個
正解
ウ．2 個
辺の始点 u を数えると出次数は 1→2本, 2→2本, 3→1本, 4→1本, 5→0本, 6→0本。outdeg={2,2,1,1,0,0} のうち 0 はノード5 とノード6 の 2 個なので sinks=2、すなわち ウが正しい。
?選択肢ごとの解説
ア ×4 個は出次数が 0 でないノードまで数え込んだ過大計上であり、終端の判定を誤った結果である。
イ ×1 個はノード5・6 のどちらか一方だけを数え、もう一方を見落とした計上漏れの誤りである。
ウ ○辺の始点 u を数えると出次数は 1→2本, 2→2本, 3→1本, 4→1本, 5→0本, 6→0本。outdeg={2,2,1,1,0,0} のうち 0 はノード5 とノード6 の 2 個なので sinks=2、すなわち ウが正しい。
エ ×3 個は出次数 1 のノード（3 や 4）を終端に含めてしまうなど、0 以外を数えた誤りである。
✎くわしく
出次数は『辺の始点 u』を数えることで求まる。出次数 0 のノードはグラフの終端（シンク）であり、処理の最終段やこれ以上たどれない地点を表す。入次数とは数える側が逆である点に注意する。
✓本番での押さえどころ
試験のコツ
出次数は矢印の『元』の本数。各ノードから出る矢を数え、本数が 0 のノードだけを数え上げる。
覚え方
『出口のないノードが終端』と覚える。
よくある誤り
始点と終点を取り違えて入次数を数える、0 以外のノードも終端に含めてしまうミスが多い。
アルゴリズムとプログラミングの他の問題
次の擬似言語で表される手続 sumOdd を、引数として要素数 5 の整数型の配列 {12, 125, 1008,…次の擬似言語は、整数型の配列 arr に対して隣接交換を行う手続の一部であり、外側ループの 1 回目（1…次の擬似言語は昇順に整列された配列 arr に対する二分探索の手続である。arr = {2, 4, 6, 8, 10,…次の擬似言語で表される再帰手続 f を、引数 n = 20 で呼び出したとき、戻り値として返される値はどれか。
```…単方向連結リストの各ノードはメンバ val（整数）と next（次ノードへの参照。なければ NULL）をもつ。先頭ノード…スタックに対する push（積む）と…
この問題を、AIの8-ways解説つきで。
無料ではじめる →基本情報技術者試験の演習を、一問ごとに「なぜ」まで。まずは無料で。
ukamiru 過去問 · 基本情報技術者試験 · fe-b-algo-0155