平成17年 春期 基本情報技術者 午後 問04
問04 整数値をヒープソート次のプログラムの説明及びプログラムを読んで,設問1〜3に答えよ。
〔プログラムの説明〕 副プログラム HeapSort は,配列に格納されている整数値をヒープソートで 昇順に整列するプログラムである。 (1) 整列する Num 個(Num ≧ 2)の整数値は,大域変数の配列 A[1],A[2],…, A[Num] に格納されている。 (2) ヒープソートは,2分木を用いてデータを整列する。 2分木を配列で表現するには,ある節が A[i] に対応するとき, その左側の子の節を A[2×i] に,右側の子の節を A[2×i+1] に対応させる。 図では,丸が節を,丸中の数字が節の値を示し,実際に値が格納されている配列の要素を 丸のに示している。 (3) ヒープとは,図のように,各節の値が自分の子の節の値以上になっている2分木である。
図 ヒープの例
(4) 整列の手順は,次のとおりである。 @ 配列 A の中の,A[1],A[2],…,A[Num] を整列対象とする。 A 整列対象の各要素が,(2) で述べたような2分木を表現しているものとして, 要素の値を入れ換えてヒープを作る。 その結果,木の根(A[1])には整列対象の要素の最大値が入る。 B 木の根(A[1])の値と,木の最後の節(整列対象の最後の要素に対応する節)の値とを交換する。 C 木の最後の節を2分木から取り除く(整列対象の要素を一つ減らす)。 D C の結果が,木の根だけになるまで,A 〜 C の処理を繰り返す。 (5) ヒープを作り直す手順は,次のとおりである。 @ 木の根を親の節とする。 A 子の節がなければ終了する。 B 二つの子の節のうち値が大きい方と親の節の値を比較し,親の節の方が小さいときは, 値を交換する。 親の節の値が子の節の値以上のときは,何もしないで終了する。 C 値を交換した子の節を根とする部分木に対して,@ 〜 B の処理を繰り返す。 (6) 副プログラムの引数の仕様を表1〜4に示す。 表1 HeapSort の引数の仕様
表2 InitHeap の引数の仕様
表3 MakeHeap の引数の仕様
表4 Swap の引数の仕様
〔プログラム〕 設問1 プログラム中の に入れる正しい答えを,解答群の中から選べ。
a に関する解答群 ア L ← Top イ L ← Top + 1 ウ L ← Top × 2 エ L ← Top × 2 + 1 b に関する解答群 ア L ≦ Last イ L < Last ウ R ≦ Last − 1 エ R ≦ Last − 2
設問2 次の記述中の に入れる正しい答えを,解答群の中から選べ。
図のヒープを用いて,〔プログラムの説明〕の (4) の B,C を1回だけ実行して, A が終了したとき,最初 A[10] に入っていた値 12 が格納されている配列要素の添字は である。 また,それまでに節の値を交換した回数は である。
解答群 ア 2 イ 3 ウ 4 エ 5 オ 6 カ 7 キ 8 ク 9
設問3 最初にヒープを作成する副プログラム InitHeap は MakeHeap を 使って作ることができる。 次のプログラム中の に入れる正しい答えを, 解答群の中から選べ。
解答群 ア Idx: 1, Idx ≦ Last, 2 イ Idx: 1, Idx ≦ Last ÷ 2, 1 ウ Idx: Last, Idx ≧ 1, −2 エ Idx: Last ÷ 2, Idx ≧ 1, −1 [←前の問題] [次の問題→] [問題一覧表] [分野別] [基本情報技術者試験TOP ] | ||||||||||||||||||||||||||||||||||||||||