基本情報技術者過去問題 平成30年春期 午後問8 設問2　解説

「heapSort」をトレース

このプログラムは「本プログラム heapSort」から、副プログラム「makeHeap」と「downHeap」を順に呼び出して、数列を昇順（小さい順）に整列させます。
３行目の「makeHeap」が終わった時点で、各関数の数値は以下のようになっています。

heap[]
[0] [1] [2] [3] [4] [5] [6]
60 30 45 15 5 10 20

hnum = 7

4行目からトレースします。

・last:hnum-1, last ＞ 0, -1
last の初期値を hnum-1 として、繰り返すごとに -1　しながら、 0 より大きい間ループします。

last
6

・swap(heap, 0, last)
最大の数値であることが確定しているheap[0]を数列のお尻に移動します。

heap[]
[0] [1] [2] [3] [4] [5] [6]
60 20 30 45 15 5 10 20 60

空欄cはエです。

downHeapをトレースする

「makeHeap」の６行目を見ると「downHeap」に「heap」と「last-1」を入れています。
「downHeap」の１行目で「heap[]」と「hlast」として受けていますので、hlast の初期値は 5 になります。
n tmp hlast
　 　 5

・n ← 0
n tmp hlast
0 　 5

・lchild(n) ＜＝ hlast
左の子が整列対象領域内のあいだ、５行目から１５行目の処理をループします。

・tmp ← lchild(n)
n tmp hlast
0 1 5

・rchild(n) ＜＝ hlast
右側の子が整列対象領域内で、

・heap[tmp] ＜＝ heap[rchild(n)]
右側の子が左側の子以上だった場合、

・tmp ← rchild(n)
を実行します。

n tmp hlast
0 1 2 5

空欄dはイです。

・heap[tmp] ＞ heap[n]
最大の子と親を比べ、子のほうが大きいときは上の処理をします。

・swap(heap, n, tmp)
親と子を交換します。
heap[]
[0] [1] [2] [3] [4] [5] [6]
60 20 45 30 45 20 15 5 10 20 60

・n ← tmp
n tmp hlast
0 2 1 2 5

空欄eはイです。

「downHeap」のループ２回目

設問は以上で終わりですが、以下にその後の処理を記します。

・lchild(n) ＜＝ hlast
左の子が整列対象領域内なので５行目以降の処理をします。

・tmp ← lchild(n)
n tmp hlast
0 2 1 2 5 5

・rchild(n) ＜＝ hlast
右側の子が整列対象領域内ではないので内側の処理はしません。

・heap[tmp] ＜＝ heap[rchild(n)]
左側の子が親以上ではないので、下の処理をします。
「downHeap」を抜けます。

「heapSort」のループ２回目

heap[]
[0] [1] [2] [3] [4] [5] [6]
60 20 45 10 30 45 20 15 5 10 45 20 60

last
6 5

２回目の「downHeap」

heap[]
[0] [1] [2] [3] [4] [5] [6]
60 20 45 10 30 30 10 45 20 15 5 10 45 20 60

heap[]
[0] [1] [2] [3] [4] [5] [6]
60 20 45 10 30 30 10 15 45 20 15 10 5 10 45 20 60

「heapSort」のループ３回目

heap[]
[0] [1] [2] [3] [4] [5] [6]
60 20 45 10 30 5 30 10 15 45 20 15 10 5 30 10 45 20 60

last
6 5 4

３回目の「downHeap」

heap[]
[0] [1] [2] [3] [4] [5] [6]
60 20 45 10 30 5 20 30 10 15 45 20 5 15 10 5 30 10 45 20 60

「heapSort」のループ４回目

heap[]
[0] [1] [2] [3] [4] [5] [6]
60 20 45 10 30 5 20 10 30 10 15 45 20 5 15 10 20 5 30 10 45 20 60

last
6 5 4 3

４回目の「downHeap」

heap[]
[0] [1] [2] [3] [4] [5] [6]
60 20 45 10 30 5 20 10 15 30 10 15 10 45 20 5 15 10 20 5 30 10 45 20 60

「heapSort」のループ５回目

heap[]
[0] [1] [2] [3] [4] [5] [6]
60 20 45 10 30 5 20 10 15 5 30 10 15 10 45 20 5 15 15 10 20 5 30 10 45 20 60

last
6 5 4 3 2

５回目の「downHeap」

heap[]
[0] [1] [2] [3] [4] [5] [6]
60 20 45 10 30 5 20 10 15 5 10 30 10 15 10 5 45 20 5 15 15 10 20 5 30 10 45 20 60

「heapSort」のループ６回目

heap[]
[0] [1] [2] [3] [4] [5] [6]
60 20 45 10 30 5 20 10 15 5 10 5 30 10 15 10 5 10 45 20 5 15 15 10 20 5 30 10 45 20 60

last
6 5 4 3 2 1

６回目の「downHeap」

変化なし

以上です。
heap[0]から[6]まで、小さい順に並べなおすことができました。

ホームに戻るボタン↓