問題プレビューID: 5d3e18d6基本情報技術者試験 午前免除試験 2017年1月22日

問 6
基本情報技術者試験 午前免除試験 2017年1月22日

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

図中の A は値 25 の節点,* は要素を追加する位置を表す。

解説

正解は「イ」です。

ヒープを配列の添字で表すと,根を 1 として,節点 ii の親は ⌊i/2⌋\lfloor i/2 \rfloor です。図の配置は次のようになります。

添字12345(A)678910(*)
値911142425192829347

挿入した 7 を親と比較しながら交換していきます。

  1. 添字 10 の 7 と親(添字 5)の 25 を比較 → 7<257 < 25 なので交換。添字 5 は 7,添字 10 は 25 になる。
  2. 添字 5 の 7 と親(添字 2)の 11 を比較 → 7<117 < 11 なので交換。添字 2 は 7,添字 5 は 11 になる。
  3. 添字 2 の 7 と親(添字 1)の 9 を比較 → 7<97 < 9 なので交換。添字 1 は 7,添字 2 は 9 になる。

これでヒープの条件を満たすので,A の位置(添字 5)に来る要素は 11 です。よって「イ」が正解です。

関連問題

本文が同じ・似ている問題を表示しています