平成27年度 秋期 午前 問5

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

解説

指している要素の後ろへの追加は、一定の手間で済みます。

ポインタを用いた線形リストは、要素どうしが次の要素の場所を指し合う形でつながっています。ですから途中に新しい要素を差し込むときは、指し先を2か所つなぎ替えるだけで済みます。並びの先頭から数えて何番目かということも、全体でいくつあるかということも、この作業の手間には関わりません。ここが配列との一番の違いです。見分ける軸は2つです。1つ目は、その記述が並びの形そのものを言い換えているのか、それとも操作にかかる手間を述べているのか。2つ目は、目的の要素へたどり着く方法が、先頭から順にたどる形になっているかどうかです。順にたどるしかない構造では、真ん中を直接指す前提の探し方は活かせません。

ほかの選択肢はなぜ違うのか

• ア先頭の要素を根とした n 分木で，先頭以…：先頭以外のすべてが先頭につながる形は、枝分かれのある木の姿であって、要素が一列に連なる姿とは違います。ここでの並びは前の要素が次だけを指す一本道です。
• イ配列を用いた場合と比較して，2分探索を効…：真ん中の要素を一足飛びに参照できないと、範囲を半分ずつ狭める探し方は活きません。添字で直接指せる形と比べると、たどる手間のぶんだけ不利になります。
• ウポインタから次の要素を求めるためにハッシ…：次の要素の位置は、値から計算して求めるのではなく、要素自身が保持しています。関数で置き場所を算出する仕組みは、別のデータ構造が使う考え方です。