基本情報技術者試験「木構造」の問題
次の 2 分木がある。各ノードは値・左の子・右の子をもつ（子がなければ空）。
根=A、A の左の子=B、A の右の子=C、B の左の子=D、C の左の子=E、C の右の子=F、E の左の子=G（D・F・G の子はすべて空、B の右の子は空、E の右の子は空）。
次の擬似言語は、葉（左の子も右の子も空である節点）の個数を返す。この木の根 A に対して実行したとき、戻り値はどれか。
○整数型: countLeaf(ノード: n)
if (n が 空)
return 0
endif
if (n.左 が 空 かつ n.右 が 空)
return 1
endif
return countLeaf(n.左) + countLeaf(n.右)ア3（葉）
ウ4個
イ7（全ノード）
エ2個
正解
ア．3（葉）
countLeaf は子が両方空なら 1 を返し、そうでなければ左右の葉数を合計する。葉は D, F, G の 3 個であり戻り値は 3 となるため アが正しい。
?選択肢ごとの解説
ア ○countLeaf は子が両方空なら 1 を返し、そうでなければ左右の葉数を合計する。葉は D, F, G の 3 個であり戻り値は 3 となるため アが正しい。
ウ ×E を葉に数え入れて 4 個とした誤りで、E は左の子 G をもつため葉ではない。
イ ×全ノード数 7 を葉数と取り違えた、内部節点も数え入れた誤りである。
エ ×D と F だけを葉と数えて G を見落とし 2 個とした、最深部の葉の数え漏れである。
✎くわしく
葉は『左右どちらの子ももたない節点』である。子を 1 つでももつ節点（B や E）は内部節点であり葉に含めない点を厳密に判定する必要がある。
✓本番での押さえどころ
試験のコツ
各節点について『左も右も空か』を 1 つずつ確認し、両方空のものだけを数える。
覚え方
『葉＝子なし』と唱え、片方でも子があれば内部節点と区別する。
よくある誤り
片方の子だけをもつ節点（B, E）を葉と誤判定したり、最深部の葉を数え漏らすミスが多い。
アルゴリズムとプログラミングの他の問題
次の擬似言語で表される手続 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-0118