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




このページは

基本情報

（基本情報技術者試験）

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

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

問１ 次の流れ図は、１０進数整数ｊ（０＜ｊ＜１００）を２進数に変換する処理を表している。２進数は下位けたから順に、配列の要素ＮＩＳＨＩＮ（１）からＮＩＳＨＩＮ（８）に格納される。流れ図のａ及びｂに入る処理はどれか。ここでｊdiv２はｊを２で割った商の整数部分を、ｊmod２はｊを２で割った余りを表す。

画像（問1）を表示できません
画像（問1ans）を表示できません
解答 エ
解説 まず、１０進数の３０を２進数に変換する具体例を考えます。

３０÷２＝１５…０
１５÷２＝７…１
７÷２＝３…１
３÷２＝１…１
１÷２＝０…１

２は２進数の２であり、３進数なら３、４進数なら４となります。ここで、出てきた余りを下からたどると、１１１１０となります。これが求める２進数の値です。

それでは、アルゴリズムにあてはめてみます。
@まず、２で割った余りを取り出す。
A次に、値を半分にする（端数は切り捨て）
B上の２つを値が０になるまで繰り返す。

よって、@がａ、Aがｂに相当する選択肢エが正解となります。
問２ ある自然数ｘを２進数で表現すると、１と０が交互に並んだ２ｎけたの２進数１０１０・・・１０となった。このとき、ｘに関して成立する式はどれか。
画像（問2ans）を表示できません
解答 イ
解説 まず、ｘは１０１０・・・１０１０となっています。ｘ／２はｘを半分にしたものなので、ｘを右に１ビットシフトしたものと考えることができます。よって、０１０１・・・０１０１となります。これを足すので、１１１１・・・１１１１となります。３ビットの場合の１１１は７で２3-1となるので、これは、２2n−１となります。
問３ 負数を２の補数で表す８ビットの数値がある。この値を１０進数で表現すると−１００である。この値を符号なしの整数として解釈すると、１０進数で幾らか。
ア ２８
イ １００
ウ １５６
エ ２２８
解答 ウ
解説 補数とは、ｘ＋ｙ＝０となるときのｘとｙのことを言います。つまり、ｘの補数の補数はｘ自身になることがわかります。

１００＝０１１００１００
ビット反転をして、１００１１０１１
１を加えて、１００１１１００となります。

これは、１２８＋１６＋８＋４＝１５２となります。

もちろんこれをビット反転して、１を加えると０１１０００１１＋１で０１１００１００で元の値にもどります。
問４ 数多くの数値の加算を行う場合、絶対値の小さなものから順番に計算するとよい。これは、どの誤差を抑制する方法を述べたものか。
ア アンダフロー
イ 打切り誤差
ウ けた落ち
エ 情報落ち
解答 エ
解説 まず、それぞれの誤差について下にまとめます。

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

情報落ちは絶対値の小さいものから計算することで回避できます。
けた落ちは式を変形するなどで回避することができます。
そのほかは、誤差が許容できるほどに大きな計算桁数を準備することで軽減できます。
問５ 方程式f(x)=0の解の近似解を求めるアルゴリズムとして知られているニュートン法に関する記述として、適切なものはどれか。
ア 関数f(x)が微分不可能であっても、解の近似解を求めることができる。
イ 幾何学的には、y=f(x)の接線を利用して解の近似値を求めるものである。
ウ 異なる初期値を二つ与える必要がある。
エ どのような初期値を与えても、必ず解の近似値が得られる。
解答 イ
解説 ニュートン法は、代数方程式の解を求める代表的な手法です。任意の初期値から接線（関数の微分）を引き、ｘ軸と交わる点をもとめるということを繰り返すことで、真の解に近づけていく手法です。しかし、下に凸のようなグラフでは、解の間を行ったり来たりするため、真に解に収束しない場合があります。

ｆ（ｘ）の微分（導関数）が計算できない場合には、その近似式を用いる割線法というのがあります。
初期値をは１つで行うことができます。また、初期値を２つ使う２分法などの手法もあります。
問６ コインを４回投げたときに、表が２回だけ出る確率は幾らか。
ア ０．２
イ ０．３７５
ウ ０．５
エ ０．６２５
解答 イ
解説 ４回程度ならば、全部の可能性をしらべてもよいのですが、けたが多くなった場合に通用しなくなるので、一般化して計算をします。全部で４回のうち、２回（順番は問わない）の表が出る確率は、４個の中から２個を選ぶのと同じことです。よって、4Ｃ2＝４！／｛２！（４−２）！｝により、１／６＝０．３７５となります。
問７ 次の図は、ある地方の日単位の天気の移り代わりを示したものであり、数値は翌日の天気の変化の確率を表している。ある日の天気が雨のとき、２日後の天気が晴れになる確率は幾らか。

画像（問7）を表示できません
ア ０．１５
イ ０．２７
ウ ０．３
エ ０．３３
解答 エ
解説 このような図を状態遷移図といいます。

雨から２日後に晴れになるのは、以下の３通りがあり、その合計が確率となります。
雨→晴れ→晴れ：０．３×０．４＝０．１２
雨→曇り→晴れ：０．５×０．３＝０．１５
雨→雨→晴れ：０．２×０．３＝０．０６

よって、０．３３となります。
問８ 集合Ｓ−（Ｔ∩Ｒ）に等しいものはどれか。ここで、∩は積集合、∪は和集合、−は差集合の各演算を表す。
ア （Ｓ−Ｔ）−Ｒ
イ （Ｓ−Ｔ）∪（Ｓ−Ｒ）
ウ （Ｓ−Ｔ）∪（Ｔ−Ｒ）
エ （Ｓ−Ｔ）∩（Ｔ−Ｒ）
解答 ア
解説 まず、差集合とはＡ−Ｂのとき、ＡであってＢでないものということを表します。よって、Ａ∩¬Ｂと変換できます。これを使って式を変形していきます。

Ｓ∩¬（Ｔ∩Ｒ） → Ｓ∩¬Ｔ∩¬Ｒ → （Ｓ−Ｔ）∩¬Ｒ → （Ｓ−Ｔ）−Ｒとなります。ベン図や真理値表を用いてもよいかもしれません。
問９ ８ビットのビット列の下位４ビットが変化しない操作はどれか。
ア １６進数表記０Ｆのビット列との論理積をとる。
イ １６進数表記０Ｆのビット列との論理和をとる。
ウ １６進数表記０Ｆのビット列との排他的論理和をとる。
エ １６進数表記０Ｆのビット列との否定論理積をとる。
解答 ア
解説 ビット演算に関するもので、ネットワークのマスク処理等とかかわりが深い問題です。

代表的なビット演算を下にまとめます。
ビットと１の論理積をとるとビットが残ります。
ビットと０の論理和をとるとビットが残ります。
ビットと１の論理和をとると１になります。
ビットと０の論理積をとると０になります。
ビットと１の排他的論理和をとると、ビットの反転を取り出せます。
問１０ ７ビットの文字コードの先頭に１ビットの偶数パリティビットを付加するとき、文字コード３０、３Ｆ、７Ａ、にパリティビットを付加したものはどれか。ここで、文字コードは１６進数で表している。
ア ３０、３Ｆ、７Ａ
イ ３０、３Ｆ、ＦＡ
ウ Ｂ０、３Ｆ、ＦＡ
エ Ｂ０、ＢＦ、７Ａ
解答 イ
解説 まず、パリティを付加しないデータを整理します。

０１１００００ → １が偶数個 → パリティは０
０１１１１１１ → １が偶数個 → パリティは０
１１１１０１０ → １が奇数個 → パリティは１

よって、パリティを付加すると
００１１００００ → ３０
００１１１１１１ → ３Ｆ
１１１１１０１０ → ＦＡ
問１１ 図は１の数が偶数個のビット列を受理するオートマトンの状態遷移図であり、“遇”と書かれた二重丸が受理状態を表す。ａ、ｂの正しい組合せはどれか。

画像（問11）を表示できません
画像（問11ans）を表示できません
解答 ウ
解説 １が入力されるたびに、偶数と奇数が交互に入れ替わります。０が入力された場合は、偶数と奇数は変化しないのでそのままとなります。
問１２ ２分探索木として適切なものはどれか。ここで、１〜９の数字は各ノード（節）の値を表す。
画像（問12ans）を表示できません
解答 イ
解説 一般的に２分木とは、すべてのノードについて、左の子の値≦親の値≦右の子の値となっているものを指します。
問１３ ＰＵＳＨ命令でスタックにデータをいれ、ＰＯＰ命令でスタックからデータを取り出す。動作中のプログラムにおいて、ある状態から次の順番で１０個の命令を実行したとき、スタックの中のデータは図のようになった。１番目のＰＵＳＨ命令でスタックに入れたデータはどれか。

画像（問13）を表示できません
ア ７
イ ２９
ウ ５５
エ ３２６
解答 ア
解説 一つずつ考えるとわかりやすいです。

ＰＵＳＨ：@
ＰＵＳＨ：@A
ＰＯＰ：@
ＰＵＳＨ：@A
ＰＵＳＨ：@AB
ＰＵＳＨ：@ABC
ＰＵＳＨ：@ABCD
ＰＯＰ：@ABC
ＰＯＰ：@AB
ＰＵＳＨ：@ABC

上記のように、スタート時から４つのデータが積まれたことになり、最初のＰＵＳＨは先頭から数えて、４番目なので、７となります。
問１４ データの整列方法に関する記述のうち、適切なものはどれか。
ア クイックソートでは、ある一定間隔おきに取り出した要素から成る部分列をそれぞれ整列し、さらに間隔を詰めて同様の操作を行い、間隔が１になるまでこれを繰り返す。
イ シェルソートでは、隣り合う要素を比較して、大小の順が逆であれば、それらの要素を入れ替えるという操作を繰り返して行う。
ウ バブルソートでは、中間的な基準値を決めて、それよりも大きな値を集めた区分と小さな値を集めた区分に要素を振り分ける。次に、それぞれの区分の中で同様な処理を繰り返す。
エ ヒープソートでは、未整列の部分を順序木に構成し、そこから最大値又は最小値を取り除いて既整列の部分に移す。これらの操作を繰り返して、未整列部分を縮めていく。
解答 エ
解説 代表的な整列法を下にまとめます。

挿入ソート：既に整列済みのデータ列の正しい位置に、データを追加する操作を繰り返していく
選択ソート：データ中の最小値を求め、次にそれを除いた部分の中から最小値を求める。この操作を繰り返していく
バブルソート：隣り合ったデータの比較と入替えを繰り返すことによって、小さな値のデータを次第に端の方に移していく
クイックソート：適当な基準値を選び、それより小さな値のグループと大きな値のグループにグループを分割する。この操作を繰り返していく
シェルソート：ある一定間隔おきに取り出した要素から成る部分列をそれぞれ整列し，更に間隔を詰めて同様の操作を行い，間隔が１になるまでこれを繰り返す
ヒープソート：未整列の部分を順序木に構成し、そこから最大値又は最小値を取り除いて既整列の部分に移す。これらの操作を繰り返して、未整列部分を縮めていく
問１５ ２分探索において、データの個数が４倍になると、最大探索回数はどうなるか。
ア １回増える。
イ ２回増える。
ウ 約２倍になる。
エ 約４倍になる。
解答 イ
解説 ２分探索は、１回の探索でデータの存在範囲を半分にします。つまり、データが２個なら１回。データが４個なら２回。データが８個なら３回となります。これは、ｌｏｇ2Ｎとなります。よって、データが４倍になると検索回数は２回増えるといえます。
問１６ 電気信号によってデータの書換え、消去が可能なメモリであり、電源を切っても内容を保持できるものはどれか。
ア ＤＲＡＭ
イ ＳＲＡＭ
ウ フラッシュメモリ
エ マスクＲＯＭ
解答 ウ
解説 ＳＲＡＭやＤＲＡＭは主記憶やレジスタに利用される半導体です。また、フラッシュメモリは最近大容量化がはかれれている持ち運びしやすい記憶媒体です。マスクＲＯＭとは、読み込み専用で、書き込むことができません。
問１７ 図の論理回路と同じ出力が得られる論理回路はどれか。

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


画像（問17）を表示できません
画像（問17ans）を表示できません
解答 イ
解説 回路に出力を書いていくと以下のようになり、問題の出力を簡略化すると選択肢イと一致します。

画像（問17kai）を表示できません
問１８ クロック周波数が１ＧＨｚの処理装置がある。この処理装置の命令識別が、表に示す二つから成っているとき、処理能力は約何ＭＩＰＳか。

画像（問17）を表示できません
ア ３４
イ １００
ウ １２５
エ １３３
解答 ウ
解説 １０×０．６＋５×０．４＝６＋２＝８。１命令につき、８クロック使用するので、１Ｇ／８＝１２５Ｍとなります。
問１９ 割込みに関する記述のうち、適切なものはどれか。
ア ＣＰＵは割込みを受け付けると実行中のプログラムを中断し、プログラムの再開に必要な情報を磁気ディスクの特定の領域に格納する。
イ アプリケーションは、常に割込みの発生を感知する必要がある。
ウ 入出力装置からの動作完了の通知は、内部割込みに分類される。
エ 複数の割込みの発生に備え、個々の割込み原因には優先順位が付けられる。
解答 エ
解説 まず、割り込には大きく分けて内部割りこみと外部割り込みがあります。内部割り込はゼロによる除算に代表されるソフトウェア的な原因。外部割り込みは、入出力の完了や電圧異常などに代表されるハードウェア的な原因です。

また、割り込みを受け付けるとＣＰＵはレジスタのデータを主記憶等に退避させ、割り込みの処理を実行します。さらに、複数の割り込みに優先順位をつけ、順位の低いものが、順位の高いものに割り込みを行わないようにマスク処理をする場合もあります。
問２０ 処理装置で用いられるキャッシュメモリの使用目的として、適切なものはどれか。
ア 仮想記憶のアドレス変換を高速に行う。
イ 仮想記憶のページング処理を高速に行う。
ウ 主記憶へのアクセス速度とプロセッサの処理速度の差を埋める。
エ 使用頻度の高いプログラムを常駐させる。
解答 ウ
解説 キャッシュメモリは、主記憶とプロセッサのレジスタとのアクセス速度の差を埋めるために用いられるメモリです。同じような役割で、ハードディスクと主記憶のアクセス速度を埋めるために用いられるメモリを、ディスクキャッシュといいます。