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(2ⁿ)
  2. BO(n³)
  3. CO(n log n)
  4. DO(n²)
2.Kolay

Bu çalışma sürelerinden hangisi polinomdur?

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

Özyineleme nedir?

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

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

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

Dolduğunda kapasitesini iki katına çıkaran dinamik bir dizinin sonuna eleman eklemenin amortize zaman karmaşıklığı nedir?

  1. AO(1)
  2. BO(n²)
  3. CO(n)
  4. DO(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(log n)
  4. DO(n²)
7.Zor

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

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

Bir hash tablosunda arama neden ortalamada O(1), en kötü durumda ise O(n)'dir?

  1. AHash fonksiyonları yavaştır
  2. BDizilere erişim O(n)'dir
  3. CBirçok anahtar çakışarak aynı kovaya düşebilir
  4. DAnahtarların önce sıralanması gerekir

Cevap anahtarı

  1. 1. A · O(2ⁿ)
  2. 2. C · O(n³)
  3. 3. C · Kendisini daha küçük girdilerle çağıran bir fonksiyon
  4. 4. B · O(n²)
  5. 5. A · O(1)
  6. 6. B · O(n)
  7. 7. C · Bir düğüm çıkarıldığında kesinleşir, ama sonraki bir negatif kenar ona yine de daha kısa bir yol verebilir
  8. 8. C · Birçok anahtar çakışarak aynı kovaya düşebilir

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