アルゴリズムとプログラミング
基本情報技術者試験｜単方向連結リストと比べた双方向連結リストの利点
単方向連結リストと比べた双方向連結リストの利点として最も適切なものはどれか。
ア各ノードが前後両方のポインタを持つため、ある要素から直前の要素へ直接たどれる
イノードあたりのポインタ領域が減るため、同じ要素数を格納しても全体の消費メモリが単方向より明確に小さく済む
ウ添字計算によって任意位置の要素へ定数時間でランダムアクセスできる
エ要素を常に整列済みの状態に自動で保ち、探索が二分探索並みになる
正解
ア．各ノードが前後両方のポインタを持つため、ある要素から直前の要素へ直接たどれる
双方向連結リストは各ノードが次と前の2つのポインタを持つ。これにより単方向では不可能な直前要素への直接移動ができ、逆方向走査や末尾近くの削除が容易になるため正しい。
?選択肢ごとの解説
ア ○双方向連結リストは各ノードが次と前の2つのポインタを持つ。これにより単方向では不可能な直前要素への直接移動ができ、逆方向走査や末尾近くの削除が容易になるため正しい。
イ ×ポインタが前後2本に増えるため、双方向のほうがノードあたりのメモリは単方向より大きくなり、消費が小さくなるという説明は逆である。
ウ ×添字計算による定数時間ランダムアクセスは配列の特徴であり、連結リストは先頭から順にたどるため双方向でも任意位置アクセスはO(n)である。
エ ×連結リストは自動で整列を保つ構造ではなく、二分探索もできない。整列維持は別途挿入位置探索が必要で、構造の性質ではない。
アルゴリズムとプログラミングの他の問題
単方向連結リストの各ノードはメンバ val（整数）と next（次ノードへの参照。なければ NULL）をもつ。先頭ノード…単方向連結リスト head→[10]→[20]→[30]→NULL がある。各ノードは val と next…単方向連結リストの各ノードはメンバ val（整数）と next（次ノードへの参照。なければ…単方向連結リストの各ノードは val（整数）と next（参照、なければ NULL）をもつ。次の擬似言語は、値…単方向連結リストの各ノードは val と next（参照、末尾は NULL）をもつ。次の擬似言語は、リスト a…単方向連結リストの各ノードは val と next（参照、末尾は NULL）をもつ。次の擬似言語は、low を 1…循環連結リスト(環状リスト)の特徴として最も適切なものはどれか。後入れ先出し(LIFO)のデータ構造が処理の仕組みとして最も自然に当てはまる場面はどれか。
この問題の「深掘り・誤答の完全解説・覚え方」は、登録すると読めます。
基本情報技術者試験は全4,036問。公開しているのはその一部で、登録すると残りも一問ごとにAI解説つきで解けます。SRS暗記カード・全真模試・弱点診断まで。
登録は1分・クレジットカード不要。無料のまま練習・暗記カード・模試まで使えます。
作成・校閲：ukamiru編集部 · 基本情報技術者試験 過去問 · fe-a3-0121