基本情報技術者試験 過去問解説
二分木とは？基本情報技術者試験 令和元年度 科目A 修了認定試験 問7を解説
基本情報技術者試験 令和元年度 科目A 修了認定試験 問7は、二分木に関する理解を問う問題です。検索から入っても、問題文、選択肢、正解、解説、各選択肢がなぜ違うかをこのページだけで確認できます。
問題文
葉以外の節点は全て二つの子をもち、根から葉までの深さが全て等しい木を考える。この木に関する記述のうち、適切なものはどれか。ここで、木の深さとは根から葉に至るまでの枝の個数を表す。また、節点には根及び葉も含まれる。
この問題の出題ポイント
- 二分木の定義だけでなく、問題文中の条件がどの選択肢に当てはまるかを確認する。
- データ構造分野では、用語の目的・主体・責任範囲の違いが選択肢で問われやすい。
- 関連タグ: 二分木。
選択肢
- ア枝の個数が n ならば、節点の個数も n である。
- イ木の深さが n ならば、葉の個数は 2^(n−1) である。
- ウ節点の個数が n ならば、木の深さは log₂ n である。
- エ葉の個数が n ならば、葉以外の節点の個数は n − 1 である。正解
正解
エ: 葉の個数が n ならば、葉以外の節点の個数は n − 1 である。
解説
葉以外の節点が全て二つの子をもつ完全二分木（厳密 2 分木）では、葉の個数 n に対し、内部節点（葉以外の節点）の個数は n−1 となる。
なぜ他の選択肢が違うのか
ア
完全二分木の節点数は枝数+1 なので n+1 となり、n と等しくない。
イ
深さ n の完全二分木の葉の個数は 2^n であり、2^(n−1) ではない。
ウ
節点数 n のとき、深さは必ずしも log₂ n にならない（n+1=2^(d+1)−1 の関係から d=log₂((n+1)/1)−1）。
エ（正解）
葉 n 個の完全二分木の内部節点は n−1 個=正解。
解き方の整理
二分木の問題では、選択肢のキーワードだけで判断せず、問題文が示す条件と正解選択肢の説明が一致しているかを見ます。誤答選択肢は、似た用語を混ぜる、主体を入れ替える、目的や範囲を広げすぎる、という形で作られることが多いため、選択肢別解説まで確認しておくと復習効率が上がります。
関連用語
関連問題
前後の問題
復習を続ける
間違えた問題、苦手タグ、模試履歴を保存して復習する導線を用意しています。広告なしPro、弱点分析、復習リマインダーは段階的に提供予定です。