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

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

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

木の根（ルート）とは何ですか。

1. A最大の値を持つノード
2. B子を持たないノード
3. C中間にある任意のノード
4. D親を持たない最上位のノード

「先入れ先出し」（FIFO）の原理で動作するデータ構造はどれですか。

1. A二分木（Binary tree）
2. Bスタック（Stack）
3. Cヒープ（Heap）
4. Dキュー（Queue）

同じ長さの連結リストを走査するより、配列を走査する方が実際にはずっと速いことが多いのはなぜですか。

1. A配列の要素は連続しているので、CPU キャッシュを有効に使えるから
2. B配列の走査は全体で O(1)、連結リストの走査は O(n) だから
3. C配列では値を比較する命令が少なくて済むから
4. D連結リストは常に要素をディスクに格納するから

ある二分木の根は 1 で、左の子が 2、右の子が 3 です。ノード 2 の子は 4（左）と 5（右）です。帰りがけ順の走査はどれですか。

1. A4 5 2 3 1
2. B4 2 5 1 3
3. C1 2 4 5 3
4. D5 4 3 2 1

トライ（接頭辞木）が特に効率的なのはどのような用途ですか。

1. Aオートコンプリートなどの接頭辞検索
2. B行列の格納
3. C数値のソート
4. D最短経路の探索

スプレー木は各アクセスの後に何をしますか。

1. A木全体を平衡な形に作り直す
2. Bアクセスしたノードを根まで回転させて持ち上げる
3. Cアクセスしたノードを葉に移す
4. D探索経路上のノードの色を塗り替える

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

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