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

n sayıdan oluşan sırasız bir dizide en büyük değeri bulmanın zaman karmaşıklığı nedir?

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

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

  1. APolinom zamanda çözülebiliyorsa
  2. BHiç çözümü yoksa
  3. CYalnızca her olasılığı deneyerek çözülebiliyorsa
  4. DSabit zamanda çözülebiliyorsa
3.Kolay

Bir işlemin O(1) zamanda çalışması ne anlama gelir?

  1. AÇalışma süresinin saniyesi başına tam olarak bir eleman işler
  2. BYalnızca bir kez çalıştırılabilir
  3. CHer zaman tam olarak bir saniye sürer
  4. DÇalışma süresi girdi boyutuyla büyümez
4.Orta

İki n × n matrisi standart üçlü döngüyle çarpmanın zaman karmaşıklığı nedir?

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

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

  1. AÖrtüşen alt problemler ve optimal alt yapı
  2. BYalnızca rastgele girdiler
  3. CHiç alt problem olmaması; bu yüzden tek adımda çözülebilir
  4. DTek bir döngü
6.Orta

Şunun zaman karmaşıklığı nedir: for i = 1 to n: for j = 1 to i: O(1) iş yap?

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

Dinamik programlama ile çözülen 0/1 sırt çantası problemi O(nW) zaman alır. Buna neden sözde polinom (pseudo-polynomial) denir?

  1. AÇünkü algoritma rastgeleleştirilmiştir ve çalışma süresi her girdide değişir
  2. BW bir sayıdır, bu yüzden süre W'yi yazmak için kullanılan bit sayısına göre üsteldir
  3. CÇünkü yalnızca W = 0 için çalışır
  4. DÇünkü n her zaman küçüktür
8.Zor

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

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

Cevap anahtarı

  1. 1. B · O(n)
  2. 2. A · Polinom zamanda çözülebiliyorsa
  3. 3. D · Çalışma süresi girdi boyutuyla büyümez
  4. 4. B · O(n³)
  5. 5. A · Örtüşen alt problemler ve optimal alt yapı
  6. 6. D · O(n²)
  7. 7. B · W bir sayıdır, bu yüzden süre W'yi yazmak için kullanılan bit sayısına göre üsteldir
  8. 8. C · n!, 2ⁿ'den daha hızlı büyür

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