公務員試験 H29年 国家一般職(電気・電子・情報) No.39解説

　問 題　　　　　

次の ㋐～㋓ は整数の集合{2,3,5,7,11,13,17,19,23,29} を格納したデータ構造の例を図示したものである。㋐～㋓のうちのヒープの例のみを全て挙げ,かつ, 2 分探索木の例のみを全て挙げているのはどれか。

ヒープの例　2分探索木の例
1． ㋐　　㋓　　
2． ㋐,㋑　㋓　　
3． ㋐,㋓　㋒,㋓
4． ㋒,㋓　㋐　　
5． ㋓　　㋐

 

 

 

 

 

　解 説　　　　　

ヒープとは「子が必ず親より大きい構造」のことです。従って、㋐、㋑は共にヒープの例として適切です。一方、㋒や㋓はヒープ構造ではありません。

2 分探索木とは「左の子＜親＜右の子」が常に成り立つデータ構造です。㋒ですが、「17 と 7」、「17 と 19」、「11 と 3」 の関係が 2分探索木構造を満たしていません。

以上より、正解は 2 です。