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

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

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

重み付きグラフとは何ですか。

1. A各辺がコストや距離などの数値をもつグラフ
2. Bディスクに格納されたグラフ
3. C辺の数が多いために、一部の頂点が他の頂点より重くなっているグラフ
4. D頂点より辺の方が多いグラフ

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

1. Aデータと他のすべてのノードへの参照
2. Bデータと次のノードへの参照
3. Cデータのみ
4. Dデータとインデックス

V 個の頂点と E 本の辺をもつグラフについて、隣接リストはどれだけのメモリを使いますか。

1. AO(V²)
2. BO(E²)
3. CO(V × E)
4. DO(V + E)

負荷率がしきい値を超えた後にハッシュテーブルが再ハッシュ（rehash）すると、何が起こりますか。

1. A衝突しているキーだけが、テーブルの末尾にある新しいオーバーフローリストに移される
2. B既存のキーがその場でソートされる
3. Cより大きなテーブルが確保され、すべてのキーが挿入し直される
4. D場所を空けるために最も古いキーが削除される

二分探索木で最小のキーはどのように見つけますか。

1. A根から右の子がなくなるまで右の子をたどる
2. B根から左の子がなくなるまで左の子をたどる
3. Cすべての葉を訪問して比べる
4. D根だけを見る

すべての B 木を完全に平衡に保っている性質はどれですか。

1. Aすべての葉が同じ深さにある
2. Bすべてのノードがちょうど 2 つの子をもつ
3. Cキーは根にだけ格納される
4. D各ノードは 1 つのキーを格納する

ある動的配列は満杯になるとサイズを 2 倍にします。多くの実装が、半分ではなく 4 分の 1 まで減ったときにだけ縮小するのはなぜですか。

1. Aメモリアロケータはブロックの 4 分の 1 単位でしかメモリを解放できないから
2. B境界付近で push と pop が交互に起こるときに、サイズ変更が繰り返されるのを避けるため
3. C配列をソートされた状態に保つため
4. D半分で半減させると要素が失われるから