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

このページは

基本情報

（基本情報技術者試験）

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

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

問１	１バイトのデータで０のビット数と１のビット数が等しいもののうち、符号なしの２進数として見たときに最大となるものを、１０進整数として表したものはどれか。

ア	１２０
イ	１２７
ウ	１７０
エ	２４０

解答	エ

解説	１バイトは８ビットなので、１と０がそれぞれ４つずつ現れるようにすればよいということになります。２進数でも左側に行くほど重み付けが大きくなるので、（１１１１００００）が最大となります。よって、１２８＋６４＋３２＋１６＝２４０となります。符号がある場合は、最上位ビットが１の場合は負数となるので、（０１１１１０００）が最大となり１２０となります。

問２	数値を２進数で格納するレジスタがある。このレジスタに正の整数ｘを設定した後、“レジスタの値を２ビット左にシフトして、ｘを加える”操作をすると、レジスタの値はｘの何倍になるか。ここで、シフトによるあふれ（オーバフロー）は、発生しないものとする。

ア	３
イ	４
ウ	５
エ	６

解答	ウ

解説	桁あふれのない正の整数の２進数は、左にｎビットシフトすると２ⁿ倍されるという性質があります。（１０進数でも３４を３４０にすると１０倍になるのと同じです）また、もともとの値を加えるということは、１倍を加えるということなので、２²+1で５倍になります。

問３	８ビットで表される符号なし２進数ｘが１６の倍数であるかどうかを調べる方法として、適切なものはどれか。

ア	ｘと２進数００００１１１１のビットごとの論理積をとった結果が０である。
イ	ｘと２進数００００１１１１のビットごとの論理和をとった結果が０である。
ウ	ｘと２進数１１１１００００のビットごとの論理積をとった結果が０である。
エ	ｘと２進数１１１１００００のビットごとの論理和をとった結果が０である。

解答	ア

解説	１６の倍数であるということは、１６で割ったあまりが０であるという風に言い換えることができます。つまり、１～１５の値が存在しなければ１６の倍数になります。よって、１－１５を作るための下位４ビットがすべて０ならば１６の倍数であるといえます。そのために、下位４ビットと１（残りは０）との論理積をとることで下位４ビットを取り出すことができるので、それが０かどうかを調べることでわかります。

問４	次の２４ビットの浮動小数点数形式で表現できる最大値を表すビット列を、１６進数として表したものはどれか。ここで、この形式で表現される値は（－１）^s×１６^E-64×０.Ｍである。

ア	３ＦＦＦＦＦ
イ	７ＦＦＦＦＦ
ウ	ＢＦＦＦＦＦ
エ	ＦＦＦＦＦＦ

解答	イ

解説	最大値になるとは、正の値で、指数部と仮数部が最も大きくなるようにすればいいことになります。よって、符号部（最上位ビット）が０、残りが全部１となる（７ＦＦＦＦＦ）が最大となります。

問５	負数を２の補数で表す１６ビットの符号付き固定小数点数の最小値を表すビット列を、１６進数として表したものはどれか。

ア	７ＦＦＦ
イ	８０００
ウ	８００１
エ	ＦＦＦＦ

解答	イ

解説	２進数を負の補数で表す場合の範囲は、－２^n-1－１～２^n-1となります。よって、－３２７６８となり、これを２進数に変換し、２の補数をとると８０００₁₆となります。ここでは、もうひとつの考え方をしてみたいと思います。まず、－１は０００１₁₆のビット反転をして１を加えるとＦＦＦＦ₁₆ －２は０００２₁₆のビット反転をして１を加えるとＦＦＦＥ₁₆ －３は０００３₁₆のビット反転をして１を加えるとＦＦＦＤ₁₆ と１ずつ減っていくことがわかります。また、負数は最上位ビットが１であるので、最上位ビットが１でできる限り値を減らすと８０００₁₆になることが予想できます。

問６	浮動小数点形式で表現される数値の演算において、有効けた数が大きく減少するものはどれか。

ア	絶対値がほぼ等しく、同符号である数値の加算
イ	絶対値がほぼ等しく、同符号である数値の減算
ウ	絶対値の大きい数と絶対値の小さい数の加算
エ	絶対値の大きい数と絶対値の小さい数の減算

解答	イ

解説

まず、それぞれの誤差について下にまとめます。

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

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

情報落ちの実際の例は、１．１１１１－１．１１１０＝０．０００１のように有効桁数が減ってしまいます。

問７	男子３人、女子５人の中から３人を選ぶとき、男子が少なくとも１人含まれる選び方は何通りあるか。

ア	２１
イ	３０
ウ	４６
エ	５６

解答	ウ

解説

組み合わせ論に関する問題です。ｎ人の中からｍ人を選ぶとき（順番を考えないとき）_nＣ_mと表記し、_nＣ_m＝ｎ！／（ｍ！（ｎ－ｍ）！）となります。

解答法は以下の２つが考えられますが、②での解答の方が今回は簡単だと思うので、②でといてみます。
①男子が１人の場合＋男子が２人の場合＋男子が３人の場合の和
②全部の組み合わせ－３人とも女子の場合

まず、すべての組み合わせは、₈Ｃ₃＝８！／（３！（８－３）！）＝８×７×６×５×４×３×２×１／（３×２×１×５×４×３×２×１）＝８×７＝５６通り
３人とも女子の組み合わせは、₅Ｃ₃＝５！／（３！（５－３）！）＝５×４×３×２×１／（３×２×１×２×１）＝１０通り

よって、５６－１０＝４６通りとなります。

また、順番を考える順列は、_nＰ_m＝ｎ！／（ｎ－ｍ）！となります。

問８	次に示す手順は、列中の少なくとも一つは１であるビット列が与えられたときに、最も右にある１を残し、ほかのビットをすべて０にするアルゴリズムである。例えば、００１０１０００が与えられたとき、００００１０００が求まる。ａに入る論理演算はどれか。手順１与えられたビット列Ａを符号なしの２進数と見なし、Ａから１を引き、結果をＢとする。手順２ＡとＢの排他的論理和（ＸＯＲ）を求め、結果をＣとする。手順３ＡとＣの[ ａ ]を求め、結果をＡとする。

ア	排他的論理和（ＸＯＲ）
イ	否定論理積（ＮＡＮＤ）
ウ	論理積（ＡＮＤ）
エ	論理和（ＯＲ）

解答	ウ

解説	問題文を例に考えて見ましょうＡ＝００１０１０００Ｂ＝００１００１１１（Ａ－１）Ｃ＝００００１１１１（ＡとＢの排他的論理和））このときに、ＡとＣで何らかの演算をとると００００１０００となります。ＸＯＲだと００１００１１１ＮＡＮＤだと１１１１０１１１ＡＮＤだと００００１０００ＯＲだと００１０１１１１以上のことからＡＮＤであることがわかります。

問９	次の真理値表で、変数Ｘ、Ｙ、Ｚに対する関数Ｆを表す式はどれか。ここで、“・”は論理積、“＋”は論理和、ＡはＡの否定を表す。

ア	Ｘ・Ｙ＋Ｙ・Ｚ
イ	Ｘ・Ｙ・Ｚ＋Ｙ
ウ	Ｘ・Ｙ・Ｚ＋Ｘ・Ｙ＋Ｙ・Ｚ
エ	Ｘ・Ｙ・Ｚ＋Ｘ・Ｙ＋Ｙ・Ｚ

解答	ウ

解説	まず、出力が１となる組み合わせを書き出します。 ①Ｘ・Ｙ・Ｚ ②Ｘ・Ｙ・Ｚ ③Ｘ・Ｙ・Ｚ ④Ｘ・Ｙ・Ｚ ②と③からＹ・Ｚ ③と④からＸ・Ｙを作ります。 ①はまとめる事がないので、Ｘ・Ｙ・Ｚ＋Ｘ・Ｙ＋Ｙ・Ｚ

問１０	長さ３の文字列c₁c₂c₃の中には、長さ２以上の連続した部分文字列としてc₁c₂、c₂c₃及びc₁c₂c₃の三つがある。長さ１００の文字列c₁c₂・・・c₁₀₀の中に、長さ１０以上の連続した部分文字列が全部でいくつあるか求める式はどれか。

ア	１＋２＋３＋・・・＋８８＋８９
イ	１＋２＋３＋・・・＋８９＋９０
ウ	１＋２＋３＋・・・＋９０＋９１
エ	１＋２＋３＋・・・＋９８＋９９

解答	ウ

解説	元の文字列の中に長さ１００は１個。９９は２個。９８は３個。・・・１１は９２個。１０は９１個あるので、１～９１間での合計となります。

問１１	図で表される有限オートマトンで受理される文字列はどれか。

ア	０１０１１
イ	０１１１１
ウ	１０１１１
エ	１１１１０

解答	ウ

解説

このような有限オートマトンを特に、決定性有限オートマトン（ＤＦＡ）といいます。まず、下のように各状態に名前をつけます。ＳはＳｔａｒｔの略で初期状態を表します。ＧはＧｏａｌの略で受理状態を表します。

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

それでは、各選択肢を追跡していきます。
選択肢ア：Ｓ → Ｓ → Ａ → Ｓ → Ａ → Ｂ
選択肢イ：Ｓ → Ｓ → Ａ → Ｂ → Ｇ → Ｃ
選択肢ウ：Ｓ → Ａ → Ｓ → Ａ → Ｂ → Ｇ
選択肢エ：Ｓ → Ａ → Ｂ → Ｇ → Ｃ → Ｃ

この決定性有限オートマトンは、１が連続して４つ以上現れず、かつ１が３個続いて終わるようなものを受理します。
Ａは１が１つ続いた状態。Ｂが２つ続いた状態。Ｇが３つ続いた状態。Ｃが１度でも４つ以上続いたデッド状態（一度入ると受理しない状態）です。

問１２	四則演算の式の書き方には、演算子をオペランドの前に書く方法（前置記法）、オペランドの間に書く方法（中置記法）、オペランドの後に書く方法（後置記法）の３通りがある。図は、２分木で表現された式のたどり方と、各記法によって表される式を例示したものである。各記法で式を書く手順の説明として、適切なものはどれか。

ア	前置記法：節から上に戻るときにそこの記号を書く
イ	中置記法：節に下りたときにそこの記号を書く。
ウ	後置記法：節から上に戻るときにそこの記号を書く。
エ	後置記法：葉ならばそこの記号を書いて戻る。演算子ならば戻るときに左括弧を書き、左の枝から右の枝に移るときに記号を書き、上に戻るときに右括弧を書く。

解答	ウ

解説	一般的に数学で利用するのは、中置記法ですが、コンピュータでは、前置記法（ポーランド記法）や後置記法（逆ポーランド記法）が括弧を使わずに利用でき、スタックで実装できるため利用されることが多いです。節から戻るときとは、子から親へ戻るときです。前置記法では、親から子。後置記法は子から親に戻るときに記号がおかれます。中置記法では括弧が必要となります。

問１３	表は、配列を用いた連結セルによるリストの内部表現であり、リスト[東京、品川、名古屋、新大阪]を表している。このリストを[東京、新横浜、名古屋、新大阪]に変化させる操作はどれか。ここで、Ａ（ｉ,ｊ）は表の第ｉ行第ｊ列の要素を表す。例えば、Ａ（３,１）＝“名古屋”であり、Ａ（３,２）＝４である。また、→は代入を表す。

解答	ウ

解説	このようなデータ構造を単方向リストといいます。つまり、１行目を考えると、『東京の次は、２行目』というのをあらわしています。この２列目をたどっていくことで、次々とデータをあらわしています。よって、リストを問題文のように変更するためには、東京の次を新横浜にし、新横浜の次を名古屋にすることで、変更できます。つまり、東京の次（Ａ（１，２））を新横浜（５）に変更し、新横浜の次（Ａ（５，２））を（３）に変更します。ここでは、３という定数ではなく、間接的に変更しています。よって、先にＡ（１，２）を書き換えてしまうと、参照できなくなるので、新横浜を変更してから東京を変更するという流れになります。

問１４	昇順に整列されたｎ個のデータが配列に格納されている。探索したい値を２分探索法で探索するときの、およその比較回数を求める式はどれか。

ア	ｌｏｇ₂ｎ
イ	（ｌｏｇ₂ｎ＋１）／２
ウ	ｎ
エ	ｎ²

解答	ア

解説	２分探索は、１回の検索で探索範囲を半分にします。つまり、１探索できる個数は、１回で１／２。２回で１／４。３回で１／８・・・と範囲を狭められます。この探索回数をｎとすると比較回数はｌｏｇ₂ｎとなります。（また、およそというのは、２ⁿのデータサイズでなかった場合には近似になるためです。）

問１５	次の規則にしたがって要素Ａ[０]、Ａ[１]、・・・、Ａ[９]に正の整数ｋを格納する。１６、４３、７３、２４、８５を順に格納したとき、８５が格納される場所はどこか。ここでｘｍｏｄｙはｘをｙで割った剰余を返す。また、配列の要素はすべて０に初期化されている。 [規則] (1) Ａ[k mod 10] = 0ならば、k→Ａ[k mod 10]とする。 (2) (1)で格納できないとき、Ａ[(k+1) mod 10] = 0ならば、k→Ａ[(k+1) mod 10]とする。 (3) (2)で格納できないとき、Ａ[(k+4) mod 10] = 0ならば、k→Ａ[(k+4) mod 10]とする。

ア	Ａ［３］
イ	Ａ［５］
ウ	Ａ［６］
エ	Ａ［９］

解答	エ

解説	順番に追いかけて行きます。１６：①により、Ａ［６］に格納する。４３：①により、Ａ［３］に格納する。７３：①では衝突が起こるので、②により、Ａ［４］に格納する。２４：①では衝突が起こるので、②により、Ａ［５］に格納する。８５：①、②では衝突するので、③により、Ａ［９］に格納する。よって、８５はＡ［９］に格納されます。

問１６	フラッシュメモリに関する記述として、適切なものはどれか。

ア	紫外線で全内容を消して書き直せるメモリである。
イ	データを速く読み出せるので、キャッシュメモリとしてよく用いられる。
ウ	不揮発性メモリの一種であり、電気的に全部又は一部分を消して内容を書き直せるメモリである。
エ	リフレッシュ動作が必要なメモリであり、主記憶に広く使われる。

解答	ウ

解説	最近は、持ち運びに便利なＵＳＢフラッシュメモリが良く流通しています。フラッシュメモリは、何度でも書き換えが可能なメモリです。リフレッシュが必要なのは、ＤＲＡＭというメモリです。また、紫外線によるデータの消去をするのはＥＰＲＯＭで、電気的にデータを消去するのはＥＥＰＲＯＭです。ＥＥＰＲＯＭを改良したのがフラッシュメモリになります選択肢アは、ＥＰＲＯＭの説明です。選択肢イは、ＳＲＡＭの説明です。選択肢エは、ＤＲＡＭの説明です。

問１７	図の論理回路において、Ａ＝１、Ｂ＝０、Ｃ＝１のとき、Ｐ、Ｑ、Ｒの値の適切な組合せはどれか。

解答	ア

解説	１つずつ追いかけて行きます。Ｐ＝ＡＡＮＤＢ＝１ＡＮＤ０＝０Ｑ＝ＰＯＲＣ＝０ＯＲ１＝１Ｒ＝ＮＯＴＱ＝ＮＯＴ１＝０よって、選択肢アが正解となります。

問１８	次の図のうち、パイプライン制御の説明として適切なものはどれか。ここで、図中の各記号の意味は次のとおりとする。Ｆ：命令呼び出し、Ｄ：解読、Ａ：アドレス計算、Ｒ：オペランド呼び出し、Ｅ：実行

解答	ウ

解説	パイプラインとは、処理を少しずつずらして並列的に行うことで、処理を高速に行う処理をいいます。正解である選択肢ウは、選択肢アが従来の処理形態と比べてかなり長くなっています。選択肢エのようなものをスーパースケーラ（スーパースカラー）方式といいます。

問１９	ＰＣのＣＰＵのクロック周波数に関する記述のうち、適切なものはどれか。

ア	クロック周波数のよってＣＰＵの命令実行タイミングが変化する。クロック周波数が高くなるほど命令実行速度が上がる。
イ	クロック周波数によってＬＡＮの通信速度が変化する。クロック周波数が高くなるほどＬＡＮの通信速度が上がる。
ウ	クロック周波数によって磁気ディスクの回転数が変化する。クロック周波数が高くなるほど回転数が高くなり、磁気ディスクの転送速度が上がる。
エ	クロック周波数によってリアルタイム処理の割込み間隔が変化する。クロック周波数が高くなるほど割込み頻度が高くなり、リアルタイム処理の処理速度が上がる。

解答	ア

解説	ＣＰＵのクロックとは、ＣＰＵが行う命令の実行タイミングのようなものです。よって、クロック周波数が高いほど短い時間で処理ができるといえます。

問２０	図に示す構成で、表に示すようにキャッシュメモリと主記憶のアクセス時間だけが異なり、ほかの条件は同じ２種類のＣＰＵＸとＹがある。あるプログラムをＣＰＵＸとＹでそれぞれ実行したところ、両者の処理時間は等しかった。このとき、キャッシュメモリのヒット率は幾らか。ここで、ＣＰＵ処理以外の影響はないものとする。

ア	０．７５
イ	０．９０
ウ	０．９５
エ	０．９６

解答	イ

解説	キャッシュメモリは、ＣＰＵのレジスタと主記憶とのアクセス速度の差を埋めるために用いられるものです。ここでヒット率をａとするとＣＰＵＸのアクセス時間＝４０×ａ＋４００（１－ａ）ＣＰＵＹのアクセス時間＝２０×ａ＋５８０（１－ａ）ここで、２つのＣＰＵのアクセス時間は等しいので４０×ａ＋４００（１－ａ）＝２０×ａ＋５８０（１－ａ）２０ａ＝１８０（１－ａ）２０ａ＝１８０－１８０ａ２００ａ＝１８０ａ＝１８０／２００＝０．９よって、ヒット率は０．９であるといえます。

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

基本情報

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