平成21年12月20日に行われた基本情報技術者の午前免除試験の問題を紹介します。
問1 次の10進小数のうち，8進数に変換したときに有限小数になるものはどれか。
ア 0.3
イ 0.4
ウ 0.5
エ 0.8
答え
ウ
解説
10進数の0.5は，2進数で有限小数なので8進数でも有限。実際，0.5(10進数)=0.1(2進数)=0.4(8進数)。
問2 最上位をパリティビットとする8ビット符号において，パリティビット以外の下位7ビットを得るためのビット演算はどれか。
ア 16進数0FとのANDをとる。
イ 16進数0FとのORをとる。
ウ 16進数7FとのANDをとる。
エ 16進数FFとのXOR(排他的論理和)をとる。
答え
ウ
解説
1ビットの数字について，0とANDを取れば0になり1と0とANDを取れば元の数となる。よって取り出したい桁を1それ以外を0としたパターン7FとANDを取れば最上位ビットが0となり，下位7ビットがそのまま取り出せる。
問3 ワープロソフト，表計算ソフト，データベースソフトが使える人数を調査して図1のように図示した。これにプレゼンテーションソフトが使える人数の調査結果を加えて，図2のように図示しようとしたところ，うまくいかないことがわかった。図2において表されていないケースはどれか。回答軍ではワープロソフト，表計算ソフト，データベースソフト，プレゼンテーションソフトをそれぞれW, H, D, Pで表し，○は使えることを，×は使えないことを示している。
答え
ウ
解説
ベン図は集合の交わりや和を表示するのに便利であるが，集合が三つよりおおくなると上手く描けない。実際，図1では(描かれていない外側を含め)全体集合を8個の部分に分けている。三つの集合に含まれる・含まれないの組合せは8通りでありこれで十分である。しかし四つの集合に含まれる・含まれないの組合せは16通りであり，図2は(描かれていない外側を含め)全体集合を14個の部分に分けており，これでは不足する。つまり描かれていない集合が存在する。ウの部分を探すとW○H×D○の箇所がすべてPに含まれているので存在しないことが分かる。
問4 関数eq(X,Y)は，引数XとYの値が等しければ1を返し，異なれば0を返す。整数A,B,Cについて，eq(eq(A,B), eq(B,C))を呼び出したとき，1が返ってくるための必要十分条件はどれか。
ア (A=BかつB=C)又は(A≠BかつB≠C)
イ (A=BかつB=C)又は(A≠B又はB≠C)
ウ (A=BかつB=C)又はA=C
エ (A=B又はB=C)又はA=C
答え
ア
解説
外側のeqの二つの引数がどちらも1またはどちらも0のとき1を返す。
問5 すべての葉が同じ深さをもち，葉以外のすべての節点が二つの子をもつ2分木に関して，節点数と深さの関係を表す式はどれか。ここで，nは節点数，kは根から葉までの深さを表す。例に示す2分木の深さkは2である。
答え
イ
解説
正確に憶えていなくても，2のベキ乗が使われることを憶えていれば，アかイが選べる。k=2のときどちらも7であるが，k=3で確かめるとイ。
問6 B木に関する記述として，適切なものはどれか。
ア 階層の深さが同じになるように，ノードの分割と併合を行う。
イ キー値からある関数によって，データの格納位置を求める。
ウ 先頭データからの順次アクセスだけが可能である。
エ 登録簿とメンバに分かれ，メンバは順編成ファイルである。
答え
ア
問7 6個の数値180, 315, 282, 410, 645, 525を並べ替える。手順1～4は途中までの手順を示したものである。手順4まで終わったときの結果はどれか。
手順1 並びの左から順に，数値の1の位の値によって0～9のグループに分ける。
手順2 次に0のグループの数値を左側から順に取り出して並べ，その右側に1のグループ，以下順に2～9のグループの数値を並べていく。
手順3 手順2で得られた数値の並びの左側から順に，数値の10の位によって0～9のグループに分ける。
手順4 手順2と同様に，0のグループの数値から順に並べる。
ここで，グループ内では，処理が行われた数値を左側から順に並べるものとする。
ア 180, 282, 315, 410, 525, 645
イ 315, 410, 525, 180, 282, 645
ウ 410, 315, 525, 645, 180, 282
エ 645, 525, 410, 315, 282, 180
答え
ウ
解説
初期状態: 180, 315, 282, 410, 645, 525
手順2の後: 180, 410, 282, 315, 645, 525
手順4の後: 410, 315, 525, 645, 180, 282
問8 次の関数f(n, k)がある。f(4,2)の値は幾らか。
f(n,k)=
1(k=0),
f(n-1,k-1)+f(n-1,k) f(n-1,k-1)+f(n-1,k) (0<k<n),
1(k=n)
答え
エ
解説
f(4,2)=f(3,1)+f(3,2)
=(f(2,0)+f(2,1))+(f(2,1)+f(2,2))
=1+2 f(2,1)+1
=1+2 (f(1,0)+f(1,1))+1
=1+2 (1+1)+1
=6
