基本情報技術者 予想問題｜A 第18問

解説

深さ優先探索（DFS）は、根から出発して一つの枝を行き止まり（葉）まで深く辿り、それ以上進めなくなったら直前の分岐点まで戻って（バックトラック）別の枝を探索する方式であり、イが正解である。後から訪れたノードを先に処理する性質から、スタックまたは再帰呼出しで実装される。アの「近い階層のノードから順に訪問する」は幅優先探索（BFS）の説明であり、BFSは根に近い順に階層単位で探索し、キューで実装される点でDFSと対をなす。ウのランダムな探索やエの葉から根へ向かう訪問は、いずれも探索アルゴリズムの定義として誤りである。基本情報技術者試験では、DFS＝スタック（再帰）、BFS＝キューという実装データ構造の対応と、二分木の巡回順序（先行順・中間順・後行順）が頻出ポイントである。