令和2年度 10月 午前 問5

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

解説

指定要素の後ろへの挿入はポインタ 2 本の書き換えで済みます。

ポインタを使った線形リストは、各要素が次の要素を指すポインタを一つずつ持っている構造です。この構造の特徴を選ぶときは、要素の並びをどう変えるとき何本のポインタを書き換える必要があるかという一点で見分けます。ある要素の後ろに新しい要素を差し込む場面では、その要素が持っていた次を指すポインタを新しい要素に付け替え、新しい要素側には元々の次の要素を指すポインタを持たせるという、二本のポインタの書き換えだけで済みます。要素の総数がいくつであっても、また差し込む場所が先頭寄りでも末尾寄りでも、この二本という数は変わりません。ですから挿入の手数は要素の個数や位置に依らず一定であり、これが配列との得手不得手の分かれ目になります。

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

• ア先頭の要素を根とした n 分木で，先頭以…：先頭の要素を根とした n 分木で、先頭以外の要素は全て先頭の子だと書かれています。線形リストは各要素が次の一つを指すだけの一本道で、根の下に多数の枝が広がる木の構造ではありません。
• イ配列を用いた場合と比較して，2 分探索を…：配列と比べて 2 分探索を効率的に行えると書かれています。2 分探索は添字で真ん中の位置に一度で飛べる配列の得意技で、途中を飛ばして真ん中に届く手段のない一本道の構造には向きません。
• ウポインタから次の要素を求めるためにハッシ…：ポインタから次の要素を求めるためにハッシュ関数を用いると書かれています。ポインタは次の要素の在り処そのものを直接指す仕組みで、キーから位置を計算するハッシュ関数の働きとは別の仕掛けです。