FUNDAMENTAL INFORMATION TECHNOLOGY ENGINEER
基本情報技術者の問題解説
問題
次の深さ優先探索を実行したとき，戻り値はどれか。
整数型の二次元配列: g ← {{0,1,1,0,0}, {0,0,0,1,0}, {0,0,0,1,1}, {0,0,0,0,0}, {0,1,0,0,0}}
整数型: sum ← 0
○手続: dfs(整数型: v)
visited[v] ← true
sum ← sum ＋ v
for (u を 1 から 5 まで 1ずつ増やす)
if (g[v][u] = 1 and visited[u] = false)
dfs(u)
endif
endfor
dfs(1) を呼び出す。
return sum- ア 10
- イ 12
- ウ 15
- エ 18
出典：オリジナル問題｜参考範囲：試験要綱Ver.5.5 / FEシラバスVer.9.2 科目B範囲
正解と解説
正解：15
正解：15
dfsでは頂点番号の小さいuから順に調べる。1から2へ進み，2から4へ進む。4からは進めないので戻り，次に1から3へ進む。3から4は訪問済みなので飛ばし，5へ進む。
| 訪問順 | sum |
|---|---|
| 1 | 1 |
| 1,2 | 3 |
| 1,2,4 | 7 |
| 1,2,4,3 | 10 |
| 1,2,4,3,5 | 15 |
すべての到達頂点1〜5を一度ずつ足すので15。5から2への辺はあるが，2は訪問済みのため再帰しない。
選択肢の見分け方：10は5を訪問し忘れた値，12や18は訪問済み頂点を再度足した場合に出やすい。visitedにより，各頂点はsumへ一度だけ加算される。
この問題について
公開問題・サンプル問題の形式、擬似言語記法、アルゴリズム読解・トレース・空欄補充・セキュリティ事例判断の傾向を参考にした独自問題です。本文・数値・選択肢は新規作成しています。
公式試験問題、公開問題、市販教材、外部問題サイトの問題文を転載・改題したものではありません。