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

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

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

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

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

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

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

無向グラフの隣接行列について正しいのはどれですか。

1. A主対角線には常に 1 が入っている
2. B常に上三角行列である
3. C各行にちょうど 1 つの 1 がある
4. D主対角線に関して対称である

配列に格納された二分最小ヒープ（インデックスは 0 から）において、インデックス i のノードの子はどこにありますか。

1. Ai + 1 と i + 2
2. B2i と 2i + 1
3. Ci/2 と i/2 + 1
4. D2i + 1 と 2i + 2

二分探索木を中間順（in-order）でたどると、キーはどの順序で訪問されますか。

1. A挿入順
2. B常に降順
3. Cレベル順
4. D昇順

n 個の数の配列に対するフェニック木（Binary Indexed Tree）が O(log n) でサポートする操作はどれですか。

1. A配列のソートと二分探索
2. B接頭辞和のクエリと単一要素の更新
3. CO(1) での中央値の検索
4. D任意の位置への要素の挿入

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

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