基本情報技術者講座

基本情報技術者試験 平成20年春期問11

次のBNFで定義されるビット列Ｓであるものはどれか。

＜S＞::01｜0＜S＞1

ア

000111

イ

010010

ウ

010101

エ

011111

基本情報技術者試験 平成20年春期問12

最下位のレベル以外の節点には必ず左右に子が存在する２分探索木から，あるデータを探索する。節点の総数が15のとき，比較する節点の数は最大で幾つか。ここで，探索するデータが存在するとは限らないものとする。

ア

3

イ

4

ウ

7

エ

15

基本情報技術者試験 平成20年春期問13

データの整列方法に関する記述のうち，適切なものはどれか。

ア

クイックソートでは，ある一定間隔おきに取り出した要素から成る部分列をそれぞれ整列し，更に間隔を詰めて同様の操作を行い，間隔が１になるまでこれを繰り返す。

イ

シェルソートでは，隣り合う要素を比較して，大小の順が逆であれば，それらの要素を入れ替えるという操作を繰り返す。

ウ

バブルソートでは，中間的な基準値を決めて，それよりも大きな値を集めた区分と小さな値を集めた区分に要素を振り分ける。次に，それぞれの区分の中で同様な処理を繰り返す。

エ

ヒープソートでは，未整列の部分を順序木に構成し，そこから最大値又は最小値を取り出して既整列の部分に移す。この操作を繰り返して，未整列部分を縮めていく。

基本情報技術者試験 平成20年春期問14

キーｘのハッシュ関数としてh(x)=mod (x, 97)を用いるとき，キー1094とハッシュ値が一致するものは，キー1〜1000の中に幾つあるか。ここで, mod (x, 97)はｘを97で割った余りを表す。

ア

9

イ

10

ウ

11

エ

12

基本情報技術者試験 平成20年春期問15

次の流れ図は，2数A，Bの最大公約数を求めるユークリッドの互除法を，引き算の繰返しによって計算するものである。Aが876, Bが204のとき，何回の比較で処理は終了するか。

ア

4

イ

9

ウ

10

エ

11

基本情報技術者試験 平成20年春期問16

DRAMの説明として，適切なものはどれか。

ア

コンデンサに電荷を蓄えた状態か否かによって１ピットを表現する。主記憶としてよく用いられる。

イ

製造時にデータが書き込まれる。マイクロプログラム格納用メモリとして用いられる。

ウ

専用の装置でデータを書き込むことができ，紫外線照射で消去ができる。

エ

フリップフロップで構成され，高速であるが製造コストが高い。キャッシュメモリなどに用いられる。

基本情報技術者試験 平成20年春期問17

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

ア

処理すべきベクトルの長さがベクトルレジスタより長い場合，ベクトルレジスタ長の組に分割して処理を繰り返す方式である。

イ

パイプラインを更に細分化することによって高速化を図る方式である。

ウ

複数のパイプラインを用いて，同時に複数の命令を実行可能にすることによって高速化を図る方式である。

エ

命令語を長く取り，一つの命令で複数の機能ユニットを同時に制御することによって高速化を図る方式である。

基本情報技術者試験 平成20年春期問18

主記憶へのアクセスを伴う演算命令を実行するとき，命令解読とオベランド読出しの間に行われる動作はどれか。

ア

実効アドレス計算

イ

入出力装置起動

ウ

分岐アドレス計算

エ

割込発生

基本情報技術者試験 平成20年春期問19

クロック周波数が1GHzのCPUがある。このCPUの命令種別が，表に示す二つから成っているとき，処理能力は約何MIPSか。

ア

34

イ

100

ウ

125

エ

133

基本情報技術者試験 平成20年春期問20

処理装置で用いられるキャッシュメモリの使用目的として，適切なものはどれか。

ア

仮想記憶のアドレス変換を高速に行う。

イ

仮想記憶のページング処理を高速に行う。

ウ

主記憶へのアクセス速度とプロセッサの処理速度の差を埋める。

エ

使用頻度の高いプログラムを常駐させる。