平成１６年度春期 基本情報 問１−２０ 解答編




このページは

基本情報

（基本情報技術者試験）

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

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

問１ １０進数の演算式７÷３２の結果を２進数で表したものはどれか。
ア ０．００１０１１
イ ０．００１１０１
ウ ０．００１１１
エ ０．０１１１
解答 ウ
解説 ７÷３２＝０．２１８７５を２進数に変換します。

小数点より、上の場合は２で割った余りで計算していきますが、小数点よりしたの場合は２を掛けていったときの１の位をみます。

０．２１８７５×２＝０．４３７５により、０
０．４３７５×２＝０．８７５より、０
０．８７５×２＝１．７５により、１
０．７５×２＝１．５より１
０．５×２＝１．０により１で終了

これを上からたどって、００１１１が小数点以下の値となります。よって、０．００１１１が答えになります。

もちろん、２進数にした７と３２を使ってもよいのですが、１０進数から計算するほうが間違いが少ないかと思います。
問２ 次の式は、何進法で成立するか。
１０１５÷５＝１３１（余り０）
ア ６
イ ７
ウ ８
エ ９
解答 イ
解説 それぞれを１０進数に変換しながら計算し行きます。５は、６進数でも、７進数でも、８進数でも、９進数でも同じなので省略します。

６進数
（１０１５）6＝１×６×６×６＋１×６＋５＝（２２７）10
２２７÷５＝４５．４により、割り切れないので間違い。

７進数
（１０１５）7＝１×７×７×７＋１×７＋５＝（３５５）10
３３５÷５＝（７１）10＝１×７×７＋３×７＋１＝（１３１）7により正解

８進数
（１０１５）8＝１×８×８×８＋１×８＋５＝（５１２）10
５２５÷５＝（１０５）10＝１×８×８＋５×８＋１＝（１５１）8により不正解

９進数
（１０１５）9＝１×９×９×９＋１×９＋５＝（７４３）10
７４３÷５＝１４８．６により、割り切れないので、間違い。
問３ 実数ａをａ＝ｆ×ｒeと表す浮動小数点表記に関する記述として、適切なものはどれか。
ア ｆを仮数、ｅを指数、ｒを基数という。
イ ｆを基数、ｅを仮数、ｒを指数という。
ウ ｆを基数、ｅを指数、ｒを仮数という。
エ ｆを指数、ｅを基数、ｒを仮数という。
解答 ア
解説 コンピュータ上で数値を表す表現の一種に浮動小数点表記というのがあります。

これは、実数や、指数表記を用いるような数を表すもので、ｆ×ｒeで表現されます。
たとえば、１２３００００００は、１．２３×１０8となります。このとき、１．２３を仮数（仮数部）、１０を基数（基数部）、８を指数（指数部）といいます。
コンピュータ上では、基数を２と固定して、符号と仮数と指数を表すのが一般的です。なお、仮数を１．ｘｘｘｘとすることで、１ビット節約することを『けち表現』などといい、このように変換することを正規化といいます。
問４ ３２ビットのレジスタに１６進数ＡＢＣＤが入っているとき、２ビットだけ右に論理シフトしたときの値はどれか。
ア ２ＡＦ３
イ ６ＡＦ３
ウ ＡＦ３４
エ ＥＡＦ３
解答 ア
解説 ＡＢＣＤを２進数に変換すると
００００ ００００ ００００ ００００ １０１０１０１１１１００１１０１となります。

これを右に２ビットシフトします。すると
ｘｘ００ ００００ ００００ ００００ ００１０ １０１０ １１１１ ００１１となり、０１は捨てられます。

このとき、ｘｘに何が入るかですが、特段の取り決めがない場合は符号と同じものが入ります。（正の場合は０、負の場合は１）この場合は、暗黙ではありますが負数の定義がないので、正数であると考えられるので、ｘｘには００がはいります。よって

００００ ００００ ００００ ００００ ００１０ １０１０ １１１１ ００１１を２進数にしたものが正解となります。
よって （００００２ＡＦ３）16＝（２ＡＦ３）16となります。
問５ けた落ちの説明として、適切なものはどれか。
ア 値がほぼ等しい浮動小数点同士の減算において、有効けた数が大幅に減ってしまうことである。
イ 演算結果が、扱える数値の最大値を超えることによって生じる誤差である。
ウ 数表現のけた数に限度があるとき、最小のけたより小さい部分について四捨五入、切上げ又は切捨てを行うことによって生じる誤差である。
エ 浮動小数点の加算において、一方の数値の下位のけたが欠落することである。
解答 ア
解説 コンピュータ上で値を扱う場合には、誤差という問題があります。これは、真の値を表現しきれないために近似ということをするために、おきるものです。

選択肢アは、けた落ちに関するものです。
選択肢イは、オーバフローに関するものです。（扱える数値の最小値を下回ることによる誤差をアンダーフローといいます。）
選択肢ウは、丸め誤差に関するものです。
選択肢エは、情報落ちに関するものです。

式を変形することで解消することがあります。例：√（ｘ＋１） − √（ｘ）＝１／（√（ｘ＋１）＋√（ｘ））
問６ 赤、白、黄の３種類の球が３個ずつ入っている箱の中から、３個の球を同時に取り出すとき、すべて白の球になる確率は幾らか。
ア １／８４
イ ３／１４
ウ ５／２１
エ １１／１４
解答 ア
解説 全体の確率を３つの確率に分解します。１個目の白を出す確率、２個目の白を出す確率、３個目の白を出す確率

Ｐ（ｘ１）：１個目の白を出す確率は９個の中から３つで、３／９＝１／３
Ｐ（ｘ２）：２個目の白を出す確率は８個の中から２つで、２／８＝１／４
Ｐ（ｘ３）：３個目の白を出す確率は７個の中から１つで、１／７

全体の確率＝Ｐ（ｘ１）×Ｐ（ｘ２）×Ｐ（ｘ３）により、１／８４となります。同時といってもわずかな時間差はあると考えなおすと分かりやすいかも知れません。
問７ １ビットの数Ａ、Ｂの和を２ビットで表現したとき、上位ビットＣと下位ビットＳを表す論理式の組合せはどれか。ここで、“・”は論理積、“＋”は論理和、ＸはＸの否定を表す。

画像（問7）を表示できません
画像（問7ans）を表示できません
解答 ア
解説 一般的な半加算器の論理式です。

Ｃはけた上がりを表し、１と１の場合は１０となり繰り上がるので、１となります。
Ｓはそのけたを表し、１と０の場合と０と１の場合を表しその場合のみ１となります。

よって、ＣはＡとＢの論理積、ＳはＡとＢの排他的論理和となります。
問８ 関数eq(Ｘ、Ｙ)は引数ＸとＹの値が等しければ１を返し、異なれば０を返す。整数Ａ、Ｂ、Ｃについて、eq(eq(Ａ、Ｂ)、eq(Ｂ、Ｃ))を呼び出したとき、１が返ってくるための必要十分条件はどれか。
ア （Ａ＝ＢかつＢ＝Ｃ）又は（Ａ≠ＢかつＢ≠Ｃ）
イ （Ａ＝ＢかつＢ＝Ｃ）又は（Ａ≠Ｂ又はＢ≠Ｃ）
ウ （Ａ＝ＢかつＢ＝Ｃ）又はＡ＝Ｃ
エ （Ａ＝Ｂ又はＢ＝Ｃ）又はＡ＝Ｃ
解答 ア
解説 eq(eq(Ａ、Ｂ)、eq(Ｂ、Ｃ))が１を返すためには、eq(Ａ、Ｂ)、eq(Ｂ、Ｃ)が１と１、０と０の場合です。

これは、Ａ＝Ｂ、Ｂ＝Ｃのとき１と１になり、Ａ≠Ｂ、Ｂ≠Ｃのとき、０と０になります。

よって、（Ａ＝ＢかつＢ＝Ｃ）又は、（Ａ≠Ｂ、Ｂ≠Ｃ）のときとなります。）
問９ 論理型の変数Ａ、Ｂに関わらず、次の流れ図と同一の分岐が得られるものはどれか。ここで、ＡＮＤは論理積、ＯＲは論理和、ＸＯＲは排他的論理和、ＮＡＮＤは否定論理積を表す。

画像（問9）を表示できません
画像（問9ans）を表示できません
解答 イ
解説 流れ図を論理式に直すと分かりやすいです。

Ａ＝真、Ｂ＝真、exit2
Ａ＝真、Ｂ＝偽、exit1
Ａ＝偽、Ｂ＝真、exit1
Ａ＝偽、Ｂ＝偽、exit2

これにより、exit2は排他的論理和（XOR）であることが分かります。
問１０ ２種類の文字“Ａ”、“Ｂ”を１個以上、最大ｎ個並べた符号を作る。６０通りの符号を作るときのｎの最小値は幾らか。
ア ４
イ ５
ウ ６
エ ７
解答 イ
解説 １個以上なので、したから順に計算していきます。
１個の場合：2^1（Ａ、Ｂ）＝２種類
２個の場合：２個を並べたもの＋１個の場合＝2^2（ＡＡ、ＡＢ、ＢＡ、ＢＢ）＋２種類＝６通り
３個の場合：３個並べたもの＋２個の場合＝2^3＋６通り＝１４通り
４個の場合：４個並べたもの＋３個の場合＝2^4＋14通り＝３０通り
５個の場合：５個並べたもの＋４個の場合＝2^5＋30通り＝６２通り

ｎ個並べた場合は、一般的な２進数のビット数に相当し、６ビット＝６４となりますが、ここでは間違えないように注意してください。
問１１ 探索方法とその実行時間のオーダの正しい組み合わせはどれか。ここで、探索するデータ数をｎとし、ハッシュ値が衝突する（同じ値になる）確率は無視できるほど小さいものとする。また、実行時間がn2であるとは、ｎ個のデータを処理する時間がｃｎ2（ｃは定数）で抑えられることを言う。
画像（問11ans）を表示できません
解答 ア
解説 ２分法は、ソートされている探索領域において、中央値から大きいか小さいかで分けていくので１回につき検索範囲が半分になるので、log2ｎとなります。線形探索は、先頭から順番に見ていくので、ｎ個データがあればオーダはｎとなります。ハッシュ法はハッシュ関数と呼ばれる関数によって値を計算し、そこにデータを格納するのでハッシュ値が衝突しない限りは、１となります。ｎlog2ｎは、マージソートなどのソート法などのオーダです。
問１２ Ａ，Ｂ，Ｃ，Ｄの順に到着するデータに対して、一つのスタックだけを用いて出力可能なデータ列はどれか。
ア Ａ，Ｄ，Ｂ，Ｃ
イ Ｂ，Ｄ，Ａ，Ｃ
ウ Ｃ，Ｂ，Ｄ，Ａ
エ Ｄ，Ｃ，Ａ，Ｂ
解答 ウ
解説 スタックは、ＬＩＦＯのデータ構造で再帰的なものと関わりがが深いです。スタックにデータを入れることをプッシュ、取り出すことをポップといいます。

今回の場合は、
@プッシュ（Ａ）
Aプッシュ（Ｂ）
Bプッシュ（Ｃ）
Cポップ（Ｃ）→Ｃを取り出す。
Dポップ（Ｂ）→Ｂを取り出す。
Eプッシュ（Ｄ）
Fポップ（Ｄ）→Ｄを取り出す
Gポップ（Ａ）→Ａを取り出す

ことによって、Ｃ、Ｂ、Ｄ、Ａの順にデータを取り出せます。
問１３ １６進数で表される９個のデータ１Ａ、３５、３Ｂ、５４、８Ｅ、Ａ１、ＡＦ、Ｂ２、Ｂ３を順にハッシュ表に入れる。ハッシュ値をハッシュ関数ｆ（データ）＝ｍｏｄ（データ、８）で求めたとき、最初に衝突が起こる（既に表にあるデータと等しいハッシュ値になる）のはどのデータか。ここで、ｍｏｄ（ａ、ｂ）はａをｂで割った余りを表す。
ア ５４
イ Ａ１
ウ Ｂ２
エ Ｂ３
解答 ウ
解説 ｆ（データ）＝ｍｏｄ（データ、８）というのは、データＡ×（α８）＝データＢのとき衝突が起きます。
一般的には１０進数に変換して８で割った余りを順次もとめていけばいいのですが、今回は８で割ったあまりということなので、ビットの性質を利用したいと思います。 １→００００１
９＝１×８＋１→０１００１
１７＝２×８＋１→１０００１
２５＝３×８＋１→１１００１
以上のように、８を加えても、下位３ビットは変化しません。よって、データの下位３ビットを調べて同じものがあった場合に衝突と判断することができます。

１Ａ→０１０
３５→１０１
３Ｂ→０１１
５４→１００
８Ｅ→１１０
Ａ１→００１
ＡＦ→１１１
Ｂ２→０１１

Ｂ２と３Ｂはともに０１１で値が３でハッシュ値が衝突することがわかります。

また、直感的に分かると思いますが、９個のデータを８個の表に入れると必ず衝突がおきます。（鳩の巣論法により証明）
問１４ 非負の整数ｎに対して次のとおりに定義された関数Ｆ（ｎ）、Ｇ（ｎ）がある。Ｆ（５）の値は幾らか。

Ｆ（ｎ）：if ｎ≦１ then return １ else return ｎ×Ｇ（ｎ−１）
Ｇ（ｎ）：if ｎ≦０ then return ０ else return ｎ＋Ｆ（ｎ−１）
ア ５０
イ ６５
ウ １００
エ １２０
解答 イ
解説 再帰プログラムに関する問題です。丁寧にトレース（値の追跡）していけば解くことができます。

Ｆ（５）＝５×Ｇ（４）
Ｇ（４）＝４＋Ｆ（３）
Ｆ（３）＝３×Ｇ（２）
Ｇ（２）＝２＋Ｆ（１）
Ｆ（１）＝１
よって、したから代入していきます。 Ｇ（２）＝２＋１＝３
Ｆ（３）＝３×３＝９
Ｇ（４）＝４＋９＝１３
Ｆ（５）＝５×１３＝６５

よって、答えは６５となります。
問１５ 配列Ａの１番目からＮ番目の要素に整数が格納されている（Ｎ＞１）。次の図は、Ｘと同じ値が何番目の要素に格納されているかを調べる流れ図である。この流れ図の実行結果として、正しい記述はどれか。

画像（問15）を表示できません
ア Ｘと同じ値が配列中にない場合、ｋには１が設定されている。
イ Ｘと同じ値が配列中にない場合、ｋにはＮが設定されている。
ウ Ｘと同じ値が配列の１番目とＮ番目の２か所にある場合、ｋには１が設定されている。
エ Ｘと同じ値が配列の１番目とＮ番目の２か所にある場合、ｋにはＮが設定されている。
解答 ウ
解説 ｋには現在調べている要素の要素番号が入っています。Ｎは個数です。よって最初のif文は、最後まで調べ終わったかどうかをチェックしています。次のif文で値が等しいかをチェックしています。等しい場合はループを抜けるので、そこで終了します。よって等しい値が複数ある場合は、最初に見つかったものの要素番号となることがわかります。なお、値がなかった場合は、ｋ＞Ｎにより、Ｎ＋１がｋの最終値となります。
問１６ フリップフロップ回路を利用した高速なメモリはどれか。
ア ＤＲＡＭ
イ ＲＤＲＡＭ
ウ ＳＤＲＡＭ
エ ＳＲＡＭ
解答 エ
解説 フリップフロップとは、現在の信号と過去の状態から現在の状態（真、偽）を保持するものです。その代表例がＳＲＡＭです。ＤＲＡＭはリフレッシュと呼ばれる動作（値の定期的な更新）が必要なため、比較的低速であるといえます。
問１７ アドレス指定方式のうち、命令読出し後のメモリ参照を行わずにデータを取り出すものはどれか。
ア 間接アドレス
イ 指標付きアドレス
ウ 即値オペランド
エ 直接アドレス
解答 ウ
解説 ４つの方式を以下にまとめます。

直接アドレス：値をアドレスと見なして、そのアドレスの値を有効値とする方式です。
間接アドレス：値をアドレスと見なして、そのアドレスの値もアドレスと見なし、そのアドレス値を有効値とする方式です。
指標付きアドレス：値と指標値を足した値をアドレスと見なして、その値を有効値とする方式です。
即値オペランド：値を有効値とする方式です。

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


上記の例を考えると、直接アドレスは、１０１のアドレスの内容で１０２。間接アドレスは、１０１のアドレスの内容（１０２）の内容で、１０３.指標付きアドレスは、１０１＋５＝１０６の内容で５００。即値オペランドは値そのものなので、１０１となります。間接アドレスは、２重、３重とすることができます。また、指標付きアドレスは、相対アドレスや再配置可能プログラムを考える上で重要になります。
問１８ ５０ＭＩＰＳの処理装置の平均命令時間は幾らか。
ア ２０ナノ秒
イ ５０ナノ秒
ウ ２マイクロ秒
エ ５マイクロ秒
解答 ア
解説 １秒間に５０×１００万回の処理ができるということは、１回の処理はその逆数で、１／５０×１／１００万回＝０．０２×マイクロ秒＝２０ナノ秒となります。

１／キロ＝ミリ。１／メガ＝マイクロ。１／ギガ＝ナノ。１／テラ＝ピコであることを利用すると、計算が速く間違いが少なくなります。
問１９ キャッシュメモリと主記憶に関するアクセス時間とヒット率の組合せのうち、主記憶の実効アクセス時間が最も短くなるのはどれか。
画像（問19ans）を表示できません
解答 エ
解説 それぞれの計算結果を以下にまとめます。

選択肢ア：１０×０．６＋７０×０．４＝６＋２８＝３４
選択肢イ：１０×０．７＋７０×０．３＝７＋２１＝２８
選択肢ウ：２０×０．７＋５０×０．３＝１４＋１５＝２９
選択肢エ：２０×０．８＋５０×０．２＝１６＋１０＝２６
以上により選択肢エが最も実効アクセス時間が短くなります。
今回の場合は、アクセス時間が同じでヒット率だけことなるので、ヒット率が低い選択肢アとウは答えでないことが見抜ければ、さらに計算時間を省略することもできます。
問２０ アクセス時間の最も短い記憶装置はどれか。
ア ＣＰＵの２次キャッシュ
イ ＣＰＵのレジスタ
ウ 磁気ディスク
エ 主記憶
解答 イ
解説 アクセス時間は、コンピュータ側（ＣＰＵ側）に近いほど早くなります。よって、

ＣＰＵのレジスタ＞（ＣＰＵの１次キャッシュ）＞ＣＰＵの２次キャッシュ＞（キャッシュメモリ）＞主記憶＞（ディスクキャッシュ）＞磁気ディスクとなります。

また、速度と記憶容量とコストはトレードオフの関係にあり、記憶容量は大小関係が逆になります。