基本情報トップに戻る
練習問題難易度: 標準2009年度

基本情報技術者 過去問練習問題 第7問

問題

昇順に整列された n 個のデータが配列に格納されている。探索したい値を 2 分探索法で探索するときの、およその比較回数を求める式はどれか。

選択肢

  1. 1log₂n
  2. 2(log₂n+1)/2
  3. 3n
  4. 4

正解

1. log₂n

詳しい解説を見る

解説

2 分探索法は探索範囲を毎回半分に絞り込むため、n 個のデータに対する比較回数はおよそ log₂n に比例する。よって「ア」が正しい。線形探索(逐次探索)は平均で n/2 回、最悪 n 回の比較が必要で計算量が大きい。(出典: 平成21年度 春期 基本情報技術者試験 午前 問7)

一問一答

科目A 180問+科目B 60問

練習問題の関連問題

この調子で演習を続けよう

スキマ資格では基本情報の全2398問を分野別・難易度別に体系的に学習できます。基本情報技術者は科目A(広く浅く)と科目B(プログラミング・アルゴリズム)の両輪での対策が必要です。