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 elemanlı sırasız bir dizide doğrusal aramanın zaman karmaşıklığı (en kötü durumda) nedir?

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

Alan karmaşıklığı neyi ölçer?

  1. AProgramın derlendikten sonraki dosyasının disk alanını
  2. BKod satırı sayısını
  3. CGirdi büyüdükçe bir algoritmanın ihtiyaç duyduğu bellek miktarını
  4. DBilgisayarın fiziksel boyutunu
3.Kolay

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

  1. AΩ (Büyük Omega)
  2. Bo (küçük o)
  3. CO (Büyük O)
  4. DΘ (Büyük Teta)
4.Orta

Saf özyinelemeli Fibonacci'nin (fib(n) = fib(n−1) + fib(n−2)) zaman karmaşıklığı nedir?

  1. ASabit
  2. BLogaritmik
  3. CÜstel
  4. DDoğrusal
5.Orta

Hangi sıralama algoritması kararlıdır?

  1. AYığın sıralaması
  2. BHızlı sıralama (tipik yerinde sürüm)
  3. CSeçmeli sıralama (tipik sürüm)
  4. DBirleştirmeli sıralama
6.Orta

O(n²) bir algoritmanın aynı zamanda O(n³) olduğunu söylemek doğru mudur?

  1. AEvet, ama yalnızca n 100'den küçükse
  2. BHayır, çünkü Büyük O her zaman fonksiyonun tam büyüme hızını belirtmelidir
  3. CHayır, çünkü büyük n için n³, n²'den küçüktür
  4. DEvet, çünkü Büyük O bir üst sınırdır ve n², n³'ten daha hızlı büyümez
7.Zor

Bu sağlanabilirlik problemlerinden hangisinin polinom zamanda çözülebildiği bilinmektedir?

  1. AHer yan tümcenin en fazla iki literal içerdiği 2-SAT
  2. BDevre sağlanabilirliği
  3. CHer yan tümcenin tam olarak üç literal içerdiği 3-SAT
  4. DBirleşimli normal biçimdeki formüller üzerinde genel SAT
8.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. AW bir sayıdır, bu yüzden süre W'yi yazmak için kullanılan bit sayısına göre üsteldir
  2. BÇünkü algoritma rastgeleleştirilmiştir ve çalışma süresi her girdide değişir
  3. CÇünkü n her zaman küçüktür
  4. DÇünkü yalnızca W = 0 için çalışır

Cevap anahtarı

  1. 1. A · O(n)
  2. 2. C · Girdi büyüdükçe bir algoritmanın ihtiyaç duyduğu bellek miktarını
  3. 3. A · Ω (Büyük Omega)
  4. 4. C · Üstel
  5. 5. D · Birleştirmeli sıralama
  6. 6. D · Evet, çünkü Büyük O bir üst sınırdır ve n², n³'ten daha hızlı büyümez
  7. 7. A · Her yan tümcenin en fazla iki literal içerdiği 2-SAT
  8. 8. A · W bir sayıdır, bu yüzden süre W'yi yazmak için kullanılan bit sayısına göre üsteldir

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