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

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

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

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

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

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

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

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

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

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

a

問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
です。

問5 あるB木は,各節点に4個のキーを格納し,  5本の枝を出す。このB木の根(深さのレベルO)から深さのレベル2までの節点に格納できるキーの個数は,最大で幾つか。
ア 24  イ 31  ウ 120  エ 124

このページのトップヘ