IPA データ構造 — 頻出論点と過去問

頻出論点

1. この分野は何か

プログラムの中で複数のデータをどのような形や順序で並べて保持し、追加・削除・検索をどう効率よく行うかという仕組みを学びます。データのつなぎ方や階層構造ごとの性質には、操作に伴う状態の変化や処理時間の違いに直接関わる特徴があります。

2. 実際の出題のされ方

木構造の基本的な構成要素を確認する問題が、ITパスポートで出ています。たとえば、ファイルシステムを木構造で表したときに、空のディレクトリを許す条件のもとで中間ノードである「節」と末端ノードである「葉」にディレクトリとファイルのどれが対応するかを判断する問題があります。

応用情報技術者の午前と高度試験の午前Iでは、具体的なデータ構造に対する操作結果や性質の比較が中心になります。スタックでは、順に届くデータの挿入と取出しのタイミングを変えて作れる出力順序の総数を数える問題や、逆ポーランド表記法（後置記法）の式に数値を代入して演算結果を求める問題が出ています。リストでは、配列による実現とポインタによる実現の性質の違いや、3つの一次元配列（値・次要素の番号・前要素の番号）で表現された双方向リストに要素を挿入した後の配列の値を特定する問題が出題されています。木構造では、2分木に対する再帰処理の定義を読んで出力順を求める問題、配列の添字 $2i$ と $2i+1$ で子を表す2分木の先頭からの走査がどの探索に当たるかを問う問題、2分探索木の要素削除やAVL木への要素追加に伴う再構成を選ぶ問題があります。このほか、ハッシュ関数 $h(x) = x \bmod n$ で異なるキーが衝突する条件や、衝突がないハッシュ表の探索時間のグラフ、可変量のメモリ管理で最適適合アルゴリズムに合うデータ構造の選択も問われています。

データベースの物理構造やデータ検証に関わる構造は、データベーススペシャリストの午前IIで掘り下げられます。B+木のリーフノードが分割された後のポインタのつながり方を選ぶ問題、データ総件数 $X$ に対するB+木インデックスのノードアクセス回数のオーダーを問う問題、ブロックチェーンのデータ構造の特徴を選ぶ問題が出ています。また、衝突がないハッシュ表の探索時間のグラフを選ぶ問題は、エンベデッドシステムスペシャリストの午前IIでも出題されています。

3. 学習のポイント

スタックは後から入れたデータを先に取り出す後入れ先出し（LIFO）の構造であり、キューのような先入れ先出しの構造とは取り出される順序が異なります。スタックへの挿入と取出しを組み合わせる問題では、まだ取り出していない要素は積まれた逆順にしか取り出せないという制約を押さえます。逆ポーランド表記法の式を評価する際は、式を左から読み、数値ならスタックに積み、演算子なら直前に積んだ2つの数値を取り出して計算し、結果を再び積む手順をたどります。このとき、引き算や割り算では先に取り出した側が右オペランド、後から取り出した側が左オペランドになる点に注意します。

リストの実現方式は、要素がメモリ上で連続して並んでいるか、ポインタをたどってつないでいるかを軸に整理します。

• 配列による実現: 要素が連続した番地に並ぶため、先頭からの位置（添字）を計算してどの要素にも直接アクセスできます。その反面、あらかじめ決めた枠を確保しておく必要があり、途中に要素を入れたり消したりするときは後ろの要素を順番にずらす手間がかかります。
• ポインタによる実現: 要素を離れた番地に置き、各要素に次の要素の場所を持たせて鎖のようにつなぎます。途中の要素を探すには先頭からポインタを順にたどる必要がありますが、つなぎ入れる場所さえ分かっていれば、前後のポインタを書き換えるだけで要素を出し入れできます。

双方向リストを配列の組で表現する問題では、新要素が配列の末尾（新しい要素番号）に置かれることを確認したうえで、新要素の prev に直前の要素番号、next に直後の要素番号を設定する関係を落ち着いて追跡します。あわせて、挿入位置の前後の要素側でも next や prev を新しい要素番号へ書き換えることで双方向のつながりが完成します。

木構造では、走査順と平衡を保つ仕組みが重要です。2分木の再帰的な走査では、左の子・右の子・自身の出力がどの順序で定義されているかを問題文の定義通りに追います。配列 $A[i]$ の左右の子を $A[2i]$、$A[2i+1]$ とする表現では、添字の小さい順に同じ深さの節点が左から右へ連続して並びます。また、各節点について、左部分木のすべての値 ＜ その節点の値 ＜ 右部分木のすべての値、が成り立つ2分木が2分探索木であり、次の操作と構造の性質を押さえます。

• 2分探索木の削除: 子を2つもつ節点を削除して位置の移動だけで再構成する場合、削除する節点の位置には「左部分木の最大値」または「右部分木の最小値」を移動させます。
• AVL木: すべての節点で左部分木と右部分木の高さの差が1以下になるよう、要素の追加などで偏りが生じた際に回転を行って再構築します。
• B+木: 親の中間ノードから子のリーフノードへポインタが張られるだけでなく、すべてのリーフノード同士が横方向のポインタで順番に連結されている点が特徴です。

ハッシュ表では、衝突（シノニム）の条件と探索時間の特性を理解します。剰余を用いる $h(x) = x \bmod n$ では、たとえば $n = 7$ なら、3 と 10 はどちらも余りが 3 で同じ位置になります。2つのキーの差が $n$ の倍数になっていることを確かめます。また、衝突が発生しない条件では、キーから格納位置を直接計算できるので、データが何件あっても探索の手間は1回分で変わりません。目的に応じたデータ構造の選択では、どのデータ構造が速いかは、割り当てのたびに比べる値をキーにして並べてあるかで決まります。ブロックチェーンでは、各ブロックが直前のブロックのハッシュ値を持ちます。途中のブロックを書き換えると後ろのブロックに記録したハッシュ値と合わなくなるので、改ざんが分かります。

4. 間違えやすいところ

配列で実現したリストの特徴を選ぶ問題では、ポインタで実現したときの特徴を配列の特徴のように書いた選択肢が誤りでした。どちらの実現かを、要素が連続して並んでいるかどうかで判断します。

ハッシュ表の探索時間のグラフを選ぶ問題では、データ数に比例して増える右上がりの直線（線形探索の特性）や、増え方が次第に緩やかになる上に凸の曲線（二分探索などの特性）と混同しないようにします。また、$x \bmod n$ による衝突条件では、和と差、どちらがどちらの倍数かを入れ替えた選択肢がありました。具体的な数値を当てはめて余りが一致するかを確かめると確実です。

2分探索木の要素削除では、削除する節点のすぐ下にある子ノードの値をそのまま持ち上げてしまう誤りに気をつけます。子ノード自身がさらに子をもっている場合、そのまま持ち上げると部分木との間で木全体の大小関係が崩れてしまいます。B+木のノード分割でも、分割後の新しいリーフノードに対して親の中間ノードからのポインタが抜けている図や、リーフノード間の横方向の双方向ポインタが途切れている図を選ばないよう、縦と横の両方の矢印を確認してください。