FE SUBJECT B
基本情報技術者 科目Bの問題解説
問題
次の深さ優先探索をスタックで実行したとき，戻り値はどれか。
整数型の配列の配列: adj ← {{2,3}, {4}, {4,5}, {6}, {6}, {}}
整数型の配列: stack, order
push(stack, 1)
while (stackが空でない)
v ← pop(stack)
if (visited[v] = false)
visited[v] ← true
append(order, v)
for (adj[v]の各要素 u を先頭から順に取り出す)
if (visited[u] = false)
push(stack, u)
endif
endfor
endif
endwhile
return order[4]- ア 3
- イ 4
- ウ 5
- エ 6
出典：オリジナル問題｜参考範囲：試験要綱Ver.5.5 / FEシラバスVer.9.2 科目B範囲
正解と解説
正解：6
正解：6
スタックは後入れ先出しである。頂点1で2，3の順にpushすると，次にpopされるのは後から入った3である。さらに3から4，5をpushするため，5が先に処理される。
| pop | push後のstack | order |
|---|---|---|
| 1 | {2,3} | {1} |
| 3 | {2,4,5} | {1,3} |
| 5 | {2,4,6} | {1,3,5} |
| 6 | {2,4} | {1,3,5,6} |
4番目にorderへ入る頂点は6。幅優先探索のキュー順と混同しないこと。
選択肢の見分け方：3や5は途中の訪問頂点，4はスタック下に残っている頂点である。隣接頂点をpushした順と，popされる順が逆になることを必ず確認する。
この問題について
公開問題・サンプル問題の形式、擬似言語記法、アルゴリズム読解・トレース・空欄補充・セキュリティ事例判断の傾向を参考にした独自問題です。本文・数値・選択肢は新規作成しています。
公式試験問題、公開問題、市販教材、外部問題サイトの問題文を転載・改題したものではありません。