データ構造 (全40問中7問目)
No.7
ポインタを用いた線形リストの特徴のうち，適切なものはどれか。
出典：令和2年秋期 問5
- 先頭の要素を根としたn分木で，先頭以外の要素は全て先頭の要素の子である。
- 配列を用いた場合と比較して，2分探索を効率的に行うことが可能である。
- ポインタから次の要素を求めるためにハッシュ関数を用いる。
- ポインタによって指定されている要素の後ろに，新たな要素を追加する計算量は，要素の個数や位置によらず一定である。
- [出題歴]
- 基本情報技術者 H27秋期 問5
分類
テクノロジ系 » アルゴリズムとプログラミング » データ構造
正解
エ
解説
線形リストとは、線形で表現されるリスト構造の総称で、一般的には隣接するデータ同士をポインタで連結して表現します。
- 木構造の説明です。線形リストではデータ同士に親子関係はありません。
- 線形リストは隣接する要素同士がポインタで接続されているため、データを先頭から順に探索していく線形探索に適しています。2分探索を行うのに適したデータ構造は要素が値の大小で整列されている2分探索木です。
- ポインタとは次の要素が格納されているメモリアドレスの情報です。次の要素を得るにはポインタが指し示すメモリ上のデータを読み込みます。
- 正しい。単方向リストの場合は新たな要素の追加は以下の手順で行われます。
- ポインタで指定された要素(以降、元要素)を取得する
- 元要素のポインタを新要素のポインタに付け替える
- 元要素のポインタが新要素を指し示すようにする