応用情報技術者試験の過去問&キーワードを動画2443本の動画で解説!スキマ時間に動画!※2017年9月11日現在

PR広告

平成27年度秋応用情報技術者試験午後過去問 問3 プログラミング 設問4

問3 プログラミング

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

 2分探索木とは、全てのノードNに対して、次の条件が成立している2分木のことである。

・Nの左部分木にある全てのノードのキー値は、Nのキー値よりも小さい。

・Nの右部分木にある全てのノードのキー値は、Nのキー値よりも大きい。

 ここで、ノードのキー値は自然数で重複しないものとする。2分探索木の例を図1に示す。図中の数はキー値を表している。

平成27年度秋応用情報技術者試験午前過去問1

 2分探索木を実現するために、ノードを表す構造体Nodeを定義する。構造体Nodeの構成要素を表1に示す。

平成27年度秋応用情報技術者試験午前過去問1

 構造体の実体を生成するためには、次のように書く。

   new Node(key)

 生成した構造体への参照が戻り値となる。構造体の構成要素のうち、keyは引数keyの値で初期化され、left とright はnull で初期化される。

 変数p が参照するノードをノードp という。ノードを参照する変数からそのノードの構成要素へのアクセスには"."を用いる。例えば、ノードp のキー値には、p.key でアクセスできる。

 なお、変数p の値がnull の場合、木は空である。

〔2分探索木でのノードの探索〕

 与えられたキー値をもつノードを探索する場合、親から子の方向へ、木を順次たどりながら探索を行う。

 探索する2分探索木にノードがない場合は、目的のノードが見つからず、探索は失敗と判断して終了する。探索する2分探索木にノードがある場合は、与えられたキー値と木の根のキー値を比較し、等しければ、目的のノードが見つかったので探索は成功と判断して終了する。与えられたキー値の方が小さければ左部分木に、大きければ右部分木に移動する。移動先の部分木でも同様に探索を続ける。

 この手順によって探索を行う関数search のプログラムを図2に示す。このプログラムでは、探索が成功した場合は見つかったノードへの参照を返し、失敗した場合はnull を返す。

// ノードpを根とする2分探索木から、キー値がkであるノードを探索する
function search(k, p)
    if(pとnullが等しい)
	    return null //探索失敗
    elseif(kとp.keyが等しい)
	    return p // 探索成功
    elseif()
	    return search(k, p.left) // 左部分木を探索する
	else
	    return search(k, p.right) // 右部分木を探索する
	endif
endfunction

図2 関数searchのプログラム

〔2分探索木へのノードの挿入〕

 2分探索木にノードを挿入する場合、探索と同様に、親から子の方向へ、木を順次たどりながら、適切な位置にノードを挿入する。

 挿入する2分探索木にノードがない場合は、挿入するキー値のノードを作成する。挿入する2分探索木にノードがある場合は、挿入するキー値と木の根のキー値を比較し、挿入するキー値が小さければ左部分木に、大きければ右部分木に移動する。移動先の部分木でも同様の処理を続ける。

 この手順によって挿入を行う関数addNode のプログラムを図3に示す。このプログラムでは、挿入の結果として得られた2分探索木の根のノードへの参照を返す。ただし、このプログラムは、挿入するキー値と同じキー値をもつノードが2分探索木に既に存在するときは何もしない。

//ノードpを根とする2分探索木二、キー値がkであるノードを挿入する
function addNode(k, p)
    if(pとnullが等しい)
	    p ←  // ノードを生成する
    elseif(kとp.keyが等しくない)
	    if()
		    p.left ← addNode(k, p.left) //左部分木に移動し挿入を続ける
        else
		    p.right ← addNode(k, p.right) // 右部分木に移動し挿入を続ける
		endif
	endif
	
endfunction

図3 関数addNode のプログラム

〔2分探索木からのノードの削除〕

 2分探索木から、あるキー値をもつノードを削除する場合、次の(1)~(3)の手順を行う。

(1) 2分探索木にノードがない場合は、何もしないで処理を終了する。

(2) 削除するキー値と木の根のキー値を比較し、削除するキー値の方が小さければ左部分木に、大きければ右部分木に移動する。移動先の部分木でも同様の処理を続ける。

(3) 削除するキー値と木の根のキー値が等しい場合、削除するキー値をもつノードを削除するため、次の(3-1)~(3-3)を実行する。

 (3-1) 削除するノードが子ノードをもたない場合、そのノードを削除する。

 (3-2) 削除するノードが子ノードを一つだけもつ場合、削除するノードの位置にその子ノードを置く。

 (3-3) 削除するノードが左右両方に子ノードを持つ場合、削除するノードの左部分木の中で最大のキー値をもつノードを左部分木から取り除き、削除するノードの位置に置く。

 この手順を使って2分探索木からノードの削除を行う関数removeNode のプログラムを図4に示す。このプログラムでは、削除した後の2分探索木の根のノードへの参照を返す。ただし、このプログラムは、削除するキー値をもつノードが2分探索木に存在しないときは何もしない。

 図4中の関数extractMaxNode は、引数で指定されたノードを根とする2分探索木の中で最大のキー値をもつノードを木から削除し、削除されたノードへの参照を大域変数extractedNode に設定した上で、削除した後の2分探索木の根のノードへの参照を返す。関数extractMaxNode のプログラムを図5に示す。

//ノードpを根とする2分探索木から、キー値がkであるノードを削除する
function removeNode(k, p)
    if(pとnullが等しくない)
	    if(kがp.keyより小さい)
		    p.left ← removeNode(k, p.left)
		elseif(kがp.keyより大きい)
		    p.right ← removeNode(k, p.right)
		else
		    if(p.leftとnullが等しい かつ p.rightとnullが等しい)
			    p ← null //ノードを削除する
			elseif(とnullが等しい)
			    p ← p.right // 右部分木を置く
			elseif(とnullが等しい)
			    p ← p.left // 左部分木を置く
			else // 左部分木の中の最大ノードを置く
			    p.left ← extractMaxNode(p.left)
				r ← extractedNode
				r.left ← p.left
				r.right ← p.right
				
			endif
		endif
	endif
	return p
endfunction

図4 関数removeNode のプログラム

//ノードpを根とする2分探索木から、最大のキー値を持つノードを削除し、削除されたノードへの山椒を大域変数に格納する
function extractMaxNode(p)
    if(p.rightとnullが等しい)
	    extractedNode ← p
		p ← p.left
	else
	    p.right ← extractMaxNode(p.right)
	endif
	return p
endfunction

図5 関数extractMaxNode のプログラム

〔2分探索木の計算量〕

 2分探索木における計算量は、木の高さに依存する。図2の関数search を使ってn個のノードから成る2分探索木を探索する場合、想定される最大の計算量は、O()である。木構造が完全2分木であれば、その計算量は最大でもO()である。

設問4

次の順でキー値の挿入と削除を行った後でノードq を根とする2分探索木を答えよ。2分探索木は、図1の例に倣って表現すること。

q ← null

q ← addNode(5, q) //5を挿入

q ← addNode(2, q) //2を挿入

q ← addNode(7, q) //7を挿入

q ← addNode(1, q) //1を挿入

q ← addNode(8, q) //8を挿入

q ← addNode(4, q) //4を挿入

q ← addNode(3, q) //3を挿入

q ← addNode(12, q) //12を挿入

q ← removeNode(5, q) //5を削除

q ← removeNode(7, q) //7を削除

解説

動画で詳細を解説します!(テキストでは表現しにくいので...)

平成27年度秋応用情報技術者試験午後過去問 問3 プログラミング 目次

平成27年度秋基本情報技術者試験過去問 午後 目次

業務経験がない組込みシステム開発の解説は控えさせていただきますご了承ください。


タグ: ,,,,,

PR広告

フェイスブックコメント

難解な応用情報技術者試験午前で80点中48点を取る優しい方法

平成28年度春 応用情報技術者試験 午後 テキスト・動画解説

平成28年度春 応用情報技術者試験 午後 動画解説再生リスト

平成28年度春 応用情報技術者試験 午前 テキスト・動画解説

平成28年度秋 応用情報技術者試験 午前 動画解説再生リスト

平成27年度秋 応用情報技術者試験 午前 テキスト・動画解説

平成27年度秋 応用情報技術者試験 午前 動画解説再生リスト

平成27年度春 応用情報技術者試験 午後 テキスト・動画解説

平成27年度春 応用情報技術者試験 午後 動画解説再生リスト

平成27年度春 応用情報技術者試験 午前 テキスト・動画解説

平成27年度春 応用情報技術者試験 午前 動画解説再生リスト

平成26年度秋 応用情報技術者試験 午前 テキスト・動画解説

平成26年度秋 応用情報技術者試験 午前 動画解説再生リスト

平成26年度春 応用情報技術者試験 午前 テキスト・動画解説

平成26年度春 応用情報技術者試験 午前 動画解説再生リスト