１．データ構造とは
(1)データ構造プログラムによる処理においては、プログラムをどういう手順で実行するかという「アルゴリズム」と、データをどのように持つかという「データ構造」が重要です。
データ構造には、配列やリスト、スタック、キュー、木構造などがあります。
なんでそんなに種類があるのですか？
それぞれ特徴があるからです。データがもし書き込んだらそれでおしまいであれば、データ構造をあまり気にする必要はありません。しかし、データというのは追加したり変更したり削除したりします。
また、データベースなどの検索が重要な場合に、高速に検索できる仕組みが求められます。
そういう観点で、データ構造は重要なのです。
の上位から下位に節点をたどることによって,データを取り出すことができる構造である（H16春FE午前問43）」。
２．静的データ構造と動的データ構造
データの領域割り当てという観点でみると、データ構造は以下に分けられます。(1)静的データ構造
メモリ領域が、固定で割り当てられる。そして、プログラムが終了するとデータ領域が開放される。
①配列
たとえば、生徒の点数の結果だけを配列に入れます。
a(6)={21,5,53,71,3,17}
この配列を並べ替えたり、平均点を計算するなどのプログラムが考えられます。
データを1つずつ、
a1=21、a2=5、a3=53などと定義してもプログラムとしては処理ができますが、面倒ですよね。
②構造体
c言語の場合、structで定義されます。
構造体は、データ型などを自由に設定できます。たとえば、生徒の名前、学籍番号、英語の点数、国語の点数、などなど。それぞれ入力される値が数字（int）だったり日本語（char）だったり、いろいろです。それらを定義して、データベースのように扱うことができます。
(2)動的データ構造
データの都度、メモリ領域が変更される。
①リスト構造
・リスト構造は、データ部とポインタ部で構成される。ポインタ部にはアドレスが入る。
・過去問では、「データ部と一つのポインタ部で構成されるセルをたどることによって,データを取り出すことができる構造である（H16春FE午前問43）」
②木構造
・過去問では、「階層の上位から下位に節点をたどることによって,データを取り出すことができる構造である（H16春FE午前問43）」。
以下に少しだけ詳しく解説しています。
http://sm.seeeko.com/archives/15876927.html
■メモ過去問を例に
基本情報技術者試験の過去問（H23春FE午後問11）の「出題趣旨」でも「プログラムの作成において,データ構造は実行時の特性に大きな影響を及ぼすので,適切なデータ構造を選択することは重要である。」とあります。データ構造へのデータの格納および取り出しの順番として、FIFO（First In First Out）とLIFO（Last In First Out）があります。
キューのデータ構造では、FIFO
スタックのデータ構造では、LIFOが使われます。
過去問を基に整理します。
（１）スタック
「格納した順序とは逆の順序でデータを取り出すことができる構造である（H16春FE午前問43）」
（２）キュー
「格納した順序でデータを取り出すことができる構造である（H16春FE午前問43）。」
→スタックやキューは、配列やリスト構造を用いたもの。（静的データ構造、動的データ構造のどちらにもなりうる（らしい）） ★要調査
３．データ構造の過去問を解いてみよう
（１）H17秋FE午前
| 問13 データ構造に関する記述のうち,適切なものはどれか。 ア 2分木は,データ間の関係を階層的に表現する木構造の一種であり,すべての節が二つの子をもつデータ構造である。 イ スタックは,最初に格納したデータを最初に取り出す先入れ先出しのデータ構造である。 ウ 線形リストは,データ部と次のデータの格納先を指すポインタ部から構成されるデータ構造である。 エ 配列は,ポインタの付替えだけでデータの挿入・削除ができるデータ構造である。 |
↓
↓
↓
↓
【正解】ウ
（２）H19春AD午前問34
| 問34 データ構造の特徴のうち,適切なものはどれか。 ア 配列は,添字によってデータを任意の順序で読み出すことができる。 イ 配列を用いることによって,データ構造とアルゴリズムを独立させることができる。 ウ リストは,添字によってデータの検索や更新ができる。 エ リストは,データの挿入や削除のときに既存のデータを移動する必要がある。 |
↓
↓
↓
↓
【正解】ア
（３）H18SW春午前
| 問9 データ構造に関する記述のうち,B木の説明として適切なものはどれか。 ア ある特定のアルゴリズムに従って,レコードのキー値から物理的な格納アドレスを求めてレコードを格納する。 イ 索引部の各ノートのキー値を中心にして,小さい側のレコード数と大きい側のレコード数の比率が,ある範囲内に収まるように動的に再配置しながら格納する。 ウ レコードの物理的配置とは独立に,論理的にレコードをつなぐポインタによって,レコードを関係づけて格納する。 エ レコードをキー値の昇順にしてトラックなどのアクセス単位(ページ)ごとに格納し,各ページ内の最大キー値とそのページの番地をもつ索引を作る。 |
↓
↓
↓
↓
【正解】ウ
コメント