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

Eklemeli sıralamanın (insertion sort) en kötü durum zaman karmaşıklığı nedir?

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

Seçmeli sıralama (selection sort) nasıl çalışır?

  1. ADiziyi yarılara böler ve birleştirir
  2. BHer elemanı kaydırarak büyüyen sıralı bir kısma ekler
  3. CSıralanmamış kısmın en küçüğünü tekrar tekrar bulur ve öne yerleştirir
  4. DYanlış sırada olan komşu elemanların yerini tekrar tekrar değiştirir
3.Kolay

Komşuluk listeleriyle saklanan bir çizgede derinlik öncelikli aramanın zaman karmaşıklığı nedir?

  1. AO(V + E)
  2. BO(E log V)
  3. CO(V²)
  4. DO(V × E)
4.Orta

Amortize analiz neyi ölçer?

  1. ABir algoritmanın en iyi girdideki maliyetini
  2. BDizideki herhangi bir yerde bulunan en pahalı tek işlemin maliyetini
  3. CEn kötü durumdaki bir işlem dizisi üzerinden işlem başına ortalama maliyeti
  4. DRastgele girdiler üzerinden beklenen maliyeti
5.Orta

T(n) = 2T(n/2) + O(1) yinelemesinin çözümü nedir?

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

Basit özyinelemeli faktöriyel fonksiyonu fact(n) = n × fact(n − 1) ne kadar yığın (stack) alanı kullanır?

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

V düğümlü ve E kenarlı bir çizgede ikili yığınla Dijkstra algoritmasının çalışma süresi nedir?

  1. AO(V³)
  2. BO(V + E)
  3. CO(V × E)
  4. DO((V + E) log V)
8.Zor

22n, O(2ⁿ) içinde midir?

  1. AHayır, çünkü 22n = 4ⁿ ve 4ⁿ / 2ⁿ = 2ⁿ sınırsız büyür
  2. BEvet, çünkü üsteki sabit çarpanlar Büyük O'da her zaman göz ardı edilir
  3. CHayır, çünkü 22n, 2ⁿ'den daha yavaş büyür
  4. DEvet, çünkü ikisi de üsteldir

Cevap anahtarı

  1. 1. B · O(n²)
  2. 2. C · Sıralanmamış kısmın en küçüğünü tekrar tekrar bulur ve öne yerleştirir
  3. 3. A · O(V + E)
  4. 4. C · En kötü durumdaki bir işlem dizisi üzerinden işlem başına ortalama maliyeti
  5. 5. A · O(n)
  6. 6. C · O(n)
  7. 7. D · O((V + E) log V)
  8. 8. A · Hayır, çünkü 22n = 4ⁿ ve 4ⁿ / 2ⁿ = 2ⁿ sınırsız büyür

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