基本情報技術者試験「グラフ」の問題
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 個とした、走査範囲を後半に限定した誤りである。
✎くわしく
無向グラフでは『隣接ノード数＝次数』であり、隣接行列の該当行の 1 を数えれば求まる。行を 1 列目から 6 列目まで漏れなく走査することが必要である。
✓本番での押さえどころ
試験のコツ
該当行を抜き出し、1 だけにマークしてから数えると数え漏れを防げる。
覚え方
『隣接ノード数＝その行の 1 の数』と覚える。
よくある誤り
行の先頭列や末尾列を数え漏らす、または 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-0150