平成２１年度 春期 基本情報技術者試験 問１−２０ 解答編



このページは

基本情報

（基本情報技術者試験）

の解答と解説のページです。

問題だけで勉強したい方は目次へ戻ってください

問１ 数値を２進数で格納するレジスタがある。このレジスタに正の整数ｘを設定した後、“レジスタの値を２ビット左にシフトして、ｘを加える”操作を行うと、レジスタの値はｘの何倍になるか。ここで、あふれ（オーバフロー）は、発生しないものとする。
ア ３
イ ４
ウ ５
エ ６
解答 ウ
解説 桁あふれのない正の整数の２進数は、左にｎビットシフトすると２n倍されるという性質があります。（１０進数でも３４を３４０にすると１０倍になるのと同じです）また、もともとの値を加えるということは、１倍を加えるということなので、２2+1で５倍になります。
問２ ００００〜４９９９のアドレスのハッシュ表があり、レコードのキー値からアドレスに変換するアルゴリズムとして基数変換法を用いる。キー値が５５５５０のときのアドレスはどれか。ここで、基数変換法とは、キー値を１１進数と見なし、１０進数に変換した後、下４けたに対して０．５を乗じた結果（小数点以下は切捨て）をレコードのアドレスとする。
ア ０２６０
イ ２５２５
ウ ２７７５
エ ４４０５
解答 ア
解説 まずは、５５５５０を１０進数に直します。０×１１0＋５×１１1＋５×１１2＋５×１１3＋５×１１4＝０＋５×１１＋５×１２１＋５×１３３１＋５×１４６４１＝０＋５５＋６０５＋６６５５＋１４６４１＋７３２０５＝８０５２０

これの下４けたを半分にしたものは０２６０となります。
問３ 画像（問3）を表示できません と等しいものはどれか。ここで、・は論理積、＋は論理和、ＸはＸの否定を表す。
ア Ａ・Ｂ＋Ａ・Ｃ
イ Ａ・Ｂ＋Ａ・Ｃ
ウ （Ａ＋Ｂ）・（Ａ＋Ｃ）
エ （Ａ＋Ｂ）・（Ａ＋Ｃ）
解答 ア
解説 この問題はド・モルガンの定理と呼ばれる以下のような変換法則を利用します。

（Ａ＋Ｂ） ＝ Ａ・Ｂ
（Ａ・Ｂ） ＝ Ａ＋Ｂ

つまり、以下のようにド・モルガンの定理を２回利用して変換します。

画像（問3kai）を表示できません

あとは、＋より・の方が優先順位が高いので（ ）が省略され、二重否定を除くとＡ・Ｂ＋Ａ・Ｃとなります。

どうしても分からない場合は、真理値表などから求めるのも一つの手です。
問４ 文字列中で同じ文字が繰り返される場合、繰り返し部分をその反復回数と文字の組に置き換えて文字列をを短くする方法はどれか。
ア ＥＢＣＤＩＣ符号
イ 巡回符号
ウ ハフマン符号
エ ランレングス符号化
解答 エ
解説 ランレングス符号化とは、『ＡＡＡＡＡＢＢＢＣＣＣＣＣＣＣ』を『Ａ５Ｂ３Ｃ７』のように文字とその連続回数を使って圧縮をする方法です。なお、ＥＢＣＤＩＣ符号は、ＩＢＭのメインフレーム用の文字コードです。巡回符号は誤り検出の一種で、ハフマン符号は高い出現率の符号に短い文字コードを割り当てることで圧縮をするものです。
問５ 関数や手続を呼び出す際に、戻り値番地や処理途中のデータを一時的に保存するのに適したデータ構造はどれか。
ア ２分探索木
イ キュー
ウ スタック
エ 双方向連結リスト
解答 ウ
解説 関数を呼び出すときには、戻ってくるときのために、データを保存しておかなければなりません。それは、後入先出法（ＬＩＦＯ）で管理されます。下に先入先出法（ＦＩＦＯ）であるキューと合わせて図示しておきます。

スタックとキュー
問６ 配列と比較した場合の連結リストの特徴に関する記述として、適切なものはどれか。
ア 要素を更新する場合、ポインタを順番にたどるだけなので、処理時間は短い。
イ 要素を削除する場合、削除した要素から後ろにあるすべての要素を前に移動するので、処理時間は長い。
ウ 要素を参照する場合、ランダムにアクセスできるので、処理時間は短い。
エ 要素を挿入する場合、数個のポインタを書き換えるだけなので、処理時間は短い。
解答 エ
解説 各選択肢の解説を一つずつしていきます。

更新は、ポインタを順にたどるので時間がかかります。
削除は、削除する前のリストのポインタを変えるだけでできます。
参照は、ポインタを順にたどるので時間がかかります。
挿入は、挿入するリスト、挿入する前後の合わせて３つのポインタを変えるだけですみます。
下に配列とリストのイメージを図示します。

配列とリスト
問７ 昇順に整列されたｎ個のデータが配列に格納されている。探索したい値を２分探索法で探索するときの、およその比較回数を求める式はどれか。
ア ｌｏｇ2ｎ
イ （ｌｏｇ2ｎ＋１）／２
ウ ｎ
エ ｎ2
解答 ア
解説 ２分探索は、１回の検索で探索範囲を半分にします。つまり、１探索できる個数は、１回で１／２。２回で１／４。３回で１／８・・・と範囲を狭められます。この探索回数をｎとすると比較回数はｌｏｇ2ｎとなります。（また、およそというのは、２nのデータサイズでなかった場合には近似になるためです。）
問８ 自然数ｎに対して、次のように再帰的に定義される関数ｆ（ｎ）を考える。ｆ（５）の値はどれか。

ｆ（ｎ）：ｎ≦１ then return 1 else return ｎ＋ｆ（ｎ−１）
ア ６
イ ９
ウ １５
エ ２５
解答 ウ
解説 順番にトレースしていきます。
ｆ（５）＝５＋ｆ（４）
ｆ（４）＝４＋ｆ（３）
ｆ（３）＝３＋ｆ（２）
ｆ（２）＝２＋ｆ（１）
ｆ（１）＝１

よって、ｆ（２）＝３、ｆ（３）＝６、ｆ（４）＝１０、ｆ（５）＝１５となります。

この関数が、Σの再帰的な関数だと気づけばすぐに解くことがでいます。
問９ 平均命令実行時間が２０ナノ秒のコンピュータがある。このコンピュータの性能は何ＭＩＰＳか。
ア ５
イ １０
ウ ２０
エ ５０
解答 エ
解説 平均命令実効時間が２０ナノ秒ということは、２０ナノ秒で１回の処理クロックが発生するということです。一方でＭＩＰＳとは、１秒間で何百万命令できるかということです。
つまり、２０ナノ秒×ａ命令＝１秒。ａ命令＝１／（２０×１０-9）秒＝１×１０9×１／２０秒＝０．０５Ｇ命令＝５０百万命令となります。

計算に必要な、下の接頭語はきちんと覚えておきましょう。

１０-9：ナノ(n)
１０-6：マイクロ(μ)
１０-3：ミリ(m)
１０3：キロ(K)
１０6：メガ(M)
１０9：ギガ(G)
問１０ シングルチップマイコンの特徴として、最も適切なものはどれか。
ア ＰＣのメインＣＰＵに適している。
イ ＲＯＭは内蔵されているが、ＲＡＭは内蔵されていない。
ウ 高速処理システム又は大規模なシステムに適している。
エ 入出力機能が内臓されている。
解答 エ
解説 マイコンとは、電子機器を制御するために、使われる半導体チップをいいます。その中の一種でシングルチップマイコンとは、一つの基盤・回路上にＲＯＭ・ＲＡＭ、インタフェース類が付属されたマイコンをいいます。
問１１ プロセッサにおけるパイプライン処理方式を説明したものはどれか。
ア 単一の命令を基に、複数のデータに対して複数のプロセッサが同期をとりながら並列にそれぞれのデータを処理する方法
イ 一つのプロセッサにおいて、単一の命令に対する実行時間をできるだけ短くする方式
ウ 一つのプロセッサにおいて、複数の命令を少しずつ段階をずらしながら同時実行する方式
エ 複数のプロセッサが、それぞれ独自の命令を基に複数のデータを処理する方式
解答 ウ
解説 パイプラインとは、下の図のように命令の段階を少しずつずらして行う方式です。なお各段を多重化したスーパースケーラ（スーパスカラ）方式というのもあります。

パイプライン

なお、選択肢アはＳＩＭＤ（並列性におけるのフリンの分類の一つ）、選択肢イはＲＩＳＣ（プロセッサ設計の一種）、選択肢エはＭＩＭＤ（並列性におけるのフリンの分類の一つ）
問１２ キャッシュメモリに関する記述のうち、適切なものはどれか。
ア 書込み命令を実行したときに、キャッシュメモリと主記憶の両方を書き換える方式と、キャッシュメモリだけを書き換えておき、主記憶の書換えはキャッシュメモリから当該データが追い出されるときに行う方式とがある。
イ キャッシュメモリにヒットしない場合に割込みが生じ、プログラムによって主記憶からキャッシュメモリにデータが転送される。
ウ キャッシュメモリは、実記憶と仮想記憶のメモリ容量の差を埋めるために採用される。
エ 半導体メモリのアクセス速度の向上が著しいので、キャッシュメモリの必要性は減っている。
解答 ア
解説 キャッシュメモリは、主記憶とＣＰＵのレジスタの速度の差を埋めるために用いられるものです。データをキャッシュメモリと主記憶の同時に書き込むライトスルー方式と、退避するときのみ書き込むライトバック方式があります。

キャッシュメモリにない場合は、主記憶からロードされますが、割り込みを使ったプログラムによるロードではありません。
問１３ ＲＡＩＤ１〜５の各構成は、何に基づいて区別されるか。
ア 構成する磁気ディスク装置のアクセス性能
イ コンピュータ本体とのインタフェースの違い
ウ データ及び冗長ビットの記憶方法と記憶位置の組合せ
エ 保障する信頼性のＭＴＢＦ値
解答 ウ
解説 ＲＡＩＤ（Redundant Arrays of Inexpensive Disks あるいはRedundant Arrays of Independent Disks）とは、複数のＨＤＤを１台の高信頼性のＨＤＤとして利用する技術のことです。ＲＡＩＤ１〜５は冗長ビットをどこに配置するかで決まります。代表的なＲＡＩＤの例を下に示します。

ＲＡＩＤ０（ストライピング）：複数のＨＤＤに分散してデータを書き込む（冗長性はない）
ＲＡＩＤ１（ミラーリング）：複数のＨＤＤに同じデータを書き込む
ＲＡＩＤ５：ブロック単位で冗長データをもつが、特定のドライブに冗長データを書き込むということはしない。

また、複数の技術を組み合わせた、ＲＡＩＤ１＋０、ＲＡＩＤ０＋１、ＲＡＩＤ５＋０、ＲＡＩＤ０＋５、ＲＡＩＤ５＋１、ＲＡＩＤ１＋５などもあります。
問１４ プラズマディスプレイの説明として、適切なものはどれか。
ア ガス放電によって発生する光を利用して映像を表示する。
イ 自身では発光しないので、バックライトを使って映像を表示する。
ウ 電極の間に有機化合物を挟んだ構造で、これに電気を通すと発光することを利用して映像を表示する。
エ 電子銃から電子ビームを発射し、管面の蛍光体に当てて発光させ、文字や映像を表示する。
解答 ア
解説 ディスプレイに関する問題の出題率は高いので、以下にまとめます。

ＣＲＴ：いわゆる普通のブラウン管のディスプレイ。電子ビームと偏光版を使って画像を作ります。（選択肢エに相当）
ＰＤＰ：ＰはプラズマのＰで、高い電力が必要となります。（選択肢アに相当）
ＴＦＴ：ＴはトランジスタのＴで、１つ１つの画素をトランジスタの発光で実現しています。
有機ＥＬ：自らの発光でバックライトの不要なタイプ。次世代に期待されています。（選択肢ウに相当）
液晶：光の透過を画素ごとに制御し、カラーフィルタを用いて色を表現する。自ら発光はしない（選択肢イに相当）
問１５ フォールトトレラントシステムの説明として、適切なものはどれか。
ア システムが部分的に故障しても、システム全体としては必要な機能を維持するシステム
イ 地域的な災害などの発生に備えて、遠隔地に予備を用意しておくシステム
ウ 複数のプロセッサがネットワークを介して接続され、資源を共有するシステム
エ 複数のプロセッサで一つのトランザクションを並行して処理し、結果を照合するシステム
解答 ア
解説 重要なシステム設計法についてまとめて起きます。

フォールトトレラント：障害時に全体が停止するということなく、動作し続けるようなシステムを設計するもの。
フォールトアボイダンス：システムの構成要素の信頼性を高め, 元から故障が極力発生しないように設計すること。
フェールセーフ：障害が発生した場合、常に安全側に制御・停止すること。
フェールソフト：障害が発生した場合、故障した個所を切り離すなどして、稼動を続けること。
フールプルーフ：ユーザが誤った操作をした場合、危険に晒されることがないように、事前に安全策を行うこと。

なお、選択肢イはリモートバックアップ、選択肢ウはグリッドコンピュータ、選択肢エはデュアルシステムの説明です。
問１６ 東京〜大阪及び東京〜名古屋がそれぞれ独立した通信回線で接続されている。東京〜大阪の稼働率は０．９、東京〜名古屋の稼働率は０．８である。東京〜大阪の稼働率を０．９５以上に改善するために、大阪〜名古屋にバックアップ回線を新設することを計画している。新設される回線の稼働率は最低限幾ら必要か。
ア ０．１６７
イ ０．２０５
ウ ０．５５９
エ ０．６２５
解答 エ
解説 まず、分かりやすく図にすると下にようになります。

画像（問16kai）を表示できません

ここで、東京−名古屋−大阪は直列になっており、０．８とXの直列となります。また、東京−大阪は０．８Xと０．９の並列になっています。

並列の稼働率は１−両方が稼動しない確率＝１−（１−東京−名古屋−大阪の稼働率）×（１−東京−大阪の稼働率）

０．９５≧１−（１−０．８X）×（１−０．９） ＝ １−（０．１−０．０８X）＝０．９＋０．０８X

０．０５≧０．０８X により、５／８≦Xとなればいいので、０．６２５となります。
問１７ システムの信頼性を表す指標であるＲＡＳのうち、可用性(Availability)を表す尺度はどれか。
画像（問17ans）を表示できません
解答 ア
解説 ＲＡＳとは、ＲＡＳＩＳのうちの最初の３つを指す言葉です。ＲＡＳＩＳについて下にまとめます。

Ｒｅｌｉａｂｉｌｉｔｙ:（信頼性）:故障しにくい性質（ＭＴＢＦに相当）
Ａｖａｉｌａｂｉｌｉｔｙ:（可用性）:いつでも使える性質（稼働率＝ＭＴＢＦ／（ＭＴＢＦ＋ＭＴＴＲ）に相当）
Ｓｅｒｖｉｃｅａｂｉｌｉｔｙ:（保守性）:故障をすぐに修復できる性質（ＭＴＴＲに相当）
Ｉｎｔｅｇｒｉｔｙ:（保全性）:データが一貫しており、矛盾がない性質
Ｓｅｃｕｒｉｔｙ:（安全性）:機密性が高く、不正にアクセスされない性質
問１８ プログラムのＣＰＵ実行時間が３００ミリ秒、入出力時間が６００ミリ秒、その他のオーバヘッドが１００ミリ秒の場合、ターンアラウンドタイムを半分に改善するには、入出力時間を現在の何倍にすればよいか。
ア １／６
イ １／４
ウ １／３
エ １／２
解答 ア
解説 現在のターンアラウンドタイムは３００＋６００＋１００＝１０００ミリ秒です。これを半分にするということは５００ミリ秒にしたいので、オーバヘッドとＣＰＵ実効時間を引くと５００−１００−３００で１００となります。現在の６００ミリ秒を１００ミリ秒にするので、１／６にする必要があります。
問１９ リアルタイムシステムをハードリアルタイムシステムとソフトリアルタイムシステムに分類したとき、ハードリアルタイムシステムに該当するものはどれか。
ア Ｗｅｂ配信システム
イ エアバッグ制御システム
ウ 座席予約システム
エ バンキングシステム
解答 イ
解説 まず、念のために書いておくとここでいうハードとソフトは、ハードウェアやソフトウェアという意味ではなく、ハード（厳しい）・ソフト（優しい）という意味です。

リアルタイムシステムは一般に３つに分類されます。なお、デッドラインとはそれまでに終了しなければならない時間を指します。
@ハードリアルタイムシステム：デッドラインを超えたときに、システムに甚大な被害を及ぼす
Aファームリアルタイムシステム：デッドラインを超えたときに、システムの処理価値がなくなる
Bソフトリアルタイムシステム：デッドラインを超えはじめると、システムの処理価値が徐々に低下してく
問２０ キャッシュメモリと主記憶との間でブロックを置き換える方式にＬＲＵ方式がある。この方式で置換えの対象になるブロックはどれか。
ア 一定時間参照されていないブロック
イ 最後に参照されてから最も長い時間が経過したブロック
ウ 参照頻度の最も低いブロック
エ 読み込んでから最も長い時間が経過したブロック
解答 イ
解説 ページ（ブロック）の置換えには幾つかのアルゴリズムがあります。下にまとめます。

ＮＲＵ(Not Recently Used)：最近使われていないものから順に置き換える（選択肢アに相当）
ＬＲＵ(Least Recently Used)：最後に参照されてから最も時間が経過したものから順に置き換える（選択肢イに相当）
ＬＦＵ(Least Frequently Used)：最も使用頻度の低いものから順に置き換える（選択肢ウに相当）
ＦＩＦＯ(First In First Out)：最初に読んだものから順に置き換える（選択肢エに相当）