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

木におけるノードの深さとは何ですか。

1. Aそのノードの子の数
2. Bそのノードから最も深い葉までの辺の数
3. Cその部分木に含まれるノードの数
4. D根からそのノードまでの辺の数

ハッシュテーブルはデータをどのような形で格納しますか。

1. Aハッシュ関数で位置が決まるキーと値のペア
2. B固定長の文字列
3. Cキーが順序付けられた木
4. Dソート済みリストのみ

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

1. A二分木（Binary tree）
2. Bスタック（Stack）
3. Cキュー（Queue）
4. Dヒープ（Heap）

サイズ 7 のハッシュテーブルが h(k) = k mod 7 と線形探査法を使っています。10 を挿入した後、17 はどこに格納されますか。

1. Aインデックス 3
2. Bインデックス 0
3. Cインデックス 6
4. Dインデックス 4

連結リストにおける番兵（ダミー）ノードの目的は何ですか。

1. A要素の数を格納する
2. B先頭や末尾での特別な場合をなくしてコードを単純にする
3. Cリストをソートされた状態にする
4. Dリストのノード数が決まった最大値を超えて増えないようにする

実行中のプログラムが、有効な関数呼び出しとそのローカル変数を管理するために使うデータ構造はどれですか。

1. A関数のハッシュテーブル
2. Bヒープメモリのキュー
3. Cコールスタック
4. Dフレームの二分探索木

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

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

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

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