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

log₂ 1024 kaçtır?

  1. A10
  2. B12
  3. C512
  4. D32
2.Kolay

Büyük n için hangi karmaşıklık sınıfı en hızlı büyür?

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

Özyineleme nedir?

  1. ABir veri yapısı türü
  2. BBir sıralama yöntemi
  3. CHiç bitmeyen bir döngü
  4. DKendisini daha küçük girdilerle çağıran bir fonksiyon
4.Orta

Floyd–Warshall algoritması neyi ve ne kadar hızlı hesaplar?

  1. ATek bir kaynak düğümden diğer tüm düğümlere en kısa yolları O(V + E)'de
  2. BTüm düğüm çiftleri arasındaki en kısa yolları O(V³)'te
  3. CTopolojik sıralamayı O(V²)'de
  4. DMinimum kapsayan ağacı O(E log V)'de
5.Orta

Negatif olmayan kenar ağırlıklarına sahip bir grafta tek bir kaynaktan en kısa yolları hangi algoritma bulur?

  1. AKruskal algoritması
  2. BDijkstra algoritması
  3. CDerinlik öncelikli arama (DFS)
  4. DHer durumda Bellman–Ford gereklidir
6.Orta

Birçok kütüphane sıralama rutini çok küçük alt diziler için neden eklemeli sıralamaya geçer?

  1. AEklemeli sıralama en kötü durumda O(n log n)'dir
  2. BEklemeli sıralama büyük girdilerde diğer tüm sıralama algoritmalarından daha az bellek kullanır
  3. CEklemeli sıralamanın ek yükü azdır ve küçük veya neredeyse sıralı girdilerde hızlıdır
  4. DÖzyinelemeli algoritmalar 10 elemandan küçük dizileri işleyemez
7.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. AÇünkü n her zaman küçüktür
  2. BÇünkü yalnızca W = 0 için çalışır
  3. CW bir sayıdır, bu yüzden süre W'yi yazmak için kullanılan bit sayısına göre üsteldir
  4. DÇünkü algoritma rastgeleleştirilmiştir ve çalışma süresi her girdide değişir
8.Zor

Şunun zaman karmaşıklığı nedir: for i = 1 to n: for (j = i; j ≤ n; j = j + i) O(1) iş yap?

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

Cevap anahtarı

  1. 1. A · 10
  2. 2. D · O(2ⁿ)
  3. 3. D · Kendisini daha küçük girdilerle çağıran bir fonksiyon
  4. 4. B · Tüm düğüm çiftleri arasındaki en kısa yolları O(V³)'te
  5. 5. B · Dijkstra algoritması
  6. 6. C · Eklemeli sıralamanın ek yükü azdır ve küçük veya neredeyse sıralı girdilerde hızlıdır
  7. 7. C · W bir sayıdır, bu yüzden süre W'yi yazmak için kullanılan bit sayısına göre üsteldir
  8. 8. A · O(n log n)

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