平成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の倍数

解答・解説へ

問題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 の倍数とし、目的のデータは必ず表の中に存在するものとする。

解答・解説へ

問題9

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

ア	MIMD
イ	MISD
ウ	SIMD
エ	SISD

解答・解説へ

問題10

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

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

解答・解説へ