平成22年度秋季解答

問題6

探索表の構成法を例とともにa～cに示す。探索の平均計算量が最も小さい探索手法の組合せはどれか。ここで、探索表のコードの空欄は表の空きを示す。

解答：ア

＜解説＞

[a コード順に格納した探索表：2分探索]

2分探索は、予めソートされたデータ列を二つに分けて、そのどちらに検索対象が含まれているか判断するという手順を再帰的に繰り返していく検索方法。
⇒aは、 コード順に格納されているので、2分探索法が適している。

[b コードの使用頻度順に格納した探索表：線形探索]

線形探索は、対象データを検索範囲のデータと先頭から順に1つずつ比較し、一致するものを検索する方法。
⇒bは、使用頻度順にならんでいるので先頭から順番に検索すると早く見つけることができるので、線形探索が適している。

[c コードから一意に決まる場所に格納した探索表：ハッシュ探索]

ハッシュ探索は、キーの値を基に格納先（記録媒体上）のアドレスを算出し、そのアドレス位置にあるデータを検索する方法。
⇒cは、コードから格納場所を探索するのでハッシュ探索が適している。

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

問題へ

問題7

正の整数Mに対して、次の二つの流れ図に示すアルゴリズムを実行したとき、結果xの値が等しくなるようにしたい。aに入れる条件として、適切なものはどれか。

ア	n＜M
イ	n＞M-1
ウ	n＞M
エ	n＞M+1

解答：ウ

＜解説＞

1. M＝5として左の流れ図をトレースする。
   
2. M＝5として右の流れ図をトレースする。
   
3. nが1～5のとき実行されるようにすればよいので、n＞Mとなる。

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

問題へ

問題8

再入可能（リエントラント）プログラムに関する記述のうち、適切なものはどれか。

ア	再入可能プログラムは、逐次再使用可能プログラムから呼び出すことはできない。
イ	再入可能プログラムは、呼出し元ごとに確保された記憶領域に局所変数が割り当てられる。
ウ	実行途中で待ち状態が発生するプログラムは、再入可能プログラムではない。
エ	逐次再使用可能なプログラムは、再入可能プログラムでもある。

解答：イ

＜解説＞

リエントラント（再入可能）は、あるプログラムが呼び出したプログラムを、他のプログラムがさらに呼び出しを行い、同時に実行できるプログラムのことである。同時，非同期的に呼び出されても互いに干渉せずに動作できる性質をもつ。

ア	×	再入可能プログラムは、逐次再使用可能プログラムから呼び出すことは可能である。
イ	○	再入可能プログラムでは、局所変数はタスクごとに独立して持つ必要がある。
ウ	×	タスクは実行状態，実行可能状態，待ち状態の間を遷移するが、これはプログラムの性質とは別のものである。
エ	×	逐次再使用可能なプログラムは、複数のタスクから呼び出された場合の動作は保証していないので再入可能プログラムではない。

問題へ

問題9

動作クロック周波数が700MHzのCPUで、命令の実行に必要なクロック数及びその命令の出現率が表に示す値である場合、このCPUの性能は約何MIPSか。

ア	10
イ	50
ウ	70
エ	100

解答：エ

＜解説＞

1. 1命令の実行に必要な平均クロック数を計算する。
   4×0.3＋8×0.6＋10×0.1 ＝7クロック
2. 1秒間の命令実行可能回数を計算する。
   ※CPUの動作クロック数が 700MHz＝700 × 10⁶，1命令の実行に必要な平均クロック数は7クロックである。
   700 × 10⁶ ÷ 7 = 100 × 10⁶＝100MIPS

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

問題へ

問題10

スーパスカラの説明はどれか。

ア	処理すべきベクトルの長さがベクトルレジスタより長い場合、ベクトルレジスタ長の組に分割して処理を繰り返す方式である。
イ	パイプラインを更に細分化することによって、高速化を図る方式である。
ウ	複数のパイプラインを用い、同時に複数の命令を実行可能にすることによって、高速化を図る方式である。
エ	命令語を長く取り、一つの命令で複数の機能ユニットを同時に制御することによって、高速化を図る方法である。

解答：ウ

＜解説＞

スーパスカラとは、プロセッサの中に複数の処理系統(パイプライン)を用意し、複数の命令を並列に処理することである。

ア	×	ベクトルプロセッサに関する説明である。
イ	×	スーパパイプラインに関する説明である。
ウ	○	スーパスカラに関する説明である。
エ	×	VLIW(Very Long Instruction Word：超長命令語)に関する説明である。

問題へ