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

スタックに対する peek（または top）操作は何をしますか。

1. A一番上の要素を取り除いて返す
2. Bスタックからすべての要素を取り除く
3. C一番上の要素を取り除かずに返す
4. Dスタックの一番下の要素を返す

木において、葉（leaf）とは何ですか。

1. A親をもたないノード
2. B最大の値をもつノード
3. Cちょうど 1 つの子をもつノード
4. D子をもたないノード

配列の要素はメモリにどのように格納されますか。

1. Aメモリページの木の中に
2. Bばらばらに、ポインタでつながれて
3. C1 つの連続したブロックに、順に並んで
4. Dハッシュで選ばれたランダムな位置に

AVL 木はすべてのノードでどのような平衡条件を保っていますか。

1. A左右の部分木の高さの差が高々 1 である
2. Bすべての葉がちょうど同じ深さにある
3. Cすべてのノードが赤または黒に塗られている
4. Dすべてのノードの両方の部分木が、まったく同じ数のノードを含む

固定のアルファベットをもつトライで、長さ L の単語を探索するのにどれだけ時間がかかりますか。

1. A格納されている単語の数に関係なく O(L)
2. B単語の数を n として O(n)
3. C単語の数を n として O(log n)
4. DO(L × n)

二分探索木を中間順（in-order）でたどると、キーはどの順序で訪問されますか。

1. A昇順
2. B常に降順
3. C挿入順
4. Dレベル順

データベースやファイルシステムで B 木が使われるのはなぜですか。

1. Aデータをソートせずに格納するから
2. Bどの配列よりもメモリ使用量が少ないので、索引全体が常に主記憶に収まるから
3. C分岐数が大きいため木が浅く保たれ、遅いディスク読み込みが減るから
4. D再平衡化が不要だから

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

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