SC情報処理安全確保支援士試験 午前Ⅰ
平成28年度秋期 情報処理安全確保支援士 午前Ⅰ 問3
問題文と選択肢を読んで答えを考えてから、下の「正解と解説を見る」で確認しましょう。
問題
選択肢
- アある間隔おきに取り出した要素から成る部分列をそれぞれ整列し,更に間隔を詰めて同様の操作を行い,間隔が1になるまでこれを繰り返す。
- イ中間的な基準値を決めて,それよりも大きな値を集めた区分と,小さな値を集めた区分に要素を振り分ける。次に,それぞれの区分の中で同様な処理を繰り返す。
- ウ隣り合う要素を比較して,大小の順が逆であれば,それらの要素を入れ替えるという操作を繰り返す。
- エ未整列の部分を順序木にし,そこから最小値を取り出して整列済の部分に移す。この操作を繰り返して,未整列の部分を縮めていく。
解き方のヒントを見る
ヒープは“親子の順番ルール”を守りながら並べ替えよう
ヒープソートでは、いちばん上にいる根の要素を末尾へ移してから、残った要素でまたヒープの形に整え直すよ。たとえるなら、リーダーを列の最後に確定席として移して、残りのメンバーで“親は子より大きい(または小さい)”というルールを守るように並び直すイメージです。
この問題で問われていること
ただ何回交換するかを見る問題ではなく、ヒープが持つ親子関係の大小ルールと、根を取り出した後に再ヒープ化する流れを理解できているかがポイントです。
Heapsort
heapsort repeatedly removes the root from a heap and rebuilds the heap to produce a sorted sequence
build heap\nremove root\nreheapify
確認ポイント
- 二分探索木とは別物です。
- 根の取り出し後に再ヒープ化する。
- ヒープ条件を押さえる。
正解と解説を見る
正解
エ
解説
ヒープソートは、未整列の部分を順序木(ヒープ)に構成し、根から最小値を取り出して整列済の部分に移す操作を繰り返す整列法です。したがって正解はエであり、アはシェルソート、イはクイックソート、ウはバブルソートの説明です。
理由
ヒープソートでは、未整列のデータを順序木(ヒープ)に構成します。親の値が子の値以下になる条件を満たす木を作成すると、根に最小値が配置されます。その最小値を取り出して整列済の部分に移し、残りのデータを再び順序木に再構成する操作を繰り返すことで、未整列の部分を縮めて整列を完了させます。選択肢エの記述はこの手順と一致しています。
比較
他の選択肢はいずれも異なる整列法を説明しています。アは一定間隔の部分列を整列しながら間隔を詰めていくシェルソート、イは基準値(ピボット)を決めて大小の区分に振り分けるクイックソート、ウは隣り合う要素を比較・交換するバブルソートです。いずれも順序木を構成して最小値を取り出す手法ではないため、ヒープソートの説明には該当しません。
選択肢ア
これは不正解です。一定の間隔おきに取り出した要素から成る部分列をそれぞれ整列し、間隔を詰めながら最後は間隔1で仕上げる方法はシェルソートの説明です。離れた要素同士をあらかじめ大まかに並べておく手法であり、順序木を作って根から最小値を順に取り出していくヒープソートの手順とは異なるよ。
選択肢イ
これは不正解です。中間的な基準値(ピボット)を決め、それより大きい値と小さい値の区分に要素を振り分けてそれぞれの区分で同様の処理を繰り返すのはクイックソートの説明です。分割統治法を用いて区分を細かくしていく手法であり、未整列データを順序木にして最小値を取り出すヒープソートとは別物です。
選択肢ウ
これは不正解です。隣り合う要素を比較し、大小の順が逆であれば入れ替える操作を繰り返すのはバブルソート(隣接交換法)の説明です。比較の対象は常に隣り合う2要素であり、木構造は利用しないよ。未整列部分を順序木にして根から最小値を取り出していくヒープソートの説明には当たらないよ。
選択肢エ(正解)
これは正解です。ヒープソートでは、未整列の部分を順序木(親の値が子の値以下になるヒープ)に構成し、根にある最小値を取り出して整列済の部分に移すよ。残った要素を再び順序木に整える操作を繰り返して未整列の部分を縮めていくため、記述内容はヒープソートの手順として適切です。
学習のポイント
ヒープソート、シェルソート、クイックソート、バブルソートの各整列アルゴリズムの手順と特徴を整理し、正しく区別できるようにしましょう。
解説を確認したら、演習モードや同じ分野の類題で理解を定着させましょう。
出典:独立行政法人 情報処理推進機構(IPA)平成28年度秋期 情報処理安全確保支援士試験 午前Ⅰ 問3(公式資料:問題冊子(PDF) / 解答例)
関連する過去問一覧
IPA Advancedは非公式の学習サイトです。解説にはAIによる補助生成を含む場合があります。公式の問題冊子・解答例・採点講評を優先し、誤りは確認後に訂正します。運営・編集方針