解答つきデータ構造ワークシート

配列では O(1) だが、単方向連結リストでは O(n) となる操作はどれですか。

1. A先頭への挿入
2. Bインデックス i の要素へのアクセス
3. C先頭の要素の削除
4. D最初の要素の読み取り

キューの先頭の要素を取り除く操作の名前は何ですか。

1. Aエンキュー（Enqueue）
2. Bインサート（Insert）
3. Cプッシュ（Push）
4. Dデキュー（Dequeue）

木の高さは一般にどのように定義されますか。

1. A木の葉の数
2. B根と葉をすべて含めた、木に含まれるノードの総数
3. C根から葉までの最も長い経路上の辺の数
4. D根の子の数

二分探索木で最小のキーはどのように見つけますか。

1. A根だけを見る
2. B根から左の子がなくなるまで左の子をたどる
3. C根から右の子がなくなるまで右の子をたどる
4. Dすべての葉を訪問して比べる

オープンアドレス法を使うハッシュテーブルで、負荷率の最大値はいくつですか。

1. A2
2. B0.5
3. C最大値はない
4. D1

ある二分木の根は 1 で、左の子が 2、右の子が 3 です。ノード 2 の子は 4（左）と 5（右）です。帰りがけ順の走査はどれですか。

1. A4 5 2 3 1
2. B5 4 3 2 1
3. C1 2 4 5 3
4. D4 2 5 1 3

単純一様ハッシュの仮定の下で、n 個のキーと m 個のバケットをもつチェイン法のハッシュテーブルの探索の期待時間はどれですか。

1. AO(n)
2. BO(log n)
3. Cα = n / m として O(1 + α)
4. DO(m)

ランクによる併合（union by rank）と経路圧縮（path compression）を用いた union-find（素集合）構造の、1 操作あたりの償却コストはどれですか。

1. Aちょうど O(log n)
2. BO(n²)
3. CO(α(n))（逆アッカーマン関数）で、実用上は定数
4. DO(n)