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

O(n²) bir algoritma n = 1000 için 1 saniye sürüyor. n = 2000 için yaklaşık ne kadar sürer?

  1. A1 saniye
  2. B2 saniye
  3. C8 saniye
  4. D4 saniye
2.Kolay

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

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

Her biri n kez çalışan iç içe iki döngüye sahip bir algoritma genellikle hangi karmaşıklığa sahiptir?

  1. AO(n²)
  2. BO(n)
  3. CO(log n)
  4. DO(2n)
4.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 büyük girdilerde diğer tüm sıralama algoritmalarından daha az bellek kullanır
  2. BÖzyinelemeli algoritmalar 10 elemandan küçük dizileri işleyemez
  3. CEklemeli sıralama en kötü durumda O(n log n)'dir
  4. DEklemeli sıralamanın ek yükü azdır ve küçük veya neredeyse sıralı girdilerde hızlıdır
5.Orta

Ulaşılabilir bir temel durumu olmayan özyinelemeli bir fonksiyon hakkında hangi ifade doğrudur?

  1. AO(1) zamanda çalışır
  2. BDerleyici onu her zaman güvenli biçimde sonlanan bir döngüye dönüştürür
  3. CÇağrı yığını taşana kadar kendini çağırmaya devam eder
  4. DOtomatik olarak 0 döndürür
6.Orta

m ve n uzunluğundaki dizgilerin en uzun ortak alt dizisi için standart dinamik programlama algoritmasının zaman karmaşıklığı nedir?

  1. AO(mn)
  2. BO(2m+n)
  3. CO(m + n)
  4. DO(mn log n)
7.Zor

Yalnızca son iki değeri tutan bir döngüyle n. Fibonacci sayısını hesaplamanın zaman ve alan maliyetleri nedir?

  1. AO(2ⁿ) zaman ve O(1) alan
  2. BO(n) zaman ve O(n) alan
  3. CO(n) zaman ve O(1) alan
  4. DO(log n) zaman ve O(n) alan
8.Zor

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

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

Cevap anahtarı

  1. 1. D · 4 saniye
  2. 2. D · Sıralanmamış kısmın en küçüğünü tekrar tekrar bulur ve öne yerleştirir
  3. 3. A · O(n²)
  4. 4. D · Eklemeli sıralamanın ek yükü azdır ve küçük veya neredeyse sıralı girdilerde hızlıdır
  5. 5. C · Çağrı yığını taşana kadar kendini çağırmaya devam eder
  6. 6. A · O(mn)
  7. 7. C · O(n) zaman ve O(1) alan
  8. 8. B · Bir düğüm çıkarıldığında kesinleşir, ama sonraki bir negatif kenar ona yine de daha kısa bir yol verebilir

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