今週の午後問題〔解答〕アルゴリズム ヒープの性質を利用したデータの整列 2018 年度 春期
![](https://www.seplus.jp/dokushuzemi/ec/fe/fenavi/wp-content/uploads/2021/10/ans_this_weeks_exercise_h30h_algorithm_cover-640x360.jpg)
error
この記事は基本情報技術者試験の旧制度( 2022 年以前)の記事です。
この記事の題材となっている「午後問題」は現在の試験制度では出題されません。 ご注意くださいませ。
このコーナーでは毎週月曜に午後の必須選択問題から 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 の講評です。今後の参考になれば幸いです。
設問 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 関連タグ免除試験を受けた 74.9% の方が、 科目A免除資格を得ています。
![](https://www.seplus.jp/dokushuzemi/ec/fe/fenavi/wp-content/uploads/2021/11/ans_this_weeks_exercise_h29a_algorithm_cover-150x150.jpg)
今週の午後問題〔解答〕アルゴリズム 文字列の誤りの検出 2017 年度 秋期
update![](https://www.seplus.jp/dokushuzemi/ec/fe/fenavi/wp-content/uploads/2021/10/this_weeks_exercise_h29a_algorithm_cover-150x150.jpg)
今週の午後問題〔問題〕アルゴリズム 文字列の誤りの検出 2017 年度 秋期
update![](https://www.seplus.jp/dokushuzemi/ec/fe/fenavi/wp-content/uploads/2021/10/ans_this_weeks_exercise_h30h_algorithm_cover-150x150.jpg)
今週の午後問題〔解答〕アルゴリズム ヒープの性質を利用したデータの整列 2018 年度 春期
update![](https://www.seplus.jp/dokushuzemi/ec/fe/fenavi/wp-content/uploads/2021/10/cover_this_weeks_exercise_h29h_algorithm-150x150.jpg)
今週の午後問題〔問題〕アルゴリズム ヒープの性質を利用したデータの整列 2018 年度 春期
update![](https://www.seplus.jp/dokushuzemi/ec/fe/fenavi/wp-content/uploads/2021/10/cover_ans_this_weeks_exercise_h29a_algorithm-150x150.jpg)
今週の午後問題〔解答〕アルゴリズム 整数式の解析と計算 2018 年度 秋期
update![](https://www.seplus.jp/dokushuzemi/ec/fe/fenavi/wp-content/uploads/2021/10/cover_this_weeks_exercise_h29a_algorithm-150x150.jpg)
今週の午後問題〔問題〕アルゴリズム 整数式の解析と計算 2018 年度 秋期
update![](https://www.seplus.jp/dokushuzemi/ec/fe/fenavi/wp-content/uploads/2021/10/cover_ans_this_weeks_exercise_h30h_algorithm-150x150.jpg)
今週の午後問題〔解答〕アルゴリズム ハフマン符号化を用いた文字列圧縮 2019 年度 春期
update![](https://www.seplus.jp/dokushuzemi/ec/fe/fenavi/wp-content/uploads/2021/10/cover_this_weeks_exercise_h30h_algorithm-150x150.jpg)
今週の午後問題〔問題〕アルゴリズム ハフマン符号化を用いた文字列圧縮 2019 年度 春期
update![](https://www.seplus.jp/dokushuzemi/ec/fe/fenavi/wp-content/uploads/2021/10/cover_ans_this_weeks_exercise_h29a_sec-150x150.jpg)
今週の午後問題〔解答〕情報セキュリティ SSH による通信 2017 年度 秋期
update![](https://www.seplus.jp/dokushuzemi/ec/fe/fenavi/wp-content/uploads/2021/09/cover_this_weeks_exercise_h29a_sec-150x150.jpg)
今週の午後問題〔問題〕情報セキュリティ SSH による通信 2017 年度 秋期
update![](https://www.seplus.jp/dokushuzemi/fe/fenavi/wp-content/uploads/2019/10/icon_fenavi.png)
- 基本情報技術者試験 の受験勉強をレポート頂ける方を募集中です!
- ツイッター で過去問を配信しています
姉妹サイト 「IT資格の歩き方」 では応用情報技術者以上の情報処理技術者試験の対策記事があります!
基本情報技術者試験を合格されたら、「IT資格の歩き方」で末永く、スキルアップにお役立てください!