基本情報技術者試験の過去問と解説
[TOP] [午前分野別] [午後分野別] [キーワード索引] [令和元年秋午前] [令和元年秋午後]

平成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 の引数の仕様

引数名データ型入力/出力意味
Num整数型入力 木の最後の節に対応する配列要素の添字

   表2 InitHeap の引数の仕様

引数名データ型入力/出力意味
Last整数型入力 最初にヒープを作る木の,最後の節に対応する配列要素の添字

   表3 MakeHeap の引数の仕様

引数名データ型入力/出力意味
Top整数型入力 ヒープを作り直す部分木の,木の根に対応する配列要素の添字
Last整数型入力 ヒープを作り直す部分木の,最後の節に対応する配列要素の添字

   表4 Swap の引数の仕様

引数名データ型入力/出力意味
X整数型入力 A[Y] と交換する配列要素の添字
Y整数型入力 A[X] と交換する配列要素の添字

〔プログラム〕

設問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

解答 a ←クリックすると正解が表示されます

解答 b ←クリックすると正解が表示されます


設問2 次の記述中の に入れる正しい答えを,解答群の中から選べ。

図のヒープを用いて,〔プログラムの説明〕の (4) の B,C を1回だけ実行して, A が終了したとき,最初 A[10] に入っていた値 12 が格納されている配列要素の添字は である。 また,それまでに節の値を交換した回数は である。

解答群

ア 2    イ 3    ウ 4    エ 5    オ 6

カ 7    キ 8    ク 9

解答 c ←クリックすると正解が表示されます

解答 d ←クリックすると正解が表示されます


設問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 ]