平成26年度春季解答

問題6

従業員番号と氏名の対がn 件格納されている表に線形探索法を用いて、与えられた従業員番号から氏名を検索する。 この処理における平均比較回数を求める式はどれか。 ここで、検索する従業員番号はランダムに出現し、探索は常に表の先頭から行う。 また、与えられた従業員番号がこの表に存在しない確率をa とする。

解答：エ

＜解説＞

線形探索は、探索表の先頭から順に目的のデータが見つかるまで探索する方法である。

比較回数は次のようになる。

• 最大比較回数はn
• 平均比較回数は(n+1)÷2

この問題では「与えられた従業員番号がこの表に存在しない確率をa とする。」とある。表に検索対象が存在しない場合の比較回数は最大比較回数のnなので、比較回数の平均値は

平均比較回数×検索対象が存在する確率＋最大比較回数×検索対象が存在しない確率となる。

したがって、

{(n+1)/2}×(1-a)+n×1={n+1)(1/a)÷2}+naとなる。

したがって、エが正解である。

問題へ

問題7

プログラム言語におけるデータ型に関する記述のうち、適切なものはどれか。

ア	実数型は、有限長の2進数で表現され、数学での実数集合と一致する。
イ	整数型は、2の補数表示を使用すると8ビットでは－128～127が扱える。
ウ	文字型は、英文字と数字の集合を定めたものである。
エ	論理型は、AND、OR、NOTの三つの値をもつ。

解答：イ

＜解説＞

ア	×	有限長の2進数では、すべての実数を表現することはできない。
イ	○	整数型は、2の補数表示を使用すると8ビットでは－128～127が扱える。
ウ	×	文字型は、「!」や「?」などの記号も表現できる。
エ	×	論理型は、TrueとFalseの二つの値がある。

問題へ

問題8

100MIPSのCPUで動作するシステムにおいて、タイマ割込みが1ミリ秒ごとに発生し、タイマ割込み処理として1万命令が実行される。 この割込み処理以外のシステムの処理性能は、何MIPS相当になるか。 ここで、CPU稼働率は100%、割込み処理の呼出し及び復帰に伴うオーバヘッドは無視できるものとする。

ア	10
イ	90
ウ	99
エ	99.9

解答：イ

＜解説＞

1. CPU稼働率が100%のとき,100MIPSのCPUでは1秒間に100×100万命令=1億命令を実行できる
2. タイマ割り込みが1ミリ秒=O.OO1秒ごとに発生するので、1秒間のタイマ割込みの発生回数は1秒÷0.001秒=1,000回である
3. タイマ割込み処哩として1万命令が実行されるので1秒間のうちタイマ割込み処理は1,000回×1万命令=1,000万命令である
4. 1秒間に実行できるタイマ割込み処理以外の命令数は1億命令-1,000万命令=9,000万命令でである
5. 9,000万命令をMIPSで表現つると90MIPSになる
   

問題へ

問題9

メイン処理、及び表に示す二つの割込みA、Bの処理があり、多重割込みが許可されている。 割込みA、Bが図のタイミングで発生するとき、0ミリ秒から5ミリ秒までの間にメイン処理が利用できるCPU時間は何ミリ秒か。 ここで、割込み処理の呼出し及び復帰に伴うオーバヘッドは無視できるものとする。

ア	2
イ	2.5
ウ	3.5
エ	5

解答：ア

＜解説＞

メイン処理をMとした場合、次のようになる。

したがって、メイン処理が利用できる時間は2ミリ秒である。

問題へ

問題10

命令のアドレス部から実効アドレスを生成する方式のうち、絶対アドレス方式はどれか。

ア	基準アドレスとしてスタックポインタの値を用い、命令のアドレス部を基準アドレスからの変位として加算し、実効アドレスを生成する。
イ	基準アドレスとして命令アドレスレジスタの値を用い、命令のアドレス部を基準アドレスからの変位として加算し、実効アドレスを生成する。
ウ	命令のアドレス部で指定したメモリの内容を、実効アドレスとする。
エ	命令のアドレス部の値をそのまま実効アドレスとする。

解答：エ

＜解説＞

ア	×	スタックポインタはスタックの最上部のアドレスを示すレジスタである。
イ	×	相対アドレス方式である。相対アドレス方式は命令アドレスレジスタ(プログラムカウンタ)＋命令のアドレス部の値を実行アドレスとする。
ウ	×	間接アドレス方式である。間接アドレス方式は、命令のアドレス部の指定したメモリの内容を実行アドレスとする。
エ	○	絶対アドレス方式である。絶対アドレス方式は、命令のアドレス部をそのまま実行アドレスとする。

問題へ