応用情報技術者試験 - SE娘の剣 -

応用情報処理技術者試験の対策サイトです。 応用情報処理技術者試験の午前問題を中心とした基礎用語の解説を中心に掲載します。書き始めたばかりなので、内容はまだまだ不十分です。少しずつ追記していきます

木構造

 

1.木構造とは

木構造は、データ間の関係を階層的に表現します。
過去問(H16春FE午前問43)では、木構造に関して「ア 階層の上位から下位に節点をたどることによって,データを取り出すことができる構造である。」と述べられています。
tree
階層の○の部分ですが、最上位が「根」、最下位が「葉」、その間を「節」と呼びます。また、根や葉などを接続する線を「枝」と呼びます。

(1)2分木

すべての節が二つ以内の子(節や葉)をもつもの

(2)完全2分木

2分木の中で、「すべての葉が同じ深さであり,かつ,葉以外のすべての節点が二つの子をもつ(H19春SW午前問9)」ものである。別の過去問では、「根からどの葉に向かって木をたどっても,途中で通るノートの数が同じである完全2分木(H18秋SW午後Ⅰ)」という表現もされている。

(3)B木

枝が2つなのが2分木でしたが、枝が2つより多い場合を多分木と言います。
多分木の中で、葉までの階層が全て同じなどの特徴を持つものをB木と言います。
aaa

2.木構造の過去問を解いてみよう

(1)H29秋AP午前

問6 ノート1~5をもつグラフを隣接行列で表したもののうち,木となるものはどれか。ここで,隣接行列のi行j列目の成分は,ノートiとノートjを結ぶエッジがある場合は1,ない場合は0とする。
H29a-問6






【正解】イ

(2)H25秋AP午前

問6 葉以外の節点は全て二つの子をもち,根から葉までの深さが全て等しい木を考える。
  この木に関する記述のうち,適切なものはどれか。ここで,深さとは根から葉に至るまでの枝の個数を表す。また,節点には根及び葉も含まれる。

ア 枝の個数がnならば,節点の個数もnである。
イ 木の深さがnならば,葉の個数は2n-1である。
ウ 節点の個数がnならば,深さはlog2nである。
エ 葉の個数がnならば,葉以外の節点の個数はn-1である。






【正解】エ