平成19年度秋期 基本情報 問1−20 解答編





このページは

基本情報

(基本情報技術者試験)

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

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


問1 16進数0.Cを10進数に変換したものはどれか。
0.12
0.55
0.75
0.84
解答
解説 0.Cを2進数に直すと、0.1100となります。これを10進数になおすと、0.5+0.25なので、0.75となります。

問2 非負の2進数b12・・・bnを3倍したものはどれか。
12・・・bn0+b12・・・bn
12・・・bn00−1
12・・・bn000
12・・・bn
解答
解説 2進数は左にnビットシフトすると、2nになるという性質があります。(10進数において、10倍すると桁が1つあがるのと同じです。)つまり、3倍とは、1ビット左にシフトしそれに元の値を加えたものとなります。

問3 負の整数を表現する代表的な方法として、次の3種類がある。

a 1の補数による表現
b 2の補数による表現
c 絶対値に符号を付けた表現(左端ビットが0の場合は正、1の場合は負)

4ビットのパターン1101をa〜cの方法で表現したものと解釈したとき、値が小さい順になるように三つの方法を並べたものはどれか。

a、c、b
b、a、c
b、c、a
c、b、a
解答
解説 順番に評価していきます。

まず、補数とは、A+B=0となるようなAとBの関係です。つまり、2回補数をとると元の値にもどります。

a:1101のビット反転0010なので、−2
b:1101のビット反転をして1を加えると0011なので、−3
c:1は負数で101は5なので、−5

よって、c、b、aとなります。

問4 浮動小数点形式で表現された数値の演算結果における丸め誤差の説明はどれか。
演算結果がコンピュータの扱える最大値を超えることによって生じる誤差である。
数表現のけた数に限度があるので、最下位けたより小さい部分について四捨五入や切り上げ、切捨てを行うことによって生じる誤差。
乗除算において、指数部が小さいほうの数値の仮数部の下位部分が失われることによって生じる誤差である。
絶対値がほぼ等しい数値の加減算において、上位の有効数字が失われることによって生じる誤差である。
解答
解説 まず、それぞれの誤差について下にまとめます。

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

情報落ちは絶対値の小さいものから計算することで回避できます。
けた落ちは式を変形するなどで回避することができます。
そのほかは、誤差が許容できるほどに大きな計算桁数を準備することで軽減できます。

問5 コンピュータで連立一次方程式の解を求めるのに、式に含まれる未知数の個数が3乗に比例する時間がかかったとする。あるコンピュータで100元連立一次方程式の解を求めるのに2秒かかったとすると、その4倍の演算処理をもつコンピュータで1,000元連立一次方程式の解を求めるときの計算時間は何秒か。
50
500
5,000
解答
解説 まず、現在の性能で100と1000元方程式の比をもとめると、、1004/1003となり、1000倍であることがわかります。つまり、今の性能では、2000秒かかるので、4倍の性能では、500秒となります。

問6 白玉4個、赤玉5個が入っている袋から玉を1個取り出し、それを戻さないで続けてもう1個取り出すとき、2個とも赤である確率は幾らか。
1/6
16/81
25/81
5/18
解答
解説 順列や組み合わせを使うよりも、ひとつずつ計算する方が早いとおもいます。

1個目は5/9。2個めは、1個目が赤だったと仮定して、4/8。よって、(5/9)×(1/2)=5/18となります。

問7 相関係数に関する記述のうち、適切なものはどれか。
すべての標本点が正の傾きをもつ直線上にあるときは、相関係数が+1になる。
変量間の関係が線形のときは、相関係数が0になる。
変量間の関係が非線形のとき、相関係数が負になる。
無相関のとき、相関係数が−1になる
解答
解説 散布図とは、以下のような図で、最小2乗法などによって直線を求めたものを回帰直線と呼びます。この傾きを相関係数といい、1に近ければ正の相関。−1に近ければ負の相関といいます

画像(問7kai)を表示できません

問8 集合AとBについて、常に成立する関係はどれか。ここで、∩は積集合、∪は和集合、はAの補集合、A⊆Bは“AはBの部分集合である”ことを表す。
A⊆(A∩
(A∪B)⊆(
(A∩B)⊆(A∪
(A∩B)⊆(
解答
解説 ベン図などで書いてみるとわかりやすいと思います。

選択肢アは、A∩Bの部分が含まれていません。
選択肢イは、A∩Bの部分が含まれていません。
選択肢エは、A∩Bの部分が含まれていません。

問9 P、Q、Rはいずれも命題である。命題Pの真理値は真であり、命題(notP)orQ及び命題(notQ)orRはいずれの真理値も真であることが分かっている。Q、Rの真理値はどれか。ここで、XorYはXとYの論理和、notXはXの否定を表す。
画像(問9ans)を表示できません
解答
解説 まず、P=Tです。つぎに、(notT)orQ=Tなので、ForQ=Tにより、Q=Tです。最後に、(notT)orR=Tなので、ForR=Tにより、R=Tとなり、P、Q、RはいずれもTであることがわかります。

問10 次の状態繊維表をもつシステムの状態がS1であるときに、信号t1、t2、t3、t4、t1、t2、t3、t4の順に入力すると、最後の状態はどれになるか。ここで、空欄は状態が変化しないことを表す。

画像(問10)を表示できません
S1
S2
S3
S4
解答
解説 順番にトレースしてみます。

S1 (t1)→ S1 (t2)→ S3 (t3)→ S4 (t4)→ S2 (t1)→ S3 (t2)→ S2 (t3)→ S2 (t4)→ S1

よって、最終状態はS1となります。

問11 探索方法とその実行時間のオーダの正しい組合せはどれか。ここで、探索するデータ数をnとし、ハッシュ値が衝突する(同じ値になる)確率は無視できるほど小さいものとする。また、実行時間のオーダがn2であるとは、n個のデータを処理する時間がcn2で抑えられることをいう。
画像(問11ans)を表示できません
解答
解説 3つのオーダについてまとめると下のようになります。

2分探索:1回で対象を半分にするので、log2
線形探索:1つずつN個を探すので、N
ハッシュ探索:関数で場所を特定するので、衝突が起こらない限り、1

問12 2分木の各ノードがもつ信号を出力する再帰的なプログラムProc(ノードn)は、次のように定義される。このプログラムを、図の2分木の根(最上位のノード)に適用したときの出力はどれか。

画像(問12)を表示できません
b−c*d+a
+a*−bcd
a+b−c*d
abc−d*+
解答
解説 関数をまとめると、左→右→親の順で再帰的に表示するということなので、abc−d*+ となります。

問13 十分な大きさの配列Aと初期値が0の変数pに対して、関数f(x)とg()が次のとおり定義されている。配列Aと変数pは関数fとgだけでアクセス可能である。これらの関数が操作するデータ構造はどれか。

画像(問13)を表示できません
キュー
スタック
ハッシュ
ヒープ
解答
解説 それぞれのデータ構造を下にまとめます。

キューとスタック

画像(問13kai)を表示できません

ハッシュ

画像(問13_2kai)を表示できません

ヒープ
画像(問13_3kai)を表示できません

キューであれば、ポインタを減らすことはありません。
ハッシュであれば、何らかの計算が必要になります。
ヒープであれば、場所を特定するための判定文などが必要となります。

問14 昇順に整列されたn個のデータが格納されている配列Aがある。流れ図は、2分探索法を用いて配列Aからデータxを探し出す処理を表している。a、bに入る操作の正しい組合せはどれか。ここで、除算の結果は小数点以下が切り捨てられる。

画像(問14)を表示できません
画像(問14ans)を表示できません
解答
解説 2分探索とは、ソートされたデータに対して検索をする手法で、中央値と検索値を比較することで、範囲を徐々に半分にしていく手法です。よって
中央値>検索値だった場合は、下半分にあるので、上限=中央値の下のインデックス
中央値<検索値だった場合は、上半分にあるので、上限=中央値の上のインデックス

として、再度中央値を再計算するということを繰り返します。

問15 整数x、y(x>y≧0)に対して、次のように定義された関数F(x、y)がある。F(231、15)の値は幾らか。ここで、xmodyはxをyで割った余りである。

画像(問15)を表示できません
解答
解説 値を順番にトレースしていきます。

F(231,15)=F(15,231 mod 15)=F(15,6)
F(15,6=F(6,15 mod 6)=F(6,3)
F(6,3)=F(3,6 mod 3)=F(3,0)
F(3,0)=3

よって、F(231,15)=3となります。

なお、第2引数がyを法とした剰余をとっているので、x>yの関係が崩れることはありません。

問16 フリップフロップ回路を利用した高速なメモリはどれか。
DRAM
RDRAM
SDRAM
SRAM
解答
解説 よく使われるメモリの種類である。DRAMとSRAMを下にまとめます。

SRAM:フリップフロップで構成される。容量は小さいが高速。リフレッシュがいらず消費電力も小さい。比較的高価。主にキャッシュメモリに利用される。
DRAM:コンデンサで構成される。容量は大きいが低速。リフレッシュが必要で消費電力が大きい。比較的安価。主に主記憶に利用される。

リフレッシュとは、値を保持するために、電気的に再充電する操作をいいます。DRAMはトランジスタとコンデンサによって構成されているので、このような操作が必要となります。

問17 入力XとYの値が同じときにだけ、出力Zに1を出力する回路はどれか。

画像(問17q)を表示できません
画像(問17ans)を表示できません
解答
解説 選択肢の回路の出力する論理記号を考えて見ます。

選択肢ア:(X∩Y)∩(
=(X∩Y)∩(X ∪ Y)=0

選択肢イ:(X∪Y)∪(
=(X∪Y)∪(X ∩ Y)=1

選択肢ウ:(X NAND Y)NAND ( NAND
(X XOR Y)

選択肢エ:(X NOR Y)NOR ( NOR
=X XOR Y

問18 図に示すアドレス指定方式はどれか。

画像(問18)を表示できません
指標付きアドレス指定方式
相対アドレス指定方式
直接アドレス指定方式
レジスタ間接アドレス指定方式
解答
解説 直接アドレス:値をアドレスと見なして、そのアドレスの値を有効値とする方式です。
間接アドレス:値をアドレスと見なして、そのアドレスの値もアドレスと見なし、そのアドレス値を有効値とする方式です。
指標付きアドレス:値と指標値を足した値をアドレスと見なして、その値を有効値とする方式です。
相対アドレス:値とプログラムカウンタの値を足しして、その値をアドレスと見なして、有効値とする方式
即値オペランド:値を有効値とする方式です。

画像(問18kai)を表示できません


上記の例を考えると、直接アドレスは、101のアドレスの内容で102。間接アドレスは、101のアドレスの内容(102)の内容で、103.指標付きアドレスは、101+5=106の内容で500。即値オペランドは値そのものなので、101となります。間接アドレスは、2重、3重とすることができます。また、指標付きアドレスは、相対アドレスや再配置可能プログラムを考える上で重要になります。

問19 1GHzで動作するCPUがある。このCPUは、機械語の1命令を平均0.8クロックで実行できることが分かっている。このCPUは1秒間に約何百万命令実行できるか。
125
250
80,000
125,000
解答
解説 Gは109なので、109×1/0.8=125×109=125000×106となり、106はMに相当し、百万回を表します。

問20 外部割込みに分類されるものはどれか。
インターバルタイマによって、指定時間経過時に生じる割込み
演算結果のオーバフローやゼロによる除算で生じる割込み
仮想記憶管理において、存在しないページへのアクセスによって生じる割込み
ソフトウェア割込み命令の実行によって生じる割込み
解答
解説 まず、割り込には大きく分けて内部割りこみと外部割り込みがあります。内部割り込はゼロによる除算に代表されるソフトウェア的な原因。外部割り込みは、入出力の完了や電圧異常などに代表されるハードウェア的な原因です。

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