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

3n² + 5n + 2 ifadesinin Büyük O'su nedir?

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

Zaten sıralı bir dizide eklemeli sıralamanın en iyi durum zaman karmaşıklığı nedir?

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

Özyineleme nedir?

  1. ABir sıralama yöntemi
  2. BHiç bitmeyen bir döngü
  3. CBir veri yapısı türü
  4. DKendisini daha küçük girdilerle çağıran bir fonksiyon
4.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
5.Orta

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

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

Bir problemin optimal alt yapıya sahip olması ne anlama gelir?

  1. AProblem sabit zamanda çözülebilir
  2. BOptimal bir çözüm, alt problemlerinin optimal çözümlerinden oluşturulabilir
  3. CHer alt problem aynı boyuttadır
  4. DProblemin tam olarak bir optimal çözümü vardır ve bu çözümü her alt problem paylaşır
7.Zor

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

  1. APolinom zamanda çözülemeyen 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 olmayan problemler
8.Zor

Bazı kenar ağırlıkları negatif olduğunda Dijkstra algoritması neden yanlış sonuçlar verebilir?

  1. ABir düğüm çıkarıldığında kesinleşir, ama sonraki bir negatif kenar ona yine de daha kısa bir yol verebilir
  2. BNegatif sayılar bir öncelik kuyruğunda saklanamaz
  3. CYalnızca yönsüz çizgelerde çalışır
  4. DHer negatif kenarda sonsuz döngüye girer

Cevap anahtarı

  1. 1. B · O(n²)
  2. 2. A · O(n)
  3. 3. D · Kendisini daha küçük girdilerle çağıran bir fonksiyon
  4. 4. C · Yaklaşık 20
  5. 5. B · O(n²)
  6. 6. B · Optimal bir çözüm, alt problemlerinin optimal çözümlerinden oluşturulabilir
  7. 7. B · Evet yanıtları bir sertifika verildiğinde polinom zamanda doğrulanabilen karar problemleri
  8. 8. A · Bir düğüm çıkarıldığında kesinleşir, ama sonraki bir negatif kenar ona yine de daha kısa bir yol verebilir

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