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

グラフの隣接リスト表現では、各頂点について何が格納されますか。

1. A隣接する頂点のリスト
2. B他のすべての頂点への最短経路
3. CV 個の真偽値からなる行
4. Dグラフの辺の総数

単方向連結リストでは、最後のノードの next ポインタには何が入っていますか。

1. A最初のノードのアドレス
2. B前のノードのアドレス
3. Cnull（ノードなし）
4. Dリストのノードの数

デック（deque、両端キュー）とは何ですか。

1. A両端での挿入と削除を許す構造
2. B1 つの配列を共有する 2 つの別々のキュー
3. C末尾での削除だけを許すキュー
4. D優先度順に並べられたキュー

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

1. A√n
2. Bn（連結リストのようになる）
3. Clog₂ n
4. D1

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

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

オープンアドレス法を使うハッシュテーブルで、負荷率の最大値はいくつですか。

1. A2
2. B0.5
3. C1
4. D最大値はない

ハッシュテーブルが正しく動作するためには、ハッシュと等価性はどの規則に従わなければなりませんか。

1. Aハッシュ値は素数でなければならない
2. B等しいキーは等しいハッシュ値をもたなければならない
3. Cハッシュ値が等しければキーも等しい
4. D異なるキーは異なるハッシュ値をもたなければならない

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

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