応用情報技術者過去問題 平成27年秋期 午後問3

問3 プログラミング

2分探索木に関する次の記述を読んで,設問1〜4に答えよ。

 2分探索木とは,全てのノードNに対して,次の条件が成立している2分木のことである。
  • Nの左部分木にある全てのノードのキー値は,Nのキー値よりも小さい。
  • Nの右部分木にある全てのノードのキー値は,Nのキー値よりも大きい。
 ここで,ノードのキー値は自然数で重複しないものとする。2分探索木の例を図1に示す。図中の数はキー値を表している。
pm03_1.gif/image-size:207×166
 2分探索木を実現するために,ノードを表す構造体 Node を定義する。構造体 Node の構成要素を表1に示す。
pm03_2.gif/image-size:209×115
 構造体の実体を生成するためには,次のように書く。
  new Node(key)
 生成した構造体への参照が戻リ値となる。構造体の構成要素のうち,keyは引数keyの値で初期化され,leftとrightはnullで初期化される。
 変数pが参照するノードをノードpという。ノードを参照する変数からそのノードの構成要素へのアクセスには"."を用いる。例えば,ノードpのキー値には,p.keyでアクセスできる。
 なお,変数pの値がnullの場合,木は空である。

〔2分探索木でのノードの探索〕
 与えられたキー値をもつノードを探索する場合,親から子の方向へ,木を順次たどりながら探索を行う。
 探索する2分探索木にノードがない場合は,目的のノードが見つからず,探索は失敗と判断して終了する。探索する2分探索木にノードがある場合は,与えられたキー値と木の根のキー値を比較し,等しければ,目的のノードが見つかったので探索は成功と判断して終了する。与えられたキー値の方が小さければ左部分木に,大きければ右部分木に移動する。移動先の部分木でも同様に探索を続ける。
 この手順によって探索を行う関数 search のプログラムを図2に示す。このプログラムでは,探索が成功した場合は見つかったノードへの参照を返し,失敗した場合はnullを返す。
pm03_3.gif/image-size:496×222
〔2分探索木へのノードの挿入〕
 2分探索木にノードを挿入する場合,探索と同様に,親から子の方向へ,木を順次たどりながら,適切な位置にノードを挿入する。
 挿入する2分探索木にノードがない場合は,挿入するキー値のノードを作成する。挿入する2分探索木にノードがある場合は,挿入するキー値と木の根のキー値を比較し,挿入するキー値の方が小さければ左部分木に,大きければ右部分木に移動する。移動先の部分木でも同様の処理を続ける。
 この手順によって挿入を行う関数 addNode のプログラムを図3に示す。このプログラムでは,挿入の結果として得られた2分探索木の根のノードへの参照を返す。ただし,このプログラムは,挿入するキー値と同じキー値をもつノードが2分探索木に既に存在するときは何もしない。
pm03_4.gif/image-size:497×243
〔2分探索木からのノードの削除〕
 2分探索木から,あるキー値をもつノードを削除する場合,次の(1)〜(3)の手順を行う。
  • 2分探索木にノードがない場合は,何もしないで処理を終了する。
  • 削除するキー値と木の根のキー値を比較し,削除するキー値の方が小さければ左部分木に,大きければ右部分木に移動する。移動先の部分木でも同様の処理を続ける。
  • 削除するキー値と木の根のキー値が等しい場合,削除するキー値をもつノードを削除するため,次の(3-1)〜(3-3)を実行する。
    (3-1)
    削除するノードが子ノードをもたない場合,そのノードを削除する。
    (3-2)
    削除するノードが子ノードを一つだけもつ場合,削除するノードの位置にその子ノードを置く。
    (3-3)
    削除するノードが左右両方に子ノードをもつ場合,削除するノードの左部分木の中で最大のキー値をもつノードを左部分木から取り除き,削除するノードの位置に置く。
 この手順を使って2分探索木からノードの削除を行う関数 removeNode のプログラムを図4に示す。このプログラムでは,削除した後の2分探索木の根のノードへの参照を返す。ただし,このプログラムは,削除するキー値をもつノードが2分探索木に存在しないときは何もしない。
 図4中の関数 extractMaxNode は,引数で指定されたノードを根とする2分探索木の中で最大のキー値をもつノードを木から削除し,削除されたノードへの参照を大域変数 extractedNode に設定した上で,削除した後の2分探索木の根のノードへの参照を返す。関数 extractMaxNode のプログラムを図5に示す。
pm03_5.gif/image-size:497×654
〔2分探索木の計算量〕
 2分探索木における計算量は,木の高さに依存する。図2の関数 search を使ってn個のノードから成る2分探索木を探索する場合,想定される最大の計算量は,O()である。木構造が完全2分木であれば,その計算量は最大でもO()で ある。

設問1

図1中のに入れる適切な数を答えよ。

-解答入力欄-

  • ア:

-解答例・解答の要点-

  • ア:11

-解説-

この設問の解説はまだありません。

設問2

図2〜4中のに入れる適切な字句を答えよ。

-解答入力欄-

  • イ:
  • ウ:
  • エ:
  • オ:
  • カ:
  • キ:

-解答例・解答の要点-

  • イ:k が p.key より小さい
  • ウ:new Node(k)
  • エ:return p
  • オ:p.left
  • カ:p.right
  • キ:p ← r

-解説-

この設問の解説はまだありません。

設問3

本文中のに入れる適切な字句を答えよ。

-解答入力欄-

  • ク:
  • ケ:

-解答例・解答の要点-

  • ク:n
  • ケ:log n

-解説-

この設問の解説はまだありません。

設問4

次の順でキー値の挿入と削除を行った後でノードqを根とする2分探索木を答えよ。2分探索木は,図1の例に倣って表現すること。
pm03_6.gif/image-size:291×193

-解答入力欄-

  • (図表で回答する問題のため解答入力欄はありません。)

-解答例・解答の要点-

  • pm03_7.gif/image-size:233×91

-解説-

この設問の解説はまだありません。
問3成績
【27年秋期 午後問題】
 問1 問2 問3 問4 問5 問6 問7 問8 問9 問10 問11
© 2010-2019 応用情報技術者試験ドットコム All Rights Reserved.

Pagetop