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

Bir işlemin O(1) zamanda çalışması ne anlama gelir?

  1. AYalnızca bir kez çalıştırılabilir
  2. BÇalışma süresi girdi boyutuyla büyümez
  3. CÇalışma süresinin saniyesi başına tam olarak bir eleman işler
  4. DHer zaman tam olarak bir saniye sürer
2.Kolay

n büyüdükçe bunlardan hangisi en yavaş büyür?

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

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

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

Hızlı sıralamanın (quicksort) en kötü durum zaman karmaşıklığı nedir?

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

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

  1. ABirleştirmeli sıralama
  2. BSeçmeli sıralama (tipik sürüm)
  3. CYığın sıralaması
  4. DHızlı sıralama (tipik yerinde sürüm)
7.Zor

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

  1. AO(n²)
  2. BO(n √n)
  3. CO(n log n)
  4. DO(n)
8.Zor

Bir problem hangi durumda NP-tamdır?

  1. ANP'dedir ve her NP problemi ona polinom zamanda indirgenebilir
  2. BÇözülmesi imkânsızdır
  3. CNP'nin dışındadır ama durma problemi gibi tüm NP problemlerinden daha zordur
  4. DPolinom zamanda çözülebilir

Cevap anahtarı

  1. 1. B · Çalışma süresi girdi boyutuyla büyümez
  2. 2. B · O(log n)
  3. 3. A · O(n)
  4. 4. A · O(1)
  5. 5. A · O(n²)
  6. 6. A · Birleştirmeli sıralama
  7. 7. C · O(n log n)
  8. 8. A · NP'dedir ve her NP problemi ona polinom zamanda indirgenebilir

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