基本情報技術者平成20年秋期 午前問12

午前問12

親の節の値が子の節の値より小さいヒープがある。このヒープへの挿入は,要素を最後部に追加し,その要素が親よりも小さい間,親と子を交換することを繰り返せばよい。次のヒープの * の位置に要素7を追加したとき,Aの位置に来る要素はどれか。
12.gif/image-size:174×132

分類

テクノロジ系 » アルゴリズムとプログラミング » データ構造

正解

解説

追加した要素と親要素を比較して親要素より小さい場合は位置を交換するという手順を繰り返していきます。
  1. 要素7と親である要素25を比較し、要素7の方が小さいため位置の交換を行います。
    12_1.gif/image-size:172×128
  2. 要素7と親である要素11を比較し、要素7の方が小さいため位置の交換を行います。
    12_2.gif/image-size:172×128
  3. 要素7と親である要素9を比較し、要素7の方が小さいため位置の交換を行います。
    12_3.gif/image-size:172×128
  4. 要素7は木構造の根に位置し親要素はないのでここで整列は完了します。
整列の結果から、最初に要素25が位置していたAの位置には要素11が来ることがわかります。
© 2010-2021 基本情報技術者試験ドットコム All Rights Reserved.

Pagetop