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

アルゴリズムの比較と効率の一問一答

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

この分野の演習

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

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

問題

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

問14-13・基礎

線形探索と二分探索の使い分けを考える。次のうち、二分探索よりも線形探索を使うほうが適している場面として最も適切なものはどれか。

①並び順がばらばらのデータから、目的の値を1回だけ探す
②昇順に並んだ100万件の名簿から、何度も値を探す
③昇順に並んだデータで、最大の比較回数を減らしたい
④50音順に並んだ単語の一覧から、目的の語を何度も探す

答えと解説を見る

正解 ①並び順がばらばらのデータから、目的の値を1回だけ探す

解説
正解は「並び順がばらばらのデータから、目的の値を1回だけ探す」。二分探索を使うには、先に並べ替える手間がかかるため。

なぜ
二分探索は、データが昇順か降順に整列していることが前提。ばらばらのデータなら、まず並べ替えが要る。例えば選択ソートで n 個を並べると n×（n−1）÷2 回比べるが、線形探索なら最大 n 回で済む。1回だけ探すなら、並べ替えずに線形探索するほうが手間が少ない。文部科学省の教員研修用教材も、並んでいる保証がない場合やデータが少ない場合は線形探索が有用なこともあると説明している。

ひっかけ注意

・「昇順に並んだ100万件の名簿から、何度も値を探す」…既に並んでいるので二分探索が向く。最大20回で済み、線形探索の最大100万回よりずっと少ない。
・「昇順に並んだデータで、最大の比較回数を減らしたい」…二分探索が向く場面。データが2倍になっても最大回数は1回増えるだけ。
・「50音順に並んだ単語の一覧から、目的の語を何度も探す」…50音順も整列の一種なので、真ん中と比べて範囲を半分にする二分探索が使える。

問24-13・基礎

整列されていない9個のデータから、線形探索で目的の値を探す。目的の値は9個の中に必ず1つだけあり、1番目から9番目のどの位置にある確率も等しいとする。次の表は、目的の値があった位置と、そのときの比較回数である。

位置	1	2	3	4	5	6	7	8	9
比較回数	1	2	3	4	5	6	7	8	9

比較回数の平均は何回か。

①4.5回
②5回
③9回
④4回

答えと解説を見る

正解 ②5回

解説
正解は「5回」。平均は（1＋2＋…＋9）÷9＝5回。

手順
①表のとおり、k番目にあれば比較はk回かかる。
②1〜9回を全部足すと45回。
③どの位置も同じ確率なので、45÷9＝5回が平均になる。一般に、n個なら（n＋1）÷2回。

ひっかけ注意

・「4.5回」…9÷2で求めた値。比較は1回目から数えるので、正しくは（9＋1）÷2＝5回。
・「9回」…いちばん最後にあったときの最大回数。目的の値が無い場合も9回比べる。
・「4回」…9個を二分探索したときの最大回数。二分探索は7個までなら最大3回、8〜15個なら最大4回で、線形探索とは別の計算。

問34-13・標準

昇順に整列された100個のデータから、二分探索で目的の値を探す。探す範囲の中央にあるデータ1個と比べることを比較1回と数え、中央の位置は（左端の番号＋右端の番号）÷2の商とする。必要なら、次の表を使ってよい。

n	5	6	7	8
2のn乗	32	64	128	256

比較回数は最大で何回か。

①50回
②6回
③7回
④10回

答えと解説を見る

正解 ③7回

解説
正解は「7回」。比べるたびに、残りの範囲がほぼ半分になる。

手順
①1回目の比較で、残りは最大50個になる。
②2回目で25個、3回目で12個、4回目で6個、5回目で3個、6回目で1個になる。
③最後の1個と比べる7回目で必ず決着がつく。表のとおり、2の6乗は64、2の7乗は128で、100は64以上128未満なので7回と考えてもよい。

ひっかけ注意

・「50回」…100個の半分。線形探索の平均（（100＋1）÷2＝50.5回）に近い値で、二分探索の回数ではない。
・「6回」…2の6乗の64個未満なら6回で済むが、100個では1回足りない。
・「10回」…512個以上1023個以下のデータのときの最大回数。100個なら7回で足りる。

問44-13・標準

昇順に整列されたデータが500個から1000個に増えた。探す値とデータ1個を比べることを比較1回と数える。二分探索（範囲の中央のデータと比べて範囲を半分にする）の最大の比較回数は、データ数に応じて次の表のようになる。

データ数	二分探索の最大の比較回数
256〜511個	9回
512〜1023個	10回

線形探索と二分探索の「最大の比較回数」はそれぞれどう変わるか。

①線形2倍・二分2倍
②線形4倍・二分1回増
③線形2倍・二分変化なし
④線形2倍・二分1回増

答えと解説を見る

正解 ④線形2倍・二分1回増

解説
正解は「線形2倍・二分1回増」。線形探索は500回→1000回、二分探索は9回→10回になる。

なぜ
問題の表から、二分探索は500個で9回、1000個で10回。線形探索は全部と比べる場合があるので、最大回数はデータ数に比例する。二分探索は1回で範囲を半分にできる。データが2倍になっても、半分にする回数が1回増えるだけで済む。

データ数	線形探索	二分探索
500個	500回	9回
1000個	1000回	10回

ひっかけ注意

・「線形2倍・二分2倍」…二分探索も比例して増えると考えた誤り。二分探索はデータが2倍で1回増えるだけ。
・「線形4倍・二分1回増」…4倍になるのは、選択ソートのように n×（n−1）÷2 回比べる整列の、およその増え方。
・「線形2倍・二分変化なし」…500個は最大9回、1000個は最大10回で、1回増える。

問54-13・標準

8個のデータを昇順に並べる。クイックソートは次の手順で行う。
・未整列の部分の先頭のデータを基準値とし、残りの各データと基準値を1回ずつ比べて、「基準値より小さいグループ」と「それ以外のグループ」に分ける。
・分けたそれぞれのグループ（2個以上のとき）に、同じ処理を繰り返す。
データ2個を比べることを比較1回と数える。元のデータがすでに昇順に並んでいるとき、比較回数について正しいものはどれか。

①28回で、選択ソートと同じ回数になる
②24回で、8×log₂8 と同じ回数になる
③14回で、選択ソートの半分の回数になる
④7回で、1回目の分割だけで並び終わる

答えと解説を見る

正解 ①28回で、選択ソートと同じ回数になる

解説
正解は「28回で、選択ソートと同じ回数になる」。既に並んでいると分け方がかたより、いちばん多い回数になる。

手順
①1回目：基準値は最小の値なので、残り7個はすべてそれ以外のグループに入る（比較7回）。小さいグループは空になる。
②残り7個でも先頭が最小なので、比較6回で同じように片側に寄る。以下5回、4回、3回、2回、1回と続く。
③合計は 7＋6＋5＋4＋3＋2＋1＝28回。選択ソートの比較回数 8×7÷2＝28回と同じになる。

ひっかけ注意

・「24回で、8×log₂8 と同じ回数になる」…8×3＝24 は、毎回うまく半分ずつ分かれたときの目安。並んだデータでは片寄るので当てはまらない。
・「14回で、選択ソートの半分の回数になる」…クイックソートが速いのは分け方がかたよらないとき。8個のばらばらな並びでも平均は約17回で、整列済みでは28回に増える。
・「7回で、1回目の分割だけで並び終わる」…7回は1回目の分割の比較回数。残り7個のグループにも同じ処理が続く。

問64-13・標準

次の手順の選択ソートで、n個のデータを昇順に並べる。
・未整列の部分を先頭から末尾まで調べて最小値を見つけ、未整列の部分の先頭と入れ替える。
・これを未整列の部分が1個になるまで繰り返す。
この手順の「比較回数」について正しいものはどれか。

①既に昇順に並んでいると、最も少なくなる
②元の並び方に関係なく、常に同じ回数になる
③逆順に並んでいると、比較回数が最も多くなる
④最大値が先頭にあると、比較回数が最も多い

答えと解説を見る

正解 ②元の並び方に関係なく、常に同じ回数になる

解説
正解は「元の並び方に関係なく、常に同じ回数になる」。

なぜ
この手順では、最小値を見つけるために未整列の部分を毎回最後まで調べる。途中でやめないので、比較回数はいつも n×（n−1）÷2 回になる。並び方で変わるのは、位置を実際に入れ替える必要があるかどうかのほう（最小値がすでに先頭にあれば入れ替えは要らない）。

ひっかけ注意

・「既に昇順に並んでいると、最も少なくなる」…これは挿入ソートの性質で、n−1 回で済む。選択ソートは整列済みでも全部調べる。
・「逆順に並んでいると、比較回数が最も多くなる」…逆順でも比較回数は n×（n−1）÷2 回で同じ。変わるのは入れ替えの回数。
・「最大値が先頭にあると、比較回数が最も多い」…最大値がどこにあっても、比較回数は n×（n−1）÷2 回で同じ。6個なら、どんな並びでも15回になる。

問74-13・標準

データ「2, 5, 1, 4, 3」をバブルソートで昇順に並べる。隣り合う2個を比べ、左のほうが大きければ入れ替える。この操作を左端から右端へ向かって繰り返す。すべて並び終わるまでに、入れ替えは全部で何回起こるか。

①10回
②4回
③5回
④3回

答えと解説を見る

正解 ③5回

解説
正解は「5回」。

手順
①1周目：2と5はそのまま、5と1を入れ替え、5と4を入れ替え、5と3を入れ替える（3回）。→2,1,4,3,5
②2周目：2と1を入れ替え、2と4はそのまま、4と3を入れ替える（2回）。→1,2,3,4,5
③3周目以降は入れ替えが起こらない。合計3＋2＝5回。大小が逆になっている組の数（2と1、5と1、5と4、5と3、4と3）と一致する。

ひっかけ注意

・「10回」…5個の比較回数の合計（4＋3＋2＋1）。比べても、順序が正しい場合は入れ替えない。
・「4回」…1周目の比較回数と取り違えた値。1周目で実際に入れ替えたのは3回。
・「3回」…1周目の入れ替えだけを数えた値。2周目にも2回の入れ替えがある。

問84-13・標準

挿入ソートで、データを昇順に並べる。整列済みの部分に次の1個を加えるとき、その1個を左隣から順に比べ、左のほうが小さいか等しくなったところで止める。図は、整列済みの部分（2, 4, 7）に5を加えるときの例で、2回比べて止まっている。比較回数が最も少なくなるのは、元のデータがどのように並んでいるときか。

自作の模式図

①逆順（降順）に並んでいるとき
②最大値が先頭にあるとき
③最小値が末尾にあるとき
④既に昇順に並んでいるとき

答えと解説を見る

正解 ④既に昇順に並んでいるとき

解説
正解は「既に昇順に並んでいるとき」。

なぜ
図の例では、5は7より小さいので比べ続け、4と比べたところで止まった。昇順に並んでいれば、加える1個はいつも左隣より大きい。1回比べただけで止まるので、n個なら n−1 回で終わる。逆順だと毎回いちばん左まで比べ続け、n×（n−1）÷2 回かかる。

ひっかけ注意

・「逆順（降順）に並んでいるとき」…比較回数が最も多くなる並び方。6個なら15回かかる。
・「最大値が先頭にあるとき」…最大値を右へ送るため比較が増える。例：6, 1, 2, 3, 4, 5 なら9回で、昇順の5回より多い。
・「最小値が末尾にあるとき」…最後の1個を先頭まで比べることになる。例：2, 3, 4, 5, 6, 1 なら9回。

問94-13・標準

図は、選択ソートでn個のデータを並べるときの比較回数 n×（n−1）÷2 を、12個までグラフにしたもので、10個のデータを並べると比較回数は45回である。同じ手順で20個のデータを並べると、比較回数は何回になるか。

自作の図（比較回数は n×(n−1)÷2 で計算）

①190回
②90回
③180回
④400回

答えと解説を見る

正解 ①190回

解説
正解は「190回」。20×19÷2＝190回で、10個のときの約4.2倍になる。

手順
①図の点のとおり、10個：10×9÷2＝45回。
②20個：20×19÷2＝190回。
③データ数が2倍になると、比較回数はおよそ4倍（2の2乗）に増える。データが多いほど、この差は大きくなる。

ひっかけ注意

・「90回」…データ数に比例すると考えて2倍した値。比例して増えるのは線形探索の最大回数。
・「180回」…45回を4倍した概算。式で計算すると 20×19÷2＝190回になる。
・「400回」…20×20で計算した値。自分自身とは比べず、同じ組を2回数えないので、−1と÷2が必要。

問104-13・基礎

2つのアルゴリズムの効率を比べるとき、実行にかかった秒数ではなく「比較の回数」を数えて比べることがある。その主な理由として最も適切なものはどれか。

①比較の回数は、データの並び方が変わっても同じだから
②使うコンピュータの速さに左右されずに比べられるから
③比較の回数が同じなら、どの言語でも秒数も同じになるから
④秒数では、データの個数による違いが表れないから

答えと解説を見る

正解 ②使うコンピュータの速さに左右されずに比べられるから

解説
正解は「使うコンピュータの速さに左右されずに比べられるから」。

なぜ
秒数は、使うコンピュータの速さや、同時に動いている他の処理によって変わる。比較の回数なら、どのコンピュータで動かしても同じ手順なら同じ値になる。そのため、アルゴリズムそのものの手間を公平に比べられる。

ひっかけ注意

・「比較の回数は、データの並び方が変わっても同じだから」…線形探索は、目的の値が先頭なら1回、最後なら n 回と、並び方で回数が変わる。
・「比較の回数が同じなら、どの言語でも秒数も同じになるから」…同じ回数でも、言語やコンピュータが違えば1回にかかる時間が違うため、秒数は変わる。
・「秒数では、データの個数による違いが表れないから」…データが多くなれば秒数も増えるので、違いは表れる。秒数を使わない理由は、機械の速さに左右されるため。

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

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

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

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