平成21年度春季解答

問題6

配列と比較した場合の連結リストの特徴に関する記述として，適切なものはどれか。

ア	要素を更新する場合，ポインタを順番にたどるだけなので，処理時間は短い。
イ	要素を削除する場合，削除した要素から後ろにあるすべての要素を前に移動するので，処理時間は長い。
ウ	要素を参照する場合，ランダムにアクセスできるので，処理時間は短い。
エ	要素を挿入する場合，数個のポインタを書き換えるだけなので，処理時間は短い。

解答：エ

＜解説＞

ア	×	要素を更新する場合，ポインタを順番にたどる分だけ，処理時間は長い。
イ	×	要素を削除する場合，削除した要素から後ろにあるすべての要素を前に移動するのは、配列の特徴である。連結リストでは、ポインタの更新だけでよい。
ウ	×	要素を参照する場合，ランダムにアクセスするのは配列の特徴である。連結リストではポインタを順番にたどる必要がある。
エ	○	要素を挿入する場合，数個のポインタを書き換えるだけなので，処理時間は短い。

問題へ

問題7

昇順に整列された n 個のデータが配列に格納されている。探索したい値を2分探索法で探索するときの，およその比較回数を求める式はどれか。

ア	log2n
イ	(log2n+1)/2
ウ	n
エ	n2

解答：ア

＜解説＞

2分探索法は，整列済みの配列から効率よくデータを探索するための方法である。

2分探索法は、整列されたデータの中央の値と対象データを比較し、それより前方にあるか後方にあるかを判断する。
前方にデータがある場合は、前半分のデータの中央のデータと比較し、後方にデータがある場合は、後半分のデータの中央のデータと比較する。
この操作を繰り返すことによって、検索する方法である。
要素数がn個の場合に2分探索法を使った場合の比較回数は，次の式で求めることができる。

	平均比較回数	：	(log2 n)回
	最大比較回数	：	(log2 n)＋1回

よってアが正解である。

問題へ

問題8

自然数 n に対して，次のように再帰的に定義される関数 f (n)を考える。 f (5) の値はどれか。
f (n)：if　n ≦1　then　return　1　else　return　n + f (n - 1)

ア	6
イ	9
ウ	15
エ	25

解答：ウ

＜解説＞

f (5)	＝	5＋f (4)
	＝	5＋4+f (3)
	＝	5＋4+3+f (2)
	＝	5＋4+3+2+f (1)
	＝	5＋4+3+2+1
	＝	15

問題へ

問題9

平均命令実行時間が 20 ナノ秒のコンピュータがある。このコンピュータの性能は何MIPS か。

ア	5
イ	10
ウ	20
エ	50

解答：エ

＜解説＞

ナノ秒	：	10-9秒
MIPS	：	10-6命令/秒

1秒当たりの命令実行回数	＝	1秒÷平均命令実行時間
	＝	1秒÷（20ナノ秒／命令）
	＝	1秒÷（20×10－9秒／命令）
	＝	1000÷（20×10－6）
	＝	50×106命令
	＝	50MIPS

問題へ

問題10

シングルチップマイコンの特徴として，最も適切なものはどれか。

ア	PC のメイン CPU に適している。
イ	ROM は内蔵されているが，RAM は内蔵されていない。
ウ	高速処理システム又は大規模なシステムに適している。
エ	入出力機能が内蔵されている。

解答：エ

＜解説＞

シングルチップマイコン(ワンチップマイコン)とは，CPUに加えて，主記憶を構成するROM，RAMに加え，タイマや入出力機能などを一つのLSIに統合したものである。主に組込みシステムに用いられる。

ア	×	PCに使われるCPUは通常はROM,RAMが別々になっている。
イ	×	ROM，RAM は内蔵されている。
ウ	×	組込みシステムに適している。
エ	○	入出力機能が内蔵されている。

問題へ