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




このページは

基本情報

（基本情報技術者試験）

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

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

問１ 次の１０進小数のうち、８進数に変換したときに有限小数になるものはどれか。
ア ０．３
イ ０．４
ウ ０．５
エ ０．８
解答 ウ
解説 ８進数で表せるかということは、２進数で表せるかということと同じ意味と同じです。よって、０．５、０．２５、０．１２５、０．０６２５・・・の和で表せるかということなので、０．５は２進数で０．１。８進数で０．４となります。
問２ ００００〜４９９９のアドレスをもつハッシュ表があり、レコードのキー値からアドレスに変換するアルゴリズムとして基数変換法を用いる。キー値が５５５５０のときのアドレスはどれか。ここで、基数変換法ではキー値を１１進数とみなし、１０進数に変換した後、下４けたに対して０．５を乗じた結果（小数点以下は切捨て）をレコードのアドレスとする。
ア ０２６０
イ ２５２５
ウ ２７７５
エ ４４０５
解答 ア
解説 まずは、５５５５０を１０進数に直します。
０×１１0＋５×１１1＋５×１１2＋５×１１3＋５×１１4＝０＋５×１１＋５×１２１＋５×１３３１＋５×１４６４１＝０＋５５＋６０５＋６６５５＋１４６４１＋７３２０５＝８０５２０

これの下４けたを半分にしたものは０２６０となります。
問３ 整数ｍがレジスタに２進数として入っている。これを３ビット左にシフトしたものにｍを加えると、結果は元のｍの何倍になるか。ここで、あふれが生じることはないものとする。
ア ４
イ ７
ウ ８
エ ９
解答 エ
解説 ビットシフトは右に１ビットシフトすると、１／２倍。左に１ビットシフトすると２倍になるという性質があります。よって、３ビット左にシフトすると８倍になります。これにもともとの値を加えるので９倍となります。
問４ ｐを２以上の整数とする。任意の整数ｎに対して、

ｎ ＝ ｋｐ＋ｍ （０≦ｍ＜ｐ）

を満たす整数ｋとｍが一意に存在する。このｍをｎのｐによる剰余といい、n mod p で表す。（−１００００） ｍｏｄ ３２７６８に等しくなるものはどれか。
ア −（１００００ ｍｏｄ ３２７６８）
イ −（２２７６８ ｍｏｄ ３２７６８）
ウ １００００ ｍｏｄ ３２７６８
エ ２２７６８ ｍｏｄ ３２７６８
解答 エ
解説 一般的な余りについての問題です。ｎ ＝ ｋｐ + (n mod p)なので、式の−１００００ ＝ ｋ３２７６８ ＋ (n mod p)。よって、Ｋ＝１、(n mod p) ＝ ２２７６８となります。同様に計算していくと、選択肢アも１００００ ＝ ｋ３２７６８ − (n mod p)で(n mod p) ＝ ２２７６８となります。
問５ 多くのコンピュータが、減算回路を簡単にするために補数を用いている理由はどれか。
ア 加算を減算で処理できる。
イ 減算を加算で処理できる。
ウ 乗算を加算の組合せで処理できる。
エ 除算を減算の組合せで処理できる。
解答 イ
解説 補数（主に２の補数が用いられる場合が多い）は負数を表現するために用いられる表現で、これにより、減算を足し算で表現できます。つまり、Ａ−ＢをＡ＋（−Ｂ）と加算で表現できるようになり、回路が簡単になります。
問６ 浮動小数点表示された数値の演算結果における丸め誤差の説明はどれか。
ア 演算結果がコンピュータの扱える最大値を超えることによって生じる誤差である。
イ 数表現のけた数に限度があるので、最下位けたより小さい部分について四捨五入や切上げ、切捨てを行うことによって生じる誤差である。
ウ 乗除算において、指数部が小さい方の数値の仮数部の下位部分が失われることによって生じる誤差である。
エ 絶対値がほぼ等しい数値の加減算において、上位の有効数字が失われることによって生じる誤差である。
解答 イ
解説 まず、それぞれの誤差について下にまとめます。

アンダーフロー：演算結果が、扱える数値の最小値を超えることによって生じる誤差
オーバーフロー：演算結果が、扱える数値の最大値を超えることによって生じる誤差
打切り誤差：数表現のけた数に限度があるときに、計算を途中でやめることで起きる誤差
丸め誤差：数表現のけた数に限度があるとき、最小のけたより小さい部分について四捨五入、切上げ又は切捨てを行うことによって生じる誤差
けた落ち：値がほぼ等しい浮動小数点同士の減算において、有効けた数が大幅に減ってしまうことで起きる誤差
情報落ち：浮動小数点の加算において、一方の数値の下位のけたが欠落することで起きる誤差

情報落ちは絶対値の小さいものから計算することで回避できます。
けた落ちは式を変形するなどで回避することができます。
そのほかは、誤差が許容できるほどに大きな計算桁数を準備することで軽減できます。
問７ コンピュータで連立一次方程式の解を求めるのに、式に含まれる未知数の個数の３乗に比例する計算時間がかかるとする。あるコンピュータで１００元連立一次方程式の解を求めるのに２秒かかったとする。その４倍の演算処理をもつコンピュータで１，０００元連立一次方程式の解を求めるときの計算結果は何秒か。
ア ５
イ ５０
ウ ５００
エ ５，０００
解答 ウ
解説 まず、現在の性能で１００と１０００元方程式の比をもとめると、１００4／１００3となり、１０００倍であることがわかります。つまり、今の性能では、２０００秒かかるので、４倍の性能では、５００秒となります。
問８ 排他的論理和を４ビット単位で実行するユニットＡ、Ｂ、Ｃから構成される装置がある。この装置では、入力ビット列１１０１を与えると、出力ビット列０１００が得られる。ここで、ユニットＢの内部かぎを変更したところ、出力ビット列が１１１１になった。変更後のユニットＢの内部かぎはどれか。

画像（問8）を表示できません
ア １０１１
イ １１００
ウ １１０１
エ １１１０
解答 エ
解説 １つずつ追っていきます。

まずは、変更前をＥＸＯＲの確認の意味をこめて追跡します。
ＥＸＯＲは、ビットが同じならば０、ビットが異なる場合は１を出力します。

@１１０１ ＥＸＯＲ ０００１ ＝ １１００
A１１００ ＥＸＯＲ ０１０１ ＝ １００１
B１００１ ＥＸＯＲ １１０１ ＝ ０１００
次に変更した鍵を逆に追っていきます。
BＹＹＹＹ ＥＸＯＲ １１０１ ＝ １１１１ → ＹＹＹＹ ＝ ００１０
A１１００ ＥＸＯＲ ＸＸＸＸ ＝ ００１０ → ＸＸＸＸ ＝ １１１０

よって、２番目の鍵は、１１１０になったといえます。
問９ ＸとＹの否定論理積Ｘ ＮＡＮＤ Ｙは、ＮＯＴ（Ｘ ＡＮＤ Ｙ）として定義される。Ｘ ＯＲ ＹをＮＡＮＤだけを使って表した論理式はどれか。
ア （（Ｘ ＮＡＮＤ Ｙ）ＮＡＮＤ Ｘ）ＮＡＮＤ Ｙ
イ （Ｘ ＮＡＮＤ Ｘ）ＮＡＮＤ（Ｙ ＮＡＮＤ Ｙ）
ウ （Ｘ ＮＡＮＤ Ｙ）ＮＡＮＤ（Ｘ ＮＡＮＤ Ｙ）
エ Ｘ ＮＡＮＤ（Ｙ ＮＡＮＤ（Ｘ ＮＡＮＤ Ｙ））
解答 イ
解説 まず、Ａ ＮＡＮＤ Ａのように、同じ入力をＮＡＮＤに入れるとＡの否定を作ることができます。

Ｘ ＯＲ Ｙ ＝ （Ｘ ＯＲ Ｙ）の二重否定
（Ｘ ＯＲ Ｙ）の二重否定 ＝ Ｘの否定 ＮＡＮＤ Ｙの否定 （ド・モルガンの定理）
よって、（Ｘ ＮＡＮＤ Ｘ）ＮＡＮＤ（Ｙ ＮＡＮＤ Ｙ）はＸ ＯＲ Ｙと等価であることがわかります。

最後に、ＸＯＲやＸＡＮＤはそれだけですべての演算子を作れるため、最小万能演算系と呼ばれます。
問１０ 正規表現[Ａ−Ｚ]＋[０−９]＊が表現する文字列の集合の要素となるものはどれか。ここで、正規表現は次の規則に従う。

[Ａ−Ｚ]は、英字１文字を表す。
[０−９]は、数字１文字を表す。
＊は、直前の正規表現の０回以上の繰返しを表す。
＋は、直前の正規表現の１回以上の繰返しを表す。
ア ４５６７８９
イ ＡＢＣ９９＊
ウ ＡＢＣ＋９９
エ ＡＢＣＤＥＦ
解答 エ
解説 正規表現を日本語に直すとＡ−Ｚが１回以上現れ、その後０−９が０回以上現れるという意味になります。よって、Ａ−Ｚが含まれない選択肢アは間違いです。＋や＊は文字ではないので、選択肢イ、選択肢ウも間違いです。０−９は現れなくてもいいので、選択肢エは正解です。
問１１ 探索方法とその実行時間のオーダの正しい組合せはどれか。ここで、探索データ数をｎとし、ハッシュ値の衝突する（同じ値になる）確率は無視できるほど小さいものとする。また、実行時間のオーダがｎ2であるとは、ｎ個のデータを処理する時間がｃｎ2（ｃは定数）で抑えられることをいう。
画像（問11ans）を表示できません
解答 ア
解説 ３つのオーダについてまとめると下のようになります。

２分探索：１回で対象を半分にするので、ｌｏｇ2Ｎ
線形探索：１つずつＮ個を探すので、Ｎ
ハッシュ探索：関数で場所を特定するので、衝突が起こらない限り、１
問１２ すべての葉が同じ深さをもち、葉以外のすべての節点が二つの子をもつ２分木に関して、節点数と深さの関係を表す式はどれか。ここで、ｎは節点数、ｋは根から葉までの深さを表す。例に示す２分木の深さｋは２である。

画像（問12）を表示できません
ア ｎ ＝ ｋ（ｋ＋１）＋１
イ ｎ ＝ ２k＋３
ウ ｎ ＝ ２k+1−１
エ ｎ ＝ （Ｋ−１）（ｋ＋１）＋４
解答 ウ
解説 このような木を完全２分木といい、節点数をまとめると下のようになります。

ｋ＝０ → ｎ＝１
ｋ＝１ → ｎ＝１＋２＝３
ｋ＝２ → ｎ＝１＋２＋４＝７
ｋ＝３ → ｎ＝１＋２＋４＋８＝１５
ｋ＝４ → ｎ＝１＋２＋４＋８＋１６＝３１


よって、ｎ＝２k+1−１となります。
問１３ データ構造に関する記述のうち、適切なものはどれか。
ア ２分木は、データ間の関係を階層的に表現する木構造の一種であり、すべての節が二つの子をもつデータ構造である。
イ スタックは、最初に格納したデータを最初に取り出す先入れ先出しのデータ構造である。
ウ 線形リストは、データ部と次のデータの格納先を示すポインタ部から構成されるデータ構造である。
エ 配列は、ポインタの付替えだけでデータの挿入・削除ができるデータ構造である。
解答 ウ
解説 選択肢のデータ構造を下にまとめます。

選択肢アは、完全２分木の説明です。（２分木は、すべての節が２つの子供を持たなくても認められます。）
選択肢イは、キューの説明です。
選択肢ウは、線形リストは、リストの一種でデータと次のポインタからできています。
選択肢エは、リストの説明です。
問１４ ２分探索に関する記述のうち、適切なものはどれか。
ア ２分探索するデータ列は整列されている必要がある。
イ ２分探索は線形探索より常に速く探索できる。
ウ ２分探索は探索をデータ列の先頭から開始する。
エ ｎ個のデータの探索に要する比較回数はｎｌｏｇｎに比例する。
解答 ア
解説 ２分探索は、データを昇順または降順にソートし、そこから中央の値と探索データを比較することで範囲を半分にしていく探索手法です。よって、データは事前にソートされている必要があり、オーダは、ｌｏｇ2Ｎとなります。

選択肢ウは線形探索の説明です。線形探索のオーダは、Ｎで２分探索より大きいですが、探索値が先頭付近にある場合は、線形探索のほうが速い場合もあります。
問１５ 次の関数ｆ（ｎ，ｆ）がある。ｆ（４，２）の値は幾らか。

画像（問15）を表示できません
ア ３
イ ４
ウ ５
エ ６
解答 エ
解説 ひとつずつ追跡していきます。

ｆ（４，２）＝ｆ（３，１）＋ｆ（３，２）

まず、ｆ（３，１）のほうから計算していきます。
ｆ（３，１）＝ｆ（２，０）＋ｆ（２，１）
ｆ（２，０）＝１
ｆ（２，１）＝ｆ（１、０）＋ｆ（１，１）
ｆ（１，０）＝１
ｆ（１，１）＝１

よって、ｆ（４，２）＝３＋ｆ（３，２）

つぎに、ｆ（３，２）を計算します。
ｆ（３，２）＝ｆ（２，１）＋ｆ（２，２）
ｆ（２，２）＝１
ｆ（２，１）＝ｆ（１、０）＋ｆ（１，１）
ｆ（１，０）＝１
ｆ（１，１）＝１

つまり、ｆ（４，２）＝３＋３＝６となります。
問１６ ４ビットの入力データに対し、１の入力数が０個又は偶数個のとき出力が１、奇数個のとき出力が０になる回路はどれか。

画像（問16q）を表示できません
画像（問16ans）を表示できません
解答 エ
解説 真理値表や、入力をすべて試すのもいいのですが、ここでは、論理的な手法で考えます。

ＥＸＯＲは、１が偶数個なら０、奇数個なら１を出力します。

よって、２ビットずつ区切ったときに、偶数＝０、奇数＝１が２つ出てきます。
これを２段目のＥＸＯＲで、偶数と偶数＝０，０＝０。偶数と奇数＝０、１＝１。奇数と偶数＝１、０＝１。奇数と奇数＝１、１＝０となります。
よって、これを反転することで、偶数時に１、奇数時に０を出力する回路となります。
問１７ すべての命令が５サイクルで完了するように設計されたパイプライン制御のコンピュータがある。２０命令を実行するには何サイクル必要となるか。ここで、すべての命令は途中で停止することなく実行できるものとする。
ア ２０
イ ２１
ウ ２４
エ ２５
解答 ウ
解説 １つめの命令は、５クロックで終了します。２つめの命令は、６クロック目で終了します。３つめの命令は、７クロック目で終了します。よって、Ｎ命令は５＋（Ｎ−１）クロックで終了します。なので５＋１９＝２４クロックで２０命令が終了するといえます。
問１８ インデックス修飾によってオペランドを指定する場合、表に示す値のときの実効アドレスはどれか。

画像（問18）を表示できません
ア １１０
イ １０１０
ウ １１００
エ １１１０
解答 ア
解説 インデックス修飾は、命令部のアドレス＋インデックスレジスタの値で計算されます。よって、１０＋１００＝１１０が実効アドレスになります。
問１９ 動作クロック周波数が７００ＭＨｚのＣＰＵで、命令の実行に必要なクロック数とその命令の出現率が表に示す値である場合、このＣＰＵの性能は約何ＭＩＰＳか。

画像（問19）を表示できません
ア １０
イ ５０
ウ ７０
エ １００
解答 エ
解説 まず、命令実行に必要な平均クロック数を求めると４×０．３＋８×０．６＋１０×０．１＝７となります。よって、７命令を７００ＭＨｚで実行すると、１秒間に７００Ｍ／７＝１００ＭＩＰＳとなります。
問２０ 外部割込みに分類されるものはどれか。
ア 主記憶に存在しないページをアクセスしようとしたときに発生する割込み
イ 入出力要求など、ＯＳに対してサービスを依頼したときに発生する割込み
ウ ハードウェアが異常を検知したときに発生する割込み
エ 浮動小数点数演算でオーバフローが起こったときに発生する割込み
解答 ウ
解説 まず、割り込には大きく分けて内部割りこみと外部割り込みがあります。内部割り込はゼロによる除算に代表されるソフトウェア的な原因。外部割り込みは、入出力の完了や電圧異常などに代表されるハードウェア的な原因です。

また、割り込みを受け付けるとＣＰＵはレジスタのデータを主記憶等に退避させ、割り込みの処理を実行します。さらに、複数の割り込みに優先順位をつけ、順位の低いものが、順位の高いものに割り込みを行わないようにマスク処理をする場合もあります。