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

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

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

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

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

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

1. A左部分木、次に右部分木、次にノード
2. B左部分木、次にノード、次に右部分木
3. Cノード、次に左部分木、次に右部分木
4. D右部分木、次にノード、次に左部分木

平衡二分探索木でキーを探索する時間計算量はどれですか。

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

高さを辺の数で数えるとき、高さ h の完全（perfect）二分木にはいくつのノードがありますか。

1. A2h + 1
2. Bh²
3. C2^h+1 − 1
4. D2^h

後置記法の式 3 4 + 2 * の値は何ですか。

1. A11
2. B24
3. C14
4. D10

ある AVL ノードは、その左の子の右部分木が高くなりすぎたために平衡が崩れています（左右の場合）。どのような修正が適用されますか。

1. A左の子で左回転し、次にそのノードで右回転
2. Bそのノードで 1 回の右回転
3. C左の子で右回転し、次にそのノードで左回転
4. Dそのノードで 1 回の左回転

O(1) の追加メモリで、単方向連結リストが閉路を含むかどうかを検出するにはどうすればよいですか。

1. A数がリストの長さのフィールドを超えるまでノードを数える
2. B一方のポインタを 1 歩ずつ、もう一方を 2 歩ずつ進め、出会うかどうかを調べる
3. Cリストをソートして重複を探す
4. D訪問したすべてのノードをハッシュ集合に格納する