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

グラフは何で構成されていますか。

1. A行と列
2. Bキーとハッシュ値のみ
3. C辺（edge）で結ばれた頂点（vertex、ノード）
4. D根と葉のみ

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

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

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

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

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

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

二分探索木のあるノードが右部分木をもっています。その通りがけ順での次のノード（後続ノード）はどこにありますか。

1. A右部分木の最も左のノード
2. B左部分木の最も右のノード
3. C常にその右の子
4. D常にその親

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

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

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

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

標準的なブルームフィルタから、ビットをクリアするだけで要素を削除できないのはなぜですか。

1. Aそれらのビットは他の要素にも属している可能性があり、偽陰性を引き起こすから
2. Bブルームフィルタのビットは作成後に変更できないから
3. C削除すると偽陽性率が 100% に上がるから
4. Dブルームフィルタは要素全体を格納しており、いったんハッシュ化されると再び見つけられないから