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

木において、兄弟（sibling）ノードとは何ですか。

1. Aあるノードとその親
2. B異なる部分木の同じ深さにあるノード
3. C子をもたないノード
4. D同じ親をもつノード

静的配列と動的配列の主な違いは何ですか。

1. A静的配列は数値しか格納できない
2. B動的配列は、より大きなメモリブロックに移ることで拡張できる
3. C動的配列は要素を連結されたノードに格納するので、1 つずつ拡張できる
4. D静的配列はインデックスによるアクセスが遅い

有向グラフとは何ですか。

1. A閉路をもたないグラフ
2. B辺がある頂点から別の頂点への向きをもつグラフ
3. C相異なるすべての頂点対が辺で結ばれているグラフ
4. Dすべての辺が重みをもつグラフ

2 つのスタックでキューを実装します。「in」スタックに push し、「out」スタックから pop し、「out」が空になったら「in」から補充します。1 回の操作あたりのならしコストはどれですか。

1. AO(n²)
2. BO(n)
3. CO(1)
4. DO(log n)

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

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

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

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

二分探索木から 2 つの子を持つノードを削除するには、通常どうしますか。

1. Aその下の部分木を一から作り直し、含まれていたすべてのキーを挿入し直す
2. B根と入れ替える
3. C中間順の後続ノード（または先行ノード）で置き換え、そのノードを削除する
4. D部分木全体を削除する

オープンアドレス法を使うハッシュテーブルで、削除に「墓標」（tombstone）マーカーがよく使われるのはなぜですか。

1. A墓標がハッシュ計算を高速化するから
2. B安全のため削除したキーを永久に保持する必要があり、スロットを再利用できないから
3. Cスロットを空にすると、他のキーの探査列が途切れる可能性があるから
4. Dテーブルがソートされた状態になるから