教育統括部

いよいよ平成21年秋の情報処理技術者試験まで2週間です。

これからしばらく平成21年春の基本情報技術者試験午前問題を紹介しましょう。
直前の試験の問題そのものが出るとは考えにくいですが，ポイントの復習の意味でざっとみていきましょう。なお，答えと解説は白い字にしていますので，見たい方は選択するなどして見てください。


問1 数値を2進数で格納するレジスタがある。このレジスタに正の整数xを設定した後，“レジスタの値を2ビット左にシフトして，xを加える”操作を行うと，レジスタの値はxの何倍になるか。ここで，あふれ(オーバーフロー)は，発生しないものとする。

ア　3
イ　4
ウ　5
エ　6

答え ウ

解説 1ビット左シフトすると値は2倍になる。2ビットするとレジスタの値はxの4倍になり，それにxを加えるので，結局レジスタの値はxの5倍になる。



問2 0000～4999のアドレスをもつハッシュ表があり，レコードのキー値からアドレスに変換するアルゴリズムとして基数変換法を用いる。キー値が55550のときのアドレスはどれか。ここで，基数変換法とはキー値を11進数とみなし，10進数に変換した後，下4けたに対して0.5を乗じた結果(小数点以下は切捨て)をレコードのアドレスとする。

ア　0260
イ　2525
ウ　2775
エ　4405

答え　ア

解説　55550(16進数)=80520(10進数)。
よってアドレス値は0520×0.5=0260



問3 論理式not((not(A)+B) and (A or not(C)))と等しいものはどれか。

ア　A and not(B) or not(A) and C
イ　not(A) and B or A and not(C)
ウ　(A or not(B)) and (not(A) + C)
エ　(not(A) + B ) and (A or not(C))

答え　ア


解説
not((not(A)+B) and (A or not(C)))
= not((not(A)+B)) or not(A or not(C)) (ド・モルガン)
= not(not(A)) and not(B) or not(A) and not(not(C)) (ド・モルガン)
= A and not(B) or not(A) and C (二重否定)



問4 文字列中で同じ文字が繰り返される場合，繰り返し部分をその反復回数と文字の組に置き換えて文字列を短くする方法はどれか。

ア　EBCDIC符号
イ　巡回符号
ウ　ハフマン符号
エ　ランレングス符号化

答え　エ


解説　アは文字コード，イは誤り検出の符号，ウは符号長を短くする符号。



問5 関数や手続きを呼び出す際に，戻り番地や処理途中のデータを一時的に保存するのに適したデータ構造はどれか。

ア　二分探索木
イ　キュー
ウ　スタック
エ　双方向連結リスト

答え　ウ



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

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

答え　エ



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

ア　log2(n)
イ　(log2(n)+ 1)/2
ウ　n
エ　n^2

答え　ア


問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(1)=1
f(2)=2+f(1)=2+1=3
f(3)=3+f(2)=3+3=6
f(4)=4+f(3)=4+6=10
f(5)=5+f(4)=15
※計算途中に気づかれた方もいらっしゃると思われますが，f(n)は1からnまでの和です。