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

f(n) = Θ(g(n)) ne anlama gelir?

  1. Af, g'den kesinlikle daha hızlı büyür
  2. Bf, g ile aynı hızda büyür; yukarıdan ve aşağıdan g'nin sabit katlarıyla sınırlıdır
  3. Cf her n için her zaman g'den küçüktür, yani g onu yukarıdan sınırlar ama aşağıdan asla sınırlamaz
  4. Df, g'den kesinlikle daha yavaş büyür
2.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. BFonksiyon çağrılarının sonuçlarını saklayarak tekrarlanan çağrıları bellekten yanıtlamak
  3. CHer kod satırının yanına yorum yazmak
  4. DBir fonksiyon döndükten sonra belleği serbest bırakmak
3.Kolay

Birleştirmeli sıralama hangi tasarım stratejisini kullanır?

  1. AKaba kuvvet
  2. BBöl ve yönet
  3. CDinamik programlama
  4. DAçgözlü seçim
4.Orta

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

  1. AO(log n)
  2. BO(1)
  3. CO(n²)
  4. DO(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. CNegatif kenar ağırlıkları içeren graflardaki en kısa yolları
  4. DBaşlangıç düğümünden kenar sayısı cinsinden en kısa yolları
6.Orta

Birçok kütüphane sıralama rutini çok küçük alt diziler için neden eklemeli sıralamaya geçer?

  1. AÖzyinelemeli algoritmalar 10 elemandan küçük dizileri işleyemez
  2. BEklemeli sıralama büyük girdilerde diğer tüm sıralama algoritmalarından daha az bellek kullanır
  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
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 eleman en az bir kez karşılaştırılmalıdı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 karşılaştırma logaritmik zaman alır
8.Zor

Biri NP-tam bir problem için polinom zamanlı bir algoritma bulsaydı ne sonuç çıkardı?

  1. ADurma problemi karar verilebilir hâle gelirdi
  2. BTüm üstel zamanlı algoritmalar hemen doğrusal zamanda çalışırdı
  3. CNP'deki her problem polinom zamanda çözülebilirdi, yani P = NP
  4. DYalnızca o problem P'ye geçerdi

Cevap anahtarı

  1. 1. B · f, g ile aynı hızda büyür; yukarıdan ve aşağıdan g'nin sabit katlarıyla sınırlıdır
  2. 2. B · Fonksiyon çağrılarının sonuçlarını saklayarak tekrarlanan çağrıları bellekten yanıtlamak
  3. 3. B · Böl ve yönet
  4. 4. B · O(1)
  5. 5. D · Başlangıç düğümünden kenar sayısı cinsinden en kısa yolları
  6. 6. D · Eklemeli sıralamanın ek yükü azdır ve küçük veya neredeyse sıralı girdilerde hızlıdır
  7. 7. C · n olası sonucu olan bir karar ağacının derinliği en az log₂ n olmalıdır
  8. 8. C · NP'deki her problem polinom zamanda çözülebilirdi, yani P = NP

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