工学じじいの縁側日記

工学じじいの縁側日記

引退間際の工学じじいがきままに、プログラミングやデバイス、工学について呟きます。

応用情報技術者試験 最新問題のテクノロジ系をまったり解く 問06~問10【令和元年度秋試験】

R01 応用情報技術者試験 秋期試験に挑戦 問6~問10

f:id:gomta777:20191203143701p:plain


前回に引き続き、あまり乗り気じゃないけれど(笑)
解いていきます。今回は問06~問10です。



令和元年度秋期 応用情報技術者試験 問06~問10 解説

f:id:gomta777:20191203144205p:plain

問6(テクノロジ系:アルゴリズムとプログラミング:データ構造)

先頭ポインタと末尾ポインタを持ち、多くのデータがポインタでつながった単方向の線形リストの処理のうち、先頭ポインタ又は各データのポインタをたどる回数が最も多いものはどれか。ここで、単方向のリストは先頭ポインタからつながっているものとし、追加するデータはポインタをたどらなくても参照できるものとする。

先頭にデータを追加する処理
先頭のデータを削除する処理
末尾にデータ追加する処理
末尾のデータを削除する処理




問6 解答

リスト構造の問題です。
リスト構造は、データ構造の基本的なものの一つです。アルゴリズムとデータ構造を勉強すると必ず出てきます。実装はC言語などのような、アドレスでデータを参照する言語仕様で説明されていることが多いです。今回の問題も、ポインタにアドレスを格納してデータを繋いでいく仕様です。

リスト構造では、データ部とアドレス部(ポインタ)を持つデータ個体を作ります(下図(左))
ここのデータは別々に動的に作るので、その都度空いているところの適当なアドレスを持っています(連続して作ったからといって、配列の様にアドレスが連続しているわけではない)。
なので、配列などの連続したアドレスのデータの様に、次のアドレスを見れば次のデータが入っているわけではありません。
そこで、下図(右)のように、ポインタ(アドレス部)に次につなぎたいデータのアドレスを保存していきます。

図 リスト構造の接続前の個々のデータ(左) データを接続(右)

これを次々行うことで、一連のポインタでつながれた連続したデータ構造ができます。

図 接続されたリスト構造

あとは、先頭のアドレスから順に、次のデータを示すポインタをたどっていけばデータを参照できます。
最後はポインタがどこにもつながっていない(NULL)データを見つけた時です。
ただし、データをたどるためには一番初めのアドレスを保存しておかなければならないので、先頭を保存しておくポインタ(Headポインタ)が必ず必要です。

図 headポインタ

これで、headからすべてのデータをたどることができるようになります。また、今回は次のデータを表すポインタだけ(たん方向リスト)でしたが、前のデータを示すポインタを作ることにより、双方向に接続することや、もっと複雑な構造も可能になります。
。。。までが、リスト構造の基本です。

さて、問題に戻ると、「先頭ポインタと末尾ポインタをもち」とあります。先頭ポインタは先ほどのheadポインタのことです。そのほかに末尾ポインタ(最後のデータを指すポインタ)を持っています。

図 末尾ポインタ


この状態に、ア~エの操作を加えることを考えます。

先頭にデータを追加する処理

①用意した追加データのポインタ(アドレス部)に現在のheadに格納されているアドレスを代入
②headに追加データのアドレスを格納

図 先頭にデータを追加する手順

図 完成したリスト

追加するデータはポインタをたどることなくアクセスできるという条件ですので、ポインタをたどる回数は0回です。

先頭のデータを削除する処理

図 先頭データを削除

先頭データを削除するには、
①先頭データのポインタに格納されているアドレスを、headに代入

図 headに2番目のデータのアドレスを代入

することで、headから、2つ目のデータにアドレスが接続されます。あとは、先頭データ自体を別口の処理で削除すればいいですが、放っておいても特に問題ないといえばないです。(語弊はあります)

ポインタをたどる回数は、先頭データのポインタを取ってこなければならないので、head→先頭データのポインタ、と辿りますので1回です。

図 イの結果

末尾にデータ追加する処理

末尾にデータを追加するには、tailポインタがないと大変ですが、今回はtailポインタ=末尾のデータのアドレスがあるのでラクチンです。

図 末尾にデータを追加する操作

①tailポインタの指すデータの「ポインタ部」に追加データのアドレスを代入する(末尾なので、元はNULL)。
②tailポインタに追加データのアドレスを代入

図 末尾にデータを追加

ポインタをたどる回数は、tail→tailの指すデータのアドレス部で1回です。

末尾のデータを削除する処理

図 末尾データの削除

末尾のデータを削除するには、
①末尾の1個手前のデータのアドレス(tailポインタの1個前)を得る
②tailポインタに末尾の1個前のデータのアドレスを代入

図 末尾データの削除操作

図 末尾データの削除結果

ここで、末尾の1個前のデータのアドレスを得るには、ちょっと大変な操作が必要です。
①作業用のポインタ変数を用意(tmpとする)
②headから、以下の条件を満たすまでデータをたどる
条件:現在のデータのアドレス部 == tailのアドレス
③条件を満たさない時は、tmp=現在のデータのアドレス部

条件を満たしたときにtmpに残っているのが、tailの1個前のデータである。
問ことで(データ数-1)回のアドレス走査が必要ですので、
エが正解です。


問7(テクノロジ系:アルゴリズムとプログラミング:ハッシュアルゴリズム



自然数をキーとするデータを、ハッシュ表を用いて管理する。キーxハッシュ関数h(x)
h(x)=x \bmod n
とすると、人気のキーabが衝突する条件はどれか。ここでnはハッシュ表の大きさであり、x \bmod nxnで割った余りを表す。

a+bnの倍数 a-bnの倍数
na+bの倍数 na-bの倍数



問2 解答

ハッシュ関数が、ハッシュ表上の同じインデックスを返してしまうことを衝突(collision)といいます。
今回はハッシュ関数が、

x \bmod n

です。
あるキー値abがあり、このハッシュ値x_{1}x_{2}だったとして考えてみます。
この場合、x_{1}x_{2}はそれぞれ、nabで割った余りですので、以下のように表されます。

\begin{eqnarray}
x_{1} &=& a\bmod n \\
x_{2} &=& b\bmod n
\end{eqnarray}

ですので、abnで割った商をそれぞれmlとすると、
\begin{eqnarray}
a &=& nm+x_{1} \\
b &=& nl+x_{2}
\end{eqnarray}
と表されます。

\begin{eqnarray}
x_{1} &=& a - nm \\
x_{2} &=& b - nl
\end{eqnarray}

ここで、ハッシュ値が同じになるときはx_{1} = x_{2}となるので、

a-nm = b - nl
 a-b = nm-nl
a-b = n(m-l)

が導かれます。
m,lは、a,bnで割った商で整数です。
よって、m-lも整数となります。
この式は、x_{1}=x_{2}となるときは、「a-bnの倍数であるとき」であることを示しています。
したがって、答えは、「イ」a-bnの倍数 、が正解となります。



問8(テクノロジ系:アルゴリズムとプログラミング:ソーティングアルゴリズム


分割統治を利用した整列法はどれか。


基数ソート クイックソート
選択ソート 挿入ソート


問8 解答

ソーティングのアルゴリズムに関する知識を問う問題です。
分割統治法とは、大きな問題を小さな問題に分割して、小さな問題を順次解いていくことで結果的に大きな問題を解く手法です。
分割統治法を使ったよく見る処理として以下のようなものがあります。

この時点で、答えは「イ」のクイックソートです。
が、クイックソート以外のアルゴリズムについては、過去記事で解説があります(動画付きのものもあります)ので、一度ご覧ください。(一番肝心なクイックソートの解説をしていない(笑))

ko-gaku-jiji.hatenablog.jp
ko-gaku-jiji.hatenablog.jp
ko-gaku-jiji.hatenablog.jp


問9 (テクノロジ系:コンピュータの構成要素:CPUアーキテクチャ


CPUのプログラムレジスタ(プログラムカウンタ)の役割はどれか。


演算を行うために、メモリから読みだしたデータを保持する。
条件付き分岐命令を実行するために、演算結果の状態を保持する。
命令のでコードを行うために、メモリから読みだした命令を保持する
命令を読みだすために、次の命令が格納されたアドレスを保持する。



問9 解答

CPUの基本的な機能に関する問です。一昔前は、午後問題にアセンブラがあったので、プログラムカウンタなどは当然の知識だったのですが、最近は情報系の学校でもアセンブラやCPUアーキテクチャをそこまで詳しくやらなくなってきている気もします。(私の世代は、Z80アセンブラを書いて、外部機器をいろいろ制御する実験が定番だった気がします)

CPUは基本的に、データの複製、数値演算、論理演算、値の比較程度のことしかできません。逆にこれらの単純なことを高速に行うことで大きな仕事をしています。
その時に、CPUの持つ一番小さく高速な記憶装置として働くのがレジスタです。
レジスタは、その役割によって、

  • 専門的な役割が割り当てられている
  • 役割が決まっておらずいろいろ使いまわせる

に分類されます。
専用レジスタには、

など様々なものがあります。
この中でプログラムレジスタは、次に実行されるべき命令のアドレスを保持しているレジスタです。
次の命令のアドレスを逐次保持するので、プログラムカウンタとも呼ばれます。

正解はわかったと思いますが、選択肢を見ていくと、

演算を行うために、メモリから読みだしたデータを保持する。

様々な演算を行うために、メモリからデータを読みだして演算されるまで保持するのが、汎用レジスタです。

条件付き分岐命令を実行するために、演算結果の状態を保持する。

条件分岐命令のためのレジスタなので、フラグレジスタの説明です。

命令のデコードを行うために、メモリから読みだした命令を保持する

プログラムカウンタの値を参照して、メインメモリから命令を読みだして保持します。
保持した命令は、デコーダに渡されて、その内容が解釈されます。
命令レジスタ(Instruction register)の説明です。

命令を読みだすために、次の命令が格納されたアドレスを保持する。

メインメモリ中の、次に実行される命令の格納されているアドレスを保持しているレジスタです。
これが、プログラムレジスタの役割です。



問10(テクノロジ系:コンピュータの構成要素:メモリアクセス)


容量がaMバイトでアクセス時間xナノ秒の命令キャッシュと、容量がbM
バイトでアクセス時間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



問5 解答

結構よく見る問題ですね。なんか、全く同じ問題が過去に出ていた気もします。
(後で、調べてみます)

キャッシュメモリときたら、以下の2つのキーワードを忘れないでください。

  • ヒット率:目的のデータや命令がキャッシュメモリに存在する確率
  • NFP(Not Found Probability):キャッシュに目的のデータや命令がない確率(主記憶にはある)

ここで、
ヒット率+NFP=1
平均アクセス時間=ヒット率×キャッシュのアクセス時間+NFP×メインメモリのアクセス時間
が成り立ちます。

ここで気づいたと思いますが、平均アクセス時間にはメモリの容量は関係しません。
式にメモリサイズが入っている「ア」「ウ」は脱落です。

先ほどの平均アクセス時間の式に、出てきた記号を割り当てていくと、
\displaystyle ヒット率+NFP=1より
\displaystyle ヒット率=1-NFP=1-r

キャッシュのアクセス時間x
主記憶のアクセス時間y
\displaystyle
\begin{eqnarray}
平均アクセス時間 &=& ヒット率\timesキャッシュのアクセス時間+NFP\timesメインメモリのアクセス時間 \\
&=& (1-r)\cdot x + r\cdot y
\end{eqnarray}

「イ」が正解ですね。


所感

まったり5問解いてみました。
今回の5問は、基本情報と大差ない難易度でした(実際基本情報に同じ問題が出て要るっぽい)。
テクノロジ系はあんまりFE,APの差ってないのかもしれないですね。

なにか、間違いや突っ込みどころなどありましたら、気軽にコメントください。




良かったら、押してください!↓↓↓
にほんブログ村 科学ブログ コンピュータサイエンスへ
にほんブログ村