アルゴリズムとプログラミング
基本情報技術者試験 科目A免除 修了試験 20170122 実施分 問6
親の節の値が子の節の値より小さいヒープがある。このヒープへの挿入は，要素を最後部に追加し，その要素が親よりも小さい間，親と子を交換することを繰り返せばよい。次のヒープの＊の位置に要素7を追加したとき，Aの位置に来る要素はどれか。
二分木。根9。9の子は左11，右14。11の子は左24，右25（二重丸で，Aと記されている）。14の子は左19，右28。24の子は左29，右34。＊は25の左下（点線で25とつながる，25の子の位置）。
- ア 7
- イ 11
- ウ 24
- エ 25
出典：基本情報技術者試験 科目A免除 修了試験 20170122 実施分 問6
答えと解説を見る
正解：イ
覚える知識
ヒープへの要素挿入(上方向への交換)
ヒープへの挿入は最後部に追加し、親より小さい間は親と交換しながら上へ移動させる操作である。
この問題で必要なこと
7を25の子として追加し、親より小さい間は交換を繰り返す。25→11→9と交換して根まで上がり、Aの位置には11が来る。
ひっかけ
交換が1回で止まると思うと25を選び、2回で止まると思うと11以外を選んでしまう。
この知識の出題：本試験系 0 回・免除試験 1 回（公開問題での観測値）