データ構造 (全39問中21問目)

No.21

葉以外の節点はすべて二つの子をもち,根から葉までの深さがすべて等しい木を考える。この木に関する記述のうち,適切なものはどれか。ここで,深さとは根から葉に至るまでの枝の個数を表す。
  • 枝の個数がnならば,葉を含む節点の個数も nである。
  • 木の深さがnならば,葉の個数は2n−1 である。
  • 節点の個数がnならば,深さは log2n である。
  • 葉の個数がnならば,葉以外の節点の個数は n−1である。
  • [出題歴]
  • 応用情報技術者 H25秋期 問6
  • 応用情報技術者 H30秋期 問6
  • ソフトウェア開発技術者 H17春期 問9
  • ソフトウェア開発技術者 H20春期 問9

分類

テクノロジ系 » アルゴリズムとプログラミング » データ構造

正解

解説

問題文にある「葉以外の節点はすべて二つの子をもち,根から葉までの深さがすべて等しい木」は次のような構造をもつ木です。
06.gif/image-size:292×228
この木構造をもとに、すべての選択肢を検証してみます。
  • 枝の個数は「6」,葉を含む節点の個数は「7」で一致しないので誤りです。
  • 木の深さは「2」,葉の個数は「4」です。2n-1のnに木の深さ「2」を代入すると、
     22-1=21=2
    となり葉の個数「4」と一致しないので誤りです。
  • 葉を含む節点の個数は「7」で、木の深さは「2」です。log2nのnに節点の個数「7」を代入すると、
     log27=2.807…
    木の深さ「2」と一致しないので誤りです。

    完全2分木では深さが1つ増える毎に節点の個数は次のように増加していきます。

    (根のみ) 1
    (深さ1) 1+2=3
    (深さ2) 1+2+4=7
    (深さ3) 1+2+4+8=15
    (深さ4) 1+2+4+8+16=31
    (深さ5) 1+2+4+8+16+32=63

    このため節点の個数がnである完全2分木の深さは「log2(n+1)−1」の式で表すことができます。
  • 葉の数は「4」,葉以外の節点には根が含まれるので「3」です。
    葉の数をnとすると、葉以外の節点の数はn−1になっています。したがってこの記述が適切です。
「葉以外の節点はすべて二つの子をもち,根から葉までの深さがすべて等しい木」は完全2分木と呼ばれ、木の深さが「n」であれば葉の数は「2n」、葉の数が「n」であれば、葉以外の節点の数(根を含む)は「n−1」であるという特徴を持っています。
© 2010-2024 応用情報技術者試験ドットコム All Rights Reserved.

Pagetop