アルゴリズムとプログラミング
基本情報技術者試験｜6 個のノード（番号 1〜6）からなる有向グラフを次の辺リストで与える（u → v は u から v…
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 以外を数えた誤りである。
アルゴリズムとプログラミングの他の問題
4 個のノード 1〜4 から成る有向グラフを隣接行列 M で表す。M[i][j]=1 ならノード i から j…頂点数nのグラフを隣接行列で表現したとき、必要な記憶領域の大きさのオーダはどれか。5 個のノード 1〜5 から成る無向グラフを、隣接行列 M で表す。M[i][j] が 1 ならノード i と j…有向グラフを次の辺リストで与える（u → v は u から v への辺を表す）。
1→2, 1→4, 2→3, 2→5,…有向グラフを次の辺リストで与える（u → v は u から v への辺を表す）。
1→2, 1→4, 2→3, 4→5,…閉路のない有向グラフ（DAG）を次の辺リストで与える（u → v は u から v への辺）。
1→2, 1→3,…有向グラフを次の辺リストで与える（u → v は u から v への辺）。
1→2, 1→3, 2→4, 5→1
次の手続…6 個のノード 1〜6 から成る無向グラフを隣接行列 M で表す（M[i][j]=1 で辺あり、添字は 1…
この問題の「深掘り・誤答の完全解説・覚え方」は、登録すると読めます。
基本情報技術者試験は全4,036問。公開しているのはその一部で、登録すると残りも一問ごとにAI解説つきで解けます。SRS暗記カード・全真模試・弱点診断まで。
登録は1分・クレジットカード不要。無料のまま練習・暗記カード・模試まで使えます。
作成・校閲：ukamiru編集部 · 基本情報技術者試験 過去問 · fe-b-algo-0155