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 algoritmanın çalışma süresi O(n)'dir. Bu büyümeye ne ad verilir?

  1. ASabit
  2. BKaresel
  3. CDoğrusal
  4. DLogaritmik
2.Kolay

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

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

0 ile k aralığındaki n tamsayı için sayma sıralamasının (counting sort) çalışma süresi nedir?

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

İki n × n matrisi standart üçlü döngüyle çarpmanın zaman karmaşıklığı nedir?

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

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

  1. AHızlı sıralama (tipik yerinde sürüm)
  2. BYığın sıralaması
  3. CSeçmeli sıralama (tipik sürüm)
  4. DBirleştirmeli sıralama
6.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²)
7.Zor

Dinamik programlama ile çözülen 0/1 sırt çantası problemi O(nW) zaman alır. Buna neden sözde polinom (pseudo-polynomial) denir?

  1. AÇünkü yalnızca W = 0 için çalışır
  2. BÇünkü algoritma rastgeleleştirilmiştir ve çalışma süresi her girdide değişir
  3. CW bir sayıdır, bu yüzden süre W'yi yazmak için kullanılan bit sayısına göre üsteldir
  4. DÇünkü n her zaman küçüktür
8.Zor

Bir problem hangi durumda NP-tamdır?

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

Cevap anahtarı

  1. 1. C · Doğrusal
  2. 2. C · Büyük O
  3. 3. C · O(n + k)
  4. 4. A · O(n³)
  5. 5. D · Birleştirmeli sıralama
  6. 6. D · O(n²)
  7. 7. C · W bir sayıdır, bu yüzden süre W'yi yazmak için kullanılan bit sayısına göre üsteldir
  8. 8. B · NP'dedir ve her NP problemi ona polinom zamanda indirgenebilir

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