平成21年度春季解答

問題6

自然数をキーとするデータを、ハッシュ表を用いて管理する。キーxのハッシュ関数h(x)を

h(x)=x mod n

とすると、キーaとbが衝突する条件はどれか。ここで、nはハッシュ表の大きさであり、x mod nはxをnで割った余りを表す。

ア	a+bがnの倍数
イ	a-bがnの倍数
ウ	nがa+bの倍数
エ	nがa-bの倍数

解答：イ

＜解説＞

下図より、キーaとbが衝突する条件は(イ)a-bがnの倍数である。

問題へ

問題7

文字列を引数とする関数len、first、butfirstを用いて、関数compを再帰的に定義した。comp(“11",“101")を呼び出したとき、返されるものはどれか。

	[関数の定義]
	len(S)	：	文字列Sの長さを返す。Sが空文字列のときは0を返す。
	first(S)	：	文字列Sの先頭の1文字のASCIIコードを返す。 Sが空文字列のときはエラーを返す。
	butfirst(S)	：	文字列Sの先頭の1文字を除いた残りの文字列を返す。 Sが空文字列のときはエラーを返す。

comp(A，B)
begin
　　　　if　len(A)＝0 and len(B)＝0　then　return　0；
　　　　if　len(A)＝0 and len(B)≠0　then　return　1；
　　　　if　len(A)≠0 and len(B)＝0　then　return　-1；
　　　　if　first(A)＜first(B)　then　return　1；
　　　　if　first(A)＞first(B)　then　return　-1；
　　　　return　comp(butfirst(A)，butfirst(B))
end

解答：ア

＜解説＞

下図より、アが正解である。

問題へ

問題8

相異なるn 個のデータが昇順に整列された表がある。 この表をm 個のデータごとのブロックに分割し、各ブロックの最後尾のデータだけを線形探索することによって、目的のデータの存在するブロックを探し出す。 次に、当該ブロック内を線形探索して目的のデータを探し出す。 このときの平均比較回数を表す式はどれか。 ここで、m は十分大きく、n はm の倍数とし、目的のデータは必ず表の中に存在するものとする。

解答：イ

＜解説＞

1. ブロックは全部で、

   n

   m

   個ある。
2. 線形探索の比較回数は、最小で1回，最大でデータの総和である。したがって、データの総数÷2で目的のデータを見つけることができる。したがって、平均比較回数は、

   n

   2m

   となる。
3. ブロックの中身の検索を行う。個々のブロックはm個なので、

   n

   2

   となる。
4. したがって、

   n	＋	n
   2m		2

   となる。

問題へ

問題9

複数のデータに対して、1個の命令で同一の操作を同時並列に行う方式で、マルチメディアデータなどを扱うCPUに採用されているものはどれか。

ア	MIMD
イ	MISD
ウ	SIMD
エ	SISD

解答：ウ

＜解説＞

ア	×	MIMD(Multiple Instruction stream Multiple Data stream)は、複数の命令（Multiple Instruction）で複数のデータ(Multiple Data)を処理する方式である。
イ	×	MISD(Multiple Instruction Single Data)は、複数の命令（Multiple Instruction）で一つのデータ(Single Data)をを処理する方式である。
ウ	○	SIMD(Single Instruction Multiple Data)は、一つの命令（Single Instruction）で複数のデータ(Multiple Data)を処理する方式である。
エ	×	SISD(Single Instruction Single Data)は、一つの命令（Single Instruction）で一つのデータ(Single Data)を処理する方式である。

問題へ

問題10

外部割込みの要因となるものはどれか。

ア	仮想記憶管理における存在しないページにアクセスしたときのページフォールト
イ	システム管理命令を一般ユーザモードで実行したときの特権命令違反
ウ	ハードウェア異常などによるマシンチェック
エ	浮動小数点演算命令でのオーバフローなどの演算例外

解答：ウ

＜解説＞

割込みとは、プログラムを実行中に、優先度や緊急度が高い事象（イベント）が発生したのを受けて、プログラム実行を停止させて対応処理を行なう仕組みをいう。

割込みには、内部割込みと外部割込みがある。

内部割込みの要因には、次のものがある。

• 存在しないページへのアクセス（ページフォルト）
• オーバフロー，アンダーフロー
• 0による除算
• ユーザモードでの特権命令での実行（スーパーバイザコール呼出し）

外部割込みの要因には、次のものがある。

• ハードウェアや電源の異常
• 入出力装置の終了
• タイマ通知

ア	×	内部割込みの要因である。
イ	×	内部割込みの要因である。
ウ	○	外部割込みの要因である。
エ	×	内部割込みの要因である。

問題へ