Cevaplı Algoritmalar ve karmaşıklık çalışma kâğıdı

Ücretsiz yazdırılabilir Algoritmalar ve karmaşıklık çalışma kâğıdı: kolaydan sınav düzeyine 8 soru ve cevap anahtarı. Yazdırın ya da PDF olarak kaydedin.

Yeni çalışma kâğıdıİpuçlarıyla çevrimiçi çalışın

Öğretmenler için: sınıfta ücretsiz yazdırılabilir, çoğaltılabilir ve kullanılabilir. Her yeni çalışma kâğıdında yeni değerler ve kendi cevap anahtarı vardır. Ders sayfanızda ExamProblems bağlantısı vermeniz bizi memnun eder.

Ad: ____________________   Tarih: ____________

1.Kolay

log₂ 1024 kaçtır?

  1. A10
  2. B512
  3. C12
  4. D32
2.Kolay

Bir problem genellikle ne zaman "çözülebilir" (tractable) olarak adlandırılır?

  1. ASabit zamanda çözülebiliyorsa
  2. BHiç çözümü yoksa
  3. CPolinom zamanda çözülebiliyorsa
  4. DYalnızca her olasılığı deneyerek çözülebiliyorsa
3.Kolay

Zaten sıralı bir dizide eklemeli sıralamanın en iyi durum zaman karmaşıklığı nedir?

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

Saf özyinelemeli Fibonacci'nin (fib(n) = fib(n−1) + fib(n−2)) zaman karmaşıklığı nedir?

  1. ADoğrusal
  2. BSabit
  3. CÜstel
  4. DLogaritmik
5.Orta

T(n) = 2T(n/2) + O(1) yinelemesinin çözümü nedir?

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

T(n) = 2T(n − 1) + O(1) yinelemesinin çözümü nedir?

  1. AO(n)
  2. BO(n log n)
  3. CO(n²)
  4. DO(2ⁿ)
7.Zor

Durma problemi neyi gösterir?

  1. AHer program eninde sonunda durur
  2. BHiçbir algoritma her program ve girdi için programın durup durmayacağına karar veremez
  3. CBazı programlar daha hızlı bilgisayarlarda daha hızlı çalışır, bu yüzden durma donanıma bağlıdır
  4. DDöngülerden kaçınılmalıdır
8.Zor

Bu sağlanabilirlik problemlerinden hangisinin polinom zamanda çözülebildiği bilinmektedir?

  1. ADevre sağlanabilirliği
  2. BHer yan tümcenin en fazla iki literal içerdiği 2-SAT
  3. CBirleşimli normal biçimdeki formüller üzerinde genel SAT
  4. DHer yan tümcenin tam olarak üç literal içerdiği 3-SAT

Cevap anahtarı

  1. 1. A · 10
  2. 2. C · Polinom zamanda çözülebiliyorsa
  3. 3. B · O(n)
  4. 4. C · Üstel
  5. 5. B · O(n)
  6. 6. D · O(2ⁿ)
  7. 7. B · Hiçbir algoritma her program ve girdi için programın durup durmayacağına karar veremez
  8. 8. B · Her yan tümcenin en fazla iki literal içerdiği 2-SAT

Tam adım adım çözümler: bu konuyu examproblems.com’da çalışın.