読者です 読者をやめる 読者になる 読者になる

Compte-rendu de l'étude

年間目標の進捗記録用ブログ。

05-002...線形リストとデータ構造

問題

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

 

ア.先頭の要素を根としたn分木で、先頭以外の要素は全て先頭の要素の子である。

イ.配列を用いた場合と比較して、2分探索を効率的に行うことが可能である。

ウ.ポインタから次の要素を求めるためにハッシュ関数を用いる。

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

 (平成27年度秋、午前問題、問5)

解説

線形リストとは、データ構造のひとつ。

 

データ構造とは、データの集まりを効率よく使用するにはどのように格納すべきか? という手法のいろいろ。他には配列や木構造などがあり、手法それぞれに用途に合わせた得手不得手がある。

 

線形リストは、セル(cell)を直列に繋いで作る。このセルには「データを格納する」場所と「次のセルを指し示す」場所(ポインタ)とを含んでいる。

 

 どうもこれのイメージ

ブルボン キュービィロップ 112g×10個

ブルボン キュービィロップ 112g×10個

 

 

 

さて、線形リストに新しい要素を追加するには、

  1. 新しい要素のポインタに前の要素のポインタの内容を設定
  2. 前の要素のポインタに新しい要素のアドレスを設定

すればよく、要素の個数や位置に関係なく一定の計算量を得ることが出来る。

 

 その他の選択肢

ア.は木構造に関する説明であり、リストにはこのような枝分かれはない。

 

イ.の2分探索とは探索アルゴリズムの一つで、「全体の真ん中を調べて、ハズレなら左右を比較してまたその真ん中を調べて・・・」と繰り返す探索方法なので、先頭からポインタで辿る線形リストには向いていない。配列の方が効率的。

 

ウ.ハッシュ関数とは・・・

あるデータが与えられた場合にそのデータを代表する数値を得る操作、

>または、その様な数値を得るための関数のこと

ハッシュ関数 - Wikipedia

なんとなく分かるような気もするけど説明出来ず。

ハッシュドポテトとかハッシュドビーフの【hash】細切れ(にする)。なるほど?

とりあえず、線形リストではポインタに次の要素のアドレスが書いてあるので他に何か使う必要はない。

 

 

雑感

どこまで詳しく調べるか区切りを決めないと

果てなきWikipediaツアーが始まってしまうことに気づく・・・。

1問あたり30分以内にしよう。