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

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

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

優先度付きキューの実装に一般的に使われる構造はどれですか。

1. A順序のない単方向連結リスト
2. Bスタック
3. C文字列
4. Dヒープ

「後入れ先出し」（LIFO）の原理で動作するデータ構造はどれですか。

1. A連結リスト（Linked list）
2. Bスタック（Stack）
3. Cハッシュテーブル（Hash table）
4. Dキュー（Queue）

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

1. A5 4 3 2 1
2. B4 2 5 1 3
3. C1 2 4 5 3
4. D4 5 2 3 1

トライ（接頭辞木）が特に効率的なのはどのような用途ですか。

1. A最短経路の探索
2. Bオートコンプリートなどの接頭辞検索
3. C行列の格納
4. D数値のソート

配列に格納された二分最小ヒープ（インデックスは 0 から）において、インデックス i のノードの子はどこにありますか。

1. A2i + 1 と 2i + 2
2. Bi + 1 と i + 2
3. C2i と 2i + 1
4. Di/2 と i/2 + 1

O(1) の追加メモリで、単方向連結リストが閉路を含むかどうかを検出するにはどうすればよいですか。

1. Aリストをソートして重複を探す
2. B訪問したすべてのノードをハッシュ集合に格納する
3. C一方のポインタを 1 歩ずつ、もう一方を 2 歩ずつ進め、出会うかどうかを調べる
4. D数がリストの長さのフィールドを超えるまでノードを数える

データベースやファイルシステムで B 木が使われるのはなぜですか。

1. A分岐数が大きいため木が浅く保たれ、遅いディスク読み込みが減るから
2. Bどの配列よりもメモリ使用量が少ないので、索引全体が常に主記憶に収まるから
3. C再平衡化が不要だから
4. Dデータをソートせずに格納するから