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

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

  1. AAçgözlü seçim
  2. BBöl ve yönet
  3. CKaba kuvvet
  4. DDinamik programlama
2.Kolay

n sayıdan oluşan sırasız bir dizide en büyük değeri bulmanın zaman karmaşıklığı nedir?

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

Komşuluk listeleriyle saklanan bir çizgede derinlik öncelikli aramanın zaman karmaşıklığı nedir?

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

Bir problemin optimal alt yapıya sahip olması ne anlama gelir?

  1. AProblem sabit zamanda çözülebilir
  2. BOptimal bir çözüm, alt problemlerinin optimal çözümlerinden oluşturulabilir
  3. CHer alt problem aynı boyuttadır
  4. DProblemin tam olarak bir optimal çözümü vardır ve bu çözümü her alt problem paylaşır
5.Orta

Sıralı bir dizide her iki uçtan birer işaretçiyi içeri doğru hareket ettirerek toplamı bir hedefe eşit olan iki eleman arıyorsunuz. Zaman karmaşıklığı nedir?

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

Hızlı sıralama pivot olarak her zaman ilk elemanı kullanıyor. Hangi girdide en kötü durum davranışını gösterir?

  1. ATüm elemanları farklı olan bir dizide
  2. BUzunluğu 2 olan bir dizide
  3. CRastgele sıralı bir dizide
  4. DZaten sıralı bir dizide
7.Zor

Cook–Levin teoremi neyi ortaya koydu?

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

Büyük n için n! ve 2ⁿ nasıl karşılaştırılır?

  1. AAynı hızda büyürler
  2. B2ⁿ, n!'den daha hızlı büyür
  3. Cn!, O(n²)'dir
  4. Dn!, 2ⁿ'den daha hızlı büyür

Cevap anahtarı

  1. 1. B · Böl ve yönet
  2. 2. B · O(n)
  3. 3. A · O(V + E)
  4. 4. B · Optimal bir çözüm, alt problemlerinin optimal çözümlerinden oluşturulabilir
  5. 5. C · O(n)
  6. 6. D · Zaten sıralı bir dizide
  7. 7. C · Boole sağlanabilirlik probleminin (SAT) NP-tam olduğunu
  8. 8. D · n!, 2ⁿ'den daha hızlı büyür

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