FE SUBJECT B
基本情報技術者 科目Bの問題解説：次の手続 bfsScore() を実行したときの戻り値はどれ…
問題
次の手続 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
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 が入った頂点は再更新しない点も重要です。
このアルゴリズムの正体：これは重みのない有向グラフで始点1からの最短経路長を求める幅優先探索です。全ての辺の重みが等しいため、キューで先に到達した順がそのまま最短距離になります。重みが異なる場合はこの方法では正しくならず、ダイクストラ法などが必要になる点が両者の違いです。計算量は頂点数V・辺数Eに対してO(V+E)で、各頂点・各辺を一度ずつ調べます。
この問題について
公開問題・サンプル問題の形式、擬似言語記法、アルゴリズム読解・トレース・空欄補充・セキュリティ事例判断の傾向を参考にした独自問題です。本文・数値・選択肢は新規作成しています。
公式試験問題、公開問題、市販教材、外部問題サイトの問題文を転載・改題したものではありません。