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

平成30年 春期 基本情報技術者 午後 問08
問08   必須問題

 次のプログラムの説明及びプログラムを読んで,設問1,2に答えよ。

 

 ヒープの性質を利用して,データを昇順に整列するアルゴリズムを考える。ヒープは二分木であり, 本問では,親は一つ又は二つの子をもち,親の値は子の値よりも常に大きいか等しいという性質を もつものとする。ヒープの例を図1に示す。図1において,丸は節を, 丸の中の数値は各節が保持する値を表す。子をもつ節を,その子に対する親と呼ぶ。 親をもたない節を根と呼び,根は最大の値をもつ。

 

図1 ヒープの例

 

〔プログラム1の説明〕

(1) 配列の要素番号は,Ø から始まる。

(2) 副プログラム makeHeap は,整数型の1次元配列 data に格納されている hnum 個 (hnum > 0)のデータを,次の@〜Bの規則で整数型の1次元配列 heap に格納して, ヒープを配列で実現する。この状態を,“配列 heap は,ヒープの性質を満たしている”という。

@ 配列要素 heap[i]( i = Ø,1,2,…)は,節に対応する。配列要素 heap[i] には, 節が保持する値を格納する。

A 配列要素 heap[Ø] は,根に対応する。

B 配列要素 heap[i]( i = Ø,1,2,…)に対応する節の左側の子は配列要素 heap[2×i+1] に対応し,右側の子は配列要素 heap[2×i+2] に対応する。 子が一つの場合,左側の子として扱う。

(3) 図1のヒープの例に対応した配列 heap の内容を,図2に示す。

 

図2 図1のヒープの例に対応した配列 heap の内容

 

(4) 親の要素番号と子の要素番号を関係付ける三つの関数がある。 @ 整数型:lchild(整数型:i )

  要素番号 i の配列要素に対応する節の左側の子の配列要素の要素番号 2×i+1 を計算して返却する。

A 整数型:rchild(整数型:i )

  要素番号 i の配列要素に対応する節の右側の子の配列要素の要素番号 2×i+2 を計算して返却する。

B 整数型:parent(整数型:i )

  要素番号 i の配列要素に対応する節の親の配列要素の要素番号(i−1)÷2(小数点以下切捨て)を計算して返却する。

(5) 副プログラム swap は,二つの配列要素に格納されている値を交換する。

(6) 副プログラム makeHeap の引数の仕様を表1に,副プログラム swap の引数の仕様を表2に示す。

 

表1 副プログラム makeHeap の引数の仕様

 

表2 副プログラム swap の引数の仕様

 

〔プログラム1〕

 

設問1  プログラム1中の に入れる正しい答えを,解答群の中から選べ。

 

a に関する解答群 ア heap[k] > heap[lchild(k)]       イ heap[k] > heap[parent(k)]

ウ heap[k] > heap[rchild(k)]       エ heap[k] < heap[lchild(k)]

オ heap[k] < heap[parent(k)]       カ heap[k] < heap[rchild(k)]

 

b に関する解答群 ア heap[hnum−1]        イ heap[k]

ウ parent(hnum−1)       エ parent(k)

 

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

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

基本情報技術者試験


設問2  〔プログラム2の動作〕の記述中の に入れる正しい答えを, 解答群の中から選べ。

 

〔プログラム2の説明〕

(1) 副プログラム heapSort は,最初に副プログラム makeHeap を使って, 配列 heap にデータを格納する。配列 heap は,整列対象領域と整列済みデータ領域に 分かれている(図3参照)。last は,整列対象領域の最後の配列要素の要素番号を示している。 最初は,配列 heap 全体が整列対象領域であり,このとき last の値は hnum − 1 である。

 

図3 配列 heap における整列対象領域と整列済みデータ領域

 

(2) 整列対象領域がヒープの性質を満たすとき,配列要素 heap[Ø] の値は, この領域での最大の値となっている。そこで,配列要素 heap[Ø] の値と 配列要素 heap[last] の値を交換し,last の値を 1 減らして, 整列対象領域の範囲を狭め,整列済みデータ領域を広げる。値の交換によって, 整列対象領域はヒープの性質を満たさなくなるので,副プログラム downHeap を使って, 整列対象領域のデータがヒープの性質を満たすように再構成する。 これを繰り返すことによって,整列済みデータ領域には昇順に整列されたデータが 格納されることになる。

(3) 副プログラム heapSort の引数の仕様を表3に,副プログラム heapSort で 使用する副プログラム downHeap の引数の仕様を表4に示す。

 

表3 副プログラム heapSort の引数の仕様

 

表4 副プログラム downHeap の引数の仕様

 

〔プログラム2〕

 

〔プログラム2の動作〕

 副プログラム heapSort の行番号 3 の実行が終了した直後のαにおける配列 heap の内容は,図2のとおりであった。このとき,副プログラム heapSort の 行番号 4 から行番号 7 までの1回目の繰返し処理について考える。

 副プログラム heapSort の行番号 5 の副プログラム swap の実行が終了した直後の 配列要素 heap[Ø] の値は, となる。 このため,配列 heap の要素番号 Ø からhnum−2 までのデータは, 根に対応する配列要素 heap[Ø] が最大の値をもつというヒープの性質を満たさなくなる。

 副プログラム heapSort の行番号 6 で呼び出している副プログラム downHeap は, 配列 heap の整列対象領域の要素番号 Ø から hlast までのデータがヒープの性質を 満たすように,その領域のデータを次の手順で再構成する。

(1) 配列要素の値の大きさを比較する際に使用する要素番号を n とし,n の初期値を Ø とする。

(2) 要素番号 n の配列要素に対応する節の左側の子の要素番号を tmp に代入する。 要素番号 n の子が二つあり(rchild(n) ≦ hlast),右側の子の値が 左側の子の値 ,右側の子の要素番号を tmp に代入する。

(3) 子に対応する配列要素 heap[tmp] の値と,その親に対応する配列要素 heap[n] の値とを比較し, 配列要素 heap[tmp] の値が大きければ,配列要素 heap[n] の値と配列要素 heap[tmp] の値を交換し, tmp を次の n として (2) に戻る。ここで,副プログラム downHeap の行番号 15 において最初に n に 代入する tmp の値は, である。

 

c に関する解答群 ア 5       イ 1Ø       ウ 15       エ 2Ø

 

d に関する解答群 ア 以下のときには           イ 以上のときには

ウ よりも大きいときには        エ よりも小さいときには

 

e に関する解答群 ア 1       イ 2       ウ 3

エ 4       オ 5       カ 6

 

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

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

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


[←前の問題] [次の問題→] [問題一覧表] [分野別] [基本情報技術者試験TOP ]