基本情報技術者試験 基本情報技術者試験 平成29年度 春期 午前 午前 問7: 顧客番号をキーとして顧客データを検索する場合，2 分探索を使用するのが適しているものはどれか。

問題本文

顧客番号をキーとして顧客データを検索する場合，2 分探索を使用するのが適しているものはどれか。

選択肢

• ア.顧客番号から求めたハッシュ値が指し示す位置に配置されているデータ構造
• イ.顧客番号に関係なく，ランダムに配置されているデータ構造
• ウ.顧客番号の昇順に配置されているデータ構造
• エ.顧客番号をセルに格納し，セルのアドレス順に配置されているデータ構造

正解

ウ. 顧客番号の昇順に配置されているデータ構造

解説

2 分探索はソート済みデータを前提に半分ずつ絞り込む。顧客番号の昇順配置データが必須条件。ウが正解。

選択肢ごとの解説

• ア.ハッシュ配置はハッシュ検索 (O(1)) 用で、2 分探索には適さない。
• イ.ランダム配置では順序がないため 2 分探索不能。
• ウ.昇順配置だと中央値比較で範囲を半減できる。2 分探索の前提で正解。
• エ.セルアドレス順は格納位置の順序であり、検索キー (顧客番号) の順とは異なる。