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

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

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

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

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

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

1. Aデータと次のノードへのポインタだけ
2. Bデータの 2 つのコピーと 1 つのポインタ
3. Cデータ、次のノードへのポインタ、前のノードへのポインタ
4. Dデータと 2 つのポインタ（次のノードへのものと、その次のノードへのもの）

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

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

インデックス 0 から始まる配列に格納された二分ヒープで、インデックス i のノードの親はどこにありますか。

1. Aインデックス 2i + 1
2. Bインデックス ⌊i / 2⌋ + 1
3. Cインデックス ⌊(i − 1) / 2⌋
4. Dインデックス i − 1

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

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

サーバーがハッシュ関数を万能（universal）族からランダムに選ぶのはなぜですか。

1. Aテーブルのサイズを変更する必要をなくすため
2. B攻撃者がどのようなキーを送っても、2 つのキーが決して衝突しないことを保証するため
3. Cハッシュテーブルをソートされた状態にするため
4. D攻撃者がすべて衝突する多数のキーを選べる可能性をきわめて低くするため

基数木（radix tree、圧縮トライ）は通常のトライをどのように改良していますか。

1. A各単語を別々のノードではなく、根にあるハッシュテーブルに格納する
2. B各ノードの子を頻度順にソートする
3. C各単語の最初の文字だけを保持する
4. D子が 1 つだけのノードの連なりを、文字列でラベル付けされた 1 本の辺にまとめる