共通テスト情報Ⅰ・4-11

探索アルゴリズムの一問一答

共通テスト「情報Ⅰ」の「アルゴリズムとプログラミング」から、探索アルゴリズムに関する4択問題を10問。「答えと解説を見る」を開くと、正解とその理由がその場で読めます。会員登録は不要です。

この分野の演習

全10問／解説付き・基本無料

アプリ形式で解く（全800問）アルゴリズムとプログラミングの要点解説を読む

問題

上から順に解いてみてください。答えは各問の下で確認できます。

問14-11・基礎

図のように、データが整列されていない状態でも使用でき、先頭から順に目的のデータを探していく探索手法はどれか？

自作の図

①線形探索法（リニアサーチ）
②二分探索法（バイナリサーチ）
③ハッシュ探索法
④木構造探索法

答えと解説を見る

正解 ①線形探索法（リニアサーチ）

解説
正解は「線形探索法（リニアサーチ）」。先頭から1つずつ順に比べていく探し方。

なぜ
図のデータ（7, 3, 9, 1, 5, 8）から5を探すなら、7、3、9、1、5の順に比べて5回目で見つかる。順番に全部見ていくので、データが並んでいなくても使える。その代わり、データが多いと時間がかかる。N 個のデータなら、比較回数は最大で N 回。目的の値が必ずあり、どの位置も同じ確率なら、平均は (N＋1)÷2 回。

ひっかけ注意

・「二分探索法（バイナリサーチ）」…真ん中と比べて範囲を半分にする方法。データが昇順か降順に整列していないと使えない。1,000個なら最大10回。
・「ハッシュ探索法」…ハッシュ関数という計算式で格納場所を求める方法。データを入れるときにも同じ計算で場所を決めておく。衝突がなければ1回で見つかる。
・「木構造探索法」…データを木の形（親と子のつながり）に整理しておき、根から枝をたどって探す方法。前もって整理する準備が要る点が線形探索との違い。

問24-11・基礎

図のように、データが「昇順（または降順）」に並んでいる場合にのみ使用でき、探索範囲を半分ずつ絞り込む高速な探索手法はどれか？

自作の図

①線形探索法（リニアサーチ）
②二分探索法（バイナリサーチ）
③全探索法（ブルートフォース）
④幅優先探索法

答えと解説を見る

正解 ②二分探索法（バイナリサーチ）

解説
正解は「二分探索法（バイナリサーチ）」。真ん中の値と比べ、探す値がどちら側にあるかで範囲を半分に減らしていく方法。

なぜ
図のデータ（2, 5, 8, 12, 16, 23, 38）から23を探すなら、まず真ん中の12と比べ、23は12より大きいので右半分（16, 23, 38）だけを調べればよい。データが大きさの順に並んでいるので、真ん中より小さいか大きいかで、片方の半分をまとめて捨てられる。100万個でも最大20回の比較で済む（2の20乗は約105万）。ただし、並べ替えておく手間が前もって必要になる。

ひっかけ注意

・「線形探索法（リニアサーチ）」…先頭から順に1つずつ比べる方法。並んでいなくても使えるが、100万個なら最大100万回かかる。
・「全探索法（ブルートフォース）」…考えられる候補をすべて順に調べる方法。4けたの暗証番号なら0000〜9999の1万通りを試す。
・「幅優先探索法」…グラフや木で、出発点に近いところから順に広げて調べる方法。迷路で最短の道を探すときなどに使う。

問34-11・基礎

二分探索法を用いて、整列済みのデータ1,000個の中から特定のデータを探す場合、最大で約何回の比較が必要か？

①約50回
②約500回
③約10回
④約1000回

答えと解説を見る

正解 ③約10回

解説
正解は「約10回」。1回比べるごとに候補がほぼ半分になるので、2を何回掛ければ1,000をこえるかを考える。

手順
①比べるたびに、残りの候補は 1,000 → 約500 → 約250 → … と半分ずつ減る。
②2の9乗＝512 は1,000より小さく、2の10乗＝1,024 は1,000より大きい。
③そのため最大でも10回の比較で、見つかるか、ないことが分かる（中央は（左端＋右端）÷2 の商で決める）。

ひっかけ注意

・「約50回」…1,000÷20 のような割り算で考えた値。二分探索の回数は、2を何回掛けるかで決まる。
・「約500回」…線形探索で見つかるまでの平均の回数（(1,000＋1)÷2＝500.5回）に近い。
・「約1000回」…線形探索の最大の回数。目的の値が最後にあるときや、ないときにデータ数と同じだけ比べる。

問44-11・基礎

探索キーの値から計算式（関数）を使ってデータの格納場所（アドレス）を直接求め、ほぼ1回でアクセスする手法はどれか？

①二分探索法
②線形探索法
③深さ優先探索法
④ハッシュ探索法

答えと解説を見る

正解 ④ハッシュ探索法

解説
正解は「ハッシュ探索法」。探す値をハッシュ関数という計算式に入れ、出てきた番号の場所を直接見る方法。（情報Ⅰの範囲を少し超えた発展の内容です）

なぜ
例えば会員番号を10で割った余りを格納場所の番号にしておけば、探すときも同じ計算で場所がすぐ分かる。ただし、違う値が同じ場所になる衝突が起きると、その分の手間が増える。

ひっかけ注意

・「二分探索法」…整列したデータで、範囲を半分ずつ減らす方法。1,000個なら最大10回比べるので、ほぼ1回にはならない。
・「線形探索法」…先頭から順に1つずつ比べる方法。データ数 N に対して最大 N 回かかる。
・「深さ優先探索法」…グラフや木で、行けるところまで進んでから1つもどり、別の道を調べる方法。

問54-11・基礎

線形探索法において、探しているデータが「最後の1個」だった場合、または「存在しなかった」場合の比較回数はどうなるか？

①データ数 N と同じ回数
②データ数 N の半分の回数
③データ数に関わらず1回
④データ数 N の2乗の回数

答えと解説を見る

正解 ①データ数 N と同じ回数

解説
正解は「データ数 N と同じ回数」。すべてのデータと1回ずつ比べるので N 回になる。

なぜ
最後の1個なら、そこにたどり着くまでに N 回比べる。存在しない場合も、最後まで見ないとないと言い切れないので N 回。これが線形探索でいちばん時間がかかる場合（最悪の場合）。

ひっかけ注意

・「データ数 N の半分の回数」…目的の値が必ずあり、どの位置も同じ確率のときの平均の目安。正確には (N＋1)÷2 回。
・「データ数に関わらず1回」…先頭で見つかったときだけの、いちばん少ない場合（最良の場合）。
・「データ数 N の2乗の回数」…二重の繰り返しで全部の組を比べるような処理の回数。N が2倍なら4倍に増える。

問64-11・基礎

探索アルゴリズムの終了条件として、「データが見つかった場合」以外に設定しなければならない条件はどれか？

①比較回数が100回を超えた場合
②探索範囲のデータが無くなった場合
③データの値が負の数になった場合
④メモリ容量がいっぱいになった場合

答えと解説を見る

正解 ②探索範囲のデータが無くなった場合

解説
正解は「探索範囲のデータが無くなった場合」。探す相手がもう残っていなければ、見つからなかったとして終わる必要がある。

なぜ
探す値がデータの中にないこともある。その場合に止まる条件がないと、範囲の外を読みに行ったり、繰り返しが終わらなかったりする。そのため二分探索では、探す範囲の左端が右端以下である間だけ繰り返し、左端が右端をこえたら「見つからない」として終わる。

ひっかけ注意

・「比較回数が100回を超えた場合」…データが多ければ100回をこえても探す必要がある。線形探索なら1,000個で最大1,000回。
・「データの値が負の数になった場合」…値の正負は、探す範囲が残っているかとは関係がない。-5 のような負の値も探す対象になる。
・「メモリ容量がいっぱいになった場合」…探索はデータを読んで比べるだけで、記憶領域を増やし続けない。止める条件にすべきなのは範囲が残っていない場合。

問74-11・基礎

文字列の中から特定の文字の並び（部分文字列）を探し出す探索アルゴリズム（KMP法やBM法など）を、一般に何と呼ぶか？

①ソート
②ハッシュ化
③パターンマッチング
④エンコーディング

答えと解説を見る

正解 ③パターンマッチング

解説
正解は「パターンマッチング」。文字列照合とも呼び、長い文字列の中から決まった並びを探す処理。（情報Ⅰの範囲を少し超えた発展の内容です）

なぜ
文書の検索機能などで使われる。先頭から1文字ずつずらして比べる単純な方法のほか、KMP 法や BM 法のように、合わなかったときに比べる位置を大きくずらして速くする方法がある。

ひっかけ注意

・「ソート」…データを大きさや50音などの順に並べ替えること（整列）。探すのではなく並べる処理。
・「ハッシュ化」…データをハッシュ関数で決まった長さの値に変えること。例：SHA-256 は、どんな長さのデータも256ビットの値にする。
・「エンコーディング」…文字などを決まった規則で符号に変えること。例：UTF-8 では、ひらがな1文字を3バイトで表す。

問84-11・標準

探索木（特に二分探索木）において、目的のデータを見つけるためにルート（根）からノードを辿っていく際の計算量はどうなるか？（木がバランス良く構成されている場合）

①O(n)
②O(n²)
③O(1)
④O(log n)

答えと解説を見る

正解 ④O(log n)

解説
正解は「O(log n)」。バランスのよい二分探索木では、1段下がるごとに候補がほぼ半分になる。（情報Ⅰの範囲を少し超えた発展の内容です）

なぜ
二分探索木は、左の子には小さい値、右の子には大きい値を置く。根から比べて左か右に進むたびに、もう片方をまとめて調べなくてよくなる。段の数はおよそ log n なので、比べる回数も log n 程度。

ひっかけ注意

・「O(n)」…木が一直線にかたよった場合の計算量。n 個なら最大 n 回比べ、線形探索と同じになる。
・「O(n²)」…二重の繰り返しなどの計算量。n が2倍なら4倍に増え、木を1本の道でたどる探索ではこうならない。
・「O(1)」…データ数によらず一定の手間。ハッシュ探索で衝突がない場合などが当たる。

問94-11・基礎

ハッシュ探索法において、異なるキーから同じハッシュ値（格納場所）が計算されてしまう現象を何と呼ぶか？

①衝突（コリジョン）
②オーバーフロー
③デッドロック
④フラグメンテーション

答えと解説を見る

正解 ①衝突（コリジョン）

解説
正解は「衝突（コリジョン）」。違うデータに同じ格納場所が割り当てられてしまうこと。（情報Ⅰの範囲を少し超えた発展の内容です）

なぜ
格納場所の数は限られているので、衝突は起こりうる。起きたら、空いている別の場所に入れる方法（オープンアドレス法）や、同じ場所にリストでつなぐ方法（チェイン法）で対処する。

ひっかけ注意

・「オーバーフロー」…値や量が、用意された範囲や容量をこえること。例：符号なし8ビットで255に1を足す場合。
・「デッドロック」…2つ以上の処理が、たがいに相手の使っている資源を待ち続け、どちらも進めなくなること。
・「フラグメンテーション」…記憶領域が細切れになること。空きの合計は足りていても、連続した領域が取れないために使えなくなる。

問104-11・基礎

幅優先探索や深さ優先探索など、迷路の探索やネットワークの経路探索に使われる、頂点と辺で表すデータ構造はどれか？

①配列
②グラフ
③スタック
④ハッシュ表

答えと解説を見る

正解 ②グラフ

解説
正解は「グラフ」。点（頂点・ノード）と、それを結ぶ線（辺・エッジ）で、ものどうしのつながりを表すデータ構造。（情報Ⅰの範囲を少し超えた発展の内容です）

なぜ
迷路の分かれ道や、駅と路線などは、地点を頂点、道を辺とするグラフで表せる。幅優先探索は出発点に近い頂点から順に調べ、深さ優先探索は行けるところまで進んでからもどる。

ひっかけ注意

・「配列」…同じ種類のデータを番号（添字）順に並べたもの。共通テストの表記では、特に説明がなければ添字は0から始まる。つながりそのものは表さない。
・「スタック」…最後に入れたものを最初に取り出す入れ物（LIFO）。深さ優先探索で、戻る場所を覚えておくために使うことがある。
・「ハッシュ表」…計算（ハッシュ関数）で格納場所を決めてデータを入れる表。1回で場所が分かる代わりに、データどうしのつながりは表さない。

当サイトは、独立行政法人大学入試センターとは一切関係のない、非公式の学習サイトです。試験に関する最新情報は、大学入試センターの公式サイトでご確認ください。

共通テスト情報Ⅰ 基礎完全対策（全800問）に戻る

※本ページでは、アクセス解析（Googleアナリティクス）と、広告の配信・成果の計測（A8.net）のためにCookie等を利用し、閲覧に関する情報をGoogle LLC・株式会社ファンコミュニケーションズへ送信しています。詳しくはプライバシーポリシーをご覧ください。

※本ページの問題・解説は、生成AI（人工知能）を活用して作成しています。