問題
コンピュータでデータ処理を行うために様々なアルゴリズムが提供されている。各種業務に必要な処理内容に照らして適切なものを選択できるように、それらの特性を把握しておく必要がある。
アルゴリズムの特性や処理手順に関する以下の文章の空欄Ａ〜Ｄに入る語句の組み合わせとして、最も適切なものを下記の解答群から選べ。
次に示す2つの並べ替え手順のうち、データ交換や比較の回数が多く並べ替えの実行時間が大きいのは Ａ の方法である。
① 最も小さい(大きい)値を見つけて先頭のデータと交換し、以下残りのデータに対して同様の手順を適用する方法。
② 先頭から順に隣り合うデータを比較して、順序が逆ならば交換する作業を最終データまで行い、最も小さい(大きい)値を末端に移動させ、以下同様の手順を繰り返す方法。
データ探索において、求めるデータが中央のデータより前にあるか後ろにあるかの判定を、範囲を狭めながら繰り返し行う Ｂ では Ｃ を用意する必要がある。
また、ハッシュ法ではハッシュ値に Ｄ を組み込む必要がある。
選択肢
- 1Ａ：① Ｂ：線形探索法 Ｃ：規則性がないデータ Ｄ：衝突が生じた際の処理
- 2Ａ：① Ｂ：二分探索法 Ｃ：規則性がないデータ Ｄ：誤差が含まれた際の処理
- 3Ａ：② Ｂ：線形探索法 Ｃ：順序よく並べたデータ Ｄ：誤差が含まれた際の処理
- 4Ａ：② Ｂ：二分探索法 Ｃ：順序よく並べたデータ Ｄ：衝突が生じた際の処理
正解
4. Ａ：② Ｂ：二分探索法 Ｃ：順序よく並べたデータ Ｄ：衝突が生じた際の処理
詳しい解説を見る解説を閉じる
解説
①は選択ソート（選択法）、②はバブルソート（基本交換法）の説明。両者とも計算量はO(n²)だが、バブルソートは隣接要素の比較・交換を毎回行うためデータ交換・比較回数が選択ソートより多くなる傾向があり、実行時間が大きい。よってＡ＝②。Ｂは中央値と比較して範囲を半分ずつ絞り込む手法で二分探索法（バイナリサーチ）。二分探索法はあらかじめＣ＝順序よく並べたデータ（ソート済みデータ）が必要。ハッシュ法では異なる入力値が同じハッシュ値になる「衝突（コリジョン）」が発生するため、Ｄ＝衝突が生じた際の処理（チェイン法やオープンアドレッシング等）を組み込む必要がある。よって「エ」が正解。（出典: 一般社団法人 中小企業診断協会 平成26年度 中小企業診断士1次試験 経営情報システム 第5問）
中小企業診断士トップ
一問一答・予想問題・まとめノート