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

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

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

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

名前: ____________________   日付: ____________

1.やさしい

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

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

グラフにおいて、閉路（cycle）とは何ですか。

  1. A辺をもたない頂点
  2. B同じ頂点から始まり同じ頂点で終わる経路
  3. C重みが 0 の辺
  4. Dすべての頂点を訪問する経路
3.やさしい

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

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

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

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

同じ長さの連結リストを走査するより、配列を走査する方が実際にはずっと速いことが多いのはなぜですか。

  1. A配列の要素は連続しているので、CPU キャッシュを有効に使えるから
  2. B連結リストは常に要素をディスクに格納するから
  3. C配列では値を比較する命令が少なくて済むから
  4. D配列の走査は全体で O(1)、連結リストの走査は O(n) だから
6.ふつう

インデックス 0 から始まる配列に格納された二分ヒープで、インデックス i のノードの親はどこにありますか。

  1. Aインデックス ⌊i / 2⌋ + 1
  2. Bインデックス 2i + 1
  3. Cインデックス ⌊(i − 1) / 2⌋
  4. Dインデックス i − 1
7.むずかしい

標準的なブルームフィルタから、ビットをクリアするだけで要素を削除できないのはなぜですか。

  1. Aブルームフィルタのビットは作成後に変更できないから
  2. B削除すると偽陽性率が 100% に上がるから
  3. Cそれらのビットは他の要素にも属している可能性があり、偽陰性を引き起こすから
  4. Dブルームフィルタは要素全体を格納しており、いったんハッシュ化されると再び見つけられないから
8.むずかしい

ある AVL ノードは、その左の子の右部分木が高くなりすぎたために平衡が崩れています（左右の場合）。どのような修正が適用されますか。

  1. Aそのノードで 1 回の左回転
  2. B左の子で左回転し、次にそのノードで右回転
  3. Cそのノードで 1 回の右回転
  4. D左の子で右回転し、次にそのノードで左回転

解答

  1. 1. C · null（ノードなし）
  2. 2. B · 同じ頂点から始まり同じ頂点で終わる経路
  3. 3. C · データと次のノードへの参照
  4. 4. C · O(1)
  5. 5. A · 配列の要素は連続しているので、CPU キャッシュを有効に使えるから
  6. 6. C · インデックス ⌊(i − 1) / 2⌋
  7. 7. C · それらのビットは他の要素にも属している可能性があり、偽陰性を引き起こすから
  8. 8. B · 左の子で左回転し、次にそのノードで右回転

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