平成２２年度 秋期 応用情報技術者試験 問１−２０ 問題編

応用情報

（応用情報技術者試験）

問２ ａ，ｂ，ｃ，ｄの４文字からなるメッセージを符号化してビット列にする方法としてア〜エの４通りを考えた。この表はａ，ｂ，ｃ，ｄの各文字１文字を符号化するときのビット列を表している。メッセージ中でのａ，ｂ，ｃ，ｄの出現頻度は、それぞれ５０％、３０％、１０％、１０％であることが分かっている。符号化されたビット列から元のメッセージが一意に復号可能であって、ビット列の長さが最も短くなるものはどれか。

解答 ウ

解説 まず、一意に復号できるかどうかを考えます。 選択肢ア：ａａ（００）とｃ（００）などが同じになり、一意に復号できません。 選択肢イ：ｂｃ（０１１０）とａｄａ（０１１０）などが同じになり、一意に復号できません。 選択肢ウ：一意に復号できます。 選択肢エ：一意に復号できます。 つぎに、一意に復号できる選択肢ウと選択肢エの平均ビット列を求めます。 選択肢ウ：０．５×１ビット＋０．３×２ビット＋０．１×３ビット＋０．１×３ビット＝０．５＋０．６＋０．３＋０．３＝１．７ビット 選択肢エ：０．５×２ビット＋０．３×２ビット＋０．１×２ビット＋０．１×２ビット＝１＋０．６＋０．２＋０．２＝２ビット なお、このように出現頻度の多いものにビット数の短いものを割り当てる方法を、ハフマン符号化といいます。

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

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

解答 エ

解説 まず、今回のリスト状のデータ構造を以下に図示します。 これを元に、各選択肢のポインタ参照回数を考えていきます。ポインタの書き換えは回数に入らないので注意しましょう。 選択肢ア：先頭のポインタを追加データに書き換える。追加データのポインタを現在先頭のデータのポインタに書き換える。（参照０回、書き換え２回） 選択肢イ：先頭のポインタを｢先頭→先頭のデータ２番目のデータ｣でたどった２番目のデータに書き換えます。（参照２回、書き換え１回） 選択肢ウ：｢末尾→末尾のデータ｣でたどった、現在末尾のデータを追加でのポインタに書き換える。末尾のポインタを追加したデータに書き換える（参照１回、書き換え２回） 選択肢エ：｢先頭→先頭のデータ→２番目のデータ ・・・ 末尾から２番目のデータ｣でたどった、末尾から２番目のポインタをnil(無し）に書き換える。末尾のポインタを今たどった、末尾から２番目のデータに書き換える。（参照データ個数−１回、書き換え２回） リスト構造は、ポインタを書き換えるという方法で追加、変更、削除を表します。データそのものを消すわけではないので注意しましょう。

問６ 探索表の構成法を例とともにａ〜ｃに示す。探索の平均計算量が最も小さい探索手法の組合せはどれか。ここで、探索表のコードの空欄は表の空きを示す。

解答 ア

解説 まず、３つの探索法についてまとめます。データ量をｎとしたときのオーダ（検索時間）もあわせてまとめます。 ２分探索：ソートされているデータに対して、中間値と目的とを比較することで、大きいグループと小さいグループに分け、１回の検索で探索範囲を半分にしていく。オーダはｌｏｇ2ｎ 線形探索：上から一つずつ比較していく方法。オーダはｎ ハッシュ検索：ハッシュ関数を使って、格納場所を決める方法。ハッシュ値が同じになる衝突（シノニム）などがなければ、１度で検索場所が決まります。オーダは１ それでは、それぞれの表に適した検索法を考えます。 表ａ：コードが順番にならんでいる（ソートされている）ので、線形探索よりも２分探索のほうが高速に検索ができるので、２分探索を利用します。 表ｂ：コードに規則性がないが、使用頻度順にならんでいるということは、上にあるものほど発見しやすいので、線形探索を利用します。 表ｃ：ハッシュにより場所を決めているので、同じ関数を利用して求めるのが一番よいので、ハッシュ表探索を利用します。

問７ 正の整数Ｍに対して、次の二つの流れ図に示すアルゴリズムを実行したとき、結果ｘの値が等しくなるようにしたい。ａに入れる条件として、適切なものはどれか。

ア ｎ＜Ｍ イ ｎ＞Ｍ−１ ウ ｎ＞Ｍ エ ｎ＞Ｍ＋１

解答 ウ

解説 まず、左の流れ図をみると、ｘに１を入れた後、ｎをＭから１まで動かし、Ｍの階乗を計算しています。これと同じものを右の流れ図で行うためには、ｘ×Ｍとなるまでｎを増やす必要があります。右の流れ図は階乗を計算した後に、終了の判定が行われるのでｎ＝ｎ＋１が行われてからＭとの比較が行われます。つまり、Ｍ＋１のときにループを抜けるようにする必要があります。 分かりにくい方は、実際に値を入れて計算してみるといいと思います。 今『Ｍ＝３』として計算してみましょう。 １回目 １→ｘ １→ｎ １×１→ｘ ｎ＝ｎ＋１＝２ 続ける（ｎ＝２） ２回目 １×２→ｘ ｎ＝ｎ＋１＝３ 続ける（ｎ＝３） ３回目 ２×３→ｘ ｎ＝ｎ＋１＝４ 終わる（ｎ＝４） 選択肢ア：ｎ＜３では、一番最初のループで抜けてしまいます。 選択肢イ：４＞３−１では、その前にループを抜けてしまいます。 選択肢ウ：４＞３で確かにＹＥＳとなり、ループを抜けることができます。 選択肢エ：４＞３＋１ではＮＯでまだループは続きます。 よって、正解はウとなります。

問９ 動作クロック周波数が７００ＭＨｚのＣＰＵで、命令の実行に必要なクロック数及びその命令の出現率が表に示す値である場合、このＣＰＵの性能は約何ＭＩＰＳか。

ア １０ イ ５０ ウ ７０ エ １００

解答 エ

解説 まず、ＭＩＰＳは、１秒間に何百万個の命令が実行できるかを表しています。次に、命令実行に必要な平均クロック数を求めると４×０．３＋８×０．６＋１０×０．１＝７となります。よって、７命令を７００ＭＨｚで実行すると、１秒間に７００Ｍ／７＝１００ＭＩＰＳとなります。

問１０ スーパスカラの説明はどれか。

ア 処理すべきベクトルの長さがベクトルレジスタより長い場合、ベクトルレジスタ長の組に分割して処理を繰り返す方式である。 イ パイプラインを更に細分化することによって、高速化を図る方式である。 ウ 複数のパイプラインを用い、同時に複数の命令を実行可能にすることによって、高速化を図る方式である。 エ 命令語を長く取り、一つの命令で複数の機能ユニットを同時に制御することによって、高速化を図る方法である。

解答 ウ

解説 スーパースカラ（スーパースケーラ）方式は、パイプライン技術の応用的な技術です。パイプラインとは、下の図のように命令の段階を少しずつずらして多重化する方式です。 これを応用して、命令パイプライン上で複数の命令を同時に実行する方式をスーパースカラ方式といいます。例を図示します。 選択肢アは、ベクトルプロセッサの説明です。 選択肢イは、スーパーパイプラインの説明です。 選択肢エは、ＶＬＩＷ（Very Long Instruction Word）の説明です。

問１１ 容量がａＭバイトでアクセス時間がｘナノ秒のキャッシュメモリと、容量がｂＭバイトでアクセス時間がｙナノ秒の主記憶をもつシステムにおいて、ＣＰＵからみた、主記憶とキャッシュメモリとを合わせた平均アクセス時間を表す式はどれか。ここで、読み込みたいデータがキャッシュメモリに存在しない確率をｒとし、キャッシュメモリ管理に関するオーバヘッドは無視できるものとする。

解答 イ

解説 キャッシュメモリは、主記憶装置（＝メインメモリ）とＣＰＵとの処理能力の速度の差を埋めるために用いられるメモリです。メインメモリはまず、キャッシュメモリにデータを探しに行き、そのデータがある場合は、キャッシュメモリから、ない場合はメインメモリからデータを読み出します。よって、存在しない確率 ×メインメモリの読み込み速度＋存在する確率×キャッシュメモリの読み込み速度となります。両者の容量はアクセス速度には関係がありません。

問１４ 商品検索と発注入力を行うＷｅｂシステムについて、時間帯別のトランザクション数を表１に、ＴＰＳ（Transaction Per Second）と必要なＣＰＵ数の関係を表２に示す。このＷｅｂシステムに必要なＣＰＵ数は最低幾つか。ここで、ＯＳのオーバヘッドなどの処理については無視でき、トランザクションはそれぞれの時間帯の中で均等に発生するものとする。

ア １ イ ２ ウ ３ エ ４

解答 イ

解説 必要なＣＰＵ数を求めるには、最も処理量が多いときに何個のＣＰＵが必要かをもとめます。 一番処理量が多いのは、１１：００〜１２：００の時間帯でトランザクション数は４８０００＋２４０００＝７２０００件です。ＴＰＳは１秒間に処理できるトランザクションの量をあらわします。７２０００件のトランザクションを１時間（＝３６００秒）で処理するので、ＴＰＳは７２０００／３６００＝２０件／秒となります。 ＴＰＳが２０以下は２個のＣＰＵが必要となっているので、選択肢イが正解となります。

問１７ ３台の装置Ｘ〜Ｚを接続したシステムＡ，Ｂの稼動率について、適切なものはどれか。ここで、３台の装置の稼働率は、いずれも０より大きく１より小さいものとする。

ア 各装置の稼働率の値によって、ＡとＢの稼働率のどちらが高いかは変化する。 イ 常にＡとＢの稼働率は等しい。 ウ 常にＡの稼働率が高い。 エ 常にＢの稼働率が高い。

解答 エ

解説 ３台の装置Ｘ，Ｙ，Ｚの稼働率をそれぞれｘ、ｙ、ｚとして、全体の稼働率を計算し比較して見ます。 Ａ：ＸとＹの並列部×ｚ＝｛１−（１−ｘ）×（１−ｙ）｝ｚ Ｂ：１−（１−ＸとＹの直列部）×（１−ｚ）＝１−（１−ｘｙ）×（１−ｚ） 次に、それぞれを展開して比較しやすいようにします。×は省略します。 Ａ：ｚ−（１−ｘ）（１−ｙ）ｚ＝ｚ−（１−ｘ−ｙ＋ｘｙ）ｚ＝ｚ−（ｚ−ｘｚ−ｙｚ＋ｘｙｚ）＝ｚ−ｚ＋ｘｚ＋ｙｚ−ｘｙｚ＝ｘｚ＋ｙｚ−ｘｙｚ Ｂ：１−（１−ｘｙ−ｚ＋ｘｙｚ）＝１−１＋ｘｙ＋ｚ−ｘｙｚ＝ｘｙ＋ｚ−ｘｙｚ ｘｚ＋ｙｚ−ｘｙｚとｘｙ＋ｚ−ｘｙｚ：まず、両方にｘｙｚを加えて−ｘｙｚを除きます。 ｘｚ＋ｙｚとｙｚ＋ｚ：つぎに、両方からｘｚを引いて＋ｘｚを除きます。 ｘｚとｚ ｘ、ｚはともに１より小さいのでｘｚ＜ｚ（０．ａ，０．ｂ＜０．ａ×０．ｂ）となります。（接続的な意味を考えると｛ｘとｚの直列｝と｛ｚ｝の稼働率はｚのほうが高いという意味です。）よってＢの稼働率のほうが常に稼働率は高くなります。

問１８ 五つのタスクＡ〜Ｅの優先度と、各タスクを単独で実行した場合のＣＰＵと入出力装置（Ｉ／Ｏ）の動作順序と処理時間は、表のとおりである。優先度“高”のタスクＡとＢ〜Ｅのどのタスクを組み合わせれば、組み合わせたタスクが同時に実行を開始してから、両方のタスクの実行が終了するまでの間のＣＰＵの遊休時間をゼロにできるか。ここで、Ｉ／Ｏは競合せず、ＯＳのオーバヘッドは無視できるものとする。また、表の（ ）内の数字は処理時間を表すものとする。

解答 ウ

解説 遊休時間が最小ではなく、ゼロという仮定があるのでそれを利用した高速な解法を考えます。 遊休時間がないということは、２つのタスクが同時にＩ／Ｏ処理にならないということです。（両方ともＩ／ＯになるとＣＰＵに遊休時間が発生します。）これを踏まえて、どのようにＣＰＵとＩ／Ｏが実行されていくかを以下にまとめます。 １．タスクＡの１回目のＣＰＵ ２．優先度が低いタスクの１回目のＣＰＵとタスクＡの１回目のＩ／Ｏ ３．タスクＡの２回目のＣＰＵと優先度の低いタスクの１回目のＩ／Ｏ ４．優先度の低いタスクの２回目のＣＰＵとタスクＡの２回目のＩ／Ｏ ５．タスクＡの３回目のＣＰＵと優先度の低いタスクの２回目のＩ／Ｏ ６．優先度の低いタスクの３回目のＣＰＵ ＣＰＵの時間＜Ｉ／Ｏの時間が途中で発生するとＩ／Ｏ待ちとなります。よって常にＣＰＵ≧Ｉ／Ｏとなるように選べばよいということになります。 タスクＢ １．タスクＡのＣＰＵ→３ ２．タスクＢのＣＰＵ→２、タスクＡのＩ／Ｏ→３ この時点でＣＰＵ＜Ｉ／Ｏとなったので、遊休時間が発生する。 タスクＣ １．タスクＡのＣＰＵ→３ ２．タスクＣのＣＰＵ→３、タスクＡのＩ／Ｏ→３ ３．タスクＡのＣＰＵ→３、タスクＣのＩ／Ｏ→２ ４．タスクＣのＣＰＵ→２、タスクＡのＩ／Ｏ→３ この時点でＣＰＵ＜Ｉ／Ｏとなったので、遊休時間が発生する。 タスクＤ １．タスクＡのＣＰＵ→３ ２．タスクＤのＣＰＵ→３、タスクＡのＩ／Ｏ→３ ３．タスクＡのＣＰＵ→３、タスクＤのＩ／Ｏ→２ ４．タスクＤのＣＰＵ→３、タスクＡのＩ／Ｏ→３ ５．タスクＡのＣＰＵ→２、タスクＤのＩ／Ｏ→１ ６．タスクＤのＣＰＵ→４ すべてにおいて、ＣＰＵ≧Ｉ／Ｏだったので遊休時間はない。 タスクＥ １．タスクＡのＣＰＵ→３ ２．タスクＥのＣＰＵ→３、タスクＡのＩ／Ｏ→３ ３．タスクＡのＣＰＵ→３、タスクＥのＩ／Ｏ→４ この時点でＣＰＵ＜Ｉ／Ｏとなったので、遊休時間が発生する。 わからない場合は、以下のようにタスクＡと他のタスクのＣＰＵ，Ｉ／Ｏの時間を表や図にして回答してもよいと思います。