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

O(2ⁿ) büyümeye ne ad verilir?

  1. AÜstel
  2. BDoğrusal
  3. CLogaritmik
  4. DPolinom
2.Kolay

Bir döngü i = 1 ile başlar ve i > n olana kadar her yinelemede i'yi iki katına çıkarır. Kaç yineleme çalışır?

  1. AYaklaşık n / 2
  2. BYaklaşık log₂ n
  3. CYaklaşık n²
  4. DYaklaşık n
3.Kolay

Büyük n için hangi karmaşıklık sınıfı en hızlı büyür?

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

1, 3 ve 4 değerinde madeni paralarla 6 tutarı için açgözlü "önce en büyük para" yöntemi optimuma kıyasla kaç para kullanır?

  1. AAçgözlü 4 para kullanır; optimum 3'tür
  2. BAçgözlü 3 para kullanır; optimum 3'tür
  3. CAçgözlü 3 para kullanır; optimum 2'dir
  4. DAçgözlü 2 para kullanır; optimum 2'dir
5.Orta

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

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

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

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

Ana teorem (master theorem) kullanılarak T(n) = 8T(n/2) + O(n²) bağıntısının çözümü nedir?

  1. AΘ(n³)
  2. BΘ(n² log n)
  3. CΘ(n²)
  4. DΘ(n log n)
8.Zor

P ve NP hakkında hangi ifade doğrudur?

  1. AP ≠ NP olduğu kanıtlanmıştır
  2. BP'deki her problem aynı zamanda NP'dedir
  3. CNP, "polinom olmayan" (not polynomial) anlamına gelir
  4. DNP problemlerinin çözümleri hızlıca doğrulanamaz

Cevap anahtarı

  1. 1. A · Üstel
  2. 2. B · Yaklaşık log₂ n
  3. 3. B · O(2ⁿ)
  4. 4. C · Açgözlü 3 para kullanır; optimum 2'dir
  5. 5. C · O(log n)
  6. 6. A · O(n²)
  7. 7. A · Θ(n³)
  8. 8. B · P'deki her problem aynı zamanda NP'dedir

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