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

3n² + 5n + 2 ifadesinin Büyük O'su nedir?

  1. AO(n²)
  2. BO(n³)
  3. CO(5n)
  4. DO(3n²)
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(n)
  2. BO(n log n)
  3. CO(log n)
  4. DO(1)
3.Kolay

Büyük n için hangi karmaşıklık sınıfı en hızlı büyür?

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

Şunun zaman karmaşıklığı nedir: for i = 1 to n: for j = 1 to i: O(1) iş yap?

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

m ve n uzunluğundaki dizgilerin en uzun ortak alt dizisi için standart dinamik programlama algoritmasının zaman karmaşıklığı nedir?

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

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

  1. AHer zaman optimal çözümü verir
  2. BYalnızca özyineleme kullanır
  3. COlası her çözümü dener
  4. DHer adımda yerel olarak en iyi seçimi yapar
7.Zor

Maksimal bir eşleşmedeki her kenarın iki uç noktasını almak bir düğüm örtüsü verir. Bu örtü ne kadar iyidir?

  1. AEn fazla minimumun log n katıdır
  2. BEn fazla minimum düğüm örtüsünün iki katı büyüklüğündedir
  3. COptimuma kıyasla kalitesi bilinmez
  4. DHer zaman minimum bir düğüm örtüsüdür
8.Zor

Hangi teknik, hızlı sıralama için her girdide beklenen O(n log n) çalışma süresini sağlar?

  1. AÖzyinelemeyi yalnızca sol tarafta kullanmak
  2. BHızlı sıralamayı çalıştırmadan önce girdiyi sıralamak
  3. CHer zaman ilk elemanı seçmek
  4. DPivotu düzgün dağılımla rastgele seçmek

Cevap anahtarı

  1. 1. A · O(n²)
  2. 2. A · O(n)
  3. 3. D · O(2ⁿ)
  4. 4. D · O(n²)
  5. 5. D · O(mn)
  6. 6. D · Her adımda yerel olarak en iyi seçimi yapar
  7. 7. B · En fazla minimum düğüm örtüsünün iki katı büyüklüğündedir
  8. 8. D · Pivotu düzgün dağılımla rastgele seçmek

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