令和5年度 問69
探索アルゴリズム
出典: 令和5年度 ITパスポート試験 公開問題 問69 (IPA)
配列に格納されているデータを探索するときの，探索アルゴリズムに関する記述のうち，適切なものはどれか。
- ア 2 分探索法は，探索対象となる配列の先頭の要素から順に探索する。
- イ 線形探索法で探索するのに必要な計算量は，探索対象となる配列の要素数に比例する。
- ウ 線形探索法を用いるためには，探索対象となる配列の要素は要素の値で昇順又は降順にソートされている必要がある。
- エ 探索対象となる配列が同一であれば，探索に必要な計算量は探索する値によらず，2 分探索法が線形探索法よりも少ない。
正解と解説を見る
正解: イ
- ア: 先頭から順に探すのは線形探索法です。2 分探索法は真ん中から探します。
- イ: 線形探索法は最大で要素数と同じ回数調べるので、計算量は要素数に比例します。正しい答えです。
- ウ: 線形探索法は、並べ替えられていなくても使えます。ソートが必要なのは 2 分探索法です。
- エ: 探す値によっては、線形探索法が先頭で見つかり、少ない回数で済むことがあります。常に 2 分探索法が少ないとは限りません。
ポイント
- 線形探索法: 先頭から順に 1 つずつ調べる方法。要素数が n なら、最大 n 回調べるので、計算量は要素数に比例します。ソートされていなくても使えます。
- 2 分探索法: 昇順や降順に並んだ配列の真ん中と比べ、探す範囲を半分ずつ絞る方法。要素数が多いほど線形探索より有利です。
広告
「アルゴリズムとプログラミング」をこのサイトで解く (記録・間違えた問題の解き直し・AI教師への質問)
広告