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

ハッシュテーブルの負荷率（load factor）とは何ですか。

1. Aこれまでの衝突の数
2. Bバケットの数を、格納されたキーの平均の長さで割ったもの
3. Cディスクからテーブルを読み込むのに必要な時間
4. D格納された要素の数をバケットの数で割ったもの

静的配列と動的配列の主な違いは何ですか。

1. A静的配列は数値しか格納できない
2. B静的配列はインデックスによるアクセスが遅い
3. C動的配列は、より大きなメモリブロックに移ることで拡張できる
4. D動的配列は要素を連結されたノードに格納するので、1 つずつ拡張できる

二分木の行きがけ順（preorder）の走査は、どの順序でノードを訪問しますか。

1. A左部分木、次に右部分木、次にノード
2. B上から 1 レベルずつ
3. C左部分木、次にノード、次に右部分木
4. Dノード、次に左部分木、次に右部分木

二分探索木のあるノードが右部分木をもっています。その通りがけ順での次のノード（後続ノード）はどこにありますか。

1. A右部分木の最も左のノード
2. B常にその右の子
3. C左部分木の最も右のノード
4. D常にその親

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

1. A1 2 4 5 3
2. B4 2 5 1 3
3. C5 4 3 2 1
4. D4 5 2 3 1

あるアプリケーションには高速な検索が必要で、さらにキーをソート順に一覧にしたり、範囲クエリに答えたりする必要もあります。最も適した構造はどれですか。

1. A平衡二分探索木
2. Bソートされていない連結リスト
3. Cスタック
4. Dハッシュテーブル

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

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

配列の各要素について、その右側にある次に大きい要素を、合計 O(n) 時間で求めたいとします。役立つ構造はどれですか。

1. A要素ごとに作り直す二分探索木
2. B答えを待っている要素を保持するスタック
3. Cすべての要素のハッシュテーブル
4. D要素のすべての組を保持するキュー