アルゴリズムとプログラミング(アルゴリズム)の過去問・解説【基本情報技術者試験】

アルゴリズムとプログラミング(アルゴリズム)の過去問・解説に関するブログのアイキャッチ画像 基本情報技術者試験 科目A 過去問題・公開問題

 このページでは,基本情報技術者試験を中心に,アルゴリズムとプログラミング(アルゴリズム)分野の過去問題・サンプル問題・公開問題を掲載しています。探索,整列,再帰,計算量など,試験で頻出となるアルゴリズムのテーマを幅広くカバーしています。

 解けなかった問題は,各問題下の【参考】リンクから対応する解説ページを読み,理解した上でもう一度解いてみてください。

  1. 流れ図と基本的なアルゴリズム
    1. 平成25年度 基本情報技術者試験 秋期 午前 問8
    2. 平成28年度 基本情報技術者試験 春期 午前 問8
    3. 平成25年度 基本情報技術者試験 春期 午前 問8
    4. 平成31年度 基本情報技術者試験 春期 午前 問7
    5. 平成24年度 基本情報技術者試験 秋期 午前 問2
    6. 令和5年度 基本情報技術者試験 公開問題 科目A 問11
    7. 平成29年度 基本情報技術者試験 春期 午前 問5
    8. 平成23年度 基本情報技術者試験 特別 午前 問7
    9. 平成23年度 基本情報技術者試験 秋期 午前 問7
    10. 平成26年度 基本情報技術者試験 春期 午前 問8
    11. (令和4年度) 基本情報技術者試験 サンプル問題 科目A 問2
    12. 令和元年度 基本情報技術者試験 秋期 午前 問1
    13. (令和4年度) 基本情報技術者試験 サンプル問題 科目A 問6
    14. 令和元年度 基本情報技術者試験 秋期 午前 問9
    15. 平成27年度 基本情報技術者試験 秋期 午前 問6
  2. 再帰
    1. (令和4年度) 基本情報技術者試験 サンプル問題 科目A 問8
    2. 令和元年度 基本情報技術者試験 秋期 午前 問11
    3. 平成27年度 基本情報技術者試験 秋期 午前 問8
    4. 平成21年度 基本情報技術者試験 春期 午前 問8
    5. 平成29年度 基本情報技術者試験 春期 午前 問6
    6. 平成23年度 基本情報技術者試験 特別 午前 問6
    7. 平成28年度 基本情報技術者試験 秋期 午前 問7
    8. 平成28年度 基本情報技術者試験 春期 午前 問7
    9. 平成24年度 基本情報技術者試験 秋期 午前 問7
    10. 平成26年度 基本情報技術者試験 秋期 午前 問7
    11. 平成26年度 基本情報技術者試験 春期 午前 問6
    12. 平成31年度 基本情報技術者試験 春期 午前 問6
    13. 平成27年度 基本情報技術者試験 秋期 午前 問3
  3. 整列・探索・ハッシュ
    1. 令和8年度 基本情報技術者試験 公開問題 科目A 問2
    2. 平成30年度 基本情報技術者試験 秋期 午前 問6
    3. 平成21年度 基本情報技術者試験 秋期 午前 問6
    4. 平成27年度 基本情報技術者試験 秋期 午前 問7
    5. 平成23年度 基本情報技術者試験 特別 午前 問8
    6. 平成26年度 基本情報技術者試験 秋期 午前 問6
    7. 平成29年度 基本情報技術者試験 春期 午前 問7
    8. 平成24年度 基本情報技術者試験 秋期 午前 問6
    9. 平成27年度 基本情報技術者試験 春期 午前 問6
    10. 平成21年度 基本情報技術者試験 春期 午前 問7
    11. 平成30年度 基本情報技術者試験 春期 午前 問7
    12. 平成31年度 基本情報技術者試験 春期 午前 問18
    13. 平成22年度 基本情報技術者試験 春期 午前 問6
    14. 令和6年度 基本情報技術者試験 公開問題 科目A 問2
    15. 平成24年度 基本情報技術者試験 秋期 午前 問3
  4. プログラムの性質・その他
    1. 令和8年度 基本情報技術者試験 公開問題 科目A 問11
    2. (令和4年度) 基本情報技術者試験 サンプル問題 科目A 問9
    3. 平成30年度 基本情報技術者試験 秋期 午前 問7
    4. 平成24年度 基本情報技術者試験 春期 午前 問49
    5. 平成29年度 基本情報技術者試験 秋期 午前 問6
    6. 平成24年度 基本情報技術者試験 春期 午前 問8
    7. 平成22年度 基本情報技術者試験 春期 午前 問8
    8. 平成31年度 基本情報技術者試験 春期 午前 問8
    9. 平成27年度 基本情報技術者試験 春期 午前 問7
  5. まとめ
    1. 基本情報技術者試験の学習におすすめの問題集・参考書
    2. 学習のお役に立ちましたら
広告

流れ図と基本的なアルゴリズム

平成25年度 基本情報技術者試験 秋期 午前 問8

問 右の流れ図が左の流れ図と同じ動作をするために,a,bに入るYesとNoの組合せはどれか。

「平成25年度 基本情報技術者試験 秋期 午前 問8」の問題_画像

a

b

アNoNo
イNoYes
ウYesNo
エYesYes

【解答】ア

【解説】

Pでない場合とQの場合に処理を行うようにすればよい。

「平成25年度 基本情報技術者試験 秋期 午前 問8」の解答_画像

平成28年度 基本情報技術者試験 春期 午前 問8

平成25年度 基本情報技術者試験 春期 午前 問8

問 xとyを自然数とするとき,流れ図で表される手続を実行した結果として,適切なものはどれか。

「平成28年度 基本情報技術者試験 春期 午前 問8」の問題_画像

qの値

rの値

アx ÷ y の余りx ÷ y の商
イx ÷ y の商x ÷ y の余り
ウy ÷ x の余りy ÷ x の商
エy ÷ x の商y ÷ x の余り

【解答】イ

【解説】

たとえば,xを7,yを3とした場合の結果は,次のようになる。

「平成28年度 基本情報技術者試験 春期 午前 問8」の解答_画像

平成31年度 基本情報技術者試験 春期 午前 問7

問 次の流れ図は,2数A,Bの最大公約数を求めるユークリッドの互除法を,引き算の繰返しによって計算するものである。Aが876,Bが204のとき,何回の比較で処理は終了するか。

「平成31年度 基本情報技術者試験 春期 午前 問7」の問題_画像
ア 4イ 9ウ 10エ 11

【解答】エ

【解説】

「平成31年度 基本情報技術者試験 春期 午前 問7」の解答_画像

平成24年度 基本情報技術者試験 秋期 午前 問2

問 与えられた正の整数 x0,x1(x0 > x1)の最大公約数を,次の手順で求める。x0=175,x1=77の場合,手順(2)は何回実行するか。ここで,“A → B” は,AをBに代入することを表す。

〔手順〕

(1) 2 → i

(2) xi-2 を xi-1 で割った剰余 → xi

(3) xi = 0 ならば xi-1 を最大公約数として終了する。

(4) i+1 → i として(2)に戻る。

ア 3イ 4ウ 6エ 7

【解答】イ

【解説】

「平成24年度 基本情報技術者試験 秋期 午前 問2」の解答_画像

令和5年度 基本情報技術者試験 公開問題 科目A 問11

問 次の流れ図において,

① → ② → ③ → ⑤ → ② → ③ → ④ → ② → ⑥

の順に実行させるために,①においてmとnに与えるべき初期値aとbの関係はどれか。ここで,a,bはともに正の整数とする。

「令和5年度 基本情報技術者試験 公開問題 科目A 問11」の問題_画像
ア a = 2bイ 2a = bウ 2a = 3bエ 3a = 2b

【解答】エ

【解説】

各選択肢を順に調べればよい。

ア 「令和5年度 基本情報技術者試験 公開問題 科目A 問11」の解答_画像01

イ 「令和5年度 基本情報技術者試験 公開問題 科目A 問11」の解答_画像02

ウ b = 23 a

「令和5年度 基本情報技術者試験 公開問題 科目A 問11」の解答_画像03

エ b = 32 a

「令和5年度 基本情報技術者試験 公開問題 科目A 問11」の解答_画像04

平成29年度 基本情報技術者試験 春期 午前 問5

問 次の流れ図は,シフト演算と加算の繰返しによって2進整数の乗算を行う手順を表したものである。この流れ図中のa,bの組合せとして,適切なものはどれか。ここで,乗数と被乗数は符号なしの16ビットで表される。X,Y,Zは32ビットのレジスタであり,桁送りには論理シフトを用いる。最下位ビットを第0ビットと記す。

「平成29年度 基本情報技術者試験 春期 午前 問5」の問題_画像

a

b

アYの第0ビットXを1ビット左シフト,Yを1ビット右シフト
イYの第0ビットXを1ビット右シフト,Yを1ビット左シフト
ウYの第15ビットXを1ビット左シフト,Yを1ビット右シフト
エYの第15ビットXを1ビット右シフト,Yを1ビット左シフト

【解答】ア

【解説】

2進整数の乗算を論理シフトを用いて行う場合は,まず,乗算結果を格納する変数Zを用意する。そして,乗数Yの最下位ビット(第0ビット)が1であれば、Zに被乗数Xを加算し,その後,被乗数Xを1ビット左にシフトし,乗数Yを1ビット右にシフトする。この操作を乗数Yが0になるまで繰り返すことで,乗算結果を求めることができる。

たとえば,Xを3(10),Yを5(10)とした場合の結果Zは,15(10)となる。

「平成29年度 基本情報技術者試験 春期 午前 問5」の解答_画像

平成23年度 基本情報技術者試験 特別 午前 問7

問 次の流れ図は,1から100までの整数の総和を求め,結果を変数xに代入するアルゴリズムを示したものであるが,一部誤りがある。どのように訂正すればよいか。

「平成23年度 基本情報技術者試験 特別 午前 問7」の問題_画像

ア ①の処理を “ 0 → x ” にする。

イ ②の条件判定を “ i : 99 ” にする。

ウ ③の処理を “ x + i → i ” にする。

エ ④の処理を “ x + 1 → x ” にする。

【解答】ア

【解説】

流れ図をトレースしていくと,下図(左)のように,➊の変数xの初期化に誤りがあることが分かる。

「平成23年度 基本情報技術者試験 特別 午前 問7」の解答_画像
広告

平成23年度 基本情報技術者試験 秋期 午前 問7

問 要素番号が0から始まる配列 TANGO がある。n個の単語が TANGO[1] から TANGO[n] に入っている。図は,n番目の単語を TANGO[1] に移動するために,TANGO[1] から TANGO[n-1] の単語を順に一つずつ後ろにずらして単語表を再編成する流れ図である。aに入れる処理として,適切なものはどれか。

「平成23年度 基本情報技術者試験 秋期 午前 問7」の問題_画像

ア TANGO[i] → TANGO[i+1]

イ TANGO[i] → TANGO[n-i]

ウ TANGO[i+1] → TANGO[n-i]

エ TANGO[n-i] → TANGO[i]

【解答】ア

【解説】

たとえば,配列TANGOの各要素が次のようになっている場合に,4番目の単語をTANGO[1]に移動する流れは,次のようになる。

「平成23年度 基本情報技術者試験 秋期 午前 問7」の解答_画像

まず,4番目の単語をTANGO[0]に移動(一時的に退避)し,その後,3番目,2番目,1番目の単語を,それぞれ後ろにずらした後,TANGO[0]に一時的に退避しておいた4番目の単語をTANGO[1]に移動する。

平成26年度 基本情報技術者試験 春期 午前 問8

問 長さm,nの文字列をそれぞれ格納した配列X,Yがある。図は,配列Xに格納した文字列の後ろに,配列Yに格納した文字列を連結したものを,配列Zに格納するアルゴリズムを表す流れ図である。図中のa,bに入れる処理として,適切なものはどれか。ここで,1文字が一つの配列要素に格納されるものとする。

「平成26年度 基本情報技術者試験 春期 午前 問8」の問題_画像

a

b

アX(k) → Z(k)Y(k) → Z(m + k)
イX(k) → Z(k)Y(k) → Z(n + k)
ウY(k) → Z(k)X(k) → Z(m + k)
エY(k) → Z(k)X(k) → Z(n + k)

【解答】ア

【解説】

配列Xに格納した文字列の後ろに,配列Yに格納した文字列を連結したものを,配列Zに格納するので,

① ループ1で配列Xに格納した文字列を,配列Zに先頭から順に1文字ずつ複製する

② ループ2で配列Yに格納した文字列を,配列Zの(m+1)文字目(下の例では3+1=4文字目)以降に順に1文字ずつ複製する

という操作を行えばよい。

「平成26年度 基本情報技術者試験 春期 午前 問8」の解答_画像

(令和4年度) 基本情報技術者試験 サンプル問題 科目A 問2

令和元年度 基本情報技術者試験 秋期 午前 問1

問 次の流れ図は,10進整数 j(0 < j < 100)を8桁の2進数に変換する処理を表している。2進数は下位桁から順に,配列の要素 NISHIN(1) から NISHIN(8) に格納される。流れ図のa及びbに入れる処理はどれか。ここで,j div 2 はjを2で割った商の整数部分を,j mod 2 はjを2で割った余りを表す。

「(令和4年度) 基本情報技術者試験 サンプル問題 科目A 問2」の問題画像

a

b

アj ← j div 2NISHIN(k) ← j mod 2
イj ← j mod 2NISHIN(k) ← j div 2
ウNISHIN(k) ← j div 2j ← j mod 2
エNISHIN(k) ← j mod 2j ← j div 2

【解答】エ

【解説】

10進整数を2進数に変換し,下位桁から順に配列の各要素に値を格納するには,

10進整数を2で割った余りを配列に格納し,その後,商を次の計算対象にする

という操作を繰り返し行えばよい。

たとえば,jを123とした場合の結果は,次のようになる。

「(令和4年度) 基本情報技術者試験 サンプル問題 科目A 問2」の解答画像

(令和4年度) 基本情報技術者試験 サンプル問題 科目A 問6

令和元年度 基本情報技術者試験 秋期 午前 問9

平成27年度 基本情報技術者試験 秋期 午前 問6

問 配列Aが図2の状態のとき,図1の流れ図を実行すると,配列Bが図3の状態になった。図1の a に入れる操作はどれか。ここで,配列A,Bの要素をそれぞれ A(i,j),B(i,j) とする。

「(令和4年度) 基本情報技術者試験 サンプル問題 科目A 問6」の問題画像
ア B(7-i,7-j) ← A(i,j)イ B(7-j,i) ← A(i,j)
ウ B(i,7-j) ← A(i,j)エ B(j,7-i) ← A(i,j)

【解答】エ

【解説】

図2の「F」を,図3のように右に90度傾ければよいので,配列Aの各要素を配列Bに,

B(0, 7) ← A(0, 0)

B(1, 7) ← A(0, 1)

B(2, 7) ← A(0, 2)

「(令和4年度) 基本情報技術者試験 サンプル問題 科目A 問2」の解答画像02

B(j, 7-i) ← A(i, j)

のようにコピーすればよい。

「(令和4年度) 基本情報技術者試験 サンプル問題 科目A 問6」の解答画像01
広告

再帰

(令和4年度) 基本情報技術者試験 サンプル問題 科目A 問8

令和元年度 基本情報技術者試験 秋期 午前 問11

平成27年度 基本情報技術者試験 秋期 午前 問8

平成21年度 基本情報技術者試験 春期 午前 問8

問 自然数nに対して,次のとおり再帰的に定義される関数 f(n) を考える。f(5) の値はどれか。

f(n): if n≦1 then return 1 else return n+f(n-1)

ア 6イ 9ウ 15エ 25

【解答】ウ

【解説】

f(5)の実行結果は,次のとおりである。

「(令和4年度) 基本情報技術者試験 サンプル問題 科目A 問8」の解答画像

平成29年度 基本情報技術者試験 春期 午前 問6

平成23年度 基本情報技術者試験 特別 午前 問6

問 関数 f(x, y) が次のとおり定義されているとき,f(775, 527) の値は幾らか。ここで,x mod y はxをyで割った余りを返す。

f(x, y): if y=0 then return x else return f(y, x mod y)

ア 0イ 31ウ 248エ 527

【解答】イ

【解説】

f(775, 527) の実行結果は,次のとおりである。

「平成29年度 基本情報技術者試験 春期 午前 問6」の解答_画像

平成28年度 基本情報技術者試験 秋期 午前 問7

問 整数 x,y(x>y≧0)に対して,次のように定義された関数 F(x, y) がある。F(231, 15) の値は幾らか。ここで,x mod y はxをyで割った余りである。

「平成28年度 基本情報技術者試験 秋期 午前 問7」の問題_画像
ア 2イ 3ウ 5エ 7

【解答】イ

【解説】

f(231, 15) の実行結果は,次のとおりである。

「平成28年度 基本情報技術者試験 秋期 午前 問7」の解答_画像

平成28年度 基本情報技術者試験 春期 午前 問7

問 nの階乗を再帰的に計算する関数F(n)の定義において,aに入れるべき式はどれか。ここで,nは非負の整数とする。

n > 0 のとき,F(n) =   a  

n = 0 のとき,F(n) = 1

ア n+F(n-1)イ n-1+F(n)
ウ n×F(n-1)エ (n-1)×F(n)

【解答】ア

【解説】

階乗は「n! = n×(n−1)!」で表せる。よって,n > 0 のときは n×F(n−1) として1つ前の階乗を再帰的に求める。また,0! = 1 であるので,n = 0 のときは 1 を返す。例えば,F(4)の実行結果は,次のとおりである。

「平成28年度 基本情報技術者試験 春期 午前 問7」の解答_画像

平成24年度 基本情報技術者試験 秋期 午前 問7

問 n! の値を,次の関数 F(n) によって計算する。乗算の回数を表す式はどれか。

「平成24年度 基本情報技術者試験 秋期 午前 問7」の問題_画像
ア n-1イ nウ n2エ n!

【解答】イ

【解説】

例えば,F(4)の実行結果は,次のとおりである。

「平成24年度 基本情報技術者試験 秋期 午前 問7」の解答_画像

よって,乗算は4回行われる。したがって,F(n)による乗算の回数は,

n回

となる。

広告

平成26年度 基本情報技術者試験 秋期 午前 問7

問 次の関数 f(n,k) がある。f(4,2) の値は幾らか。

「平成26年度 基本情報技術者試験 秋期 午前 問7」の問題_画像
ア 3イ 4ウ 5エ 6

【解答】エ

【解説】

f(4, 2) の実行結果は,次のとおりである。

「平成26年度 基本情報技術者試験 秋期 午前 問7」の解答_画像

【別解】

f(4, 2) = f(3, 1) + f(3, 2)

= f(2, 0) + f(2, 1) + f(2, 1) + f(2, 2)

= 1 + f(1, 0) + f(1, 1) + f(1, 0) + f(1, 1) + 1

= 1 + 1 + 1 + 1 + 1 + 1

= 6

平成26年度 基本情報技術者試験 春期 午前 問6

問 2分木の各ノードがもつ記号を出力する再帰的なプログラム Proc(n) の定義は,次のとおりである。このプログラムを,図の2分木の根(最上位のノード)に適用したときの出力はどれか。

「平成26年度 基本情報技術者試験 春期 午前 問6」の問題_画像
ア +a*-bcdイ a+b-c*d
ウ abc-d*+エ b-c*d+a

【解答】ウ

【解説】

Proc(n) を2分木の根(最上位のノード)に適用したときの出力は,次のとおりである。

「平成26年度 基本情報技術者試験 春期 午前 問6」の解答_画像

平成31年度 基本情報技術者試験 春期 午前 問6

問 三つのスタックA,B,Cのいずれの初期状態も [1, 2, 3] であるとき,再帰的に定義された関数 f() を呼び出して終了した後のBの状態はどれか。ここで,スタックが [a1, a2, … , an-1] の状態のときにanをpushした後のスタックの状態は [a1, a2, … , an-1, an] で表す。

f() {

Aが空ならば {

何もしない。

}

そうでない場合 {

Aからpopした値をCにpushする。

f()を呼び出す。

Cからpopした値をBにpushする。

}

}

ア [1, 2, 3, 1, 2, 3]イ [1, 2, 3, 3, 2, 1]
ウ [3, 2, 1, 1, 2, 3]エ [3, 2, 1, 3, 2, 1]

【解答】ア

【解説】

f()の実行結果は,次のとおりである。

「平成31年度 基本情報技術者試験 春期 午前 問6」の解答_画像

平成27年度 基本情報技術者試験 秋期 午前 問3

問 関数f(x)は,引数も戻り値も実数型である。この関数を使った,①~⑤から成る手続を考える。手続の実行を開始してから②~⑤を十分に繰り返した後に,③で表示されるyの値に変化がなくなった。このとき成立する関係式はどれか。

① x ← a

② y ← f(x)

③ yの値を表示する。

④ x ← y

⑤ ②に戻る。

ア f(a) = yイ f(y) = 0ウ f(y) = aエ f(y) = y

【解答】エ

【解説】

②~⑤の処理は,前回の結果を次の入力として繰り返し更新する処理であり,値がある一定の値に近づくため,最終的に変化しなくなる。

【参考】

たとえば,関数f(x)を,繰り返し適用すると2に収束する関数として,aの値を4とした場合は,次のようになる。

「平成27年度 基本情報技術者試験 秋期 午前 問3」の解答_画像
広告

整列・探索・ハッシュ

令和8年度 基本情報技術者試験 公開問題 科目A 問2

平成30年度 基本情報技術者試験 秋期 午前 問6

平成21年度 基本情報技術者試験 秋期 午前 問6

問 クイックソートの処理方法を説明したものはどれか。

ア 既に整列済みのデータ列の正しい位置に,データを追加する操作を繰り返していく方法である。

イ データ中の最小値を求め,次にそれを除いた部分の中から最小値を求める。この操作を繰り返していく方法である。

ウ 適当な基準値を選び,それよりも小さな値のグループと大きな値のグループにデータを分割する。同様にして,グループの中で基準値を選び,それぞれのグループを分割する。この操作を繰り返していく方法である。

エ 隣り合ったデータの比較と入替えを繰り返すことによって,小さな値のデータを次第に端の方に移していく方法である。

【解答】ウ

【解説】

■ クイックソート

データの中で基準値(ピボット)を選択し,その基準値よりも値の小さいグループと大きいグルーに分け,さらに,それぞれのグループの中で基準値を選択し、その基準値よりも値の小さいグループと大きいグループに分け…,という操作を繰り返し行い,昇順(または降順)に並べ替えるアルゴリズムである。

※ 計算量(平均):O(n log2n),最悪の場合:O(n2)

ア 基本挿入法(挿入ソート)

イ 基本選択法(選択ソート)

エ 基本交換法(隣接交換法,バブルソート)

平成27年度 基本情報技術者試験 秋期 午前 問7

平成23年度 基本情報技術者試験 特別 午前 問8

問 整列アルゴリズムの一つであるクイックソートの記述として,適切なものはどれか。

ア 対象集合から基準となる要素を選び,これよりも大きい要素の集合と小さい要素の集合に分割する。この操作を繰り返すことによって,整列を行う。

イ 対象集合から最も小さい要素を順次取り出して,整列を行う。

ウ 対象集合から要素を順次取り出し,それまでに取り出した要素の集合に順序関係を保つよう挿入して,整列を行う。

エ 隣り合う要素を比較し,逆順であれば交換して,整列を行う。

【解答】ア

【解説】

■ クイックソート

データの中で基準値(ピボット)を選択し,その基準値よりも値の小さいグループと大きいグルーに分け,さらに,それぞれのグループの中で基準値を選択し、その基準値よりも値の小さいグループと大きいグループに分け…,という操作を繰り返し行い,昇順(または降順)に並べ替えるアルゴリズムである。

※ 計算量(平均):O(n log2n),最悪の場合:O(n2)

イ 基本選択法(選択ソート)

ウ 基本挿入法(挿入ソート)

エ 基本交換法(隣接交換法,バブルソート)

平成26年度 基本情報技術者試験 秋期 午前 問6

問 2分探索に関する記述のうち,適切なものはどれか。

ア 2分探索するデータ列は整列されている必要がある。

イ 2分探索は線形探索よりも常に速く探索できる。

ウ 2分探索は探索をデータ列の先頭から開始する。

エ n個のデータの2分探索に要する比較回数は,n log2 n に比例する。

【解答】ア

【解説】

■ 2分探索

整列済みデータの中から探索データを探索する場合に有効なアルゴリズムである。探索データと整列済みデータの中心に位置するデータを比較し,整列済みデータの前半分か後半分を次の探索範囲として,これを繰り返すことによりデータを探索する。

※ 計算量:O(log2n)

イ 探索データが先頭にある場合は,線形探索の方が速い

平成29年度 基本情報技術者試験 春期 午前 問7

問 顧客番号をキーとして顧客データを検索する場合,2分探索を使用するのが適しているものはどれか。

ア 顧客番号から求めたハッシュ値が指し示す位置に配置されているデータ構造

イ 顧客番号に関係なく,ランダムに配置されているデータ構造

ウ 顧客番号の昇順に配置されているデータ構造

エ 顧客番号をセルに格納し,セルのアドレス順に配置されているデータ構造

【解答】ウ

【解説】

■ 2分探索

整列済みデータの中から探索データを探索する場合に有効なアルゴリズムである。探索データと整列済みデータの中心に位置するデータを比較し,整列済みデータの前半分か後半分を次の探索範囲として,これを繰り返すことによりデータを探索する。

※ 計算量:O(log2n)

平成24年度 基本情報技術者試験 秋期 午前 問6

問 昇順に整列済みの配列要素 A(1),A(2),…,A(n) から,A(m)=k となる配列要素A(m)の添字mを2分探索法によって見つける処理を図に示す。終了時点でm=0である場合は,A(m)=kとなる要素は存在しない。図中のaに入る式はどれか。ここで,“/” は,小数点以下を切り捨てる除算を表す。

「平成24年度 基本情報技術者試験 秋期 午前 問6」の問題_画像
ア (x+y) → mイ (x+y)/2 → m
ウ (x-y)/2 → mエ (y-x)/2 → m

【解答】イ

【解説】

配列A(m)の添字を求める処理である。探索範囲の最小の添字を示すxと最大の添字を示すyの平均 (x+y)÷2 を求めることで,探索範囲の中央の要素を選択し,探索範囲を半分に絞り込むことができる。

【参考】

たとえば,配列A(m)を A()={10,20,30,40,50,60,70},k=50 とした場合の結果は,次のようになる。

「平成24年度 基本情報技術者試験 秋期 午前 問6」の問題_画像

平成27年度 基本情報技術者試験 春期 午前 問6

問 整列されたn個のデータの中から,求める要素を2分探索法で探索する。この処理の計算量のオーダを表す式はどれか。

ア log nイ nウ n2エ n log n

【解答】ア

【解説】

■ 2分探索

整列済みデータの中から探索データを探索する場合に有効なアルゴリズムである。探索データと整列済みデータの中心に位置するデータを比較し,整列済みデータの前半分か後半分を次の探索範囲として,これを繰り返すことによりデータを探索する。

※ 計算量:O(log2n)

ア 比較回数をxとした場合,探索範囲は比較のたびに半分になるため,n=2xという関係が成り立ち,x=log2nとなる。⇒ 全体の実行回数:log2n回となり,O(log2n)となる

※ n=2の場合:2=21(1回比較),n=4の場合:4=22(2回比較),n=8の場合:8=23(3回比較)…,となる

平成21年度 基本情報技術者試験 春期 午前 問7

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

ア log2nイ (log2n+1)/2
ウ nエ n2

【解答】ア

【解説】

■ 2分探索

整列済みデータの中から探索データを探索する場合に有効なアルゴリズムである。探索データと整列済みデータの中心に位置するデータを比較し,整列済みデータの前半分か後半分を次の探索範囲として,これを繰り返すことによりデータを探索する。

※ 計算量:O(log2n)

ア 比較回数をxとした場合,探索範囲は比較のたびに半分になるため,n=2xという関係が成り立ち,x=log2nとなる。⇒ 全体の実行回数:log2n回となり,O(log2n)となる

※ n=2の場合:2=21(1回比較),n=4の場合:4=22(2回比較),n=8の場合:8=23(3回比較)…,となる

広告

平成30年度 基本情報技術者試験 春期 午前 問7

問 表探索におけるハッシュ法の特徴はどれか。

ア 2分木を用いる方法の一種である。

イ 格納場所の衝突が発生しない方法である。

ウ キーの関数値によって格納場所を決める。

エ 探索に要する時間は表全体の大きさにほぼ比例する。

【解答】ウ

【解説】

■ ハッシュ法

直接探索が可能なアルゴリズムである。データのキー値をハッシュ関数に通して得られるハッシュ値によりデータの格納位置が決まるので,探索時には同じ計算により格納位置を見つけることができる。ただし,異なるキー値から同じハッシュ値が得られる場合がある(衝突(シノニム))。

※ 計算量:O(1)

ア 2分木は用いない

イ 衝突(シノニム)が発生することがある

エ 探索に要する時間は表全体の大きさによらず一定である

平成31年度 基本情報技術者試験 春期 午前 問18

問 データ検索時に使用される,理想的なハッシュ法の説明として,適切なものはどれか。

ア キーワード検索のヒット率を高めることを目的に作成した,一種の同義語・類義語リストを用いることによって,検索漏れを防ぐ技術である。

イ 蓄積されている膨大なデータを検索し,経営やマーケティングにとって必要な傾向,相関関係,パターンなどを導き出すための技術や手法である。

ウ データとそれに対する処理を組み合わせたオブジェクトに,認識や判断の機能を加え,利用者の検索要求に対して,その意図を判断する高度な検索技術である。

エ データを特定のアルゴリズムによって変換した値を格納アドレスとして用いる,高速でスケーラビリティの高いデータ検索技術である。

【解答】エ

【解説】

■ ハッシュ法

直接探索が可能なアルゴリズムである。データのキー値をハッシュ関数に通して得られるハッシュ値によりデータの格納位置が決まるので,探索時には同じ計算により格納位置を見つけることができる。ただし,異なるキー値から同じハッシュ値が得られる場合がある(衝突(シノニム))。

※ 計算量:O(1)

平成22年度 基本情報技術者試験 春期 午前 問6

問 ハッシュ表探索において,同一のハッシュ値となる確率が最も低くなるのは,ハッシュ値がどの分布で近似されるときか。

ア 2項分布イ 一様分布ウ 正規分布エ ポアソン分布

【解答】イ

【解説】

イ ハッシュ値が均等に分散しているほど同一のハッシュ値(衝突)が発生しにくく,どのハッシュ値も同じ確率で現れる分布を一様分布という。

■ ハッシュ法

直接探索が可能なアルゴリズムである。データのキー値をハッシュ関数に通して得られるハッシュ値によりデータの格納位置が決まるので,探索時には同じ計算により格納位置を見つけることができる。ただし,異なるキー値から同じハッシュ値が得られる場合がある(衝突(シノニム))。

※ 計算量:O(1)

令和6年度 基本情報技術者試験 公開問題 科目A 問2

問 キーが小文字のアルファベット1文字(a,b,…,z のいずれか)であるデータを,大きさが10のハッシュ表に格納する。ハッシュ関数として,アルファベットのASCIIコードを10進表記法で表したときの1の位の数を用いることにする。衝突が起こるキーの組合せはどれか。ASCIIコードでは,昇順に連続した2進数が,アルファベット順にコードとして割り当てられている。

ア a と iイ b と rウ c と lエ d と x

【解答】エ

【解説】

たとえば,アルファベットの小文字a~zに連続した適当なコードを割り当てて考えてみればよい。

「令和6年度 基本情報技術者試験 公開問題 科目A 問2」の解答_画像

表より,各文字のコードの1の位の値を求めると,

ア:a=0,i=8

イ:b=1,r=7

ウ:c=2,l=1

エ:d=3,x=3

となる。

平成24年度 基本情報技術者試験 秋期 午前 問3

問 探索方法とその実行時間のオーダの適切な組合せはどれか。ここで,探索するデータの数をnとし,ハッシュ値が衝突する(同じ値になる)確率は無視できるほど小さいものとする。また,実行時間のオーダがn2であるとは,n個のデータを処理する時間がcn2(cは定数)で抑えられることをいう。

2分探索

線形探索

ハッシュ探索

アlog2 nn1
イn log2 nnlog2 n
ウn log2 nn21
エn21n

【解答】ア

【解説】

■ 2分探索の計算量

比較回数をxとした場合,探索範囲は比較のたびに半分になるため,n=2xという関係が成り立ち,x=log2nとなる。⇒ 全体の実行回数:log2n回となり,O(log2n)となる

※ n=2の場合:2=21(1回比較),n=4の場合:4=22(2回比較),n=8の場合:8=23(3回比較)…,となる

■ 線形探索の計算量

探索回数:約n回 ⇒ 全体の実行回数:n回となり,O(n)となる

■ ハッシュ探索の計算量

O(1)

広告

プログラムの性質・その他

令和8年度 基本情報技術者試験 公開問題 科目A 問11

問 あるシステムにおいて,“プログラムの記述方法が統一されていないので保守がしづらい” という問題が発生している。今後の新規開発プロジェクトにおけるこの問題の低減策として,最も適切なものはどれか。

ア コーディング規約を見直し,教育する。

イ セキュアプログラミングを採用する。

ウ 単体テストでの命令網羅度を上げる。

エ プロジェクト管理レビューに全プログラマーが参加する。

【解答】ア

【解説】

■ コーディング規約

プログラミングについては,誰が見ても読めるように,コーディング規約を定める。

  • 命名規則を定める(変数名や関数名などに統一性のある名前を付ける)
  • コーディングのスタイルを定める(括弧の付け方やインデントなどの記述を統一する)
  • 禁止事項を定める(利用してはいけない機能などを定める)

ア セキュアプログラミングとは,脆弱性を作り込まないようにプログラミングするという考え方

(令和4年度) 基本情報技術者試験 サンプル問題 科目A 問9

平成30年度 基本情報技術者試験 秋期 午前 問7

問 プログラムのコーディング規約に規定する事項のうち,適切なものはどれか。

ア 局所変数は,用途が異なる場合でもデータ型が同じならば,できるだけ同一の変数を使うようにする。

イ 処理性能を向上させるために,ループの制御変数には浮動小数点型変数を使用する。

ウ 同様の計算を何度も繰り返すときは,関数の再帰呼出しを用いる。

エ 領域割付け関数を使用するときは,割付けができなかったときの処理を記述する。

【解答】エ

【解説】

ア 用途が異なる場合は,データ型が同じでも,それぞれ別の変数を使用する

イ ループの制御変数には整数型を使用する

ウ 同様の計算を繰り返す場合は,独立した関数を使用する(再帰関数の使用は,スタックのサイズが予測できないため,(コーディング規約で)禁止される場合がある)

平成24年度 基本情報技術者試験 春期 午前 問49

問 サブルーチンへの引数の渡し方のうち,変数を引数として渡しても,サブルーチンの実行後に変数の値が変更されないことが保証されているものはどれか。

ア 値呼出しイ 結果呼出しウ 参照呼出しエ 名前呼出し

【解答】ア

【解説】

値渡し(値呼出し)と参照渡し(参照呼出し)

値渡しとは,主プログラムで宣言して初期化した変数の値のコピーを,副プログラムに渡して呼び出す方法をいう。副プログラムで,渡された変数の値が変化した場合,元々の(主プログラムの)変数の値は変化しない。

参照渡しとは,主プログラムで宣言して初期化した変数のアドレス(主記憶装置内の変数の値の保存場所)を,副プログラムに渡して呼び出す方法をいう。副プログラムで、,渡されたアドレスの変数の値が変化した場合,元々の(主プログラムの)変数の値も変化する。

平成29年度 基本情報技術者試験 秋期 午前 問6

平成24年度 基本情報技術者試験 春期 午前 問8

問 再帰呼出しの説明はどれか。

ア あらかじめ決められた順番ではなく,起きた事象に応じた処理を行うこと

イ 関数の中で自分自分を用いた処理を行うこと

ウ 処理が終了した関数をメモリから消去せず,必要になったときに再び用いること

エ 処理に失敗したときに,その処理を呼び出す直前の状態に戻すこと

【解答】イ

【解説】

■ 再帰的(リカーシブ)プログラム

プログラムの中で自身を呼び出して処理するプログラムのことをいう。再帰呼び出しでは,実行途中の処理状態や戻り先を,LIFO方式で管理する必要がある。

※ LIFO … Last In First Out。後入れ先出しのこと

平成22年度 基本情報技術者試験 春期 午前 問8

問 あるプログラムAの処理が終了していないときに,別のプログラムから再度呼び出されても正しく動作するとき,このプログラムAの性質を何と呼ぶか。

ア 再帰的イ 再使用可能
ウ 再入可能エ 再配置可能

【解答】ウ

【解説】

■ 再入可能(リエントラント)プログラム

複数の処理を同時に実行する要求に対して並列に処理し,それぞれに正しい結果を返すことのできるプログラムのことをいう。プログラムは,実行によって内容が変化しない手続き部分と,実行ごとに内容が変化するデータ部分に分ける。手続き部分は複数のタスクで共有し,データ部分はタスクごとに分離することで,同時実行しても互いに影響しないようにする。

「平成31年度 基本情報技術者試験 春期 午前 問8」の解答_画像

平成31年度 基本情報技術者試験 春期 午前 問8

問 複数のプロセスから同時に呼び出されたときに,互いに干渉することなく並行して動作することができるプログラムの性質を表すものはどれか。

ア リエントラントイ リカーシブ
ウ リユーザブルエ リロケータブル

【解答】ア

【解説】

■ 再入可能(リエントラント)プログラム

複数の処理を同時に実行する要求に対して並列に処理し,それぞれに正しい結果を返すことのできるプログラムのことをいう。プログラムは,実行によって内容が変化しない手続き部分と,実行ごとに内容が変化するデータ部分に分ける。手続き部分は複数のタスクで共有し,データ部分はタスクごとに分離することで,同時実行しても互いに影響しないようにする。

「平成31年度 基本情報技術者試験 春期 午前 問8」の解答_画像

平成27年度 基本情報技術者試験 春期 午前 問7

問 再入可能プログラムの特徴はどれか。

ア 主記憶上のどこのアドレスに配置しても,実行することができる。

イ 手続の内部から自分自身を呼び出すことができる。

ウ 必要な部分を補助記憶装置から読み込みながら動作する。主記憶領域の大きさに制限があるときに,有効な手法である。

エ 複数のタスクからの呼出しに対して,並行して実行されても,それぞれのタスクに正しい結果を返す。

【解答】エ

【解説】

■ 再入可能(リエントラント)プログラム

複数の処理を同時に実行する要求に対して並列に処理し,それぞれに正しい結果を返すことのできるプログラムのことをいう。プログラムは,実行によって内容が変化しない手続き部分と,実行ごとに内容が変化するデータ部分に分ける。手続き部分は複数のタスクで共有し,データ部分はタスクごとに分離することで,同時実行しても互いに影響しないようにする。

「平成31年度 基本情報技術者試験 春期 午前 問8」の解答_画像

ア 再配置可能(リロケータブル)プログラム

イ 再帰的(リカーシブ)プログラム

広告

まとめ

 今回は,基本情報技術者試験の過去問題・サンプル問題・公開問題のうち,アルゴリズムとプログラミング(アルゴリズム)分野に関するものを集め,シンプルにまとめてみました。みなさんは,どのくらい解けましたか? アルゴリズムは,「どのような手順で処理を行うか」を考える分野です。はじめは,探索や整列,再帰,計算量など,覚える内容が多く感じるかもしれません。しかし,問題演習を繰り返すことで,「どのアルゴリズムを選べば効率よく処理できるのか」が自然と理解できるようになります。 8割以上(できれば9割以上)解けるようになることを目標に,ぜひ取り組んでみてください。また,一度解けるようになっても,時間が経つと忘れてしまうことがあります。1週間後や1か月後など,期間をあけてもう一度解き直すことで,知識の定着につながると思います。

基本情報技術者試験の学習におすすめの問題集・参考書

過去問演習や苦手分野の復習に役立つ,おすすめの問題集・参考書です。

科目A・Bの両方をまとめて対策できる,演習重視の問題集です。頻出・重要問題を中心に,科目Bのアルゴリズムや情報セキュリティも丁寧に解説。WebアプリやPDFの過去問題などの特典も充実しており,試験直前まで活用できます。
¥1,540 (2026/08/31 13:04時点 | Amazon調べ)
科目Aの頻出テーマを効率よく演習できる問題集です。コンパクトにまとまっているため,スキマ時間の学習や試験直前の総復習にもおすすめです。
¥1,628 (2026/08/31 13:05時点 | Amazon調べ)
イラストを使った解説が特徴の人気参考書です。基礎理論の考え方や計算問題もイメージで理解しやすく,独学学習との相性が良い一冊です。
¥2,420 (2026/08/31 13:06時点 | Amazon調べ)

学習のお役に立ちましたら

この記事が少しでも学習のお役に立ちましたら,今後も分かりやすい解説や学習コンテンツを継続してお届けする励みになります。

よろしければ,このサイトを応援いただけますと嬉しいです。

※OFUSEは,クリエイターやコンテンツ制作を直接支援できるサービスです。

広告