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

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

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

二分木の行きがけ順（preorder）の走査は、どの順序でノードを訪問しますか。

1. A上から 1 レベルずつ
2. Bノード、次に左部分木、次に右部分木
3. C左部分木、次にノード、次に右部分木
4. D左部分木、次に右部分木、次にノード

テキストエディタの「元に戻す」（undo）機能に最も適したデータ構造はどれですか。

1. Aキュー
2. Bスタック
3. Cグラフ
4. Dハッシュセット

二分ヒープに新しい要素はどのように挿入されますか。

1. A根に置き、下へ移動させる（sift down）
2. B配列の末尾に置き、ヒープ性に反している間は上へ移動させる（sift up）
3. Cヒープ全体を一から作り直す
4. Dより大きい要素をすべて 1 つ右にずらして、ソートされた位置に挿入する

あるアプリケーションには高速な検索が必要で、さらにキーをソート順に一覧にしたり、範囲クエリに答えたりする必要もあります。最も適した構造はどれですか。

1. Aハッシュテーブル
2. Bスタック
3. Cソートされていない連結リスト
4. D平衡二分探索木

キーをソート済みの順序で挿入した場合、n 個のノードを持つ二分探索木の最悪の高さはいくつですか。

1. An（連結リストのようになる）
2. Blog₂ n
3. C1
4. D√n

ブルームフィルタは「この要素は集合に含まれるか」という問いにどのように答えますか。

1. A数値に対してのみ答えられる
2. B偽陽性はあり得るが、偽陰性はない
3. C偽陰性はあり得るが、偽陽性はない
4. D常に正確な答えを返す

二分ヒープにおける decrease-key（要素の位置が分かっている場合）の時間計算量はどれですか。

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