平成２４年度 秋期 基本情報技術者試験 問１−２０ 解答編



このページは

基本情報

（基本情報技術者試験）

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

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


問１ ８ビットの２進数１１０１００００を右に２ビット算術シフトしたものを、０００１０１００から減じた値はどれか。ここで、負の値は２の補数表現によるものとする。
ア ００００１０００
イ ０００１１１１１
ウ ００１０００００
エ １１１０００００
解答 ウ
解説 まず、論理シフトと算術シフトについてまとめます。
論理シフト：符号を無視して、全体をシフトします。
算術シフト：符号ビットを考慮し、空いた部分に符号と同じビットを詰めます。

解法には、２進数のまま計算する方法と１０進数に変換して計算する方法が考えられます。 ■２進数のまま計算する方法
１１０１００００を右に２ビット算術シフトをすると１１１１０１００となります。
対象から減じるために２の補数の加算に変換すると、２の補数＝ビット反転＋１＝００００１０１１＋１＝００００１１００
０００１０１００＋００００１１００＝００１０００００となります。

■１０進数に変換して計算する方法
まず、２の補数で表現されている１１１１０１００の絶対値を考えます。２の補数は２回計算すると元の値にもどるので、１１１１０１００２の補数をとると００００１０１１＋１＝００００１１００なので、８＋４＝１２となるため、、元の値は−１２であることが分かります。
減算対象は、００１０１００なので、１６＋４＝２０です。
よって、２０−（−１２）＝２０＋１２＝３２となり、２進数に戻し００１０００００が正解であることがわかります。
問２ 与えられた正の整数ｘ0、ｘ1（ｘ0＞ｘ1）の最大公約数を、次の手順で求める。ｘ0＝１７５、ｘ1＝７７の場合、手順（２）は何回実行するか。ここで“Ａ→Ｂ”は、ＡをＢに代入することを表す。

【手順】
（１） ２→ｉ
（２） ｘi-2をｘi-1で割った剰余→ｘi
（３） ｘi＝０ならばｘi-1を最大公約数として終了する。
（４） ｉ＋１→ｉとして（２）に戻る。
ア ３
イ ４
ウ ６
エ ７
解答 イ
解説 順番に計算していきます。

１回目の（１）：２→ｉ
１回目の（２）：１７５÷７７の余り２１をｘ2とする。
１回目の（３）：ｘ2は0ではないので、終了しない。
１回目の（４）：３→ｉ
２回目の（２）：７７÷２１の余り１４をｘ3とする。
２回目の（３）：ｘ3は0ではないので、終了しない。
２回目の（４）：４→ｉ
３回目の（２）：２１÷１４の余り７をｘ4とする。
３回目の（３）：ｘ4は0ではないので、終了しない。
３回目の（４）：５→ｉ
４回目の（２）：１４÷７の余り０をｘ5とする。
４回目の（３）：ｘ5は0なので、終了する。

よって、（２）は４回実行されます。
問３ 探索方法とその実行時間のオーダの適切な組合せはどれか。ここで、探索するデータの数をｎとし、ハッシュ値が衝突する（同じ値になる）確率は無視できるほど小さいものとする。また、実行時間のオーダがｎ2であるとは、ｎ個のデータを処理する時間がｃｎ2（ｃは定数）で抑えられることをいう。
画像（問3ans）を表示できません
解答 ア
解説 ３つのオーダについてまとめると下のようになります。

２分探索：１回で対象を半分にするので、ｌｏｇ2Ｎ
線形探索：１つずつＮ個を探すので、Ｎ
ハッシュ探索：関数で場所を特定するので、衝突が起こらない限り、１
問４ 英字の大文字（Ａ〜Ｚ）と数字（０〜９）を同一のビット数で一意にコード化するには、少なくとも何ビットが必要か。
ア ５
イ ６
ウ ７
エ ８
解答 イ
解説 Ａ〜Ｚまでは２６種類、０〜９までは１０種類のコードがあるため、３６種類を表現できる必要があります。１ビットは０か１で２つの情報を表せます。ｎビットは以下のように２nの情報を表現できます。

１ビット→２種類
２ビット→４種類
３ビット→８種類
４ビット→１６種類
５ビット→３２種類
６ビット→６４種類

よって、５ビットでは表現しきれないので、６ビットとなります。
問５ 四つのデータＡ，Ｂ，Ｃ，Ｄがこの順に入っているキューと空のスタックがある。手続きｐｏｐ＿ｅｎｑ，ｄｅｑ＿ｐｕｓｈを使ってキューの中のデータをＤ，Ｃ，Ｂ，Ａの順に並べ替えるとき、ｄｅｑ＿ｐｕｓｈの実行回数は最少で何回か。ここで、ｐｏｐ＿ｅｎｑはスタックから取り出したデータをキューに入れる操作であり、ｄｅｑ＿ｐｕｓｈはキューから取り出したデータをスタックに入れる操作である。
ア ２
イ ３
ウ ４
エ ５
解答 イ
解説 まず、スタックとキューのデータ構造を以下の図に示します。

スタックとキューを表示できません

それでは、入れ替えをしていきます。（左側を先頭とします。）
キュー：Ａ，Ｂ，Ｃ，Ｄ
スタック：

deq_push（Ａ）
キュー：Ｂ，Ｃ，Ｄ
スタック：Ａ

deq_push（Ｂ）
キュー：Ｃ，Ｄ
スタック：Ｂ、Ａ

deq_push（Ｃ）
キュー：Ｄ
スタック：Ｃ，Ｂ,Ａ

pop_enq（Ｃ） キュー：Ｄ,Ｃ
スタック：Ｂ,Ａ

pop_enq（Ｂ） キュー：Ｄ,Ｃ,Ｂ
スタック：Ａ

pop_enq（Ａ） キュー：Ｄ,Ｃ,Ｂ,Ａ
スタック：

よって、deq_pushもpop_enqを３回ずつ行われます。
問６ 昇順に整列済みの配列要素Ａ（１）、Ａ（２）、・・・Ａ（ｎ）から、Ａ（ｍ）＝ｋとなる配列要素Ａ（ｍ）の添字ｍを２分探索法によって見つける処理を図に示す。終了時点でｍ＝０である場合は、Ａ（ｍ）＝ｋとなる要素は存在しない。図中のａに入れる式はどれか。ここで、“／”は、小数点以下を切り捨てる除算を表す。

画像（問6）を表示できません
ア （ｘ＋ｙ）→ｍ
イ （ｘ＋ｙ）／２→ｍ
ウ （ｘ−ｙ）／２→ｍ
エ （ｙ−ｘ）／２→ｍ
解答 イ
解説 一般的な２分探索に関する問題です。２分探索を行うデータはソートされていることが前提です。

ｘが探索範囲の下限、ｙが探索範囲の上限をあらわしています。ｍが探索範囲の中間をあらわしています。

よって、探索値＜ｍだった場合は、探索範囲は下半分。探索値＞ｍだった場合は、探索範囲は上半分となります。この時にこのｍをどうやって更新するかという問題です。判定の後に上限や下限が更新されるので、ｘとｙを足して２で割った値が中間となります。
問７ ｎ！の値を、次の関数Ｆ（ｎ）によって計算する。乗算の回数を表す式はどれか。

画像（問7）を表示できません
ア ｎ−１
イ ｎ
ウ ｎ2
エ ｎ！
解答 イ
解説 ｎ＝３として、値を見ていきます。
Ｆ（３）＝３×Ｆ（２）
　＝３×２×Ｆ（１）
　＝３×２×１×Ｆ（０）
　＝３×２×１×１

よって、ｎ回の乗算が行われています。
問８ ＸＭＬの特徴として、最も適切なものはどれか。
ア ＸＭＬでは、ＨＴＭＬに、Ｗｅｂページの表示性能の向上を主な目的とした機能を追加している。
イ ＸＭＬでは、ネットワークを介した情報システム間のデータ交換を容易にするために、任意のタグを定義することができる。
ウ ＸＭＬで用いることができるスタイル言語は、ＨＴＭＬと同じものである。
エ ＸＭＬは、ＳＧＭＬを基に開発されるＨＴＭＬとは異なり、独自の仕様として開発された。
解答 イ
解説 まず、代表的な３つのマークアップ言語をまとめます

ＨＴＭＬ：インターネットで最も多く用いらているマークアップ言語
ＳＧＭＬ：ＨＴＭＬやＸＭＬの元となった、国際標準のマークアップ言語
ＸＭＬ：ユーザ自身がタグを定義することができるマークアップ言語

転送には基本的に、ＨＴＴＰが使われます。さらに、最近はＸＨＴＭＬというのもあります
問９ 割り込み発生時のプロセッサの処理手順はどれか。

@ プログラムレジスタ（プログラムカウンタ）などの退避
A ユーザモードから特権モードへの移行
B 割込み処理ルーチンの開始番地の決定
C 割込み処理ルーチンの実行
ア @ → B → C → A
イ @ → C → A → B
ウ A → @ → B → C
エ A → B → C → @
解答 ウ
解説 割込み処理は、大きく分けて、現在の情報の退避、割込み情報の構築と実行、退避した情報の復元という順番で行われます。

よって、レジスタを退避させるための特権モードへの移行（A）→レジスタ類の退避（@）→アドレスの決定（B）→実行（C）が正しい順といえます。

なお、割込み時には優先順位が考慮され、優先順位の低い割込みできないようになっています。
問１０ 主記憶のアクセス時間が６０ナノ秒、キャッシュメモリのアクセス時間が１０ナノ秒であるシステムがある。キャッシュメモリを介して主記憶にアクセスする場合の実効アクセス時間が１５ナノ秒であるとき、キャッシュメモリのヒット率は幾らか。
ア ０．１
イ ０．１７
ウ ０．８３
エ ０．９
解答 エ
解説 ヒット率をａとして計算します。

１０×ａ＋６０×（１−ａ）＝１５
１０ａ＋６０−６０ａ＝１５
５０ａ＝４５

よって、ａ＝０．９（９０％）となります。
問１１ 並列にアクセス可能な複数台の時期ディスクに、各ファイルのデータを一定サイズのブロックに分割して分散配置し、ファイルアクセスの高速化を図る手法はどれか。
ア ディスクアットワンス
イ ディスクキャッシュ
ウ ディスクストライピング
エ ディスクミラーリング
解答 ウ
解説 選択肢の内容を下にまとめます。ディスクとついていますが、全く違う用語です。

選択肢ア：ＣＤ−Ｒなどへの書き込み方式の一つ。データをまとめて一度に書き込む方式、互換性が高いが後から追記ができない。
選択肢イ：主記憶とハードディスクのアクセス速度の差を埋めるために用いられるメモリ
選択肢ウ：複数のディスクに並列に書き込み、アクセス速度を向上させる（ＲＡＩＤ−０に相当）
選択肢エ：複数のディスクに同じデータを書き込み、信頼性を向上させる（ＲＡＩＤ−１に相当
問１２ ９６ｄｐｉのディスプレイに１２ポイントの文字をビットマップで表示したい。正方フォントの縦は何ドットになるか。ここで、１ポイントは１／７２インチとする。
ア ８
イ ９
ウ １２
エ １６
解答 エ
解説 ｄｐｉ（dot per inch）とは、１インチ当たりどの程度のドットを表現できるかを表したものでプリンタやディスプレイの解像度を表す際の単位です。

まず、１２ポイントとは、１２×（１／７２）＝１／６インチです。つぎに、９６ｄｐｉは１インチあたり９６ビット表示できるので、９６／６＝１６ビットとなります。
問１３ ３層クライアントサーバシステム構成で実現したＷｅｂシステムの特徴として、適切なものはどれか。
ア ＨＴＭＬで記述されたプログラムをサーバ側で動作させ、クライアントソフトはその結果を画面に表示する。
イ 業務処理の変更のたびに、Ｗｅｂシステムを動作させるための業務処理用アプリケーションを配布し、クライアント端末にインストールする必要がある。
ウ 業務処理はサーバ側で実行し、クライアントソフトはＨＴＭＬの記述に従って、その結果を画面に表示する。
エ クライアント端末には、サーバ側からのＨＴＴＰ要求を待ち受けるサービスを常駐させておく必要がある。
解答 ウ
解説 サーバとはサービスを提供するもので、クライアントとはサービスを依頼する（受け取る）ものです。まず、２層と３層についてまとめます。

２層：サーバとクライアント
３層：プレゼンテーション層・ファンクション層（アプリケーション層）・データベース層

そして、プレゼンテーション層がクライアントに該当する部分で、ファンクション層とデータベース層がサーバに該当する部分になります。

最後に、主な機能は以下のようになります。
プレゼンテーション層：クライアントへのインタフェース部分
ファンクション層：データの加工
データベース層：データへのアクセス

上記を踏まえて、順に選択肢を見ていきます。
選択肢ア：ＨＴＭＬはクライアントのブラウザ上の動作を記述するもので、サーバ上で動作するものではありません。
選択肢イ：Ｗｅｂシステムは、基本的にクライアントの動作環境としてブラウザを利用するため、専用のアプリケーションは不要です。
選択肢ウ：処理はサーバ側で動作し、結果をＨＴＭＬやＪａｖａＳｃｒｉｐｔで返し、クライアントはブラウザで確認します。（正解）
選択肢エ：サーバ側にクライアントからのＨＴＴＰ要求を待ち受けるサービスを常駐させる必要があります。
問１４ デュアルシステムの説明として、最も適切なものはどれか。
ア 同じ処理を行うシステムを二重に用意し、処理結果を照合することで処理の正しさを確認する。どちらかのシステムに障害が発生した場合は、縮退運転によって処理を継続する。
イ オンライン処理を行う現用系と、バッチ処理などを行いながら待機させる待機系を用意し、現用系に障害が発生した場合は待機系に切り替え、オンライン処理を続行する。
ウ 待機系に現用系のオンライン処理プログラムをロードして待機させておき、現用系に障害が発生した場合は、即時に待機系に切り替えて処理を続行する。
エ プロセッサ、メモリ、チャネル、電源系などを二重に用意しておき、それぞれの装置で片方に障害が発生した場合でも、処理を継続する。
解答 ア
解説 代表的な冗長化構造についてまとめます。メインで動作しているシステムを主系、サブで動作しているシステムを従系といいます。

デュアルシステムは：２台が常に同時に稼働していて結果を照合するシステム
デュプレックスシステム（ホットスタンバイ）：２台を同時に稼働させておき、同期などを行い、いつでも従系が作業を引き継げるようにしておくシステム
デュプレックスシステム（ウォームスタンバイ）：２台を同時に稼働させておき、従系を起動させておくが、同期は行わないシステム
デュプレックスシステム（コールドスタンバイ）：１台のみ稼働させておき、主系が故障したときに従系に切り替えて処理を継続するシステム
シンプレックスシステムは：１台のみの単純なシステム。故障するとお終いです。

稼働率の比較はデュアルシステム ＞ ホットスタンバイシステム ＞ ウォームスタンバイ ＞ コールドスタンバイシステム ＞ シンプレクスシステムとなります。
なお、ホットスタンバイ、ウォームスタンバイ、コールドスタンバイの差は、一方が故障してから切り替えるまでのスピードの差によります。

他の選択肢のシステムは以下のようになります。
選択肢イは、デュプレックスシステムの説明です。
選択肢ウは、デュプレックスシステムのホットスタンバイの説明です。
選択肢エは、フォールトトレラントの説明です。
問１５ 図のような、稼働率Ｐのシステムで構成された多重化システム全体の稼働率を表す式はどれか。ここで、並列の部分は、どちらか一方が稼働していればよいものとする。

画像（問15）を表示できません
ア １−（１−Ｐ）（１−Ｐ2）2
イ Ｐ｛１−（１−Ｐ）4｝
ウ Ｐ｛１−（１−Ｐ）2｝2
エ Ｐ｛１−（１−Ｐ2）2｝
解答 エ
解説 以下のように段階的に求めていくと、Ｐ｛１−（１−Ｐ2）2｝となります。

画像（問15kai）を表示できません
問１６ コンピュータシステムの信頼性に関する記述のうち、適切なものはどれか。
ア システムの遠隔保守は、ＭＴＴＲを長くし、稼働率を向上させる。
イ システムの稼働率は、ＭＴＴＲとＭＴＢＦを長くすることで向上する。
ウ システムの構成が複雑なほど、ＭＴＢＦは長くなる。
エ システムの予防保守は、ＭＴＢＦを長くするために行う。
解答 エ
解説 まず、２つの用語と稼働率をまとめます。

平均故障間隔（ＭＴＢＦ：Mean Time Between Failure）は故障と故障の間の動作していた時間の平均
平均故障時間（ＭＴＴＲ：Mean Time To Repair）は実際に故障していた時間の平均
稼働率＝ＭＴＢＦ／（ＭＴＢＦ＋ＭＴＴＲ）

それでは、選択肢を順に見ていきます。
選択肢ア：遠隔保守はＭＴＴＲを短くし、稼働率を向上させます。
選択肢イ：ＭＴＴＲを長くすることは稼働率の向上になりますが、ＭＴＢＦを長くすることは稼働率の低下になります。
選択肢ウ：一般的にシステムの構成が複雑なほど、多くの要素が稼働していなければならないので、稼働率は低下します。
選択肢エ：予防保守は、事前に障害を避けるため、ＭＴＢＦを長くし、稼働率を向上させます。（正解）
問１７ タスクスケジューリング方式の説明のうち、特定のタスクがＣＰＵ資源の割当てを持ち続ける可能性が最も高いものはどれか。
ア 各タスクの優先度を決めて、優先度が高い順に実行し、ＣＰＵ割当てまでの待ち時間の長さに応じて優先度を徐々に上げていく。
イ 各タスクを実行可能待ち行列に置かれた順に実行し、一定時間が経過したら実行を中断して実行可能待ち行列の最後尾に加える。
ウ 処理予定時間が最も短いタスクから順に処理を実行する。現在実行中の処理が終了するか、又は何らかの要因によって中断されたとき、次のタスクを開始する。
エ タスクがシステムに到着した順に実行可能待ち行列の最後尾に加え、常に実行可能待ち行列の先頭タスクにＣＰＵを割り当てる。
解答 ウ
解説 それぞれのスケジューリング方式の待たされるタスクについて順に見ていきます。

選択肢ア（優先順位方式）：単純に優先度の高いものを実行すると、待ち続けるタスクが発生するが、待った時間に応じて優先順位を上げる（エイジング）を行うことでこれを回避しています。
選択肢イ（ラウンドロビン方式）：タスクの切り替えに多少のオーバヘッドがかかりますが、すべてのタスクに順番にＣＰＵの使用権がわたります。
選択肢ウ（処理時間順方式）：常に自分よりも処理時間の短いものが投入され続ける限り、そのタスクはまたされ続けます。
選択肢エ（到着順方式）：リアルタイム性は失われますが、投入したタスクはいつかは処理してもらえます。

いつまでも投入したジョブが実行されないことをスタベーションといいます。
問１８ ＯＳが記憶領域の割当てと解放を繰り返すことによって、細切れの未使用領域が多数できてしまう場合がある。この現象を何というか。
ア コンパクション
イ スワッピング
ウ フラグメンテーション
エ ページング
解答 ウ
解説 選択肢の用語を以下にまとめます。
コンパクション：メモリコンパクションともいい、メインメモリ内を整理して、使用されていない領域を連続した領域にすること。
スワッピング：仮想記憶において，実主記憶と仮想記憶の間で行う入れ替えのこと。
フラグメンテーション：ファイルが断片化され、ＨＤＤの様々な部分に格納されること。これにより、ファイルの読み出しに余計に時間がかかる。
ページング：仮想記憶において、固定長のページという単位でデータを入れ替えたりすること。
問１９ ページング方式の仮想記憶において、ページ置換えアルゴリズムにＬＲＵ方式を採用する。主記憶に割り当てられるページ枠が４のとき、ページ１，２，３，４，５，２，１，３，２，６の順にアクセスすると、ページ６をアクセスする場合で置き換えられるページはどれか。ここで、初期状態では主記憶にどのページも存在しないものとする。
ア １
イ ２
ウ ４
エ ５
解答 エ
解説 まず、ＬＲＵ（Least Recently Used）とは最近最も使われていないもの（使われてから最も時間が経過したもの）をページアウトして、新しいページを入れるというアルゴリズムです。これにのっとりトレースをしていきます。

@（１へアクセス）１
A（２へアクセス）１，２
B（３へアクセス）１，２，３
C（４へアクセス）１，２，３，４
D（５へアクセス）２，３，４，５（１がページアウト）
E（２へアクセス）３，４，５，２
F（１へアクセス）４，５，２，１（３がページアウト）
G（３へアクセス）５，２，１，３（４がページアウト）
H（２へアクセス）５，１，３，２
I（６へアクセス）１，３，２，５（５がページアウト）

よって、選択肢エが正解となります。
問２０ プログラムを構成するモジュールの結合を、プログラムの実行時に行う方法はどれか。
ア インタプリタ
イ オーバレイ
ウ 静的リンキング
エ 動的リンキング
解答 エ
解説 選択肢の用語を以下にまとめます。

インタプリタ：ソースコードを１行ずつ機械語に変換しながら実行するソフトウェア
オーバレイ：プログラムが大きくメインメモリ上に入らない場合に、機能（モジュール）ごとに交換しながらメインメモリに入れていく手法
静的リンキング：実行ファイルと必要なモジュールやライブラリをコンパイル時に結合すること
動的リンキング：実行ファイルと必要なモジュールやライブラリをプログラムの実行中に必要になったタイミングで結合すること