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

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

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

二分最小ヒープの最小の要素はどこにありますか。

1. Aいずれかの葉にあり、探さなければならない
2. B最も左の葉
3. C配列の最後の位置
4. D根

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

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

実行中のプログラムが、有効な関数呼び出しとそのローカル変数を管理するために使うデータ構造はどれですか。

1. Aヒープメモリのキュー
2. Bフレームの二分探索木
3. C関数のハッシュテーブル
4. Dコールスタック

衝突したキーを同じバケット内のリストに格納する衝突解決法はどれですか。

1. Aダブルハッシュ法（Double hashing）
2. B二次探査法（Quadratic probing）
3. C線形探査法（Linear probing）
4. Dチェイン法（Separate chaining）

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

1. A最大値はない
2. B2
3. C0.5
4. D1

二分ヒープにおける decrease-key（要素の位置が分かっている場合）の時間計算量はどれですか。

1. AO(n)
2. BO(log n)
3. CO(1)
4. DO(n log n)

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

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