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

İkili arama girdisinden ne gerektirir?

  1. ADizi uzunluğunun ikinin kuvveti olmasını
  2. BDizinin yalnızca pozitif sayılar içermesini
  3. CDizinin 1000'den fazla eleman içermemesini
  4. DDizinin sıralı olmasını
2.Kolay

Eklemeli sıralamanın (insertion sort) en kötü durum zaman karmaşıklığı nedir?

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

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

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

Karşılaştırmaya dayalı sıralama için en kötü durumdaki alt sınır nedir?

  1. AΩ(n)
  2. BΩ(log n)
  3. CΩ(n log n)
  4. DΩ(n²)
5.Orta

O(log n)'de olduğu gibi, Büyük O'da logaritmanın tabanı neden genellikle yazılmaz?

  1. ABilgisayar bilimindeki tüm logaritmaların tabanı 10'dur, bu yüzden zımnen bellidir
  2. BTaban yalnızca küçük n için önemlidir
  3. CLogaritmalar her zaman tamsayılara yuvarlanır
  4. DFarklı tabanlı logaritmalar yalnızca sabit bir çarpan kadar farklıdır
6.Orta

Basit özyinelemeli faktöriyel fonksiyonu fact(n) = n × fact(n − 1) ne kadar yığın (stack) alanı kullanır?

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

NP sınıfının hangi tanımı doğrudur?

  1. AEvet yanıtları bir sertifika verildiğinde polinom zamanda doğrulanabilen karar problemleri
  2. BPolinom zamanda çözülemeyen problemler
  3. CHiçbir algoritmanın çözemeyeceği problemler
  4. DPolinom olmayan problemler
8.Zor

Hangi algoritma, döngü oluşturmayan en ucuz kenarı tekrar tekrar ekleyerek minimum kapsayan ağacı bulur?

  1. AKruskal algoritması
  2. BFloyd–Warshall
  3. CTek bir düğümden başlayan Prim algoritması
  4. DDijkstra algoritması

Cevap anahtarı

  1. 1. D · Dizinin sıralı olmasını
  2. 2. A · O(n²)
  3. 3. A · Büyük O
  4. 4. C · Ω(n log n)
  5. 5. D · Farklı tabanlı logaritmalar yalnızca sabit bir çarpan kadar farklıdır
  6. 6. D · O(n)
  7. 7. A · Evet yanıtları bir sertifika verildiğinde polinom zamanda doğrulanabilen karar problemleri
  8. 8. A · Kruskal algoritması

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