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

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

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

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

名前: ____________________   日付: ____________

1.やさしい

重み付きグラフとは何ですか。

  1. Aディスクに格納されたグラフ
  2. B各辺がコストや距離などの数値をもつグラフ
  3. C辺の数が多いために、一部の頂点が他の頂点より重くなっているグラフ
  4. D頂点より辺の方が多いグラフ
2.やさしい

優先度付きキューの実装に一般的に使われる構造はどれですか。

  1. Aスタック
  2. B順序のない単方向連結リスト
  3. Cヒープ
  4. D文字列
3.やさしい

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

  1. A左部分木、次に右部分木、次にノード
  2. B左部分木、次にノード、次に右部分木
  3. Cノード、次に左部分木、次に右部分木
  4. D上から 1 レベルずつ
4.ふつう

二分探索木で最小のキーはどのように見つけますか。

  1. A根だけを見る
  2. B根から左の子がなくなるまで左の子をたどる
  3. C根から右の子がなくなるまで右の子をたどる
  4. Dすべての葉を訪問して比べる
5.ふつう

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

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

衝突したキーを同じバケット内のリストに格納する衝突解決法はどれですか。

  1. A二次探査法（Quadratic probing）
  2. Bダブルハッシュ法（Double hashing）
  3. C線形探査法（Linear probing）
  4. Dチェイン法（Separate chaining）
7.むずかしい

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

  1. A80
  2. B40
  3. C60
  4. D70
8.むずかしい

ヒープソートについて正しい記述はどれですか。

  1. A最悪 O(n log n) 時間でその場でソートするが、安定ではない
  2. B安定で、O(n) の追加メモリを必要とする
  3. C追加の記憶領域として二分探索木を必要とするので、O(n) の追加メモリを使う
  4. Dどの入力に対しても O(n) 時間で動作する

解答

  1. 1. B · 各辺がコストや距離などの数値をもつグラフ
  2. 2. C · ヒープ
  3. 3. C · ノード、次に左部分木、次に右部分木
  4. 4. B · 根から左の子がなくなるまで左の子をたどる
  5. 5. D · 再平衡化による O(log n) の高さ
  6. 6. D · チェイン法（Separate chaining）
  7. 7. C · 60
  8. 8. A · 最悪 O(n log n) 時間でその場でソートするが、安定ではない

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