データ構造(全52問中38問目)

午前試験免除制度対応!基本情報技術者試験のeラーニング【独習ゼミ】
親の節の値が子の節の値より小さいヒープがある。このヒープへの挿入は,要素を最後部に追加し,その要素が親よりも小さい間,親と子を交換することを繰り返せばよい。次のヒープの * の位置に要素7を追加したとき,Aの位置に来る要素はどれか。
12.gif

出典:平成20年秋期 問12

  • 7
  • 11
  • 24
  • 25
正解 問題へ
分野:テクノロジ系
中分類:アルゴリズムとプログラミング
小分類:データ構造
解説
追加した要素と親要素を比較して親要素より小さい場合は位置を交換するという手順を繰り返していきます。
  1. 要素7と親である要素25を比較し、要素7の方が小さいため位置の交換を行います。
    12_1.gif
  2. 要素7と親である要素11を比較し、要素7の方が小さいため位置の交換を行います。
    12_2.gif
  3. 要素7と親である要素9を比較し、要素7の方が小さいため位置の交換を行います。
    12_3.gif
  4. 要素7は木構造の根に位置し親要素はないのでここで整列は完了します。
整列の結果から、最初に要素25が位置していたAの位置には要素11が来ることがわかります。

Pagetop