配列と連結リストは、どちらも「データを一列に並べる」ための道具ですが、得意技はほぼ正反対です。速く読み出したいのか、途中に差し込みたいのか——目的が変われば選ぶべき構造も変わります。基本情報技術者 データ構造「配列・連結リスト・スタック・キュー・木構造・ハッシュ法」の練習問題8問で、その選び分けを確かめましょう。
アクセスか挿入か — データ構造は「得意な操作」で選ぶ
用語を暗記する前に、「どの操作が速く、どの操作が遅いか」を一枚の表で見比べておくと、設問の選択肢のねらいが読めるようになります。計算量は、データ量 n が増えたときに手間がどれだけ増えるかの目安です。
| データ構造 | 速い操作 | 遅い操作 | 代表的な使いどころ |
|---|---|---|---|
| 配列 | 添字アクセス O(1) | 途中挿入・削除 O(n) | 順番に大量アクセス |
| 連結リスト | 途中挿入・削除 O(1) （位置が分かる場合） |
添字アクセス O(n) | 要素の出入りが多い列 |
| スタック | push / pop O(1) | 途中の参照 | 関数呼び出し・後戻り |
| キュー | enqueue / dequeue O(1) | 途中の参照 | 順番待ち・ジョブ管理 |
| 二分探索木 | 探索・挿入 平均 O(log n) | 偏ると最悪 O(n) | 大小で絞り込む検索 |
| ハッシュ表 | 探索・挿入 平均 O(1) | 衝突多発で悪化 | キーから一発引き |
・配列と連結リストの強みを逆に覚える … 配列は「読み出しが速い」、連結リストは「差し込みが速い」。
・スタックとキューの向き … スタックは LIFO（後入れ先出し）、キューは FIFO（先入れ先出し）。
・二分探索木の計算量 … 偏った木では平均 O(log n) が最悪 O(n) まで落ちる。
・ハッシュの衝突 … 別のキーが同じ値になる衝突は起こり得るもので、チェイン法などで受け止める。
選び分けのコツは、「何をいちばん速くしたいか」を先に決めることです。読み出し中心なら配列、出入りが多いなら連結リスト、出し入れの順序が決め手ならスタックかキュー、キーから素早く引きたいならハッシュ表、大小で絞るなら二分探索木——この対応を頭に置いて、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 の二分探索木は大小関係で値を探す用途で順番待ちには向かないため、いずれも誤りです。
試験全体の流れを俯瞰したい時は、基本情報技術者 試験全体概要 に戻れます。
学習の全体像と次に進む分野は、基本情報技術者 学習ロードマップ で確認できます。