応用情報技術者試験 最新問題のテクノロジ系をまったり解く 問06~問10【令和元年度秋試験】
R01 応用情報技術者試験 秋期試験に挑戦 問6~問10
前回に引き続き、あまり乗り気じゃないけれど(笑)
解いていきます。今回は問06~問10です。
令和元年度秋期 応用情報技術者試験 問06~問10 解説
問6(テクノロジ系:アルゴリズムとプログラミング:データ構造)
ア | 先頭にデータを追加する処理 | |
---|---|---|
イ | 先頭のデータを削除する処理 | |
ウ | 末尾にデータ追加する処理 | |
エ | 末尾のデータを削除する処理 |
問6 解答
リスト構造の問題です。
リスト構造は、データ構造の基本的なものの一つです。アルゴリズムとデータ構造を勉強すると必ず出てきます。実装はC言語などのような、アドレスでデータを参照する言語仕様で説明されていることが多いです。今回の問題も、ポインタにアドレスを格納してデータを繋いでいく仕様です。
リスト構造では、データ部とアドレス部(ポインタ)を持つデータ個体を作ります(下図(左))
ここのデータは別々に動的に作るので、その都度空いているところの適当なアドレスを持っています(連続して作ったからといって、配列の様にアドレスが連続しているわけではない)。
なので、配列などの連続したアドレスのデータの様に、次のアドレスを見れば次のデータが入っているわけではありません。
そこで、下図(右)のように、ポインタ(アドレス部)に次につなぎたいデータのアドレスを保存していきます。
これを次々行うことで、一連のポインタでつながれた連続したデータ構造ができます。
あとは、先頭のアドレスから順に、次のデータを示すポインタをたどっていけばデータを参照できます。
最後はポインタがどこにもつながっていない(NULL)データを見つけた時です。
ただし、データをたどるためには一番初めのアドレスを保存しておかなければならないので、先頭を保存しておくポインタ(Headポインタ)が必ず必要です。
これで、headからすべてのデータをたどることができるようになります。また、今回は次のデータを表すポインタだけ(たん方向リスト)でしたが、前のデータを示すポインタを作ることにより、双方向に接続することや、もっと複雑な構造も可能になります。
。。。までが、リスト構造の基本です。
さて、問題に戻ると、「先頭ポインタと末尾ポインタをもち」とあります。先頭ポインタは先ほどのheadポインタのことです。そのほかに末尾ポインタ(最後のデータを指すポインタ)を持っています。
この状態に、ア~エの操作を加えることを考えます。
ア | 先頭にデータを追加する処理 |
---|
①用意した追加データのポインタ(アドレス部)に現在のheadに格納されているアドレスを代入
②headに追加データのアドレスを格納
追加するデータはポインタをたどることなくアクセスできるという条件ですので、ポインタをたどる回数は0回です。
イ | 先頭のデータを削除する処理 |
---|
先頭データを削除するには、
①先頭データのポインタに格納されているアドレスを、headに代入
することで、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(テクノロジ系:アルゴリズムとプログラミング:ハッシュアルゴリズム)
自然数をキーとするデータを、ハッシュ表を用いて管理する。キーのハッシュ関数を
とすると、人気のキーとが衝突する条件はどれか。ここではハッシュ表の大きさであり、はをで割った余りを表す。
ア | がの倍数 | イ | がの倍数 |
---|---|---|---|
ウ | がの倍数 | エ | がの倍数 |
問2 解答
ハッシュ関数が、ハッシュ表上の同じインデックスを返してしまうことを衝突(collision)といいます。
今回はハッシュ関数が、
です。
あるキー値とがあり、このハッシュ値がとだったとして考えてみます。
この場合、とはそれぞれ、を、で割った余りですので、以下のように表されます。
ですので、、をで割った商をそれぞれ、とすると、
と表されます。
ここで、ハッシュ値が同じになるときはとなるので、
が導かれます。
は、をで割った商で整数です。
よって、も整数となります。
この式は、となるときは、「がの倍数であるとき」であることを示しています。
したがって、答えは、「イ」がの倍数 、が正解となります。
問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(テクノロジ系:コンピュータの構成要素:メモリアクセス)
容量がMバイトでアクセス時間がナノ秒の命令キャッシュと、容量がM
バイトでアクセス時間がナノ秒の主記憶を持つシステムにおいて、CPUからみた、主記憶と命令キャッシュとを合わせた平均アクセス時間を表す式はどれか。ここで、読み込みたい命令コードがキャッシュに存在しない確率をとし、キャッシュ管理に関するオーバーヘッドは無視できるものとする。
ア | イ | ||
---|---|---|---|
ウ | エ |
問5 解答
結構よく見る問題ですね。なんか、全く同じ問題が過去に出ていた気もします。
(後で、調べてみます)
キャッシュメモリときたら、以下の2つのキーワードを忘れないでください。
- ヒット率:目的のデータや命令がキャッシュメモリに存在する確率
- NFP(Not Found Probability):キャッシュに目的のデータや命令がない確率(主記憶にはある)
ここで、
ヒット率+NFP=1
平均アクセス時間=ヒット率×キャッシュのアクセス時間+NFP×メインメモリのアクセス時間
が成り立ちます。
ここで気づいたと思いますが、平均アクセス時間にはメモリの容量は関係しません。
式にメモリサイズが入っている「ア」「ウ」は脱落です。
先ほどの平均アクセス時間の式に、出てきた記号を割り当てていくと、
より
「イ」が正解ですね。