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

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

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

最大ヒープ性（max-heap property）とは何ですか。

1. Aすべての左の子のキーが右の兄弟のキー以上である
2. Bすべての親のキーがその子のキー以上である
3. Cキーが左から右へソートされている
4. Dすべての葉が最大のキーをもつ

配列では O(1) だが、単方向連結リストでは O(n) となる操作はどれですか。

1. Aインデックス i の要素へのアクセス
2. B最初の要素の読み取り
3. C先頭への挿入
4. D先頭の要素の削除

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

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

ある二分木の根は 1 で、左の子が 2、右の子が 3 です。ノード 2 の子は 4（左）と 5（右）です。行きがけ順の走査はどれですか。

1. A1 2 3 4 5
2. B4 5 2 3 1
3. C4 2 5 1 3
4. D1 2 4 5 3

AVL 木と赤黒木が保証するものは何ですか。

1. Aどの場合でも定数時間での探索
2. B2 つの子を持つノードが存在しないこと
3. C再平衡化による O(log n) の高さ
4. Dキーが挿入順に格納されること

根が 50、左部分木が 30（子は 20, 40）、右部分木が 70（子は 60, 80）の BST で、通りがけ順の後続ノードを使って根を削除します。新しい根になるキーはどれですか。

1. A70
2. B80
3. C40
4. D60

n 個の数の配列に対するフェニック木（Binary Indexed Tree）が O(log n) でサポートする操作はどれですか。

1. A任意の位置への要素の挿入
2. BO(1) での中央値の検索
3. C接頭辞和のクエリと単一要素の更新
4. D配列のソートと二分探索