データ構造と基本アルゴリズム

データ構造とは、データを格納し、追加・削除・参照といった操作を行うための形式を指す。配列、線形リスト、集合、木などがあり、基本アルゴリズムは、これらの構造を使って探索や計算を効率的に進める手順である。試験では、配列とリストの違い、単方向リストの操作、集合の演算、2次元配列の要素の数え方、流れ図の追跡が中心になる。

配列とリストの実現方式の違い

配列では、要素を連続した領域に格納するため、添字が分かれば中間の要素も直接参照でき、通常は一定時間で参照できる。ただし、配列で実現したリストは、実際の要素数にかかわらず最大要素数に対応する領域を確保する必要があり、使用されない領域が発生する可能性がある。

ポインタで実現したリストは、要素ごとに次の要素へのポインタ領域が必要になる一方、データの追加や削除はポインタの付け替えで行える。配列で途中に挿入する場合は、後続要素の移動が必要となり、挿入位置が分かっていても最悪で要素数に比例する時間がかかる。

単方向リストの先頭・末尾ポインタと削除の計算量

先頭ポインタと末尾ポインタをもつ単方向の線形リストでは、先頭データの削除は先頭ポインタを次のデータへ更新するだけで済む。また、末尾への追加は末尾ポインタが指すデータのポインタをつなぎ替えればよく、既存の要素をたどる必要はない。

一方、末尾のデータを削除する処理では、末尾の一つ前のデータを特定する必要がある。単方向であるため末尾ポインタから前のデータへは戻れず、先頭から次のポインタを順にたどって末尾の直前まで進まなければならない。この処理のたどる回数はデータ数に比例し、同種の操作の中で最も多くなる。

集合の補集合と差集合

全体集合 S における A の補集合 A̅ は、S から A を除いた集合である。差集合 A−B は A から B を除いた集合であり、A̅−B は A̅ と B の補集合の積に等しく、A̅∩B̅ と表される。