基本情報技術者試験 - 平成30年春期(科目B) - 問8

問題

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

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



〔プログラム1の説明〕
(1) 配列の要素番号は,0から始まる。
(2) 副プログラム makeHeap は,整数型の1次元配列 data に格納されている hnum 個(hnum>0)のデータを,次の①~③の規則で整数型の1次元配列 heap に格納して,ヒープを配列で実現する。この状態を,“配列 heap は,ヒープの性質を満たしている” という。
① 配列要素 heap[i](i=0,1,2,…)は,節に対応する。配列要素 heap[i] には,節が保持する値を格納する。
② 配列要素 heap[0] は,根に対応する。
③ 配列要素 heap[i](i=0,1,2,…)に対応する節の左側の子は配列要素 heap[2×i+1] に対応し,右側の子は配列要素 heap[2×i+2] に対応する。子が一つの場合,左側の子として扱う。
(3) 図1のヒープの例に対応した配列heapの内容を,図2に示す。


(4) 親の要素番号と子の要素番号を関係付ける三つの関数がある。
①整数型:lchild(整数型:i)
 要素番号iの配列要素に対応する節の左側の子の配列要素の要素番号 2×i+1 を計算して返却する。
②整数型:rchild(整数型:i)
 要素番号iの配列要素に対応する節の右側の子の配列要素の要素番号 2×i+2 を計算して返却する。
③整数型:parent(整数型:i)
 要素番号iの配列要素に対応する節の親の配列要素の要素番号(i-1)÷2(小数点以下切捨て)を計算して返却する。
(5) 副プログラム swap は,二つの配列要素に格納されている値を交換する。
(6) 副プログラム makeHeap の引数の仕様を表1に,副プログラム swap の引数の仕様を表2に示す。

表1 副プログラムmakeHeapの引数の仕様
引数データ型入出力説明
data[]整数型入力データが格納されている1次元配列
heap[]整数型出力ヒープの性質を満たすようにデータを格納する1次元配列
hnum整数型入力データの個数
表2 副プログラムswapの引数の仕様
引数データ型入出力説明
heap[]整数型入力/出力交換対象のデータが格納されている1次元配列
i整数型入力交換対象の要素番号
j整数型入力交換対象の要素番号


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

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

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



(2) 整列対象領域がヒープの性質を満たすとき,配列要素 heap[0] の値は,この領域での最大の値となっている。そこで,配列要素 heap[0] の値と配列要素 heap[last] の値を交換し,last の値を1減らして,整列対象領域の範囲を狭め,整列済みデータ領域を広げる。値の交換によって,整列対象領域はヒープの性質を満たさなくなるので,副プログラム downHeap を使って,整列対象領域のデータがヒープの性質を満たすように再構成する。これを繰り返すことによって,整列済みデータ領域には昇順に整列されたデータが格納されることになる。
(3) 副プログラム heapSort の引数の仕様を表3に,副プログラム heapSort で使用する副プログラム downHeap の引数の仕様を表4に示す。
表3 副プログラムheapSortの引数の仕様
引数データ型入出力説明
data[]整数型入力整列対象のデータが格納されている1次元配列
heap[]整数型出力整列済みのデータを格納する1次元配列
hnum整数型入力データの個数
表4 副プログラムdownHeapの引数の仕様
引数データ型入出力説明
heap[]整数型入力/出力整列対象のデータを格納する1次元配列
hlast整数型入力整列対象領域の最後の要素番号



〔プログラム2の動作〕
 副プログラム heapSort の行番号3の実行が終了した直後のαにおける配列 heap の内容は,図2のとおりであった。このとき,副プログラム heapSort の行番号4から行番号7までの1回目の繰返し処理について考える。
 副プログラム heapSort の行番号5の副プログラム swap の実行が終了した直後の配列要素 heap[0] の値は,[ c ] となる。このため,配列 heap の要素番号0から hnum-2 までのデータは,根に対応する配列要素 heap[0] が最大の値をもつというヒープの性質を満たさなくなる。
 副プログラム heapSort の行番号6で呼び出している副プログラム downHeap は,配列 heap の整列対象領域の要素番号0から hlast までのデータがヒープの性質を満たすように,その領域のデータを次の手順で再構成する。
(1) 配列要素の値の大きさを比較する際に使用する要素番号をnとし,nの初期値を0とする。
(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に関する解答群
ア5
イ10
ウ15
エ20

dに関する解答群
ア以下のときには
イ以上のときには
ウよりも大きいときには
エよりも小さいときには

eに関する解答群
ア1
イ2
ウ3
エ4
オ5
カ6

正解と解説

正解設問1 (a)イ (b)エ 設問2 (c)エ (d)イ (e)イ 
分野テクノロジ系 › 基礎理論 › アルゴリズムとプログラミング › アルゴリズム

解説

■ この問題のテーマ

 ヒープとは,「親の値が子の値以上」という性質をもつ二分木です。この性質から,根(一番上)には必ず最大値が入ります。ヒープソートは,「根の最大値を取り出して末尾に置き,残りを再びヒープに整える」という操作を繰り返してデータを並べる方法です。
この
 問題では,ヒープを配列で表し,要素番号iの節の子を2×i+1(左)と2×i+2(右),親を(i-1)÷2で求めます。

■ 設問1

 makeHeapは,データを1個ずつ配列の末尾に追加し,そのデータを親と比べながら上へ移動させてヒープの性質を保ちます。

[空欄a]

 追加したデータ(heap[k])が親の値より大きいときは,ヒープの性質に反するので親と交換します。条件は「heap[k]>heap[parent(k)]」です。そうでなければ正しい位置にあるので,繰返しを抜けます(break)。正解は「イ」です。

[空欄b]

 交換する相手は親なので,parent(k)です。交換後は,kを親の位置に移して比較を続けます。正解は「エ」です。

■ 設問2

 heapSortの1回目の繰返しを,図2の配列 60,30,45,15,5,10,20 で追跡します。

[空欄c]

 swap(heap,0,last)で,根のheap[0](60)と末尾のheap[6](20)を交換します。heap[0]は20になります。正解は「エ」です。

[空欄d]

 downHeapの行番号7では,heap[tmp](左の子)≦heap[rchild(n)](右の子)のとき,tmpを右の子にしています。つまり,右の子の値が左の子の値「以上のときには」右の子を選びます。正解は「イ」です。

[空欄e]

 downHeap(heap,5)を,配列 20,30,45,15,5,10 で実行します。
  • n=0の左の子は要素番号1(30),右の子は要素番号2(45)です。30≦45なので,tmp=2になります。
  • heap[2](45)>heap[0](20)なので交換し,配列は 45,30,20,15,5,10 になります。
  • 行番号15で,n←tmpとしてnに2が代入されます。
 正解は「イ」です。
ホーム画面への追加方法
1.ブラウザの 共有ボタンのアイコン 共有ボタンをタップ
2.メニューの「ホーム画面に追加」をタップ
閉じる