ポインタを用いた線形リストの特徴のうち、適切なものはどれか。

選択肢

• ア先頭の要素を根としたn分木で、先頭以外の要素は全て先頭の要素の子である。
• イ配列を用いた場合と比較して、2分探索を効率的に行うことが可能である。
• ウポインタから次の要素を求めるためにハッシュ関数を用いる。
• エポインタによって指定されている要素の後ろに、新たな要素を追加する計算量は、要素の個数や位置によらず一定である。

正解と解説

正解：エ ポインタによって指定されている要素の後ろに、新たな要素を追加する計算量は、要素の個数や位置によらず一定である。

ポインタで連結された線形リストは、要素の追加・削除がポインタの張り替えだけで済む。挿入位置がポインタで指定されていれば、要素数や位置に関係なく一定の手間（計算量O(1)）で挿入できる。一方、任意の要素へアクセスするには先頭から順にたどる必要がある。

選択肢ごとの解説

• アn分木の説明であり、線形リストは各要素が次の要素を1つ指す一次元の並びである。
• イリストは添字による直接アクセスができないため、2分探索には配列のほうが向く。
• ウハッシュ関数を使うのはハッシュ表であり、リストは次要素のアドレスを直接保持する。
• エ正しい。ポインタの張り替えだけで挿入できるため、計算量は要素数によらず一定である。

同じ分野の他の問題

• 図の2分探索木に1と0の二つの要素を順に追加したAVL木として，適切なものはどれか。2025年度 春期 午前 問6
• A，B，Cの順序で入力されるデータがある。各データについてスタックへの挿入と取出しを1回ずつ行うことができる場合，データ…2016年度 春期 午前 問5
• 次の2分探索木から要素12を削除したとき、その位置に別の要素を移動するだけで2分探索木を再構成するには、削除された要素の…2024年度 秋期 午前 問5
• 各ノードがもつデータを出力する再帰処理f(ノードn)を定義した。この処理を、図の2分木の根(最上位のノード)から始めたと…2024年度 春期 午前 問6
• 双方向リストを三つの一次元配列elem[i]、next[i]、prev[i]の組で実現する。双方向リストが図の状態のとき…2023年度 秋期 午前 問5