FE SUBJECT B
基本情報技術者 科目Bの問題解説：次の手続 degree2() を実行したときの戻り値はどれか…
問題
次の手続 degree2() を実行したときの戻り値はどれか。
○整数型: degree2()
整数型の二次元配列: m[1..5, 1..5] ← すべて0
辺 (1,2), (1,4), (2,3), (2,4), (3,5) を順に読む
m[u, v] ← 1
m[v, u] ← 1
end
return m[2,1] ＋ m[2,2] ＋ m[2,3] ＋ m[2,4] ＋ m[2,5]- ア 2
- イ 3（正解）
- ウ 4
- エ 5
出典：オリジナル問題｜参考範囲：試験要綱Ver.5.5 / FEシラバスVer.9.2 科目B範囲
正解と解説
正解：3
無向グラフなので、辺 (u,v) を読むたびに m[u,v] と m[v,u] の両方を1にします。戻り値は隣接行列の2行目の合計なので、頂点2に隣接する頂点数を表します。
頂点2につながる辺は (1,2), (2,3), (2,4) の3本です。したがって m[2,1], m[2,3], m[2,4] が1になり、合計は3になります。頂点2自身を表す m[2,2] は0です。
| 列 | m[2,列] | 理由 |
|---|---|---|
| 1 | 1 | 辺(1,2) |
| 2 | 0 | 自己ループなし |
| 3 | 1 | 辺(2,3) |
| 4 | 1 | 辺(2,4) |
| 5 | 0 | 辺なし |
関連用語との違い：隣接行列の各行の合計はその頂点の次数を表すため、戻り値3は頂点2の次数そのものです。無向グラフでは m[u,v]＝m[v,u] となり行列は対角線について対称になりますが、有向グラフなら向きごとに片方だけ1になり対称になりません。対角成分 m[2,2] は自己ループがある場合だけ1になります。
この問題について
公開問題・サンプル問題の形式、擬似言語記法、アルゴリズム読解・トレース・空欄補充・セキュリティ事例判断の傾向を参考にした独自問題です。本文・数値・選択肢は新規作成しています。
公式試験問題、公開問題、市販教材、外部問題サイトの問題文を転載・改題したものではありません。