基本情報技術者 試験情報＆徹底解説 -新制度に完全対応-

掲示板[1150]にも書きましたが、知りたい方も多いと思うので載せておきます。

------------以下解説---------------

H30春  午後  問8  データ構造及びアルゴリズム  ヒープの性質を利用したデータの整列

ヒープの性質を利用した、データ整列アルゴリズムです。

プログラム1は,配列 data に格納されている無作為な数値を,法則に従ってヒープとなるように並び替えるプログラムです。
重要なのは〔プログラム1の説明〕の (2)③ の記述,
「配列要素 heap[i] (i = 0, 1, 2, ...) に対応する節の"左側の子は配列要素 heap[2×i + 1] に対応し,右側の子は配列要素 heap[2×i + 2] に対応する。」
にある""で囲った部分です。
つまり,親が 0 なら左の子は 0×2 + 1 = 1 で右の子は 0×2 + 2 = 2 となり,親が 2 なら左の子は 2×2 + 1 = 5 で右の子は 2×2 + 2 = 6 となります。

(4) で説明されている関数ですが,
lchild は左の子の配列要素の【要素番号】を返却
rchild は右の子の配列要素の【要素番号】を返却
parent は親の配列要素の【要素番号】を返却
というふうに,【要素番号】を返却することに注意です。

プログラム makeHeap の中身を見ると,
繰り返し処理の一行目で"heap にデータを追加"しています。
その後に空欄 a の処理をしていますが,空欄 a が真ならばプログラム swap によって,
"【要素番号】の引数 k と 空欄b の配列要素を入れ替えて"います。
元のデータ配列 data を事前に入れているわけですが, data はヒープの性質を満たすように整列されていないので,並べ替える必要があります。
並べ替える必要がある状況は,【自分の親の配列要素と比較して自分の方が大きいとき】です。

例えばヒープの根である heap[0] は一番大きくなくてはいけないので,
deta が 30 60 45 15 5 10 20 と並んでいたら 30 と 60 を入れ替えなくてはなりません。

要素番号 3,4 の親は要素番号 1 であり,子の配列要素は親の配列要素よりも大きくてはダメなので,
dataが 60 15 45 30 5 10 20 と並んでいたら 15 と 45 を入れ替えなくてはなりません。

（ここに書いてある例を図2の配列に書き込むとわかりやすいです、ここではわかりにくいと思います）

つまり、"子の配列要素が親の配列要素よりも大きくなっている"とき,
swap プログラムによって子の配列番号と"親の配列番号"を引数にとって,その配列要素を入れ替える
という操作が必要です。
いま""でそれぞれ囲んだところが空欄 a, b の答えです。
親の配列番号を返却する関数は parent ですので,
空欄 a は  イ
空欄 b は  エ  です。

==========続く

==========続き

プログラム2は、プログラム1でヒープとなるように並べた配列を用いて,データを降順に並べるプログラムです。
このプログラムの"降順に並べる"という仕組みは書かれてはいませんが,解く際はあまり関係ないと思います。分かっていた方がプログラムの内容は分かりやすいです。

〔プログラム2の動作〕中の空欄が問題ですが,
最初の記述が大事です。この記述の中では図 2 に示されている,
60 30 45 15 5 10 20 という順番でデータが格納されている状態でプログラム 2 を動かす,ということをしています。

空欄 c で聞かれていることは「副プログラム heapSort の行番号 5 の副プログラム swap の実行が終了した直後の配列要素 heap[0] の値」です。
行番号 5 は「・swap(heap, 0, last)」ですから,heap[0] と heap[last] の値を交換しています。
最初の last の値は繰り返しの記述にある通り hnum - 1 つまり最後の要素ですから,
60 と 20 を交換していることになります。
すなわちデータの並びは 20 30 45 15 5 10 60 となりますから直後の haep[0] の値は 20 です。
よって空欄 c は  エ  です。

空欄 d ですが、ここは文脈から「rchild(n) ≦ hlast」の次の行「heap[tmp] ≦ heap[rchild(n)]」の意味を聞いているということがわかります。
tmp は (2) の最初の記述から左側の子の要素番号ですので,不等号の向きを見れば
空欄 d は  イ  です。

空欄 e についてはプログラム downheap を追えばわかります。
データは 20 30 45 15 5 10 60 と並んでいて,最初の n は 0 ですから
tmp には heap[0] = 20 の左の子 heap[1] = 30 の要素番号 1 が入ります。
左の子 heap[1] = 30 と右の子 heap[2] = 45 では 45 の方が大きいですから
tmp は右の子 heap[2] = 45 の要素番号 2 に置き換わります。
heap[tmp] = heap[2] = 45 と heap[n] = heap[0] = 20 は heap[tmp] の方が大きいので
swap(heap, n, tmp) = swap(heap, 0, 2) が実行され 20 と 45 が入れ替わり
データは 45 30 20 15 5 10 60 と並びが変わります。
そして行番号 15 の「n ← tmp」には  tmp = 2 が入ります。
よって空欄 e は  2  です。

【総評】
僕個人ではですが、ここ最近で一番簡単だと感じました。
プログラムを埋める問題も少なかったので、点の取りどころだと思います。

ご投稿くださった内容を参考にアルゴリズムの解説を書きあげました。誠にありがとうございました。