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

2.プログラミング > 2.2 木構造

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

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

完全2分木
2分木の中で、「すべての葉が同じ深さであり,かつ,葉以外のすべての節点が二つの子をもつ(H19春SW午前問9)」ものである。別の過去問では、「根からどの葉に向かって木をたどっても,途中で通るノートの数が同じである完全2分木(H18秋SW午後機法廚箸いι集修發気譴討い襦

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

過去問を見てみよう!
■H29秋
問6 ノート1〜5をもつグラフを隣接行列で表したもののうち,木となるものはどれか。ここで,隣接行列のi行j列目の成分は,ノートiとノートjを結ぶエッジがある場合は1,ない場合は0とする。
H29a-問6
【正解】イ

■H25秋
問6 葉以外の節点は全て二つの子をもち,根から葉までの深さが全て等しい木を考える。
  この木に関する記述のうち,適切なものはどれか。ここで,深さとは根から葉に至るまでの枝の個数を表す。また,節点には根及び葉も含まれる。
ア 枝の個数がnならば,節点の個数もnである。
イ 木の深さがnならば,葉の個数は2n-1である。
ウ 節点の個数がnならば,深さはlog2nである。
エ 葉の個数がnならば,葉以外の節点の個数はn-1である。
【正解】エ

2分探索木に関して過去問(H18秋SW午後1問5)では、「ノードが一つずつデータをもつ2分探索木は,どのノートNから見ても,左側の部分木のノートがもつデータはすべてNのデータよりも小さく,逆に右側の部分木のノートがもつデータはすべてNのデータよりも大きい,という性質をもつ。」と述べられている。

過去問(H28秋FE午前問6)を見てみよう。

2分探索木になっている2分木はどれか

a

過去問を見てみよう!
■H29秋
問5 配列A[1],A[2],・・・,A[n]で,A[1]を根とし,A[i]の左側の子をA[2i],右側の子をA[2i+1]とみなすことによって,2分木を表現する。このとき,配列を先頭から順に調べていくことは,2分木の探索のどれに当たるか。
ア 行きがけ順(先行順)深さ優先探索
イ 帰りがけ順(後行順)深さ優先探索
ウ 通りがけ順(中間順)深さ優先探索
エ 幅優先探索
【正解】エ

平成18年秋期 SW 午後 問5
問5 2分探索木に関する次の記述を読んで,設問1~4に答えよ。

 ノートが一つずつデータをもつ2分探索木は,どのノートNから見ても,左側の部分木のノートがもつデータはすべてNのデータよりも小さく,逆に右側の部分木のノートがもつデータはすべてNのデータよりも大きい,という性質をもつ。ここでは,ノートがもつデータはすべて自然数で重複がないものとする。図1に2分探索木の例を示す。ノート内の数が,データを表している。
2分探索木に対して,表1に示す二つの操作を定義する。
18-SW問5-1
 2分探索木を扱うために,それぞれのノートの情報を保持するデータ構造nodeを定義する。データ構造nodeへは, nodeの場所を指す変数であるポインタによってアクセスする。nodeがもつ変数を表2に示す。ここで,nilは,どのnodeも指していないことを示すポインタである。
18-SW問5-2
 nodeとnodeへのポインタの関係を図2に示す。図2では,変数pはnode0へのポインタであり,また,node0の変数left,rightは,それぞれnode1,node2へのポインタである。
 このとき,node0の三つの変数はそれぞれp->value,p->left,p->rightと表す。また,図2に示す状況で,p->leftの値をpへ代入すると,変数pはnode1へのポインタとなる。
18-SW問5-3
 操作lookupでは,2分探索木を根から葉の方向へ順次たどりながら探索を行う。まず,探索するデータと木の根がもつデータとを比べて,等しければ探索は終了する。探索するデータの方が小さければ左の子のノートに,大きければ右の子のノートに移動する。ここで,移動しようとした先に子のノートが存在しない場合,探索するデータが2分探索木内に見つからなかったことになり,探索終了となる。移動した先のノートでも同様にデータを比較し,探索するデータが見つかるか,又は見つからないことが分かるまで繰り返す。



設問1  図1の2分探索木に,操作insertを使って40,34,38の順にデータを挿入したときの2分探索木を,解答欄に示せ。
正解は、
18-SW問5-4
です。

B木に関しては、以下で簡単に解説をしました。
http://sm.seeeko.com/archives/65908873.html

H28秋AP午前問5 
問5 あるB木は,各節点に4個のキーを格納し,  5本の枝を出す。このB木の根(深さのレベル0)から深さのレベル2までの節点に格納できるキーの個数は,最大で幾つか。
ア 24  イ 31  ウ 120  エ 124
雑ですが、問題文の内容を図にすると、以下のようになります。
aaaa
深さレベル0には4個。深さレベル1には4×5=20個、深さレベル2には、20×4=80個を格納できます。
結果、4+20+80=124個、つまり、エが正解です。

過去問を見てみよう!
■H28秋AP午前
問27 B+木インデックスが定義されている候補キーを利用して,1件のデータを検索するとき,データ総件数Xに対するB+木インデックスを格納するノートへのアクセス回数のオーダを表す式はどれか。

ア √X
イ logX
ウ X
エ X!
正解は、イです。

このページのトップヘ