修了試験 2017-01-22実施分 基本情報技術者試験 問6

解説

正解は2です。 図のヒープでは、根が9で、その子が11と14です。 11の子が24と25（Aの位置）、14の子が19と28です。 24の子が29と34で、＊はAの位置の25の子として点線で示されています。 7を＊に追加し、親より小さい間は親と交換していきます。 【計算】 7を＊の位置に置くと、親は25です。 7＜25なので交換し、7がAの位置に、25が＊の位置に移ります。 次の親は11で、7＜11なので交換します。 7が11の位置に上がり、11がAの位置に下ります。 次の親は根の9で、7＜9なので交換し、7が根になります。 根まで上がったので処理は終わり、Aの位置には11が残ります。 【選択肢別解説】 1：× 7はAの位置を通過して根まで上がるので、最終的にAの位置には残りません。 2：○ 7との交換で11がAの位置に下りてくるので、Aの位置の要素は11です。 3：× 24はAの兄弟の位置にあり、今回の交換の経路に含まれないので動きません。 4：× 25は最初の交換で＊の位置に移るので、Aの位置には残りません。 【ポイント】 ヒープへの挿入では、追加した要素が根に向かって上がる経路上の要素だけが1段ずつ下がります。 経路から外れた要素は位置が変わりません。