BohYoh.com《第２種情報処理技術者試験》1996年度＝平成8年度・秋期午前問13

第２種情報処理技術者試験

1996年度＝平成8年度・秋期

午前

問13

　親の節の値が子の節の値より小さいヒープがある。このヒープへの挿入は、要素を最後部に追加し、その要素が親よりも小さいとき親と子を交換することを繰り返せばよい。次のヒープの＊の位置に要素7を追加したとき、Ａの位置に来る要素はどれか。

　ア　7

　イ　9

　ウ　11

　エ　24

　オ　25

解答

　ウ

解説

　＊の位置に７を挿入すると、７は、親である25より小さいですので、これらを交換します。すなわち、次のようにします。

　　　　　　　　９　　　　　　　／　　＼　　　　　　11　　　　14 　　　　／　　＼　／　＼　　　 24　　　７ 19　　28 　　　／＼　　／　　29　　34 25

　交換した７は、親である11より小さいですので、これらを交換します。すなわち、次のようにします。

　　　　　　　　９　　　　　　　／　　＼　　　　　　７　　　　14 　　　　／　　＼　／　＼　　　 24　　　 11 19　　28 　　　／＼　　／　　29　　34 25

　交換した７は、親である9より小さいですので、これらを交換します。すなわち、次のようにします。

　　　　　　　　７　　　　　　　／　　＼　　　　　　９　　　　14 　　　　／　　＼　／　＼　　　 24　　　 11 19　　28 　　　／＼　　／　　29　　34 25

　これで、親の節の値は、子の節の値よりも小さくなり、挿入作業は完了します。このとき、Aの位置には11が来ています。