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

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

1. Aハッシュテーブル（Hash table）
2. Bキュー（Queue）
3. C連結リスト（Linked list）
4. Dスタック（Stack）

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

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

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

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

ある道路網には 100,000 の交差点があり、それぞれが約 4 つの他の交差点とつながっています。最も適した表現はどれですか。

1. A隣接リスト
2. B隣接行列
3. C頂点の 1 つのソート済み配列
4. D辺の二分ヒープ

連結リストにおける番兵（ダミー）ノードの目的は何ですか。

1. A要素の数を格納する
2. Bリストをソートされた状態にする
3. Cリストのノード数が決まった最大値を超えて増えないようにする
4. D先頭や末尾での特別な場合をなくしてコードを単純にする

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

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

単方向連結リストをその場で反転させる時間と追加領域のコストはどれですか。

1. A時間 O(n)、追加領域 O(n)
2. B時間 O(n log n)、追加領域 O(1)
3. C時間 O(1)、追加領域 O(1)
4. D時間 O(n)、追加領域 O(1)

n 個の数からなるストリームから、O(k) のメモリで最小の k 個の値を保持しなければなりません。O(n log k) 時間で動作する方法はどれですか。

1. An 個すべての値のソート済み配列
2. Bn 個すべての値を保持する最小ヒープで、最後に小さい方から k 個を取り出す
3. Cサイズ k の最大ヒープを使い、より小さい値が来たら根を置き換える
4. D最後の k 個の値の FIFO キュー