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

Hangi gösterim büyüme için bir üst sınırı tanımlar?

  1. AKüçük omega
  2. BBüyük O
  3. CBüyük Omega
  4. DBüyük Teta
2.Kolay

Özyinelemeli bir fonksiyonun temel durumu nedir?

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

log₂ 1024 kaçtır?

  1. A32
  2. B512
  3. C12
  4. D10
4.Orta

Şunun zaman karmaşıklığı nedir: for i = 1 to n: (j = 1; while j < n: j = j × 2)?

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

Hızlı sıralamanın (quicksort) en kötü durum zaman karmaşıklığı nedir?

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

Etkinlik seçimi probleminde hangi açgözlü kural her zaman çakışmayan en fazla sayıda etkinliği verir?

  1. AÖnce en kısa etkinliği seç
  2. BEn erken biten etkinliği seç, sonra uyumlu olanlarla tekrarla
  3. CEn erken başlayan etkinliği seç
  4. DÖnce en az çakışması olan etkinliği seç, sonra uyumlu olanlarla tekrarla
7.Zor

Küçük o gösterimi hakkında hangi ifade doğrudur?

  1. An = o(n²)'dir, ama n, o(n) değildir
  2. Bn = o(n), çünkü her fonksiyon kendisinin küçük o'sudur
  3. Cn² = o(n)
  4. D2n = o(n), çünkü 2n yavaş büyür
8.Zor

P sınıfının hangi tanımı doğrudur?

  1. AÇözümleri kontrol edilebilen ama polinom zamanda asla bulunamayan problemler
  2. BParalel olarak çözülebilen problemler
  3. CDeterministik bir algoritmayla polinom zamanda çözülebilen karar problemleri
  4. DHer bilgisayarda üstel zaman gerektiren problemler

Cevap anahtarı

  1. 1. B · Büyük O
  2. 2. C · Yeni bir özyinelemeli çağrı yapmadan doğrudan yanıtlanan bir durum
  3. 3. D · 10
  4. 4. A · O(n log n)
  5. 5. B · O(n²)
  6. 6. B · En erken biten etkinliği seç, sonra uyumlu olanlarla tekrarla
  7. 7. A · n = o(n²)'dir, ama n, o(n) değildir
  8. 8. C · Deterministik bir algoritmayla polinom zamanda çözülebilen karar problemleri

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