次のプログラム中の [ ] に入れる正しい答えを，解答群の中から選べ。…
科目B アルゴリズムとプログラミング 科目B 問3
次のプログラム中の [ ] に入れる正しい答えを，解答群の中から選べ。ここで，配列の要素番号は1 から始まる。図1 に示すグラフの頂点には，1 から順に整数で番号が付けられている。グラフは無向グラフであり，各頂点間には高々一つの辺がある。一つの辺は両端の頂点の番号を要素にもつ要素数2 の整数型の 配列で表現できる。例えば，{1，3} は頂点1 と頂点3 を端点とする辺を表す。グラフ全体は，グラフに含まれる辺を表す要素数2 の配列を全て格納した配列（以下，辺の配列という）で表現できる。辺の配列の要素数はグラフの辺の個数と等しい。図1 のグラフは整数型配列の配列{{1, 3}, {1, 4}, {3,4}, {2, 4}, {4, 5}}と表現できる。関数edgesToMatrix は，辺の配列を隣接行列に変換する。隣接行列とは，グラフに含まれる頂点の個数と等しい行数及び列数の正方行列で，i 行j 列の成分は頂点i と頂点j を結ぶ辺があるときに1 となり，それ以外は0 となる。行列の対角成分は全て0 で，無向グラフの場合は対称行列になる。図1 のグラフを表現する隣接行列を図2に示す。関数edgesToMatrix は，引数edgeList で辺の配列を，引数nodeNum でグラフの頂点の個数をそれぞれ受け取り，隣接行列を表す整数型の二次元配列を返す。
参考：擬似言語の記述形式（基本情報技術者試験，応用情報技術者試験用）
問題冊子の末尾に載っている参考のページです。
正答 エ
正答は エ。空欄には、次の 2 行が入ります。
adjMatrix[u, v] ← 1
adjMatrix[v, u] ← 1
辺 {u, v} があるとき、隣接行列では u 行 v 列と v 行 u 列の両方を1 にします。無向グラフでは、頂点 u から v へも、v から u へもつながっているので、行列は対角線に対して対称になります。各辺の 2 頂点 u、v を取り出して、両方の成分を 1 にすれば、図 2 の隣接行列ができます。
【トレース（エを入れ、図 1 の辺の配列、nodeNum＝5）】
解説の続きをみる続きを閉じる
初めは 5 行 5 列の全ての成分が 0
i＝1：{1, 3} → [1, 3] と [3, 1] を 1
i＝2：{1, 4} → [1, 4] と [4, 1] を 1
i＝3：{3, 4} → [3, 4] と [4, 3] を 1
i＝4：{2, 4} → [2, 4] と [4, 2] を 1
i＝5：{4, 5} → [4, 5] と [5, 4] を 1
できた行列の 1 の行は、1 行目が 3・4 列、2 行目が 4 列、3 行目が1・4 列、4 行目が 1・2・3・5 列、5 行目が 4 列で、図 2 と一致します。
【ほかの選択肢】
ア adjMatrix[u, u] ← 1 誤り
イ adjMatrix[u, u] ← 1 と adjMatrix[v, v] ← 1 誤り
カ adjMatrix[v, v] ← 1 誤り
→ どれも対角成分（[1, 1] など）を 1 にしてしまう。
対角成分は全て 0 でなければならず、辺の情報も残らない
ウ adjMatrix[u, v] ← 1 だけ 誤り
→ [1, 3] は 1 になるが [3, 1] は 0 のままで、対称にならない。
例えば 3 行目は 4 列だけが 1 となり、図 2 の 1・4 列と違う
オ adjMatrix[v, u] ← 1 だけ 誤り
→ [3, 1] は 1 になるが [1, 3] は 0 のまま。1 行目が全て 0
になり、図 2 と違う
出典：令和6年度 基本情報技術者試験 科目B 公開問題 問3（独立行政法人情報処理推進機構）出典元ページ
最終更新日
「科目B アルゴリズムとプログラミング」のほかの問題
- 2025年度（令和7年度）公開問題 科目B 問3次のプログラム中の [a] と [b] に入れる正しい答えの組合せを，解答群の中から選べ
- 2025年度（令和7年度）公開問題 科目B 問4次の記述中の [ ] に入れる正しい答えを，解答群の中から選べ。
- 2025年度（令和7年度）公開問題 科目B 問5次の記述中の [a] と [b] に入れる正しい答えの組合せを，解答群の中から選べ。
- 2026年度（令和8年度）公開問題 科目B 問1次のプログラム中の [ ] に入れる正しい答えを，解答群の中から選べ。
- 2026年度（令和8年度）公開問題 科目B 問2次のプログラム中の [ ] に入れる正しい答えを，解答群の中から選べ。
- 2026年度（令和8年度）公開問題 科目B 問3次のプログラム中の [ ] に入れる正しい答えを，解答群の中から選べ。
スポンサーリンク