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

Hangi sıralama algoritması yanlış sırada olan komşu elemanların yerini tekrar tekrar değiştirir?

  1. ABirleştirmeli sıralama (merge sort)
  2. BYığın sıralaması (heap sort)
  3. CHızlı sıralama (quicksort)
  4. DKabarcık sıralaması (bubble sort)
2.Kolay

Bir algoritmanın en kötü durum çalışma süresi neyi tanımlar?

  1. An boyutundaki rastgele bir girdide beklenen süreyi
  2. BEn küçük girdide aldığı süreyi
  3. CYavaş bir bilgisayarda aldığı süreyi
  4. Dn boyutundaki tüm girdiler üzerinden aldığı en uzun süreyi
3.Kolay

Özyineleme nedir?

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

Açgözlü (greedy) bir algoritma:

  1. AOlası her çözümü dener
  2. BHer adımda yerel olarak en iyi seçimi yapar
  3. CYalnızca özyineleme kullanır
  4. DHer zaman optimal çözümü verir
5.Orta

V düğümlü ve E kenarlı bir çizgede Bellman–Ford algoritmasının zaman karmaşıklığı nedir?

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

Hızlı sıralamanın (quicksort) en kötü durum zaman karmaşıklığı nedir?

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

Hangi teknik, hızlı sıralama için her girdide beklenen O(n log n) çalışma süresini sağlar?

  1. AHer zaman ilk elemanı seçmek
  2. BÖzyinelemeyi yalnızca sol tarafta kullanmak
  3. CPivotu düzgün dağılımla rastgele seçmek
  4. DHızlı sıralamayı çalıştırmadan önce girdiyi sıralamak

Cevap anahtarı

  1. 1. D · Kabarcık sıralaması (bubble sort)
  2. 2. D · n boyutundaki tüm girdiler üzerinden aldığı en uzun süreyi
  3. 3. A · Kendisini daha küçük girdilerle çağıran bir fonksiyon
  4. 4. B · Her adımda yerel olarak en iyi seçimi yapar
  5. 5. C · O(V × E)
  6. 6. C · O(n²)
  7. 7. A · Θ(n³)
  8. 8. C · Pivotu düzgün dağılımla rastgele seçmek

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