ポインタを用いた線形リストの特徴のうち、適切なものはどれか。
ア | 先頭の要素を根としたn 分木で、先頭以外の要素は全て先頭の要素の子である。 |
イ | 配列を用いた場合と比較して、2分探索を効率的に行うことが可能である。 |
ウ | ポインタから次の要素を求めるためにハッシュ関数を用いる。 |
エ | ポインタによって指定されている要素の後ろに、新たな要素を追加する計算量は、要素の個数や位置によらず一定である。 |
答え エ
【解説】
線形リスト(連結リスト)では、リストの要素は次の要素の位置をポインタで持っているため、ポインタによって指定されている要素の後ろに要素を追加するときの計算量は、ポインタによって指定されている要素が差しているポインタを追加する要素のポインタにコピーし、自身のポインタは追加する要素の位置に書き換えることで行え、この処理の内容は追加する要素の個数や位置によらず一定になります。
【キーワード】
・連結リスト