葉以外の節点はすべて二つの子をもち、根から葉までの深さがすべて等しい木を考える。この木に関する記述のうち、適切なものはどれか。ここで、深さとは根から葉に至るまでの枝の個数を表す。
ア 枝の個数がnならば、葉を含む節点の個数もnである。
イ 木の深さがnならば、葉の個数は2n-1である。
ウ 節点の個数がnならば、深さは log2nである。
エ 葉の個数がnならば、葉以外の節点の個数はn−1である。
エ
葉以外の節点はすべて二つの子をもち、根から葉までの深さがすべて等しい木のことを完全2分木という。
ア 枝の個数がnならば、節点の個数はn＋1である。
イ 木の深さがnならば、葉の個数は2n である。
ウ 節点の個数がnならば、深さは log2(n＋1) −1 である。
逆に深さがnならば、節点の個数は 2n+1−1である。
エ 正しい。
| 問５ | 目次 | 問７ |