次のプログラムの説明及びプログラムを読んで，設問１，２に答えよ。
ヒープの性質を利用して，データを昇順に整列するアルゴリズムを考える。ヒープは二分木であり， 本問では，親は一つ又は二つの子をもち，親の値は子の値よりも常に大きいか等しいという性質を もつものとする。ヒープの例を図１に示す。図１において，丸は節を， 丸の中の数値は各節が保持する値を表す。子をもつ節を，その子に対する親と呼ぶ。 親をもたない節を根と呼び，根は最大の値をもつ。
図１ ヒープの例
〔プログラム１の説明〕
(1) 配列の要素番号は，Ø から始まる。
(2) 副プログラム makeHeap は，整数型の１次元配列 data に格納されている hnum 個 （hnum ＞ 0）のデータを，次の①～③の規則で整数型の１次元配列 heap に格納して， ヒープを配列で実現する。この状態を，“配列 heap は，ヒープの性質を満たしている”という。
② 配列要素 heap[Ø] は，根に対応する。
③ 配列要素 heap[i]（ i = Ø，1，2，…）に対応する節の左側の子は配列要素 heap[2×i＋1] に対応し，右側の子は配列要素 heap[2×i＋2] に対応する。 子が一つの場合，左側の子として扱う。
(3) 図１のヒープの例に対応した配列 heap の内容を，図２に示す。
図２ 図１のヒープの例に対応した配列 heap の内容
(4) 親の要素番号と子の要素番号を関係付ける三つの関数がある。
要素番号 i の配列要素に対応する節の左側の子の配列要素の要素番号 2×i＋1 を計算して返却する。
② 整数型：rchild（整数型：i )
要素番号 i の配列要素に対応する節の右側の子の配列要素の要素番号 2×i＋2 を計算して返却する。
③ 整数型：parent（整数型：i )
要素番号 i の配列要素に対応する節の親の配列要素の要素番号（i－1)÷2（小数点以下切捨て)を計算して返却する。
(6) 副プログラム makeHeap の引数の仕様を表１に，副プログラム swap の引数の仕様を表２に示す。
〔プログラム１〕
| 設問１ | プログラム１中の に入れる正しい答えを，解答群の中から選べ。 |
a に関する解答群
ウ heap[k] ＞ heap[rchild(k)] エ heap[k] ＜ heap[lchild(k)]
オ heap[k] ＜ heap[parent(k)] カ heap[k] ＜ heap[rchild(k)]
b に関する解答群
ウ parent(hnum－1) エ parent(k)
| 設問２ | 〔プログラム２の動作〕の記述中の に入れる正しい答えを， 解答群の中から選べ。 |
〔プログラム２の説明〕
(1) 副プログラム heapSort は，最初に副プログラム makeHeap を使って， 配列 heap にデータを格納する。配列 heap は，整列対象領域と整列済みデータ領域に 分かれている（図３参照）。last は，整列対象領域の最後の配列要素の要素番号を示している。 最初は，配列 heap 全体が整列対象領域であり，このとき last の値は hnum － 1 である。
図３ 配列 heap における整列対象領域と整列済みデータ領域
(2) 整列対象領域がヒープの性質を満たすとき，配列要素 heap[Ø] の値は， この領域での最大の値となっている。そこで，配列要素 heap[Ø] の値と 配列要素 heap[last] の値を交換し，last の値を 1 減らして， 整列対象領域の範囲を狭め，整列済みデータ領域を広げる。値の交換によって， 整列対象領域はヒープの性質を満たさなくなるので，副プログラム downHeap を使って， 整列対象領域のデータがヒープの性質を満たすように再構成する。 これを繰り返すことによって，整列済みデータ領域には昇順に整列されたデータが 格納されることになる。
(3) 副プログラム heapSort の引数の仕様を表３に，副プログラム heapSort で 使用する副プログラム downHeap の引数の仕様を表４に示す。
〔プログラム２〕
〔プログラム２の動作〕
副プログラム heapSort の行番号 3 の実行が終了した直後のαにおける配列 heap の内容は，図２のとおりであった。このとき，副プログラム heapSort の 行番号 4 から行番号 7 までの１回目の繰返し処理について考える。
副プログラム heapSort の行番号 5 の副プログラム swap の実行が終了した直後の 配列要素 heap[Ø] の値は，c となる。 このため，配列 heap の要素番号 Ø からhnum－2 までのデータは， 根に対応する配列要素 heap[Ø] が最大の値をもつというヒープの性質を満たさなくなる。
副プログラム heapSort の行番号 6 で呼び出している副プログラム downHeap は， 配列 heap の整列対象領域の要素番号 Ø から hlast までのデータがヒープの性質を 満たすように，その領域のデータを次の手順で再構成する。
(1) 配列要素の値の大きさを比較する際に使用する要素番号を n とし，n の初期値を Ø とする。
(2) 要素番号 n の配列要素に対応する節の左側の子の要素番号を tmp に代入する。 要素番号 n の子が二つあり（rchild(n) ≦ hlast)，右側の子の値が 左側の子の値 d ，右側の子の要素番号を tmp に代入する。
(3) 子に対応する配列要素 heap[tmp] の値と，その親に対応する配列要素 heap[n] の値とを比較し， 配列要素 heap[tmp] の値が大きければ，配列要素 heap[n] の値と配列要素 heap[tmp] の値を交換し， tmp を次の n として (2) に戻る。ここで，副プログラム downHeap の行番号 15 において最初に n に 代入する tmp の値は，e である。
c に関する解答群
d に関する解答群
ウ よりも大きいときには エ よりも小さいときには
e に関する解答群
エ 4 オ 5 カ 6
[←前の問題] [次の問題→] [問題一覧表] [分野別] [基本情報技術者試験TOP ]
