基本情報技術者試験「連結リスト」の問題
単方向連結リストと比べた双方向連結リストの利点として最も適切なものはどれか。
ア各ノードが前後両方のポインタを持つため、ある要素から直前の要素へ直接たどれる
イノードあたりのポインタ領域が減るため、同じ要素数を格納しても全体の消費メモリが単方向より明確に小さく済む
ウ添字計算によって任意位置の要素へ定数時間でランダムアクセスできる
エ要素を常に整列済みの状態に自動で保ち、探索が二分探索並みになる
正解
ア．各ノードが前後両方のポインタを持つため、ある要素から直前の要素へ直接たどれる
双方向連結リストは各ノードが次と前の2つのポインタを持つ。これにより単方向では不可能な直前要素への直接移動ができ、逆方向走査や末尾近くの削除が容易になるため正しい。
?選択肢ごとの解説
ア ○双方向連結リストは各ノードが次と前の2つのポインタを持つ。これにより単方向では不可能な直前要素への直接移動ができ、逆方向走査や末尾近くの削除が容易になるため正しい。
イ ×ポインタが前後2本に増えるため、双方向のほうがノードあたりのメモリは単方向より大きくなり、消費が小さくなるという説明は逆である。
ウ ×添字計算による定数時間ランダムアクセスは配列の特徴であり、連結リストは先頭から順にたどるため双方向でも任意位置アクセスはO(n)である。
エ ×連結リストは自動で整列を保つ構造ではなく、二分探索もできない。整列維持は別途挿入位置探索が必要で、構造の性質ではない。
✎くわしく
連結リストはポインタで要素をつなぐ構造で、単方向は次のみ、双方向は前後を指す。双方向は逆走査と任意ノードの削除(直前を知る必要がない)が容易になる代わりにポインタ領域が増える。トレードオフを理解することが核心である。
✓本番での押さえどころ
試験のコツ
『双方向=前後にたどれる代わりにポインタ1本分メモリ増』とトレードオフをセットで覚える。ランダムアクセスは配列の特権と区別する。
覚え方
双方向は『行きも帰りもできる二車線道路』、ただし道幅(メモリ)は広く要る、とイメージする。
よくある誤り
連結リストに配列の特徴(ランダムアクセス)を当てはめたり、双方向化でメモリが減ると誤解する例が多い。
アルゴリズムとプログラミングの他の問題
次の擬似言語で表される手続 sumOdd を、引数として要素数 5 の整数型の配列 {12, 125, 1008,…次の擬似言語は、整数型の配列 arr に対して隣接交換を行う手続の一部であり、外側ループの 1 回目（1…次の擬似言語は昇順に整列された配列 arr に対する二分探索の手続である。arr = {2, 4, 6, 8, 10,…次の擬似言語で表される再帰手続 f を、引数 n = 20 で呼び出したとき、戻り値として返される値はどれか。
```…単方向連結リストの各ノードはメンバ val（整数）と next（次ノードへの参照。なければ NULL）をもつ。先頭ノード…スタックに対する push（積む）と…
この問題を、AIの8-ways解説つきで。
無料ではじめる →基本情報技術者試験の演習を、一問ごとに「なぜ」まで。まずは無料で。
ukamiru 過去問 · 基本情報技術者試験 · fe-a3-0121