今週の午後問題〔解答〕アルゴリズム ヒープの性質を利用したデータの整列 2018 年度 春期

今週の午後問題

このコーナーでは毎週月曜に午後の必須選択問題から 1 問ピックアップして出題し、 解答欄 を設け、読者の皆さまにも解答してもらっています!

今週の午後問題は「ヒープの性質を利用したデータの整列」でしたが、皆さん、手応えはいかがでしょうか?

金曜になりましたので、出題の 解答 と 矢沢久雄さんによる 解説 に加えて、皆さんの正解率を公開します。

今週の午後問題
2018 年度 春期 ヒープの性質を利用したデータの整列

解答と解説

設問 1a

正解

heap の末端に追加されたデータは、そのデータが親より大きい限り、データと親を交換することを繰り返します。

したがって、空欄 a は、「データ > 親」を意味する heap[k] > heap[parent(k)] が適切です。

設問 1b

正解

heap[k] と heap[parent(k)] の値を交換するので、 swap(heap, h, parent(k)) が適切です。

空欄 b には、 parent(k) が入ります。

設問 2c

正解

1 回目の処理では、 last = 6 であり副プログラム swap によって、 heap[0] の 60 と、 heap[6] の 20 が交換されます。

したがって、 heap[0] の値は、 20 になります。

設問 2d

正解

この部分の説明は、副プログラム downHeap の 7 行目の

heap[tmp] ≦ heap[rchild(n)]

に該当します。 5 行目で tmp に lchild(n) を代入しているので、 7 行目は

heap[lchild(n)] ≦ heap[rchild(n)]

と同じです。

したがって、

右側の子が左側の子以上のときには

という条件になります。

設問 2e

正解

1 回目の処理では、 heap[0] の左側の子が heap[1] = 30 で、右側の子が heap[2] = 45 です。

| ▲ heap[tmp] > heap[n]
| | ・ swap (heap, n, tmp)
| +---
| | ・ return                /* downHeap から抜ける */
| ▼
| ・ n ← tmp

これは、

右側の子が左側の子以上のときには

という条件に一致するので、 15 行目では tmp に右側の子の要素番号の 2 が格納されています。

みんなの解答

ご解答いただいた皆さん、ありがとうございました!

手応えはいかがでしたでしょうか?

 

なお、以下はこの問題の IPA の講評です。今後の参考になれば幸いです。

 問 8 では,整数型のデータを,ヒープの性質を満たすように配列に格納(ヒープを配列で実現)する処理,配列に格納した整数型のデータをヒープソートで昇順に整列する処理について出題した。
 設問 1 の正答率は平均的で,おおむね理解されていた。ヒープの構造と配列 heap に格納されるデータの関係を理解し,配列 heap にデータを追加する位置が,対応する親の値との関係で,どのように決まるのかを理解すれば,正答できた。
 設問 2 では, c の正答率は平均的で,おおむね理解されていた。プログラムの動作の説明と配列に格納されているデータを対応付ければ,正答できた。 d, e の正答率は低く,あまり理解されていなかった。d ではウと, e ではオと誤って解答した受験者が見受けられた。 d は,副プログラム downHeap の行番号 5 ~ 10 で使われている変数及び関数と行番号 7 の条件式で使われている関係演算子に着目すれば,正答できた。 e は,変数 n の値が 0 で配列 heap の要素番号 1 ~ 5 の内容が図 2 のとおりであることに着目して,副プログラム downHeap の行番号 5 ~ 10 の処理を追跡すれば,正答できた。
 プログラムでアルゴリズムが正しく実現されていることを確認するためには,プログラムの説明とプログラム中で使用されている変数の意味や処理の条件を対応付けてプログラムの動きを追跡する能力が求められるので,身につけておいてほしい。

来週は「アルゴリズム特集」の最終問題です! 試験期間が残りわずかになるので、腕試ししてみてください!

label 関連タグ
Q. 午前試験を
『免除』するには?
A. 独習ゼミで午前免除制度を活用しましょう。
免除試験を受けた 86% の方が、
1 年間の午前免除資格を得ています。
2022 年 下期 試験向け
コース資料公開中!
info_outline
2022 年 下期 試験向け
コース資料公開中!
詳しく見てみるplay_circle_filled
label これまでの『今週の午後問題』の連載一覧 label 著者