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

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

2分探索木

 

1.2分探索木とは

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

2.2分探索木の過去問を解いてみよう

(1)H28秋FE午前

問6 2分探索木になっている2分木はどれか。
a






【正解】イ

(2)H29秋AP午前

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






【正解】エ

(3)H18秋SW午後1

問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