問1. 未整列の配列に格納された10万件の商品IDを、先頭から順に比較する線形探索で検索している。検索対象の商品IDが配列に存在しない場合の処理時間が問題となった。このときの比較回数と、その理由を説明したものとして最も適切なものはどれか。
- 比較回数は最大10万回であり、一致する要素が見つからないことを確認するには全要素との比較が必要になる。
- 比較回数は最大約17回であり、各比較後に探索対象を半分に分割できる。
- 比較回数は常に1回であり、商品IDから配列上の格納位置を直接計算できる。
- 比較回数は最大5万回であり、一致する要素が存在しなければ配列の中央で探索を終了できる。
問2. n個の要素を格納した未整列配列を線形探索する。検索の80%では目的の要素が配列内に存在し、その位置は各要素について同じ確率である。残り20%では目的の要素が存在しない。比較は先頭要素から開始するとき、1回の検索当たりの期待比較回数として最も適切なものはどれか。
- 0.4n＋0.4回
- 0.6n＋0.4回
- 0.8n＋0.2回
- n回
問3. 社員番号を格納した配列に対して二分探索を適用する設計を検討している。配列の中央要素の社員番号が検索対象より小さい場合に、中央要素以前を次の探索対象から除外できる理由として最も適切なものはどれか。
- 配列が社員番号の昇順に整列されているため、中央要素以前には検索対象より大きい社員番号が存在しないから。
- 配列が社員番号の昇順に整列されているため、中央要素以前の値は全て中央要素以下であり、検索対象とは一致しないから。
- 中央要素を調べた時点で、配列内に検索対象が存在することが保証されるから。
- 社員番号から配列添字を計算できるため、中央要素以前を比較せずに直接目的位置へ移動できるから。