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

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

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

スタックの一番上に要素を追加する操作の名前は何ですか。

1. Aプッシュ（Push）
2. Bピーク（Peek）
3. Cポップ（Pop）
4. Dエンキュー（Enqueue）

抽象データ型としての集合（set）を定義する特徴は何ですか。

1. A一方の端でだけアクセスを許す
2. B要素をソート順に格納する
3. C重複なしに要素を格納する
4. Dキーと値の組を格納する

リストの中ほどにあるノードへの参照をもっています。どのリストなら、それを O(1) で削除できますか。

1. A単方向連結リスト
2. B双方向連結リスト
3. Cソート済み配列
4. D動的配列

二分ヒープをポインタなしで配列に格納できるのはなぜですか。

1. Aヒープは 100 個を超える要素を含むことがないから
2. Bヒープのすべてのキーは等しいから
3. C完全二分木なので、位置が単純なインデックスの式に従うから
4. D配列は自動的にキーをソート順に保つので、ポインタが不要になるから

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

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

セグメント木は一般的に何に使われますか。

1. A各接頭辞を別々の木のノードに格納することで、文字列をアルファベット順にソートする
2. Bグラフの辺を格納する
3. C区間クエリ（区間和など）と更新を O(log n) で処理する
4. Dスタックを実装する

あるオブジェクトをハッシュマップのキーとして格納した後、そのハッシュ関数で使われるフィールドを変更しました。起こりうる結果はどれですか。

1. Aキーのハッシュはプログラムの開始時に 1 回しか計算されないので、何も変わらない
2. Bオブジェクトは古いハッシュのバケットにあるので、検索に失敗することがある
3. Cフィールドが変更された瞬間にマップがエラーを投げる
4. Dマップが自動的にキーを新しいバケットに移す