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

Özyinelemeli bir fonksiyonun temel durumu nedir?

  1. AEn büyük girdiye sahip durum; herhangi bir özyinelemeli çağrıdan önce ele alınır
  2. BFonksiyonun ilk satırı
  3. CEn fazla bellek kullanan çağrı
  4. DYeni bir özyinelemeli çağrı yapmadan doğrudan yanıtlanan bir durum
2.Kolay

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

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

log₂ 1024 kaçtır?

  1. A512
  2. B32
  3. C12
  4. D10
4.Orta

Basit özyinelemeli faktöriyel fonksiyonu fact(n) = n × fact(n − 1) ne kadar yığın (stack) alanı kullanır?

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

İkili arama 1,000,000 elemanlı sıralı bir dizide en kötü durumda yaklaşık kaç karşılaştırma gerektirir?

  1. AYaklaşık 1,000
  2. BYaklaşık 100
  3. CYaklaşık 20
  4. DYaklaşık 500,000
6.Orta

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

  1. AO(1)
  2. BO(log n)
  3. CO(n log 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ü n her zaman küçüktür
  4. DÇünkü yalnızca W = 0 için çalışır
8.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 log n)
  2. BΘ(n³)
  3. CΘ(n²)
  4. DΘ(n² log n)

Cevap anahtarı

  1. 1. D · Yeni bir özyinelemeli çağrı yapmadan doğrudan yanıtlanan bir durum
  2. 2. C · Polinom zamanda çözülebiliyorsa
  3. 3. D · 10
  4. 4. A · O(n)
  5. 5. C · Yaklaşık 20
  6. 6. B · O(log 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. B · Θ(n³)

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