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

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

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

O(n²) bir algoritma n = 1000 için 1 saniye sürüyor. n = 2000 için yaklaşık ne kadar sürer?

  1. A4 saniye
  2. B8 saniye
  3. C2 saniye
  4. D1 saniye
3.Kolay

Her biri n kez çalışan iç içe iki döngüye sahip bir algoritma genellikle hangi karmaşıklığa sahiptir?

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

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

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

Aşağıdan yukarıya bir tabloyla n. Fibonacci sayısını hesaplamanın zaman karmaşıklığı nedir?

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

Dinamik programlama, bir problemde hangisi olduğunda yararlıdır?

  1. ATek bir döngü
  2. BYalnızca rastgele girdiler
  3. CÖrtüşen alt problemler ve optimal alt yapı
  4. DHiç alt problem olmaması; bu yüzden tek adımda çözülebilir
7.Zor

Büyük n için n! ve 2ⁿ nasıl karşılaştırılır?

  1. AAynı hızda büyürler
  2. Bn!, O(n²)'dir
  3. Cn!, 2ⁿ'den daha hızlı büyür
  4. D2ⁿ, n!'den daha hızlı büyür
8.Zor

Bazı kenar ağırlıkları negatif olduğunda Dijkstra algoritması neden yanlış sonuçlar verebilir?

  1. AYalnızca yönsüz çizgelerde çalışır
  2. BHer negatif kenarda sonsuz döngüye girer
  3. CBir düğüm çıkarıldığında kesinleşir, ama sonraki bir negatif kenar ona yine de daha kısa bir yol verebilir
  4. DNegatif sayılar bir öncelik kuyruğunda saklanamaz

Cevap anahtarı

  1. 1. C · Polinom zamanda çözülebiliyorsa
  2. 2. A · 4 saniye
  3. 3. B · O(n²)
  4. 4. A · O(log n)
  5. 5. B · O(n)
  6. 6. C · Örtüşen alt problemler ve optimal alt yapı
  7. 7. C · n!, 2ⁿ'den daha hızlı büyür
  8. 8. C · Bir düğüm çıkarıldığında kesinleşir, ama sonraki bir negatif kenar ona yine de daha kısa bir yol verebilir

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