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

ハッシュテーブルにおいて、ハッシュ関数は何をしますか。

1. Aキーをテーブル内のインデックスに対応させる
2. Bテーブル内の値を暗号化する
3. Cテーブル内のキーをソートする
4. D格納されているキーの数を数える

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

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

二分最小ヒープの最小の要素はどこにありますか。

1. A配列の最後の位置
2. B最も左の葉
3. Cいずれかの葉にあり、探さなければならない
4. D根

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

1. A4 2 5 1 3
2. B5 4 3 2 1
3. C4 5 2 3 1
4. D1 2 4 5 3

二分探索木を中間順（in-order）でたどると、キーはどの順序で訪問されますか。

1. A挿入順
2. B常に降順
3. Cレベル順
4. D昇順

インデックス 0 から始まる配列に格納された二分ヒープで、インデックス i のノードの親はどこにありますか。

1. Aインデックス ⌊(i − 1) / 2⌋
2. Bインデックス i − 1
3. Cインデックス 2i + 1
4. Dインデックス ⌊i / 2⌋ + 1

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

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

キー 5, 3, 8, 1 をこの順に、空の配列ベースの二分最小ヒープに挿入します。最終的な配列はどれですか。

1. A[1, 5, 8, 3]
2. B[1, 3, 5, 8]
3. C[3, 1, 8, 5]
4. D[1, 3, 8, 5]