基本情報技術者試験「木構造」の問題
次の 2 分木がある。各ノードは値・左の子・右の子をもつ（子がなければ空）。
根=A、A の左の子=B、A の右の子=C、B の左の子=D、C の左の子=E、C の右の子=F、E の左の子=G（D・F・G の子はすべて空、B の右の子は空、E の右の子は空）。
次の擬似言語は木の高さを、根から最も遠い葉までに含まれる節点の数として返す（空の木は 0）。この木の根 A に対して実行したとき、戻り値はどれか。
○整数型: height(ノード: n)
if (n が 空)
return 0
endif
整数型: hl ← height(n.左)
整数型: hr ← height(n.右)
if (hl > hr)
return hl + 1
else
return hr + 1
endifウ4節点
ア3段
イ7（全ノード数）
エ14
正解
ウ．4節点
height は左右の高さの大きい方に 1 を足して返す。最長経路 A→C→E→G は 4 節点で、これが最大となるため戻り値は 4 となり ウが正しい。
?選択肢ごとの解説
ウ ○height は左右の高さの大きい方に 1 を足して返す。最長経路 A→C→E→G は 4 節点で、これが最大となるため戻り値は 4 となり ウが正しい。
ア ×A→B→D の経路（3 節点）だけを見て 3 段とした、より深い右側 A→C→E→G を見落とした誤りである。
イ ×木全体の節点数 7 を高さと取り違えた、高さと総ノード数を混同した誤りである。
エ ×節点ラベルや無関係な数値に引きずられて 14 とした、定義から外れた過大評価である。
✎くわしく
木の高さは『根から最も遠い葉までの節点数（または辺数）』で定義され、左右部分木の高さの最大値に親 1 を加えて求める。最長経路がどの枝にあるかを見極めることが核心である。
✓本番での押さえどころ
試験のコツ
各葉までの節点数を枝ごとに数え、その最大値を高さとする。
覚え方
『高さ＝いちばん深い葉までの段数』と覚え、最長の枝を探す。
よくある誤り
高さを総ノード数と混同したり、より浅い枝だけを見て最長経路を取り違えるミスが多い。
アルゴリズムとプログラミングの他の問題
次の擬似言語で表される手続 sumOdd を、引数として要素数 5 の整数型の配列 {12, 125, 1008,…次の擬似言語は、整数型の配列 arr に対して隣接交換を行う手続の一部であり、外側ループの 1 回目（1…次の擬似言語は昇順に整列された配列 arr に対する二分探索の手続である。arr = {2, 4, 6, 8, 10,…次の擬似言語で表される再帰手続 f を、引数 n = 20 で呼び出したとき、戻り値として返される値はどれか。
```…単方向連結リストの各ノードはメンバ val（整数）と next（次ノードへの参照。なければ NULL）をもつ。先頭ノード…スタックに対する push（積む）と…
この問題を、AIの8-ways解説つきで。
無料ではじめる →基本情報技術者試験の演習を、一問ごとに「なぜ」まで。まずは無料で。
ukamiru 過去問 · 基本情報技術者試験 · fe-b-algo-0117