アルゴリズムとプログラミング
基本情報技術者試験｜6 個のノード 1〜6 から成る無向グラフを隣接行列 M で表す（M[i][j]=1 で辺あり、添字は 1…
6 個のノード 1〜6 から成る無向グラフを隣接行列 M で表す（M[i][j]=1 で辺あり、添字は 1 から、自己ループなし）。
M[1] = {0,1,1,0,1,0}
M[2] = {1,0,0,1,0,0}
M[3] = {1,0,0,1,1,1}
M[4] = {0,1,1,0,0,0}
M[5] = {1,0,1,0,0,1}
M[6] = {0,0,1,0,1,0}
次の手続 neighbors は、ノード v に隣接するノード（直接辺で結ばれたノード）の個数を返す。neighbors(M, 3) を実行したとき、戻り値はどれか。
○整数型: neighbors(整数型の二次元配列: M, 整数型: v)
整数型: c ← 0
整数型: j
for (j を 1 から 6 まで 1 ずつ増やす)
if (M[v][j] が 1 と等しい)
c ← c + 1
endif
endfor
return cア3 個
イ隣接 4 個
ウ全 6 個
エ2 個だけ
正解
イ．隣接 4 個
隣接ノード数は行 M[v] の 1 の個数に等しい。M[3]={1,0,0,1,1,1} には 1 が列 1,4,5,6 の 4 か所あり、c=4 となるため イが正しい。
?選択肢ごとの解説
ア ×列 1 を見落とし列 4,5,6 だけを数えて 3 個とした、走査開始位置を取り違えた過少カウントである。
イ ○隣接ノード数は行 M[v] の 1 の個数に等しい。M[3]={1,0,0,1,1,1} には 1 が列 1,4,5,6 の 4 か所あり、c=4 となるため イが正しい。
ウ ×ノード総数 6 をそのまま隣接数とした、0 の列も含めて全列を数えた誤りである。
エ ×列 5,6 だけを数えて 2 個とした、走査範囲を後半に限定した誤りである。
アルゴリズムとプログラミングの他の問題
5 個のノード 1〜5 から成る無向グラフを隣接行列 M で表す（M[i][j]=1 で辺あり、添字は 1…無向グラフを次の辺リストで与える（u — v は u と v を結ぶ辺）。
1—2, 1—3, 2—4, 3—4,…無向グラフを次の辺リストで与える（u — v は u と v を結ぶ辺）。
1—2, 2—3, 4—5
次の手続…有向グラフを次の辺リストで与える（u → v は u から v への辺）。
1→3, 2→3, 4→3, 2→5, 4→5…6 個のノード（番号 1〜6）からなる有向グラフを次の辺リストで与える（u → v は u から v への辺）。
1→2,…4 個のノード 1〜4 から成る有向グラフを隣接行列 M で表す。M[i][j]=1 ならノード i から j…頂点数nのグラフを隣接行列で表現したとき、必要な記憶領域の大きさのオーダはどれか。5 個のノード 1〜5 から成る無向グラフを、隣接行列 M で表す。M[i][j] が 1 ならノード i と j…
この問題の「深掘り・誤答の完全解説・覚え方」は、登録すると読めます。
基本情報技術者試験は全4,036問。公開しているのはその一部で、登録すると残りも一問ごとにAI解説つきで解けます。SRS暗記カード・全真模試・弱点診断まで。
登録は1分・クレジットカード不要。無料のまま練習・暗記カード・模試まで使えます。
作成・校閲：ukamiru編集部 · 基本情報技術者試験 過去問 · fe-b-algo-0150