応用情報技術者試験 午前「基礎理論・アルゴリズム」の練習問題10問です。基数変換と補数、情報量とエントロピー、浮動小数点の誤差、計算量（オーダ記法）、整列・探索アルゴリズム、スタックとキュー、2分探索木、ハッシュ法、確率と期待値、標準偏差など、応用情報レベルで問われやすいテーマを集めました。
計算量が読めれば、アルゴリズムの選び方が決まる
2進数・情報量・計算量——基礎理論とアルゴリズムは、数の性質から筋道立てて導ける分野です。8ビットの2の補数で表せる範囲は－128〜＋127、探索や整列の速さは要素数nに対する計算量で比べる、という具合に、丸暗記でなく仕組みで攻められます。土台になるのは「どれくらいの手間がかかるか」という計算量の感覚です。
アルゴリズムは、目的から選び方をたどれます。まず「並べ替えたいのか、探したいのか」。探索なら、整列済みのデータは二分探索（計算量はlog n）、未整列は線形探索（n）、高速な出し入れが要るならハッシュ法（平均で一定時間）。整列なら、実装のしやすさ重視で選択・挿入・バブルソート（いずれも最悪n²）、速さ重視でクイックソート・マージソート（平均n log n）。データ構造も同じで、後入れ先出しならスタック、先入れ先出しならキュー、大小関係で探すなら2分探索木、と用途から一意に決まります。
・2の補数 … 各ビットを反転して1を足す、の順序を逆にしない。
・浮動小数点の誤差 … 有限桁で表せない小数を丸めることで生じる。桁数を増やしても完全には消えない。
・計算量の比較 … n²とn log nは、nが大きいほど差が開く。小さいnでの逆転に惑わされない。
用語の暗記でなく「どれくらいの速さか」を意識しておくと、後の機械学習やデータベースの分野の理解にもつながります。まずは10問。数の扱いとアルゴリズムの選び方を、手を動かして確かめてみてください。手が止まった設問は、解説内のリンクから該当テーマの記事に戻れます。
Q1. 8ビットで負の整数を表す2の補数表現に関する説明として、もっとも適切なものはどれですか？
回答
解説
正解は「C」です。
2の補数は「各ビットを反転（1の補数を作る）したうえで1を加える」ことで求めます。これにより減算を加算で処理でき、回路が簡潔になります。8ビットの2の補数表現で表せる整数の範囲は -128 から +127 までの256通りで、正の0と負の0が分かれないため0の表現が1通りに統一されるのが特徴です。
A は範囲を -255 から +255 とする誤り、B は「1を加える」操作を省いており1の補数の説明になっている誤り、D は2の補数では0が1通りに統一される点を取り違えた誤りで、いずれも適切ではありません。
Q2. 起こりやすさが異なる事象の情報量（自己情報量）に関する説明として、もっとも適切なものはどれですか？
回答
解説
正解は「A」です。
自己情報量は、生起確率 p の事象に対してビット単位で -log2(p) と定義されます。確率が小さい（めったに起こらない）事象ほど「起きたと分かったときの驚き」が大きく、情報量も大きくなります。たとえば生起確率が 1/2 の事象は1ビット、1/4 の事象は2ビットです。
B は確率に正比例するという誤り（実際は確率が大きいほど情報量は小さい）、C は確実に起こる事象の情報量は0ビットになるという点を取り違えた誤り、D は対数の底を変えると単位（ビット・ナットなど）と数値が変わる点を否定した誤りで、いずれも適切ではありません。
Q3. コンピュータの浮動小数点演算で生じる誤差に関する説明として、もっとも適切なものはどれですか？
回答
解説
正解は「D」です。
桁落ちは、大きさがほぼ等しい2つの数を減算したときに、有効数字の上位桁が打ち消し合い有効桁が大きく失われる現象です。情報落ちは、大きさが大きく異なる数を加減算したときに、小さいほうの数の下位桁が丸めで失われ結果に反映されにくくなる現象です。浮動小数点は有限ビットで実数を近似するため、こうした誤差が避けられません。
A は0.1などの10進小数が2進数では循環し正確に表せないため丸め誤差が生じる点を否定した誤り、B は桁落ちと情報落ちの名称が逆、C は現象名が誤り（オーバーフローは表現範囲を超える現象）で、いずれも適切ではありません。
Q4. 整列（ソート）アルゴリズムの平均・最悪計算量（時間計算量）に関する説明として、もっとも適切なものはどれですか？
回答
解説
正解は「B」です。
クイックソートは平均計算量が O(n log n) と高速ですが、ピボット（基準値）の選び方が偏ると分割がうまくいかず、最悪計算量は O(n^2) に悪化します。マージソートは分割と併合を再帰的に行うため、最悪の場合でも O(n log n) を保証できる点が長所です（一方で併合用の追加領域を必要とします）。
A はバブルソートの平均計算量が O(n^2) であり O(n log n) は誤り、C は選択ソート・挿入ソートの平均計算量が O(n^2) であり O(log n) は誤り、D はマージソートが追加領域を必要とし最悪計算量も O(n log n) である点を取り違えた誤りで、いずれも適切ではありません。
Q5. 探索アルゴリズムの計算量に関する説明として、もっとも適切なものはどれですか？
回答
解説
正解は「C」です。
2分探索は、あらかじめ昇順または降順に整列された配列に対して、中央の要素と目的の値を比較し探索範囲を毎回半分に狭めていく手法です。範囲が半分ずつ減るため、最悪計算量は O(log n) になります。一方の線形探索は未整列のデータにもそのまま使えますが、先頭から順に調べるため最悪計算量は O(n) です。
A は線形探索の最悪計算量が O(n) である点の誤り、B は2分探索が半分ずつ狭める点と計算量の表記の誤り、D は2分探索が整列済みデータを前提とする点を否定した誤りで、いずれも適切ではありません。
Q6. 基本的なデータ構造であるスタックとキューに関する説明として、もっとも適切なものはどれですか？
回答
解説
正解は「A」です。
スタックは、最後に入れたデータを最初に取り出す後入れ先出し（LIFO・Last In First Out）のデータ構造で、関数呼び出しの戻り先管理や式の評価などに使われます。キューは、最初に入れたデータを最初に取り出す先入れ先出し（FIFO・First In First Out）のデータ構造で、印刷ジョブの待ち行列やタスクの順番待ちなどに使われます。
B はスタックとキューの出し入れ順序が逆、C は両者とも出し入れの順序に制約があり任意位置の直接取り出しを前提としない点の誤り、D はスタックが関数呼び出しの戻り先管理に広く使われる点を否定した誤りで、いずれも適切ではありません。
Q7. 2分探索木（バイナリサーチツリー）に関する説明として、もっとも適切なものはどれですか？
回答
解説
正解は「D」です。
2分探索木は、任意のノードについて「左部分木に含まれる値がそのノードの値より小さく、右部分木に含まれる値が大きい」という大小関係を保つ木構造です。この性質により、根から比較して左右どちらへ進むかを選びながら探索でき、木が平衡している場合の探索計算量は O(log n) になります。通りがけ順（中間順）に走査すると値を昇順で取り出せます。
A は左右の大小関係が逆、B は挿入順序によっては木が一方向に偏り高さが O(n) に悪化しうる点を見落とした誤り、C は通りがけ順で昇順に取り出せる点を否定した誤りで、いずれも適切ではありません。
Q8. ハッシュ法（ハッシュ表）によるデータの格納・探索に関する説明として、もっとも適切なものはどれですか？
回答
解説
正解は「B」です。
ハッシュ法は、キーをハッシュ関数で格納位置（添字）に変換し、その位置に直接アクセスする手法です。衝突が少なければ平均して O(1) 程度で格納・探索ができます。異なるキーが同じ位置に割り当てられる衝突（コリジョン）は避けられないため、同じ位置の要素を連結リストでつなぐチェイン法や、空いている別の位置を探すオープンアドレス法などで対処します。
A は衝突が原理上起こらないとする誤り、C はハッシュ法を線形探索と同一視した誤り、D はハッシュ表が整列済みデータを前提とするという誤りで、いずれも適切ではありません。
Q9. 公正なサイコロ（1から6の目が等確率で出る）を1回振るときの出目の期待値として、もっとも適切なものはどれですか？
回答
解説
正解は「A」です。
期待値は「とりうる各値に、その値が起こる確率を掛けて合計したもの」です。公正なサイコロは1から6の目が等確率（各 1/6）で出るため、期待値は (1+2+3+4+5+6) × (1/6) = 21 / 6 = 3.5 となります。期待値は実際に出る目の1つと一致するとは限らない点に注意してください。
B は最大値を期待値とする誤り、C は最頻値（実際には全目が等確率）と取り違えた誤り、D は確率を掛けずに値を単純合計した誤りで、いずれも適切ではありません。
Q10. データのばらつきを表す分散・標準偏差に関する説明として、もっとも適切なものはどれですか？
回答
解説
正解は「C」です。
分散は、各データの偏差（データから平均を引いた値）を2乗して平均した値です。偏差をそのまま合計すると正負が打ち消し合って0になるため、2乗してばらつきの大きさを測ります。分散の正の平方根が標準偏差で、元のデータと同じ単位に戻るため平均値と並べて散らばり具合を解釈しやすくなります。値が大きいほどばらつきが大きいことを表します。
A は標準偏差を偏差の合計とする誤り（偏差の合計は0になる）、B は分散が2乗値の平均なので負にならない点を見落とした誤り、D は標準偏差が元データと同じ単位になる点を否定した誤りで、いずれも適切ではありません。
基礎理論やアルゴリズムの土台を確認したい時は、擬似言語とは や CPUとメモリの違いとは も参考になります。