アルゴリズムと計算量やさしい
増加の上界（upper bound）を表す記法はどれですか？
- ABig Omega
- BLittle omega
- CBig O
- DBig Theta
ヒントを表示
- 「高々」です。
- 誤答を 2 つ消しました。残りの 2 つのうち 1 つが正解です。
答えと解説を表示
これが答えになる理由
O は上界、Ω は下界、Θ はタイトな上下界（tight bound）を表します。
答え
C · Big O
データ構造とアルゴリズム：練習問題と試験問題
オーダー記法（Big-O）、代表的なアルゴリズムの実行時間、配列、連結リスト、木、ハッシュテーブル、グラフの間のトレードオフを扱います。
直前対策パック（PDF）公式集、解法のステップ、完全な解答つきの演習問題。そのまま印刷できます。
この科目のトピック
データ構造とアルゴリズムの試験のコツ
- 入れ子のループでは反復回数を掛け合わせ、順に並んだループでは大きいほうの項を残します。
- 各データ構造について、探索、挿入、削除のコストを覚えましょう。
- 各ステップで入力が半分になるなら、計算時間は対数時間になります。
解答例
データ構造ふつう
二分最小ヒープの extract-min はどのように動作しますか。
- A配列の最後の要素を取り除く
- B最後の要素を根に移し、下へ移動させる（sift down）
- C根を取り除き、すべての要素を 1 つ左にずらす
- Dすべての葉から新しい最小値を探す
ヒントを表示
- 木を完全に保ってから、順序を直します。
- 誤答を 2 つ消しました。残りの 2 つのうち 1 つが正解です。
答えと解説を表示
これが答えになる理由
最後の要素が根の穴を埋め、ヒープ性が成り立つまでより小さい子と交換されます。これには O(log n) かかります。
答え
B · 最後の要素を根に移し、下へ移動させる（sift down）
練習のしかた
- 「この科目を練習する」では、本番の試験のように、すべてのトピックの問題が混ざって出題されます。
- 問題ごとに数値が変わるので、答えではなく解き方が身につきます。
- 行き詰まったら、まず小さなヒントを開き、必要なときだけ詳しい解説を見ましょう。
- 模擬試験には制限時間があり、ヒントはありません。最後にスコアと詳しい振り返りが表示されます。