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

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

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

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

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

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

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

リストの中ほどにあるノードへの参照をもっています。どのリストなら、それを O(1) で削除できますか。

1. A双方向連結リスト
2. B単方向連結リスト
3. C動的配列
4. Dソート済み配列

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

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

無向グラフの隣接行列について正しいのはどれですか。

1. A主対角線には常に 1 が入っている
2. B主対角線に関して対称である
3. C常に上三角行列である
4. D各行にちょうど 1 つの 1 がある

ヒープソートについて正しい記述はどれですか。

1. A追加の記憶領域として二分探索木を必要とするので、O(n) の追加メモリを使う
2. Bどの入力に対しても O(n) 時間で動作する
3. C安定で、O(n) の追加メモリを必要とする
4. D最悪 O(n log n) 時間でその場でソートするが、安定ではない

異なるキーをもつ二分木を常に一意に決定する走査の組はどれですか。

1. A行きがけ順だけ
2. B行きがけ順と通りがけ順
3. Cレベル順だけ
4. D行きがけ順と帰りがけ順