基本情報技術者試験 無料問題 8 / 10 ・ 分野4: 科目B アルゴリズムとプログラミング分野
関数 search は、整数型の配列 a の要素番号 1〜n の中から key と等しい要素を先頭から探し、最初に見つかった要素番号を返す。見つからないときは -1 を返す。a の要素数は n + 1 で、a[n + 1] は番兵を置くために空けてある。プログラム中の〔a〕に入れる正しい答えを、解答群の中から選べ。 注記: 配列の要素番号は1から始まる。 〔プログラム〕 ○整数型: search(整数型の配列: a, 整数型: n, 整数型: key) 整数型: i ← 1 a[n + 1] ← key while (a[i] ≠ key) i ← i + 1 endwhile if (〔a〕) return i endif return -1
- i = n + 1
- a[i] = key
- i < n
- i ≦ n
正解と解説を見る
正解: D
正解の理由
番兵として a[n + 1] に key を置いているので、while は必ず止まる。止まった位置 i が 1〜n の範囲なら本物の要素で見つかったことになり、n + 1 なら番兵で止まった＝見つからなかったことになる。したがって〔a〕は「i ≦ n」である。a = {4, 8, 2, 0}、n = 3 のとき、key = 2 では i = 3 で止まり 3 ≦ 3 なので 3 を返す。key = 5 では番兵の a[4] で止まり i = 4 なので -1 を返す。
違う選択肢
「i < n」… 等号を落としている。key が要素番号 n にあるとき（key = 2 で i = 3）も -1 を返してしまう。
「i = n + 1」… 真偽が逆である。番兵で止まった i = n + 1 のときに i を返すので、key = 5 で 4 を返し、見つかった key = 2 では -1 を返す。
「a[i] = key」… 番兵を置いた後は、止まった位置では常に a[i] = key が成り立つ。見つからないときも番兵の位置 n + 1 を返してしまう。
押さえどころ
番兵は「繰返しの中で i ≦ n を毎回調べずに済ませる」ための工夫で、その代わりに止まった位置が番兵かどうかを最後に1回だけ調べる。