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

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

  1. ADiziyi yarılara böler ve birleştirir
  2. BHer elemanı kaydırarak büyüyen sıralı bir kısma ekler
  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
2.Kolay

Bir problem genellikle ne zaman "çözülebilir" (tractable) olarak adlandırılır?

  1. AHiç çözümü yoksa
  2. BSabit zamanda çözülebiliyorsa
  3. CPolinom zamanda çözülebiliyorsa
  4. DYalnızca her olasılığı deneyerek çözülebiliyorsa
3.Kolay

Birleştirmeli sıralamanın en kötü durum zaman karmaşıklığı nedir?

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

İkili arama 1,000,000 elemanlı sıralı bir dizide en kötü durumda yaklaşık kaç karşılaştırma gerektirir?

  1. AYaklaşık 100
  2. BYaklaşık 500,000
  3. CYaklaşık 20
  4. DYaklaşık 1,000
5.Orta

Hangi sıralama algoritması kararlıdır?

  1. AYığın sıralaması
  2. BSeçmeli sıralama (tipik sürüm)
  3. CHızlı sıralama (tipik yerinde sürüm)
  4. DBirleştirmeli sıralama
6.Orta

Karşılaştırmaya dayalı sıralama için en kötü durumdaki alt sınır nedir?

  1. AΩ(n log n)
  2. BΩ(n)
  3. CΩ(n²)
  4. DΩ(log n)
7.Zor

P ve NP hakkında hangi ifade doğrudur?

  1. AP ≠ NP olduğu kanıtlanmıştır
  2. BP'deki her problem aynı zamanda NP'dedir
  3. CNP problemlerinin çözümleri hızlıca doğrulanamaz
  4. DNP, "polinom olmayan" (not polynomial) anlamına gelir
8.Zor

Cook–Levin teoremi neyi ortaya koydu?

  1. ADurma probleminin karar verilemez olduğunu
  2. BHer NP probleminin üstel zamanda çözülebileceğini
  3. CBoole sağlanabilirlik probleminin (SAT) NP-tam olduğunu
  4. DP'nin NP'ye eşit olmadığını

Cevap anahtarı

  1. 1. D · Sıralanmamış kısmın en küçüğünü tekrar tekrar bulur ve öne yerleştirir
  2. 2. C · Polinom zamanda çözülebiliyorsa
  3. 3. B · O(n log n)
  4. 4. C · Yaklaşık 20
  5. 5. D · Birleştirmeli sıralama
  6. 6. A · Ω(n log n)
  7. 7. B · P'deki her problem aynı zamanda NP'dedir
  8. 8. C · Boole sağlanabilirlik probleminin (SAT) NP-tam olduğunu

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