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