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

無料で印刷できるデータ構造のワークシート：やさしい問題から試験レベルまで 8 問、解答つき。印刷するか PDF で保存できます。

新しいワークシートヒントつきでオンライン練習

先生方へ： 授業で自由に印刷・コピーしてお使いいただけます。新しいワークシートごとに数値が変わり、専用の解答が付きます。授業ページに ExamProblems へのリンクを載せていただけると嬉しいです。

名前: ____________________   日付: ____________

1.やさしい

木のレベル順（level-order）走査を行うのに使われるデータ構造はどれですか。

  1. Aハッシュテーブル
  2. Bスタック
  3. Cキュー
  4. D優先度付きキュー
2.やさしい

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

  1. Anull（ノードなし）
  2. Bリストのノードの数
  3. C前のノードのアドレス
  4. D最初のノードのアドレス
3.やさしい

単方向連結リストでは、各ノードに何が含まれていますか。

  1. Aデータと他のすべてのノードへの参照
  2. Bデータと次のノードへの参照
  3. Cデータのみ
  4. Dデータとインデックス
4.ふつう

隣接行列を使って辺 (u, v) が存在するかを調べるのにどれだけ時間がかかりますか。

  1. AO(log V)
  2. BO(V)
  3. CO(E)
  4. DO(1)
5.ふつう

トライ（接頭辞木）が特に効率的なのはどのような用途ですか。

  1. A数値のソート
  2. B最短経路の探索
  3. C行列の格納
  4. Dオートコンプリートなどの接頭辞検索
6.ふつう

二分最小ヒープの extract-min はどのように動作しますか。

  1. A配列の最後の要素を取り除く
  2. B最後の要素を根に移し、下へ移動させる（sift down）
  3. Cすべての葉から新しい最小値を探す
  4. D根を取り除き、すべての要素を 1 つ左にずらす
7.むずかしい

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

  1. AO(1)
  2. BO(n log n)
  3. CO(n)
  4. DO(log n)
8.むずかしい

赤黒木が満たさなければならない性質はどれですか。

  1. Aすべての赤ノードの子は赤でなければならないので、赤ノードは葉まで途切れなく連なる
  2. Bすべてのノードが赤でなければならない
  3. C根は赤でなければならない
  4. Dあるノードからその子孫の葉までのすべての経路に含まれる黒ノードの数が等しい

解答

  1. 1. C · キュー
  2. 2. A · null（ノードなし）
  3. 3. B · データと次のノードへの参照
  4. 4. D · O(1)
  5. 5. D · オートコンプリートなどの接頭辞検索
  6. 6. B · 最後の要素を根に移し、下へ移動させる（sift down）
  7. 7. D · O(log n)
  8. 8. D · あるノードからその子孫の葉までのすべての経路に含まれる黒ノードの数が等しい

ステップごとの詳しい解答：このトピックは examproblems.com で練習できます。