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

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

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

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

名前: ____________________   日付: ____________

1.やさしい

n 個のノードをもつ木には何本の辺がありますか。

  1. An − 1
  2. B2n
  3. Cn + 1
  4. Dn
2.やさしい

ハッシュテーブルにおいて、衝突（collision）とは何ですか。

  1. A2 つの異なるキーが同じインデックスに対応すること
  2. Bテーブルのメモリが不足すること
  3. C2 つの等しいキーが 2 回格納されること
  4. Dキーをまったくハッシュできないこと
3.やさしい

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

  1. Aキュー（Queue）
  2. Bハッシュテーブル（Hash table）
  3. Cスタック（Stack）
  4. D連結リスト（Linked list）
4.ふつう

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

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

リストの中ほどにあるノードへの参照をもっています。どのリストなら、それを O(1) で削除できますか。

  1. Aソート済み配列
  2. B単方向連結リスト
  3. C動的配列
  4. D双方向連結リスト
6.ふつう

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

  1. AO(E)
  2. BO(1)
  3. CO(log V)
  4. DO(V)
7.むずかしい

配列のサイズ k のすべてのウィンドウの最大値を合計 O(n) で計算できる構造はどれですか。

  1. Aウィンドウの要素の単方向連結リスト
  2. Bずらすことで更新するソート済み配列
  3. Cウィンドウごとに作り直す最小ヒープ
  4. D値の降順にインデックスを保持するデック
8.むずかしい

配列の各要素について、その右側にある次に大きい要素を、合計 O(n) 時間で求めたいとします。役立つ構造はどれですか。

  1. A要素ごとに作り直す二分探索木
  2. B要素のすべての組を保持するキュー
  3. C答えを待っている要素を保持するスタック
  4. Dすべての要素のハッシュテーブル

解答

  1. 1. A · n − 1
  2. 2. A · 2 つの異なるキーが同じインデックスに対応すること
  3. 3. C · スタック（Stack）
  4. 4. D · 隣接リスト
  5. 5. D · 双方向連結リスト
  6. 6. B · O(1)
  7. 7. D · 値の降順にインデックスを保持するデック
  8. 8. C · 答えを待っている要素を保持するスタック

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