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

Bu çalışma sürelerinden hangisi polinomdur?

  1. AO(n³)
  2. BO(2ⁿ)
  3. CO(nⁿ)
  4. DO(n!)
2.Kolay

f(n) = Θ(g(n)) ne anlama gelir?

  1. Af, g'den kesinlikle daha hızlı büyür
  2. Bf, g'den kesinlikle daha yavaş büyür
  3. Cf, g ile aynı hızda büyür; yukarıdan ve aşağıdan g'nin sabit katlarıyla sınırlıdır
  4. Df her n için her zaman g'den küçüktür, yani g onu yukarıdan sınırlar ama aşağıdan asla sınırlamaz
3.Kolay

Bir dizide indeksle bir elemana erişmenin karmaşıklığı nedir?

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

Hızlı sıralama pivot olarak her zaman ilk elemanı kullanıyor. Hangi girdide en kötü durum davranışını gösterir?

  1. ARastgele sıralı bir dizide
  2. BTüm elemanları farklı olan bir dizide
  3. CZaten sıralı bir dizide
  4. DUzunluğu 2 olan bir dizide
5.Orta

O(log n)'de olduğu gibi, Büyük O'da logaritmanın tabanı neden genellikle yazılmaz?

  1. ABilgisayar bilimindeki tüm logaritmaların tabanı 10'dur, bu yüzden zımnen bellidir
  2. BLogaritmalar her zaman tamsayılara yuvarlanır
  3. CFarklı tabanlı logaritmalar yalnızca sabit bir çarpan kadar farklıdır
  4. DTaban yalnızca küçük n için önemlidir
6.Orta

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

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

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

  1. APolinom olmayan problemler
  2. BEvet yanıtları bir sertifika verildiğinde polinom zamanda doğrulanabilen karar problemleri
  3. CHiçbir algoritmanın çözemeyeceği problemler
  4. DPolinom zamanda çözülemeyen problemler
8.Zor

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

  1. AHer yan tümcenin tam olarak üç literal içerdiği 3-SAT
  2. BHer yan tümcenin en fazla iki literal içerdiği 2-SAT
  3. CBirleşimli normal biçimdeki formüller üzerinde genel SAT
  4. DDevre sağlanabilirliği

Cevap anahtarı

  1. 1. A · O(n³)
  2. 2. C · f, g ile aynı hızda büyür; yukarıdan ve aşağıdan g'nin sabit katlarıyla sınırlıdır
  3. 3. C · O(1)
  4. 4. C · Zaten sıralı bir dizide
  5. 5. C · Farklı tabanlı logaritmalar yalnızca sabit bir çarpan kadar farklıdır
  6. 6. B · O(n log n)
  7. 7. B · Evet yanıtları bir sertifika verildiğinde polinom zamanda doğrulanabilen karar problemleri
  8. 8. B · Her yan tümcenin en fazla iki literal içerdiği 2-SAT

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