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

マップ（辞書）は何を格納しますか。

1. A等しいキーの組
2. B一意なキーをもつキーと値の組
3. C大きさの順にソートされた値
4. D挿入順の値だけ

デック（deque、両端キュー）とは何ですか。

1. A1 つの配列を共有する 2 つの別々のキュー
2. B優先度順に並べられたキュー
3. C末尾での削除だけを許すキュー
4. D両端での挿入と削除を許す構造

双方向連結リストの各ノードには何が含まれていますか。

1. Aデータの 2 つのコピーと 1 つのポインタ
2. Bデータと次のノードへのポインタだけ
3. Cデータ、次のノードへのポインタ、前のノードへのポインタ
4. Dデータと 2 つのポインタ（次のノードへのものと、その次のノードへのもの）

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

1. A5 4 3 2 1
2. B1 2 4 5 3
3. C4 5 2 3 1
4. D4 2 5 1 3

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

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

衝突したキーを同じバケット内のリストに格納する衝突解決法はどれですか。

1. A二次探査法（Quadratic probing）
2. Bチェイン法（Separate chaining）
3. Cダブルハッシュ法（Double hashing）
4. D線形探査法（Linear probing）

基数木（radix tree、圧縮トライ）は通常のトライをどのように改良していますか。

1. A各単語を別々のノードではなく、根にあるハッシュテーブルに格納する
2. B各ノードの子を頻度順にソートする
3. C各単語の最初の文字だけを保持する
4. D子が 1 つだけのノードの連なりを、文字列でラベル付けされた 1 本の辺にまとめる

赤黒木が満たさなければならない性質はどれですか。

1. Aすべてのノードが赤でなければならない
2. Bすべての赤ノードの子は赤でなければならないので、赤ノードは葉まで途切れなく連なる
3. C根は赤でなければならない
4. Dあるノードからその子孫の葉までのすべての経路に含まれる黒ノードの数が等しい