基本情報技術者 データ構造「配列・連結リスト・スタック・キュー・木構造・ハッシュ法」の練習問題8問です。解けなかった問題は、各問の解説末尾のリンクから対応する解説記事に進んでください。
Q1. 配列と連結リストの違いとして、もっとも適切なものはどれですか？
回答
解説
正解は「B」です。
配列はメモリ上で要素が連続して並び、添字によるランダムアクセスを O(1) で行えます。一方の連結リストは各要素が次の要素へのポインタを持ち、ポインタの付け替えだけで途中挿入・削除を O(1) で行えるのが強みです。配列を「整然と並んだロッカー」、連結リストを「順番にチケットを渡していく行列」とイメージすると違いをつかみやすくなります。
A は配列と連結リストの強みが逆、C は計算量が同じではない、D は連結リストの要素がメモリ上で散らばってもポインタでつながる点を取り違えているため、いずれも誤りです。
Q2. スタックとキューの動作として、もっとも適切な組合せはどれですか？
回答
解説
正解は「D」です。
スタックは LIFO（Last In First Out）構造で、最後に入れたものを最初に取り出します。お皿を積み上げて上から取るイメージです。キューは FIFO（First In First Out）構造で、最初に入れたものを最初に取り出します。レジ待ちの行列が代表例です。スタックは関数呼び出しの管理（コールスタック）、キューはタスクや印刷ジョブの順番管理によく使われます。
A は LIFO と FIFO が入れ替わり、B は両方を FIFO とし、C は両者とも取り出し操作（pop / dequeue）を備える点を見落としているため、いずれも誤りです。
Q3. 二分探索木（Binary Search Tree）の性質として、もっとも適切なものはどれですか？
回答
解説
正解は「A」です。
二分探索木は、各ノードについて「左部分木の値 < 親 < 右部分木の値」という大小関係を保つ木構造です。この性質によって、根から比較を繰り返すだけで目的の値を素早く絞り込めます。バランスが取れた状態であれば探索・挿入・削除の計算量は平均 O(log n) となり、線形探索より速くなります。
B は大小関係こそが二分探索木の核なので誤り、C は最悪ケース限定の話で平均では O(log n) で動作するため誤りです。
Q4. ハッシュ法で異なるキーが同じハッシュ値になる衝突への対策「チェイン法」の説明として、もっとも適切なものはどれですか？
回答
解説
正解は「C」です。
チェイン法（連鎖法）は、ハッシュ表の各位置に連結リストを持たせ、同じハッシュ値になった要素をそのリストにつないで格納する方法です。衝突が起きてもリストを順にたどれば目的の要素にたどり着けます。実装がシンプルで、要素数がハッシュ表のサイズを超えても破綻しにくいのが強みです。
A は衝突のたびに作り直す方法は一般的な対策ではないため誤り、B は暗号化と衝突対策は別概念なので誤り、D は別方式（オープンアドレス法）の説明なので誤りです。
Q5. ヒープ（二分ヒープ）の性質として、もっとも適切なものはどれですか？
回答
解説
正解は「B」です。
ヒープは、親と子の間に大小の制約を持たせた木構造です。親が子より大きい「最大ヒープ」では根に最大値が来ます（最小ヒープなら根が最小値）。根の取り出しと再構成がともに O(log n) で行えるため、優先度付きキューの実装によく使われます。
A は左右の大小関係を定める二分探索木の説明なので誤り、C はキューなど線形構造の説明で木構造であるヒープとは異なるため誤りです。
Q6. 連結リストで、ある要素の直後に新しい要素を1つ挿入する操作の計算量として、もっとも適切なものはどれですか（挿入位置のポインタは分かっているものとする）？
回答
解説
正解は「A」です。
挿入位置のポインタが分かっている場合、連結リストへの要素挿入は、前後のポインタを付け替えるだけで完了します。要素数 n に関係なく一定回数の操作で済むため、計算量は O(1) です。配列の途中挿入では後続要素をずらす必要があり O(n) になるのと対照的です。
B の O(log n) は二分探索のような絞り込み、C の O(n²) は二重ループの処理を指し、いずれもポインタ付け替えだけのこの操作には当てはまらないため誤りです。
Q7. 配列で、添字を指定して要素を1つ読み出すアクセスの計算量として、もっとも適切なものはどれですか？
回答
解説
正解は「D」です。
配列はメモリ上で要素が連続して並ぶため、先頭アドレスと添字から目的の要素の位置を計算で直接求められます。要素数 n に関係なく一定時間でアクセスできるので、計算量は O(1) です。これが配列の最大の強みである「高速なランダムアクセス」です。
A の O(n) は連結リストのように先頭からたどる場合、C の O(log n) は二分探索、B の O(n²) は二重ループの計算量で、添字アクセスには当てはまらないため、いずれも誤りです。
Q8. 「データを入れた順に、先に入れたものから順番に処理したい」という要件に、もっとも適したデータ構造はどれですか？
回答
解説
正解は「C」です。
「先に入れたものから順番に処理する」のは FIFO（先入れ先出し）の動きそのものです。これを実現するデータ構造がキューで、印刷ジョブの順番待ちやタスクスケジューリングなどに使われます。データ構造は、求める出し入れの順序や操作の計算量に合わせて選ぶのが基本です。
A のスタックは LIFO（後入れ先出し）なので順序が逆、B の二分探索木は大小関係で値を探す用途で順番待ちには向かないため、いずれも誤りです。
試験全体の流れを俯瞰したい時は、基本情報技術者 試験全体概要 に戻れます。