FE SUBJECT B
基本情報技術者 科目Bの問題解説
問題
次の手続 bfsOrder() を実行したときの戻り値はどれか。
○整数型: bfsOrder()
グラフの辺: (1,2), (1,3), (2,5), (3,4), (3,6), (4,5), (5,6)
dist[1] ← 0, dist[2]〜dist[6] ← -1
整数型: order ← 0
キュー q ← 空
enqueue(q, 1)
while (qが空でない)
v ← dequeue(q)
order ← order ＋ 1
if (v = 5)
return order × 10 ＋ dist[v]
endif
vに隣接する各頂点 u について番号の小さい順に調べる
if (dist[u] = -1)
dist[u] ← dist[v] ＋ 1
enqueue(q, u)
endif
endfor
endwhile
return 0- ア 32
- イ 42
- ウ 52
- エ 23
出典：オリジナル問題｜参考範囲：試験要綱Ver.5.5 / FEシラバスVer.9.2 科目B範囲
正解と解説
正解：42
正解：42
BFSは1を取り出して order=1、2と3を入れる。次に2を取り出して order=2、5を入れる。次に3を取り出して order=3、4と6を入れる。次に5を取り出すので order=4、dist[5]=2。戻り値は4×10+2=42。
32は3番目に5を取り出すと誤った場合、52は距離と取り出し順をずらした場合に出やすい。23は dist[5] だけを先に見て order を無視している。
BFSでは発見順と取り出し順が一致しない場合がある。enqueueした時点ではなく、dequeueしてorderを増やす時点を追う。
この問題について
公開問題・サンプル問題の形式、擬似言語記法、アルゴリズム読解・トレース・空欄補充・セキュリティ事例判断の傾向を参考にした独自問題です。本文・数値・選択肢は新規作成しています。
公式試験問題、公開問題、市販教材、外部問題サイトの問題文を転載・改題したものではありません。