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

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

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

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

名前: ____________________   日付: ____________

1.やさしい

二分探索木において、あるノードの左部分木にある値はどうなっていますか。

  1. Aランダムな順序
  2. Bそのノードの値より大きい
  3. Cそのノードの値より小さい
  4. Dそのノードの値と等しい
2.やさしい

無向グラフにおいて、頂点の次数（degree）とは何ですか。

  1. Aその頂点につながっている辺の数
  2. Bグラフの頂点の数
  3. Cその頂点からの最長経路の長さ
  4. D隣接リストにおけるその位置
3.やさしい

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

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

無向グラフの隣接行列について正しいのはどれですか。

  1. A常に上三角行列である
  2. B主対角線に関して対称である
  3. C主対角線には常に 1 が入っている
  4. D各行にちょうど 1 つの 1 がある
5.ふつう

キーをソート済みの順序で挿入した場合、n 個のノードを持つ二分探索木の最悪の高さはいくつですか。

  1. A1
  2. Blog₂ n
  3. Cn（連結リストのようになる）
  4. D√n
6.ふつう

高さを辺の数で数えるとき、高さ h の完全（perfect）二分木にはいくつのノードがありますか。

  1. A2h + 1
  2. B2h
  3. C2h+1 − 1
  4. Dh2
7.むずかしい

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

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

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

  1. AO(n)
  2. BO(n log n)
  3. CO(log n)
  4. DO(1)

解答

  1. 1. C · そのノードの値より小さい
  2. 2. A · その頂点につながっている辺の数
  3. 3. A · 各辺がコストや距離などの数値をもつグラフ
  4. 4. B · 主対角線に関して対称である
  5. 5. C · n（連結リストのようになる）
  6. 6. C · 2h+1 − 1
  7. 7. A · 分岐数が大きいため木が浅く保たれ、遅いディスク読み込みが減るから
  8. 8. C · O(log n)

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