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

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

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

Hangi gösterim büyüme için bir üst sınırı tanımlar?

  1. AKüçük omega
  2. BBüyük O
  3. CBüyük Omega
  4. DBüyük Teta
3.Kolay

Standart dizi tabanlı birleştirmeli sıralama ne kadar ek bellek kullanır?

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

Karşılaştırmaya dayalı sıralama için en kötü durumdaki alt sınır nedir?

  1. AΩ(n²)
  2. BΩ(n log n)
  3. CΩ(log n)
  4. DΩ(n)
5.Orta

Ağırlıksız bir grafta genişlik öncelikli arama neyi bulur?

  1. AMinimum kapsayan ağacı
  2. BTüm graflarda bir topolojik sırayı
  3. CBaşlangıç düğümünden kenar sayısı cinsinden en kısa yolları
  4. DNegatif kenar ağırlıkları içeren graflardaki en kısa yolları
6.Orta

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

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

Sıralı bir dizide karşılaştırmaya dayalı her arama neden en kötü durumda Ω(log n) karşılaştırma gerektirir?

  1. AHer karşılaştırma logaritmik zaman alır
  2. Bİkili arama mümkün olan tek algoritmadır ve log₂ n karşılaştırma gerektirir
  3. Cn olası sonucu olan bir karar ağacının derinliği en az log₂ n olmalıdır
  4. DHer eleman en az bir kez karşılaştırılmalıdır
8.Zor

Ana teorem (master theorem) kullanılarak T(n) = 8T(n/2) + O(n²) bağıntısının çözümü nedir?

  1. AΘ(n²)
  2. BΘ(n log n)
  3. CΘ(n² log n)
  4. DΘ(n³)

Cevap anahtarı

  1. 1. D · O(2ⁿ)
  2. 2. B · Büyük O
  3. 3. D · O(n)
  4. 4. B · Ω(n log n)
  5. 5. C · Başlangıç düğümünden kenar sayısı cinsinden en kısa yolları
  6. 6. B · O(n log n)
  7. 7. C · n olası sonucu olan bir karar ağacının derinliği en az log₂ n olmalıdır
  8. 8. D · Θ(n³)

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