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

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

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

O(2ⁿ) büyümeye ne ad verilir?

  1. ALogaritmik
  2. BPolinom
  3. CDoğrusal
  4. DÜstel
3.Kolay

Bir döngü i = 1 ile başlar ve i > n olana kadar her yinelemede i'yi iki katına çıkarır. Kaç yineleme çalışır?

  1. AYaklaşık log₂ n
  2. BYaklaşık n / 2
  3. CYaklaşık n²
  4. DYaklaşık n
4.Orta

Prim algoritması minimum kapsayan ağacı nasıl oluşturur?

  1. ABir başlangıç düğümünden tek bir ağaç büyütür ve ağaçtan çıkan en ucuz kenarı ekler
  2. BDöngü kalmayana kadar en pahalı kenarı çıkarır
  3. CGenişlik öncelikli arama çalıştırır ve BFS ağacını tutar
  4. DTüm kenarları ağırlığa göre sıralar ve ormanda döngü oluşturmayacaksa her birini ekler
5.Orta

T(n) = 2T(n/2) + O(n) yineleme bağıntısının çözümü nedir?

  1. AO(n log n)
  2. BO(log n)
  3. CO(n)
  4. DO(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 az çakışması olan etkinliği seç, sonra uyumlu olanlarla tekrarla
  2. BÖnce en kısa etkinliği seç
  3. CEn erken biten etkinliği seç, sonra uyumlu olanlarla tekrarla
  4. DEn erken başlayan etkinliği seç
7.Zor

Eklemeli sıralama sıralı girdide O(n)'de çalışır. Bu, karşılaştırmalı sıralama için Ω(n log n) alt sınırıyla çelişir mi?

  1. AEvet, ama yalnızca 100'den kısa diziler için
  2. BEvet, dolayısıyla alt sınır yanlıştır
  3. CHayır, çünkü eklemeli sıralama bir karşılaştırmalı sıralama değildir
  4. DHayır, alt sınır her girdiye değil, tüm girdiler üzerinden en kötü duruma uygulanır
8.Zor

Yeni bir X probleminin NP-zor olduğunu göstermek için ne yapmalısınız?

  1. AX'in küçük girdiler için polinom algoritması olmadığını göstermek
  2. BX'in polinom zamanda doğrulanabildiğini göstermek
  3. CBilinen bir NP-zor problemi polinom zamanda X'e indirgemek
  4. DX'i polinom zamanda bilinen bir NP-zor probleme indirgemek

Cevap anahtarı

  1. 1. C · O(1)
  2. 2. D · Üstel
  3. 3. A · Yaklaşık log₂ n
  4. 4. A · Bir başlangıç düğümünden tek bir ağaç büyütür ve ağaçtan çıkan en ucuz kenarı ekler
  5. 5. A · O(n log n)
  6. 6. C · En erken biten etkinliği seç, sonra uyumlu olanlarla tekrarla
  7. 7. D · Hayır, alt sınır her girdiye değil, tüm girdiler üzerinden en kötü duruma uygulanır
  8. 8. C · Bilinen bir NP-zor problemi polinom zamanda X'e indirgemek

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