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

Memoizasyon nedir?

  1. AÖzyinelemeyi, çağrı yığınına gerek kalmayacak biçimde eşdeğer bir döngüye otomatik olarak dönüştürmek
  2. BHer kod satırının yanına yorum yazmak
  3. CFonksiyon çağrılarının sonuçlarını saklayarak tekrarlanan çağrıları bellekten yanıtlamak
  4. DBir fonksiyon döndükten sonra belleği serbest bırakmak
2.Kolay

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

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

Kaba kuvvet algoritması nedir?

  1. ARastgele bir yanıt tahmin eden bir algoritma
  2. BTüm olası aday çözümleri deneyen bir algoritma
  3. CHer zaman özyineleme kullanan bir algoritma
  4. DBirçok işlemci üzerinde çalışan bir algoritma
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 en kötü durumda O(n log n)'dir
  2. BEklemeli sıralamanın ek yükü azdır ve küçük veya neredeyse sıralı girdilerde hızlıdır
  3. CEklemeli sıralama büyük girdilerde diğer tüm sıralama algoritmalarından daha az bellek kullanır
  4. DÖzyinelemeli algoritmalar 10 elemandan küçük dizileri işleyemez
5.Orta

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

  1. AHer adımda yerel olarak en iyi seçimi yapar
  2. BOlası her çözümü dener
  3. CHer zaman optimal çözümü verir
  4. DYalnızca özyineleme kullanır
6.Orta

Prim algoritması minimum kapsayan ağacı nasıl oluşturur?

  1. AGenişlik öncelikli arama çalıştırır ve BFS ağacını tutar
  2. BTüm kenarları ağırlığa göre sıralar ve ormanda döngü oluşturmayacaksa her birini ekler
  3. CBir başlangıç düğümünden tek bir ağaç büyütür ve ağaçtan çıkan en ucuz kenarı ekler
  4. DDöngü kalmayana kadar en pahalı kenarı çıkarır
7.Zor

Eklemeli sıralama sıralı girdide O(n)'de çalışır. Bu, karşılaştırmalı sıralama için Ω(n log n) alt sınırıyla çelişir mi?

  1. AHayır, alt sınır her girdiye değil, tüm girdiler üzerinden en kötü duruma uygulanır
  2. BEvet, dolayısıyla alt sınır yanlıştır
  3. CHayır, çünkü eklemeli sıralama bir karşılaştırmalı sıralama değildir
  4. DEvet, ama yalnızca 100'den kısa diziler için
8.Zor

Bir artırmanın birçok biti değiştirebileceği göz önüne alındığında, ikili bir sayacı artırmanın amortize maliyeti nedir?

  1. AArtırma başına O(log n)
  2. BArtırma başına O(n)
  3. CArtırma başına O(n log n)
  4. DArtırma başına O(1)

Cevap anahtarı

  1. 1. C · Fonksiyon çağrılarının sonuçlarını saklayarak tekrarlanan çağrıları bellekten yanıtlamak
  2. 2. A · O(n²)
  3. 3. B · Tüm olası aday çözümleri deneyen bir algoritma
  4. 4. B · Eklemeli sıralamanın ek yükü azdır ve küçük veya neredeyse sıralı girdilerde hızlıdır
  5. 5. A · Her adımda yerel olarak en iyi seçimi yapar
  6. 6. C · Bir başlangıç düğümünden tek bir ağaç büyütür ve ağaçtan çıkan en ucuz kenarı ekler
  7. 7. A · Hayır, alt sınır her girdiye değil, tüm girdiler üzerinden en kötü duruma uygulanır
  8. 8. D · Artırma başına O(1)

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