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

基本情報

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

解答 エ

解説 まず、１０進数の３０を２進数に変換する具体例を考えます。 ３０÷２＝１５…０ １５÷２＝７…１ ７÷２＝３…１ ３÷２＝１…１ １÷２＝０…１ ２は２進数の２であり、３進数なら３、４進数なら４となります。ここで、出てきた余りを下からたどると、１１１１０となります。これが求める２進数の値です。 それでは、アルゴリズムにあてはめてみます。 �@まず、２で割った余りを取り出す。 �A次に、値を半分にする（端数は切り捨て） �B上の２つを値が０になるまで繰り返す。 よって、�@がａ、�Aがｂに相当する選択肢エが正解となります。

問５ 実数ａを引数とする関数ｉｎｔ（ａ）は、ａを超えない最大の整数値を返す。例えば、 ｉｎｔ（８．９）＝８ ｉｎｔ（−８．５）＝−９ である。整数ｂと正の小数ｃ（０＜ｃ＜１）に対して、 ａ＝−（ｂ＋ｃ） が成り立つとき、 ａ−ｉｎｔ（ａ） を使って表した式はどれか。

ア ｃ イ −ｃ ウ １−ｃ エ ｃ−１

解答 ウ

解説 まず、ｉｎｔ関数の性質を数直線を使って図示すると下のようになります。 Ａは元の値で、ｉｎｔ（ａ）は端数を取り除いた値。つまり、３．８−３＝０．８のようなものです。 今回は、負の値なので、−１．４＋１＝０．４のようになります。 一方で、０＜ｃ＜１により、ｂは小数点以上。ｃが小数点以下を表現していると考えられるので、−１．４はｂ＝１。ｃ＝０．４という具合です。 最後に、ａ−ｉｎｔ（ａ）は−１．４＋２＝０．６のようになるので、１−ｃが正解となります。

問７ 図の線上を、点Ｐから点Ｒを通って、点Ｑに至る最短経路は何通りあるか。

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

解答 エ

解説 Ｐ〜ＲとＲ〜Ｑに分けて考えます。とりうる値は右と上の二つです。 Ｐ〜Ｒの場合は、上に２つ右に２つあるので、この組み合わせを考えると4Ｃ2＝４！／（２！（４−２）！）＝６ Ｒ〜Ｑの場合は、上に２つ右に３つあるので、この組み合わせを考えると5Ｃ2＝５！／（２！（５−２）！）＝１０ よって、６×１０で６０通りとなります。

問１０ 次の真理値表の演算結果を表す真理値表はどれか。ここで、＋は論理和、・は論理積を表す。

ア （ｘ・ｙ）＋ｚ イ （ｘ＋ｙ）・ｚ ウ ｘ・（ｙ＋ｚ） エ ｘ＋（ｙ・ｚ）

解答 ウ

解説 まず、出力が１となる組み合わせを書き出します。 �@ｘ・ｙ・ｚ �Aｘ・ｙ・ｚ �Bｘ・ｙ・ｚ �@と�Bをまとめて、ｘ・ｚ �Aと�Bをまとめて、ｘ・ｙ さらに、この二つをまとめてｘ・（ｙ＋ｚ）となります。

問１２ 親の節がこの節の値より小さいヒープがある。このヒープへの挿入は、要素が最後部に追加し、その要素が親より小さい間、親と子を交換することを繰り返せばよい。次のヒープの＊の位置に要素７を追加したとき、Ａの位置に来る要素はどれか。

ア ７ イ １１ ウ ２４ エ ２５

解答 イ

解説 まず、最初に＊の位置に７が挿入されます。その後、親の値と比較しながら適切な位置に調整されます。説明のために以下のようにＡのほかに、Ｂ、Ｃのラベルを振ります。 �@７＜２５により、＊の位置に２５。Ａの位置に７が入ります。 �A７＜１１により、Ａの位置に１１。Ｂの位置に１１が入ります。 �B７＜９により、Ｂの位置に９。Ｃの位置に７が入ります。 よって、Ａの位置には１１が入ります。

問１５ 業務の改善提案に対する賞金が、次の決定表で決められる。改善提案１と改善提案２に対する賞金の総額は何円か。 [改善提案] 改善提案１：改善額２０万円、期間短縮３日 改善提案２：改善額５万円、期間短縮２週間

ア １，０００ イ １，５００ ウ ２，０００ エ ３，５００

解答 ウ

解説 このような図を決定表（デジョンテーブル）といいます。当てはまるものをＹ（Ｙｅｓ）。当てはまらないものをＮ（Ｎｏ）としたときに、その列のＸがついているものとする（場合によっては、複数も可）ことで、状況の整理などをすることができます。 改善提案１は、改善額１０万円未満＝Ｎ。期間短縮１週間未満＝Ｙ。よって、左から３番目に該当し、賞金１０００円 改善提案２は、改善額１０万円未満＝Ｙ。期間短縮１週間未満＝Ｎ。よって、左から２番目に該当し、賞金１０００円 よって、１０００＋１０００で２０００円となります。

問１７ ４ビットの入力データに対し、１の入力数が０個又は偶数個のとき出力が１に、奇数個のとき出力が０になる回路はどれか。

解答 エ

解説 真理値表や、入力をすべて試すのもいいのですが、ここでは、論理的な手法で考えます。 ＥＸＯＲは、１が偶数個なら０、奇数個なら１を出力します。 よって、２ビットずつ区切ったときに、偶数＝０、奇数＝１が２つ出てきます。 これを２段目のＥＸＯＲで、偶数と偶数＝０，０＝０。偶数と奇数＝０、１＝１。奇数と偶数＝１、０＝１。奇数と奇数＝１、１＝０となります。 よって、これを反転することで、偶数時に１、奇数時に０を出力する回路となります。

問１９ キャッシュメモリのアクセス時間及びヒット率と、主記憶のアクセス時間の組合せのうち、主記憶の実効アクセス時間が最も短くなるのはどれか。

解答 エ

解説 すべてを計算してもよいのですが、今回はアクセス時間が同じでヒット率が低いという理由で、選択肢イとくらべて選択肢アを除外。選択肢エとくらべて選択肢ウを除外できます。よって、選択肢イと選択肢エだけを計算すれば十分です。 選択肢イ：１０×０．７＋７０×０．３＝７＋２１＝２８ 選択肢エ：２０×０．８＋５０×０．２＝１６＋１０＝２６ よって、２６ナノ秒で選択肢エが最も高速だといえます。

問２０ 主記憶装置の高速化の技法として、主記憶を幾つかのアクセス単位に分割し、各アクセス単位をできるだけ並行動作させることによって、実効アクセス時間を短縮する方法を何というか。

ア 仮想記憶 イ キャッシュメモリ方式 ウ ダイレクトメモリアクセス エ メモリインタリーブ

解答 エ

解説 メモリインタリーブとは、主記憶を複数の独立したグループに分けて、各グループに交互にアクセスすることによって、主記憶へのアクセスの高速化を図るものです。以下の例ではアクセス幅が１の場合は３語分、アクセス幅が２の場合は６語分に同時にアクセスできます。 仮想記憶は、実メモリが少ない場合に、ＨＤＤの一部を仮想的に主記憶のように見せかけて、大きなプログラムを動作させたりする技術です。 キャッシュメモリ方式は、ＣＰＵのレジスタと主記憶との差を埋めるために、キャッシュメモリというものをおき、同じデータにアクセスする際に高速化する手法です。、 ダイレクトメモリアクセス（ＤＭＡ）は、ＣＰＵを経由せずに、メモリとＩ／Ｏ間でデータを転送する方式をいいます。