令和元年度秋期 基本情報技術者試験 午前 問7～問10｜過去問解説
令和元年度秋期・基本情報技術者試験の午前問7～問10を解説します。BNFによる変数名の定義、スタック、二次元配列の変換、ハッシュ関数による格納位置を扱います。
この記事について
2019年（令和元年度）秋期に実施された基本情報技術者試験 午前の問7～問10を扱う過去問解説です。現在の試験制度や出題形式とは一部異なりますが、コンピュータサイエンスの基礎学習には引き続き活用できます。
出典・引用について
問題文、選択肢および試験問題に含まれる図表は、独立行政法人情報処理推進機構（IPA）が公開している令和元年度秋期試験から引用しています。掲載にあたり、改行、表組み、全角・半角、画像配置などを調整している場合があります。問題の趣旨は変更していません。解説、補足、計算過程および当サイト作成の図は、工学じじいの縁側日記によるものです。
IPA公式・問題冊子（PDF） ／ IPA公式・解答例（PDF） ／ 2019年度の過去問題一覧
R01基本情報技術者試験 秋期試験に挑戦
令和元年度 基本情報技術者試験 午前問題 問7～問10
令和元年度 基本情報技術者試験 午前問題 問7
次のBNFで定義される変数名に合致するものはどれか。
<数字> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<英字> ::= A | B | C | D | E | F
<英数字> ::= <英字> | <数字> | _
<変数名> ::= <英字> | <変数名><英数字>
| 選択肢 | 文字列 |
|---|---|
| ア | _B39 |
| イ | 246 |
| ウ | 3E5 |
| エ | F5_1 |
解説
BNF（Backus-Naur Form）の問題です。
BNFの基本的な読み方は、次のとおりです。
<左辺> ::= <右辺>
これは、左辺を右辺の規則によって生成できるという意味です。
今回調べる規則は、次の部分です。
<変数名> ::= <英字> | <変数名><英数字>
変数名は、最初の1文字が必ず英字になります。その後ろには、英字、数字、またはアンダースコアを追加できます。
各選択肢を分解すると、次のようになります。
ア _B39 = <英数字><英字><数字><数字>
イ 246 = <数字><数字><数字>
ウ 3E5 = <数字><英字><数字>
エ F5_1 = <英字><数字><英数字><数字>
ア、イ、ウは、先頭が英字ではありません。したがって、変数名の規則には合致しません。
エの F5_1 は、次のように生成できます。
F
↓
F5
↓
F5_
↓
F5_1
BNFの記号で表すと、次の流れです。
<変数名>
→ <英字>
→ <英字><英数字>
→ <英字><英数字><英数字>
→ <英字><英数字><英数字><英数字>
→ F5_1
よって、エの F5_1 が正解です。
令和元年度 基本情報技術者試験 午前問題 問8
A、C、K、S、Tの順に文字が入力される。スタックを利用して、S、T、A、C、Kという順に文字を出力するために、最小限必要となるスタックは何個か。
ここで、どのスタックにおいても、ポップ操作が実行されたときには必ず文字を出力する。また、スタック間で文字を移動することはできない。
| 選択肢 | スタック数 |
|---|---|
| ア | 1 |
| イ | 2 |
| ウ | 3 |
| エ | 4 |
解説
スタックは、後入れ先出し（LIFO）のデータ構造です。
push(x)でデータを積み、pop()で一番上のデータを取り出します。
例えば、次の順番で操作します。
① push(3)
② push(5)
③ push(2)
④ pop() → 2を取り出す
⑤ push(1)
⑥ pop() → 1を取り出す
⑦ pop() → 5を取り出す
スタックの状態は、次のように変化します。左側が取り出し口、右側が底です。
操作前 [ ]
push(3) [ 3 ]
push(5) [ 5 | 3 ]
push(2) [ 2 | 5 | 3 ]
pop() → 2 [ 5 | 3 ]
push(1) [ 1 | 5 | 3 ]
pop() → 1 [ 5 | 3 ]
pop() → 5 [ 3 ]
今回の入力順は、次のとおりです。
入力順：A → C → K → S → T
出力順：S → T → A → C → K
スタックが1個の場合、すべて積むと次の状態になります。
[ T | S | K | C | A ]
最初に取り出せるのはTなので、Sから出力できません。
スタックが2個の場合、Tを別のスタックへ入れることでS、Tまでは取り出せます。
スタック1：[ S | K | C | A ]
スタック2：[ T ]
しかし、その後にA、C、Kの順で取り出せません。
配置を工夫しても、2個ではCとKの順番を解決できません。
スタック1：[ S | A ]
スタック2：[ T | K | C ]
スタックを3個にすると、次のように配置できます。
スタック1：[ S | A ]
スタック2：[ T | K ]
スタック3：[ C ]
この状態なら、次の順番で取り出せます。
S → T → A → C → K
よって、ウの3個が正解です。
令和元年度 基本情報技術者試験 午前問題 問9
配列Aが図2の状態のとき、図1の流れ図を実行すると、配列Bが図3の状態になった。図1のaに入れる操作はどれか。
ここで、配列A、Bの要素を、それぞれ A(i,j)、B(i,j) とする。
図1 流れ図
図2 配列Aの状態
図3 実行後の配列Bの状態
| 選択肢 | 操作 |
|---|---|
| ア | 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) |
解説
配列のインデックスを使って、配列Aの配置を時計回りに90度回転させる問題です。
図2と図3を見比べると、例えば次の位置が対応しています。
A(0,1) → B(1,7)
A(7,1) → B(1,0)
A(3,4) → B(4,4)
まず、A(0,1) → B(1,7)を各選択肢へ代入します。
ア B(7-0, 7-1) = B(7,6)
イ B(7-1, 0) = B(6,0)
ウ B(0, 7-1) = B(0,6)
エ B(1, 7-0) = B(1,7)
この時点で、エが対応しています。
ほかの座標でも確認します。
A(7,1) → B(1,0)
エ：B(1, 7-7)
= B(1,0)
→ 一致
A(3,4) → B(4,4)
エ：B(4, 7-3)
= B(4,4)
→ 一致
よって、エが正解です。
令和元年度 基本情報技術者試験 午前問題 問10
10進法で5桁の数 a1a2a3a4a5 を、ハッシュ表を用いて配列へ格納したい。
ハッシュ関数を次のように定める。
mod(a1 + a2 + a3 + a4 + a5, 13)
求めたハッシュ値に対応する位置の配列要素へ格納する場合、54321は配列のどの位置に入るか。
ここで、mod(x,13)は、xを13で割った余りとする。
| 選択肢 | 配列の位置 |
|---|---|
| ア | 1 |
| イ | 2 |
| ウ | 7 |
| エ | 11 |
解説
指定されたハッシュ関数へ、54321の各桁を代入します。
mod(5 + 4 + 3 + 2 + 1, 13)
= mod(15, 13)
= 2
ハッシュ値は2なので、イが正解です。
次回予告
次回も、まったり問11から解いていこうと思います。
参考になれば幸いです。
シリーズ内の記事
- 前の記事：問3～問6の解説
- 一覧：令和元年度秋期 基本情報技術者試験 テクノロジ系まとめ
- 次の記事：問11～問15の解説
内容の誤りや分かりにくい箇所は、お問い合わせページからお知らせください。
