アルゴリズムとプログラミング
基本情報技術者試験 科目A免除 修了試験 20260614 実施分 問6
図の木構造において，木の根の左の葉から行きがけ順深さ優先によって探索した場合，●の葉は何番目に探索されるか。ここで，木の根の探索は0番目とする。
根（○）の子は左から3ノード X1，X2，X3。
X1 の子は2ノード：左は葉，右のノードは子として葉を2つもつ。
X2 の子は3ノード：左のノードは子として葉を1つもつ，中央は葉，右のノードは子として2つの子（左が●の葉，右が○の葉）をもつ。
X3 の子は2ノード：左のノードは子として葉を2つもつ，右のノードは子として葉を1つもつ。
（●は X2 の右の子の左の子である葉。それ以外は全て○）
- ア 9
- イ 10
- ウ 11
- エ 12
出典：基本情報技術者試験 科目A免除 修了試験 20260614 実施分 問6
答えと解説を見る
正解：ウ
覚える知識
木の行きがけ順(先行順)探索の番号計算
行きがけ順深さ優先探索は、節点に到達した時点で訪問し、その後左の子から順に子孫を巡る。
この問題で必要なこと
行きがけ順は節点を訪れた時点で番号を付け、左の子から順に深さ優先で進む。根を0として数えると●は11番目。
ひっかけ
帰りがけ順や幅優先と混同して数える、または根を1番目と数えるとずれる。
この知識の出題：本試験系 0 回・免除試験 1 回（公開問題での観測値）