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

Hangi gösterim büyüme için bir alt sınırı tanımlar?

  1. AO (Büyük O)
  2. BΘ (Büyük Teta)
  3. CΩ (Büyük Omega)
  4. Do (küçük o)
2.Kolay

Bir döngü i = 1 ile başlar ve i > n olana kadar her yinelemede i'yi iki katına çıkarır. Kaç yineleme çalışır?

  1. AYaklaşık n
  2. BYaklaşık log₂ n
  3. CYaklaşık n²
  4. DYaklaşık n / 2
3.Kolay

Hangi gösterim büyüme için bir üst sınırı tanımlar?

  1. AKüçük omega
  2. BBüyük Teta
  3. CBüyük Omega
  4. DBüyük O
4.Orta

V düğümlü ve E kenarlı bir çizgede Bellman–Ford algoritmasının zaman karmaşıklığı nedir?

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

n elemanlı bir diziyi bir kez sıralıyor ve ardından k üyelik sorgusunu ikili aramayla yanıtlıyorsunuz. Toplam maliyet nedir?

  1. AO(n + k)
  2. BO(k n log n)
  3. CO(nk)
  4. DO(n log n + k log n)
6.Orta

Dinamik programlama, bir problemde hangisi olduğunda yararlıdır?

  1. AYalnızca rastgele girdiler
  2. BÖrtüşen alt problemler ve optimal alt yapı
  3. CTek bir döngü
  4. DHiç alt problem olmaması; bu yüzden tek adımda çözülebilir
7.Zor

Karatsuba çarpması T(n) = 3T(n/2) + O(n) yinelemesini sağlar. Bunun çözümü nedir?

  1. AΘ(nlog₂ 3), yaklaşık n1,585
  2. BΘ(n²)
  3. CΘ(n log n)
  4. DΘ(n3)
8.Zor

Gezgin satıcı problemi nasıl sınıflandırılır?

  1. ADijkstra algoritması her şehri bir kez ziyaret ederek onu çözdüğü için P'dedir
  2. BKarar versiyonu P'de, optimizasyon versiyonu ise NP-tamdır
  3. CKarar verilemezdir
  4. DKarar versiyonu NP-tam, optimizasyon versiyonu NP-zordur

Cevap anahtarı

  1. 1. C · Ω (Büyük Omega)
  2. 2. B · Yaklaşık log₂ n
  3. 3. D · Büyük O
  4. 4. B · O(V × E)
  5. 5. D · O(n log n + k log n)
  6. 6. B · Örtüşen alt problemler ve optimal alt yapı
  7. 7. A · Θ(nlog₂ 3), yaklaşık n1,585
  8. 8. D · Karar versiyonu NP-tam, optimizasyon versiyonu NP-zordur

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