応用情報技術者試験 令和元年度秋試験 問題のテクノロジ系をまったり解く 問０６～問１０
令和元年 応用情報技術者試験 秋期試験に挑戦 テクノロジ系を中心に問題を解説してみます。 たまに横道にそれて関連技術や知識の解説をします。ほかのサイトよりなるべく丁寧に解説していこうと思っています。
R01 応用情報技術者試験 秋期試験に挑戦 問６～問１０
前回に引き続き、あまり乗り気じゃないけれど(笑)
解いていきます。今回は問０６～問１０です。
この記事は、令和元年度秋期の応用情報技術者試験を扱った過去問解説です。
現在の試験制度とは一部異なりますが、コンピュータサイエンスの基礎知識や過去問学習には引き続き活用できます。令和元年度秋期 応用情報技術者試験 問０６～問１０ 解説
問６（テクノロジ系：アルゴリズムとプログラミング：データ構造）
先頭ポインタと末尾ポインタを持ち、多くのデータがポインタでつながった単方向の線形リストの処理のうち、先頭ポインタ又は各データのポインタをたどる回数が最も多いものはどれか。ここで、単方向のリストは先頭ポインタからつながっているものとし、追加するデータはポインタをたどらなくても参照できるものとする。
| ア | 先頭にデータを追加する処理 | |
|---|---|---|
| イ | 先頭のデータを削除する処理 | |
| ウ | 末尾にデータ追加する処理 | |
| エ | 末尾のデータを削除する処理 |
問６ 解答
リスト構造の問題です。
リスト構造は、データ構造の基本的なものの一つです。アルゴリズムとデータ構造を勉強すると必ず出てきます。実装はC言語などのような、アドレスでデータを参照する言語仕様で説明されていることが多いです。今回の問題も、ポインタにアドレスを格納してデータを繋いでいく仕様です。
リスト構造では、データ部とアドレス部（ポインタ）を持つデータ個体を作ります（下図（左））
ここのデータは別々に動的に作るので、その都度空いているところの適当なアドレスを持っています（連続して作ったからといって、配列の様にアドレスが連続しているわけではない）。
なので、配列などの連続したアドレスのデータの様に、次のアドレスを見れば次のデータが入っているわけではありません。
そこで、下図（右）のように、ポインタ（アドレス部）に次につなぎたいデータのアドレスを保存していきます。
これを次々行うことで、一連のポインタでつながれた連続したデータ構造ができます。
あとは、先頭のアドレスから順に、次のデータを示すポインタをたどっていけばデータを参照できます。
最後はポインタがどこにもつながっていない（NULL）データを見つけた時です。
ただし、データをたどるためには一番初めのアドレスを保存しておかなければならないので、先頭を保存しておくポインタ（Headポインタ）が必ず必要です。
これで、headからすべてのデータをたどることができるようになります。また、今回は次のデータを表すポインタだけ（単方向リスト）でしたが、前のデータを示すポインタを作ることにより、双方向に接続することや、もっと複雑な構造も可能になります。
。。。までが、リスト構造の基本です。
さて、問題に戻ると、「先頭ポインタと末尾ポインタをもち」とあります。先頭ポインタは先ほどのheadポインタのことです。そのほかに末尾ポインタ（最後のデータを指すポインタ）を持っています。
この状態に、ア～エの操作を加えることを考えます。
| ア | 先頭にデータを追加する処理 |
|---|
①用意した追加データのポインタ（アドレス部）に現在のheadに格納されているアドレスを代入
②headに追加データのアドレスを格納
追加するデータはポインタをたどることなくアクセスできるという条件ですので、ポインタをたどる回数は０回です。
| イ | 先頭のデータを削除する処理 |
|---|
先頭データを削除するには、
①先頭データのポインタに格納されているアドレスを、headに代入
することで、headから、２つ目のデータにアドレスが接続されます。元の先頭ノードが動的に確保されたものであれば、不要になったノードを適切に解放する必要があります。解放しないまま参照を失うと、メモリリークの原因になります。
ポインタをたどる回数は、先頭データのポインタを取ってこなければならないので、head→先頭データのポインタ、と辿りますので１回です。
| ウ | 末尾にデータ追加する処理 |
|---|
末尾にデータを追加するには、tailポインタがないと大変ですが、今回はtailポインタ＝末尾のデータのアドレスがあるのでラクチンです。
①tailポインタの指すデータの「ポインタ部」に追加データのアドレスを代入する（末尾なので、元はNULL）。
②tailポインタに追加データのアドレスを代入
ポインタをたどる回数は、tail→tailの指すデータのアドレス部で１回です。
| エ | 末尾のデータを削除する処理 |
|---|
末尾のデータを削除するには、
①末尾の１個手前のデータのアドレス（tailポインタの１個前）を得る
②tailポインタに末尾の１個前のデータのアドレスを代入
ここで、末尾の１個前のデータのアドレスを得るには、ちょっと大変な操作が必要です。
①作業用のポインタ変数を用意（ｔｍｐとする）
②headから、以下の条件を満たすまでデータをたどる
条件：現在のデータのアドレス部 ＝＝ tailのアドレス
③条件を満たさない時は、ｔｍｐ＝現在のデータのアドレス部
条件を満たしたときにｔｍｐに残っているのが、tailの１個前のデータである。
ということで（データ数-1）回のアドレス走査が必要ですので、
エが正解です。
問７（テクノロジ系：アルゴリズムとプログラミング：ハッシュアルゴリズム）
自然数をキーとするデータを、ハッシュ表を用いて管理する。キー\(x\)のハッシュ関数\(h(x)\)を
\(h(x)=x \bmod n\)
とすると、任意のキー\(a\)と\(b\)が衝突する条件はどれか。ここで\(n\)はハッシュ表の大きさであり、\(x \bmod n\)は\(x\)を\(n\)で割った余りを表す。
| ア | \(a+b\)が\(n\)の倍数 | イ | \(a-b\)が\(n\)の倍数 |
|---|---|---|---|
| ウ | \(n\)が\(a+b\)の倍数 | エ | \(n\)が\(a-b\)の倍数 |
問７ 解答
ハッシュ関数が、ハッシュ表上の同じインデックスを返してしまうことを衝突（collision）といいます。
今回はハッシュ関数が、
\[
x \bmod n
\]
です。
あるキー値 (a) と (b) があり、このハッシュ値が (x_{1}) と (x_{2}) だったとして考えてみます。
この場合、(x_{1}) と (x_{2}) はそれぞれ、(n) を (a)、(b) で割った余りですので、以下のように表されます。
\[
\begin{aligned}
x_{1} &= a \bmod n \
x_{2} &= b \bmod n
\end{aligned}
\]
ですので、(a)、(b) を (n) で割った商をそれぞれ (m)、(l) とすると、
\[
\begin{aligned}
a &= nm + x_{1} \
b &= nl + x_{2}
\end{aligned}
\]
と表されます。
それぞれの式を (x_{1})、(x_{2}) について変形すると、
\[
\begin{aligned}
x_{1} &= a - nm \
x_{2} &= b - nl
\end{aligned}
\]
となります。
ここで、ハッシュ値が同じになるときは、
\[
x_{1} = x_{2}
\]
となるので、
\[
a - nm = b - nl
\]
\[
a - b = nm - nl
\]
\[
a - b = n(m-l)
\]
が導かれます。
(m)、(l) は、(a)、(b) を (n) で割った商で整数です。
よって、
\[
m-l
\]
も整数となります。
この式は、(x_{1}=x_{2}) となるときは、「(a-b) が (n) の倍数であるとき」であることを示しています。
したがって、答えは、「イ」(a-b) が (n) の倍数、が正解となります。
問８（テクノロジ系：アルゴリズムとプログラミング：ソーティングアルゴリズム）
分割統治を利用した整列法はどれか。
| ア | 基数ソート | イ | クイックソート |
|---|---|---|---|
| ウ | 選択ソート | エ | 挿入ソート |
問８ 解答
ソーティングのアルゴリズムに関する知識を問う問題です。
分割統治法とは、大きな問題を小さな問題に分割して、小さな問題を順次解いていくことで結果的に大きな問題を解く手法です。
分割統治法を使ったよく見る処理として以下のようなものがあります。
- 二分探索法
- ハノイの塔の解法
- クイックソート
- マージソート
この時点で、答えは「イ」のクイックソートです。
が、クイックソート以外のアルゴリズムについては、過去記事で解説があります（動画付きのものもあります）ので、一度ご覧ください。（一番肝心なクイックソートの解説をしていない(笑)）
問９ （テクノロジ系：コンピュータの構成要素：CPUアーキテクチャ）
CPUのプログラムレジスタ（プログラムカウンタ）の役割はどれか。
| ア | 演算を行うために、メモリから読みだしたデータを保持する。 |
|---|---|
| イ | 条件付き分岐命令を実行するために、演算結果の状態を保持する。 |
| ウ | 命令のでコードを行うために、メモリから読みだした命令を保持する |
| エ | 命令を読みだすために、次の命令が格納されたアドレスを保持する。 |
問９ 解答
CPUの基本的な機能に関する問です。一昔前は、午後問題にアセンブラがあったので、プログラムカウンタなどは当然の知識だったのですが、最近は情報系の学校でもアセンブラやCPUアーキテクチャをそこまで詳しくやらなくなってきている気もします。（私の世代は、Z80のアセンブラを書いて、外部機器をいろいろ制御する実験が定番だった気がします）
CPUは基本的に、データの複製、数値演算、論理演算、値の比較程度のことしかできません。逆にこれらの単純なことを高速に行うことで大きな仕事をしています。
その時に、CPUの持つ一番小さく高速な記憶装置として働くのがレジスタです。
レジスタは、その役割によって、
- 専門的な役割が割り当てられている
- 専用レジスタ
- 役割が決まっておらずいろいろ使いまわせる
- 汎用レジスタ
に分類されます。
専用レジスタには、
- データレジスタ
- アドレスレジスタ
- インデックスレジスタ
- ベースレジスタ
- アキュムレータ
- フラグレジスタ
- プログラムレジスタ
など様々なものがあります。
この中でプログラムレジスタは、次に実行されるべき命令のアドレスを保持しているレジスタです。
次の命令のアドレスを逐次保持するので、プログラムカウンタとも呼ばれます。
正解はわかったと思いますが、選択肢を見ていくと、
| ア | 演算を行うために、メモリから読みだしたデータを保持する。 |
|---|
様々な演算を行うために、メモリからデータを読みだして演算されるまで保持するのが、汎用レジスタです。
| イ | 条件付き分岐命令を実行するために、演算結果の状態を保持する。 |
|---|
条件分岐命令のためのレジスタなので、フラグレジスタの説明です。
| ウ | 命令のデコードを行うために、メモリから読みだした命令を保持する |
|---|
プログラムカウンタの値を参照して、メインメモリから命令を読みだして保持します。
保持した命令は、デコーダに渡されて、その内容が解釈されます。
命令レジスタ（Instruction register)の説明です。
| エ | 命令を読みだすために、次の命令が格納されたアドレスを保持する。 |
|---|
メインメモリ中の、次に実行される命令の格納されているアドレスを保持しているレジスタです。
これが、プログラムレジスタの役割です。
問１０（テクノロジ系：コンピュータの構成要素：メモリアクセス）
容量が\(a\)Mバイトでアクセス時間が\(x\)ナノ秒の命令キャッシュと、容量が\(b\)M
バイトでアクセス時間が\(y\)ナノ秒の主記憶を持つシステムにおいて、CPUからみた、主記憶と命令キャッシュとを合わせた平均アクセス時間を表す式はどれか。ここで、読み込みたい命令コードがキャッシュに存在しない確率を\(r\)とし、キャッシュ管理に関するオーバーヘッドは無視できるものとする。
| ア | \(\displaystyle \frac{(1-r)\cdot a}{a+b}\cdot x + \frac{r\cdot b}{a+b}\cdot y\) | イ | \(\displaystyle (1-r)\cdot x + r \cdot y\) |
|---|---|---|---|
| ウ | \(\displaystyle \frac{r\cdot a}{a+b}\cdot x + \frac{(1-r)\cdot b}{a+b}\cdot y\) | エ | \(\displaystyle r\cdot x + (1-r)\cdot y\) |
問５ 解答
結構よく見る問題ですね。なんか、全く同じ問題が過去に出ていた気もします。
（後で、調べてみます）
キャッシュメモリときたら、以下の２つのキーワードを忘れないでください。
- ヒット率：目的のデータや命令がキャッシュメモリに存在する確率
- NFP（Not Found Probability）：キャッシュに目的のデータや命令がない確率（主記憶にはある）
ここで、
ヒット率＋NFP＝１
平均アクセス時間＝ヒット率×キャッシュのアクセス時間＋NFP×メインメモリのアクセス時間
が成り立ちます。
ここで気づいたと思いますが、平均アクセス時間にはメモリの容量は関係しません。
式にメモリサイズが入っている「ア」「ウ」は脱落です。
先ほどの平均アクセス時間の式に、出てきた記号を割り当てていくと、
\(\displaystyle ヒット率+NFP=１\)より
\(\displaystyle ヒット率=１-NFP=1-r\)
キャッシュのアクセス時間：\(x\)
主記憶のアクセス時間：\(y\)
\(\displaystyle \begin{eqnarray} 平均アクセス時間 &=& ヒット率\timesキャッシュのアクセス時間+NFP\timesメインメモリのアクセス時間 \\ &=& (1-r)\cdot x + r\cdot y \end{eqnarray}\)
「イ」が正解ですね。
所感
まったり５問解いてみました。
今回の５問は、基本情報と大差ない難易度でした（実際基本情報に同じ問題が出て要るっぽい）。
テクノロジ系はあんまりＦＥ，ＡＰの差ってないのかもしれないですね。
なにか、間違いや突っ込みどころなどありましたら、気軽にコメントください。
